COIN-OR::LEMON - Graph Library

Changeset 400:cb377609cf1d in lemon-0.x


Ignore:
Timestamp:
04/25/04 22:16:16 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@531
Message:

class NodeSet?: A graph class with no edges
class EdgeSet?: A graph class using the node set of another graph.
It compiles but untested and undocumented.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/list_graph.h

    r397 r400  
    6969  public:
    7070    template <typename T> class EdgeMap;
    71     template <typename T> class EdgeMap;
     71    template <typename T> class NodeMap;
    7272   
    7373    class Node;
     
    301301      friend class ListGraph;
    302302      template <typename T> friend class NodeMap;
    303      
     303       
    304304      friend class Edge;
    305305      friend class OutEdgeIt;
     
    322322      friend class ListGraph;
    323323    public:
     324      NodeIt() : Node() { }
     325      NodeIt(Invalid i) : Node(i) { }
    324326      NodeIt(const ListGraph& G) : Node(G.first_node) { }
    325       NodeIt() : Node() { }
    326327    };
    327328
     
    722723  };
    723724 
     725
     726  ///A smart graph class.
     727
     728  ///This is a simple and fast erasable graph implementation.
     729  ///
     730  ///It conforms to the graph interface documented under
     731  ///the description of \ref GraphSkeleton.
     732  ///\sa \ref GraphSkeleton.
     733  class NodeSet {
     734
     735    //Nodes are double linked.
     736    //The free nodes are only single linked using the "next" field.
     737    struct NodeT
     738    {
     739      int first_in,first_out;
     740      int prev, next;
     741      //      NodeT() {}
     742    };
     743
     744    std::vector<NodeT> nodes;
     745    //The first node
     746    int first_node;
     747    //The first free node
     748    int first_free_node;
     749   
     750  protected:
     751   
     752    template <typename Key> class DynMapBase
     753    {
     754    protected:
     755      const NodeSet* G;
     756    public:
     757      virtual void add(const Key k) = NULL;
     758      virtual void erase(const Key k) = NULL;
     759      DynMapBase(const NodeSet &_G) : G(&_G) {}
     760      virtual ~DynMapBase() {}
     761      friend class NodeSet;
     762    };
     763   
     764  public:
     765    template <typename T> class EdgeMap;
     766    template <typename T> class NodeMap;
     767   
     768    class Node;
     769    class Edge;
     770
     771    //  protected:
     772    // HELPME:
     773  protected:
     774    ///\bug It must be public because of SymEdgeMap.
     775    ///
     776    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
     777    //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
     778   
     779  public:
     780
     781    class NodeIt;
     782    class EdgeIt;
     783    class OutEdgeIt;
     784    class InEdgeIt;
     785   
     786    template <typename T> class NodeMap;
     787    template <typename T> class EdgeMap;
     788   
     789  public:
     790
     791    NodeSet() : nodes(), first_node(-1),
     792                  first_free_node(-1) {}
     793    NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
     794                                     first_free_node(_g.first_free_node) {}
     795   
     796    ~NodeSet()
     797    {
     798      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     799          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
     800      //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
     801      //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
     802    }
     803
     804    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
     805    int edgeNum() const { return 0; }  //FIXME: What is this?
     806
     807    ///\bug This function does something different than
     808    ///its name would suggests...
     809    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
     810    ///\bug This function does something different than
     811    ///its name would suggests...
     812    int maxEdgeId() const { return 0; }  //FIXME: What is this?
     813
     814    Node tail(Edge e) const { return INVALID; }
     815    Node head(Edge e) const { return INVALID; }
     816
     817    Node aNode(OutEdgeIt e) const { return INVALID; }
     818    Node aNode(InEdgeIt e) const { return INVALID; }
     819
     820    Node bNode(OutEdgeIt e) const { return INVALID; }
     821    Node bNode(InEdgeIt e) const { return INVALID; }
     822
     823    NodeIt& first(NodeIt& v) const {
     824      v=NodeIt(*this); return v; }
     825    EdgeIt& first(EdgeIt& e) const {
     826      e=EdgeIt(*this); return e; }
     827    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
     828      e=OutEdgeIt(*this,v); return e; }
     829    InEdgeIt& first(InEdgeIt& e, const Node v) const {
     830      e=InEdgeIt(*this,v); return e; }
     831
     832//     template< typename It >
     833//     It first() const { It e; first(e); return e; }
     834
     835//     template< typename It >
     836//     It first(Node v) const { It e; first(e,v); return e; }
     837
     838    bool valid(Edge e) const { return false; }
     839    bool valid(Node n) const { return n.n!=-1; }
     840   
     841    void setInvalid(Edge &e) { }
     842    void setInvalid(Node &n) { n.n=-1; }
     843   
     844    template <typename It> It getNext(It it) const
     845    { It tmp(it); return next(tmp); }
     846
     847    NodeIt& next(NodeIt& it) const {
     848      it.n=nodes[it.n].next;
     849      return it;
     850    }
     851    OutEdgeIt& next(OutEdgeIt& it) const { return it; }
     852    InEdgeIt& next(InEdgeIt& it) const { return it; }
     853    EdgeIt& next(EdgeIt& it) const { return it; }
     854
     855    int id(Node v) const { return v.n; }
     856    int id(Edge e) const { return -1; }
     857
     858    /// Adds a new node to the graph.
     859
     860    /// \todo It adds the nodes in a reversed order.
     861    /// (i.e. the lastly added node becomes the first.)
     862    Node addNode() {
     863      int n;
     864     
     865      if(first_free_node==-1)
     866        {
     867          n = nodes.size();
     868          nodes.push_back(NodeT());
     869        }
     870      else {
     871        n = first_free_node;
     872        first_free_node = nodes[n].next;
     873      }
     874     
     875      nodes[n].next = first_node;
     876      if(first_node != -1) nodes[first_node].prev = n;
     877      first_node = n;
     878      nodes[n].prev = -1;
     879     
     880      nodes[n].first_in = nodes[n].first_out = -1;
     881     
     882      Node nn; nn.n=n;
     883
     884      //Update dynamic maps
     885      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     886          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
     887
     888      return nn;
     889    }
     890   
     891    void erase(Node nn) {
     892      int n=nn.n;
     893     
     894      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
     895      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
     896      else first_node = nodes[n].next;
     897     
     898      nodes[n].next = first_free_node;
     899      first_free_node = n;
     900
     901      //Update dynamic maps
     902      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     903          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
     904    }
     905   
     906    ///\bug Dynamic maps must be updated!
     907    ///
     908    void clear() {
     909      nodes.clear();
     910      first_node = first_free_node = -1;
     911    }
     912
     913    class Node {
     914      friend class NodeSet;
     915      template <typename T> friend class NodeMap;
     916     
     917      friend class Edge;
     918      friend class OutEdgeIt;
     919      friend class InEdgeIt;
     920
     921    protected:
     922      int n;
     923      friend int NodeSet::id(Node v) const;
     924      Node(int nn) {n=nn;}
     925    public:
     926      Node() {}
     927      Node (Invalid i) { n=-1; }
     928      bool operator==(const Node i) const {return n==i.n;}
     929      bool operator!=(const Node i) const {return n!=i.n;}
     930      bool operator<(const Node i) const {return n<i.n;}
     931    };
     932   
     933    class NodeIt : public Node {
     934      friend class NodeSet;
     935    public:
     936      NodeIt(const NodeSet& G) : Node(G.first_node) { }
     937      NodeIt() : Node() { }
     938    };
     939
     940    class Edge {
     941      //friend class NodeSet;
     942      //template <typename T> friend class EdgeMap;
     943
     944      //template <typename T> friend class SymNodeSet::SymEdgeMap;     
     945      //friend Edge SymNodeSet::opposite(Edge) const;
     946     
     947      //      friend class Node;
     948      //      friend class NodeIt;
     949    protected:
     950      //friend int NodeSet::id(Edge e) const;
     951      //      Edge(int nn) {}
     952    public:
     953      Edge() { }
     954      Edge (Invalid) { }
     955      bool operator==(const Edge i) const {return true;}
     956      bool operator!=(const Edge i) const {return false;}
     957      bool operator<(const Edge i) const {return false;}
     958      ///\bug This is a workaround until somebody tells me how to
     959      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
     960      //      int idref() {return -1;}
     961      //      int idref() const {return -1;}
     962    };
     963   
     964    class EdgeIt : public Edge {
     965      //friend class NodeSet;
     966    public:
     967      EdgeIt(const NodeSet& G) : Edge() { }
     968      EdgeIt (Invalid i) : Edge(i) { }
     969      EdgeIt() : Edge() { }
     970      ///\bug This is a workaround until somebody tells me how to
     971      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
     972      //      int idref() {return -1;}
     973    };
     974   
     975    class OutEdgeIt : public Edge {
     976      friend class NodeSet;
     977    public:
     978      OutEdgeIt() : Edge() { }
     979      OutEdgeIt (Invalid i) : Edge(i) { }
     980      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
     981    };
     982   
     983    class InEdgeIt : public Edge {
     984      friend class NodeSet;
     985    public:
     986      InEdgeIt() : Edge() { }
     987      InEdgeIt (Invalid i) : Edge(i) { }
     988      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
     989    };
     990
     991    template <typename T> class NodeMap : public DynMapBase<Node>
     992    {
     993      std::vector<T> container;
     994
     995    public:
     996      typedef T ValueType;
     997      typedef Node KeyType;
     998
     999      NodeMap(const NodeSet &_G) :
     1000        DynMapBase<Node>(_G), container(_G.maxNodeId())
     1001      {
     1002        G->dyn_node_maps.push_back(this);
     1003      }
     1004      NodeMap(const NodeSet &_G,const T &t) :
     1005        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
     1006      {
     1007        G->dyn_node_maps.push_back(this);
     1008      }
     1009     
     1010      NodeMap(const NodeMap<T> &m) :
     1011        DynMapBase<Node>(*m.G), container(m.container)
     1012      {
     1013        G->dyn_node_maps.push_back(this);
     1014      }
     1015
     1016      template<typename TT> friend class NodeMap;
     1017 
     1018      ///\todo It can copy between different types.
     1019      ///
     1020      template<typename TT> NodeMap(const NodeMap<TT> &m) :
     1021        DynMapBase<Node>(*m.G)
     1022      {
     1023        G->dyn_node_maps.push_back(this);
     1024        typename std::vector<TT>::const_iterator i;
     1025        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     1026            i!=m.container.end();
     1027            i++)
     1028          container.push_back(*i);
     1029      }
     1030      ~NodeMap()
     1031      {
     1032        if(G) {
     1033          std::vector<DynMapBase<Node>* >::iterator i;
     1034          for(i=G->dyn_node_maps.begin();
     1035              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
     1036          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
     1037          //A better way to do that: (Is this really important?)
     1038          if(*i==this) {
     1039            *i=G->dyn_node_maps.back();
     1040            G->dyn_node_maps.pop_back();
     1041          }
     1042        }
     1043      }
     1044
     1045      void add(const Node k)
     1046      {
     1047        if(k.n>=int(container.size())) container.resize(k.n+1);
     1048      }
     1049
     1050      void erase(const Node) { }
     1051     
     1052      void set(Node n, T a) { container[n.n]=a; }
     1053      //'T& operator[](Node n)' would be wrong here
     1054      typename std::vector<T>::reference
     1055      operator[](Node n) { return container[n.n]; }
     1056      //'const T& operator[](Node n)' would be wrong here
     1057      typename std::vector<T>::const_reference
     1058      operator[](Node n) const { return container[n.n]; }
     1059
     1060      ///\warning There is no safety check at all!
     1061      ///Using operator = between maps attached to different graph may
     1062      ///cause serious problem.
     1063      ///\todo Is this really so?
     1064      ///\todo It can copy between different types.
     1065      const NodeMap<T>& operator=(const NodeMap<T> &m)
     1066      {
     1067        container = m.container;
     1068        return *this;
     1069      }
     1070      template<typename TT>
     1071      const NodeMap<T>& operator=(const NodeMap<TT> &m)
     1072      {
     1073        copy(m.container.begin(), m.container.end(), container.begin());
     1074        return *this;
     1075      }
     1076     
     1077      void update() {}    //Useless for Dynamic Maps
     1078      void update(T a) {}  //Useless for Dynamic Maps
     1079    };
     1080   
     1081    template <typename T> class EdgeMap
     1082    {
     1083    public:
     1084      typedef T ValueType;
     1085      typedef Edge KeyType;
     1086
     1087      EdgeMap(const NodeSet &) { }
     1088      EdgeMap(const NodeSet &,const T &) { }
     1089      EdgeMap(const EdgeMap<T> &) { }
     1090      //      template<typename TT> friend class EdgeMap;
     1091
     1092      ///\todo It can copy between different types.
     1093      ///
     1094      template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
     1095      ~EdgeMap() { }
     1096
     1097      void add(const Edge  ) { }
     1098      void erase(const Edge) { }
     1099     
     1100      void set(Edge, T) { }
     1101      //T get(Edge n) const { return container[n.n]; }
     1102      ValueType &operator[](Edge) { return *((T*)(NULL)); }
     1103      const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
     1104
     1105      const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
     1106   
     1107      template<typename TT>
     1108      const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
     1109     
     1110      void update() {}
     1111      void update(T a) {}
     1112    };
     1113  };
     1114
     1115
     1116
     1117  ///This is a simple and fast erasable graph implementation.
     1118  ///
     1119  ///It conforms to the graph interface documented under
     1120  ///the description of \ref GraphSkeleton.
     1121  ///\sa \ref GraphSkeleton.
     1122  template<typename GG>
     1123  class EdgeSet {
     1124
     1125    typedef GG NodeGraphType;
     1126
     1127    NodeGraphType &G;
     1128
     1129    class Node;
     1130   
     1131    //Edges are double linked.
     1132    //The free edges are only single linked using the "next_in" field.
     1133    struct NodeT
     1134    {
     1135      int first_in,first_out;
     1136      NodeT() : first_in(-1), first_out(-1) { }
     1137    };
     1138
     1139    struct EdgeT
     1140    {
     1141      Node head, tail;
     1142      int prev_in, prev_out;
     1143      int next_in, next_out;
     1144    };
     1145
     1146   
     1147    typename NodeGraphType::NodeMap<NodeT> nodes;
     1148   
     1149    std::vector<EdgeT> edges;
     1150    //The first free edge
     1151    int first_free_edge;
     1152   
     1153  protected:
     1154   
     1155    template <typename Key> class DynMapBase
     1156    {
     1157    protected:
     1158      const EdgeSet* G;
     1159    public:
     1160      virtual void add(const Key k) = NULL;
     1161      virtual void erase(const Key k) = NULL;
     1162      DynMapBase(const EdgeSet &_G) : G(&_G) {}
     1163      virtual ~DynMapBase() {}
     1164      friend class EdgeSet;
     1165    };
     1166   
     1167  public:
     1168    //template <typename T> class NodeMap;
     1169    template <typename T> class EdgeMap;
     1170   
     1171    class Node;
     1172    class Edge;
     1173
     1174    //  protected:
     1175    // HELPME:
     1176  protected:
     1177    // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
     1178    ///\bug It must be public because of SymEdgeMap.
     1179    ///
     1180    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
     1181   
     1182  public:
     1183
     1184    class NodeIt;
     1185    class EdgeIt;
     1186    class OutEdgeIt;
     1187    class InEdgeIt;
     1188   
     1189    template <typename T> class NodeMap;
     1190    template <typename T> class EdgeMap;
     1191   
     1192  public:
     1193
     1194    EdgeSet(const NodeGraphType &_G) : G(_G),
     1195                                       nodes(_G), edges(),
     1196                                       first_free_edge(-1) {}
     1197    EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
     1198                                 first_free_edge(_g.first_free_edge) {}
     1199   
     1200    ~EdgeSet()
     1201    {
     1202      // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
     1203      //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
     1204      for(typename std::vector<DynMapBase<Edge> * >::iterator
     1205            i=dyn_edge_maps.begin();
     1206          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
     1207    }
     1208
     1209    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
     1210    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
     1211
     1212    ///\bug This function does something different than
     1213    ///its name would suggests...
     1214    int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
     1215    ///\bug This function does something different than
     1216    ///its name would suggests...
     1217    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
     1218
     1219    Node tail(Edge e) const { return edges[e.n].tail; }
     1220    Node head(Edge e) const { return edges[e.n].head; }
     1221
     1222    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
     1223    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
     1224
     1225    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
     1226    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
     1227
     1228    NodeIt& first(NodeIt& v) const {
     1229      v=NodeIt(*this); return v; }
     1230    EdgeIt& first(EdgeIt& e) const {
     1231      e=EdgeIt(*this); return e; }
     1232    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
     1233      e=OutEdgeIt(*this,v); return e; }
     1234    InEdgeIt& first(InEdgeIt& e, const Node v) const {
     1235      e=InEdgeIt(*this,v); return e; }
     1236
     1237//     template< typename It >
     1238//     It first() const { It e; first(e); return e; }
     1239
     1240//     template< typename It >
     1241//     It first(Node v) const { It e; first(e,v); return e; }
     1242
     1243    bool valid(Edge e) const { return e.n!=-1; }
     1244    bool valid(Node n) const { return G.valid(n); }
     1245   
     1246    void setInvalid(Edge &e) { e.n=-1; }
     1247    void setInvalid(Node &n) { G.setInvalid(n); }
     1248   
     1249    template <typename It> It getNext(It it) const
     1250    { It tmp(it); return next(tmp); }
     1251
     1252    NodeIt& next(NodeIt& it) const { G.next(it); return it; }
     1253    OutEdgeIt& next(OutEdgeIt& it) const
     1254    { it.n=edges[it.n].next_out; return it; }
     1255    InEdgeIt& next(InEdgeIt& it) const
     1256    { it.n=edges[it.n].next_in; return it; }
     1257    EdgeIt& next(EdgeIt& it) const {
     1258      if(edges[it.n].next_in!=-1) {
     1259        it.n=edges[it.n].next_in;
     1260      }
     1261      else {
     1262        typename NodeGraphType::Node n;
     1263        for(n=G.next(edges[it.n].head);
     1264            G.valid(n) && nodes[n].first_in == -1;
     1265            G.next(n)) ;
     1266        it.n = (G.valid(n))?-1:nodes[n].first_in;
     1267      }
     1268      return it;
     1269    }
     1270
     1271    int id(Node v) const { return G.id(v); }
     1272    int id(Edge e) const { return e.n; }
     1273
     1274    /// Adds a new node to the graph.
     1275    Node addNode() { return G.AddNode(); }
     1276   
     1277    Edge addEdge(Node u, Node v) {
     1278      int n;
     1279     
     1280      if(first_free_edge==-1)
     1281        {
     1282          n = edges.size();
     1283          edges.push_back(EdgeT());
     1284        }
     1285      else {
     1286        n = first_free_edge;
     1287        first_free_edge = edges[n].next_in;
     1288      }
     1289     
     1290      edges[n].tail = u.n; edges[n].head = v.n;
     1291
     1292      edges[n].next_out = nodes[u.n].first_out;
     1293      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
     1294      edges[n].next_in = nodes[v.n].first_in;
     1295      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
     1296      edges[n].prev_in = edges[n].prev_out = -1;
     1297       
     1298      nodes[u.n].first_out = nodes[v.n].first_in = n;
     1299
     1300      Edge e; e.n=n;
     1301
     1302      //Update dynamic maps
     1303      for(typename std::vector<DynMapBase<Edge> * >::iterator
     1304            i=dyn_edge_maps.begin();
     1305          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     1306
     1307      return e;
     1308    }
     1309
     1310  private:
     1311    void eraseEdge(int n) {
     1312     
     1313      if(edges[n].next_in!=-1)
     1314        edges[edges[n].next_in].prev_in = edges[n].prev_in;
     1315      if(edges[n].prev_in!=-1)
     1316        edges[edges[n].prev_in].next_in = edges[n].next_in;
     1317      else nodes[edges[n].head].first_in = edges[n].next_in;
     1318     
     1319      if(edges[n].next_out!=-1)
     1320        edges[edges[n].next_out].prev_out = edges[n].prev_out;
     1321      if(edges[n].prev_out!=-1)
     1322        edges[edges[n].prev_out].next_out = edges[n].next_out;
     1323      else nodes[edges[n].tail].first_out = edges[n].next_out;
     1324     
     1325      edges[n].next_in = first_free_edge;
     1326      first_free_edge = -1;     
     1327
     1328      //Update dynamic maps
     1329      Edge e; e.n=n;
     1330      for(typename std::vector<DynMapBase<Edge> * >::iterator
     1331            i=dyn_edge_maps.begin();
     1332          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
     1333    }
     1334     
     1335  public:
     1336
     1337//     void erase(Node nn) {
     1338//       int n=nn.n;
     1339//       int m;
     1340//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
     1341//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
     1342//     }
     1343   
     1344    void erase(Edge e) { eraseEdge(e.n); }
     1345
     1346//     //\bug Dynamic maps must be updated!
     1347//     //
     1348//     void clear() {
     1349//       nodes.clear();edges.clear();
     1350//       first_node=first_free_node=first_free_edge=-1;
     1351//     }
     1352
     1353    class Node : public NodeGraphType::Node {
     1354      friend class EdgeSet;
     1355      //      template <typename T> friend class NodeMap;
     1356     
     1357      friend class Edge;
     1358      friend class OutEdgeIt;
     1359      friend class InEdgeIt;
     1360      friend class SymEdge;
     1361
     1362    protected:
     1363      friend int EdgeSet::id(Node v) const;
     1364      //      Node(int nn) {n=nn;}
     1365    public:
     1366      Node() : NodeGraphType::Node() {}
     1367      Node (Invalid i) : NodeGraphType::Node(i) {}
     1368      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
     1369    };
     1370   
     1371    class NodeIt : public NodeGraphType::NodeIt {
     1372      friend class EdgeSet;
     1373    public:
     1374      NodeIt() : NodeGraphType::NodeIt() { }
     1375      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
     1376      NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { }
     1377      NodeIt(const typename NodeGraphType::NodeIt &n)
     1378        : NodeGraphType::NodeIt(n) {}
     1379      operator Node() { return Node(*this);}
     1380    };
     1381
     1382    class Edge {
     1383      friend class EdgeSet;
     1384      template <typename T> friend class EdgeMap;
     1385
     1386      //template <typename T> friend class SymEdgeSet::SymEdgeMap;     
     1387      //friend Edge SymEdgeSet::opposite(Edge) const;
     1388     
     1389      friend class Node;
     1390      friend class NodeIt;
     1391    protected:
     1392      int n;
     1393      friend int EdgeSet::id(Edge e) const;
     1394
     1395      Edge(int nn) {n=nn;}
     1396    public:
     1397      Edge() { }
     1398      Edge (Invalid) { n=-1; }
     1399      bool operator==(const Edge i) const {return n==i.n;}
     1400      bool operator!=(const Edge i) const {return n!=i.n;}
     1401      bool operator<(const Edge i) const {return n<i.n;}
     1402      ///\bug This is a workaround until somebody tells me how to
     1403      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
     1404      int &idref() {return n;}
     1405      const int &idref() const {return n;}
     1406    };
     1407   
     1408    class EdgeIt : public Edge {
     1409      friend class EdgeSet;
     1410    public:
     1411      EdgeIt(const EdgeSet& G) : Edge() {
     1412        typename NodeGraphType::Node m;
     1413        for(G.first(m);
     1414            G.valid(m) && nodes[m].first_in == -1;  G.next[m]);
     1415        n = G.valid(m)?-1:nodes[m].first_in;
     1416      }
     1417      EdgeIt (Invalid i) : Edge(i) { }
     1418      EdgeIt() : Edge() { }
     1419      ///\bug This is a workaround until somebody tells me how to
     1420      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
     1421      int &idref() {return n;}
     1422    };
     1423   
     1424    class OutEdgeIt : public Edge {
     1425      friend class EdgeSet;
     1426    public:
     1427      OutEdgeIt() : Edge() { }
     1428      OutEdgeIt (Invalid i) : Edge(i) { }
     1429
     1430      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
     1431    };
     1432   
     1433    class InEdgeIt : public Edge {
     1434      friend class EdgeSet;
     1435    public:
     1436      InEdgeIt() : Edge() { }
     1437      InEdgeIt (Invalid i) : Edge(i) { }
     1438      InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
     1439    };
     1440
     1441    template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
     1442    {
     1443    public:
     1444      NodeMap(const EdgeSet &_G) :
     1445        NodeGraphType::NodeMap<T>(_G.G) { }
     1446      NodeMap(const EdgeSet &_G,const T &t) :
     1447        NodeGraphType::NodeMap<T>(_G.G,t) { }
     1448      //It is unnecessary
     1449      NodeMap(const typename NodeGraphType::NodeMap<T> &m)
     1450        : NodeGraphType::NodeMap<T>(m) { }
     1451
     1452      ///\todo It can copy between different types.
     1453      ///
     1454      template<typename TT> friend class NodeMap;
     1455      NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
     1456        : NodeGraphType::NodeMap<T>(m) { }
     1457    };
     1458   
     1459    template <typename T> class EdgeMap : public DynMapBase<Edge>
     1460    {
     1461      std::vector<T> container;
     1462
     1463    public:
     1464      typedef T ValueType;
     1465      typedef Edge KeyType;
     1466
     1467      EdgeMap(const EdgeSet &_G) :
     1468        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
     1469      {
     1470        //FIXME: What if there are empty Id's?
     1471        //FIXME: Can I use 'this' in a constructor?
     1472        G->dyn_edge_maps.push_back(this);
     1473      }
     1474      EdgeMap(const EdgeSet &_G,const T &t) :
     1475        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
     1476      {
     1477        G->dyn_edge_maps.push_back(this);
     1478      }
     1479      EdgeMap(const EdgeMap<T> &m) :
     1480        DynMapBase<Edge>(*m.G), container(m.container)
     1481      {
     1482        G->dyn_node_maps.push_back(this);
     1483      }
     1484
     1485      template<typename TT> friend class EdgeMap;
     1486
     1487      ///\todo It can copy between different types.
     1488      ///
     1489      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
     1490        DynMapBase<Edge>(*m.G)
     1491      {
     1492        G->dyn_node_maps.push_back(this);
     1493        typename std::vector<TT>::const_iterator i;
     1494        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     1495            i!=m.container.end();
     1496            i++)
     1497          container.push_back(*i);
     1498      }
     1499      ~EdgeMap()
     1500      {
     1501        if(G) {
     1502          typename std::vector<DynMapBase<Edge>* >::iterator i;
     1503          for(i=G->dyn_edge_maps.begin();
     1504              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     1505          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
     1506          //A better way to do that: (Is this really important?)
     1507          if(*i==this) {
     1508            *i=G->dyn_edge_maps.back();
     1509            G->dyn_edge_maps.pop_back();
     1510          }
     1511        }
     1512      }
     1513     
     1514      void add(const Edge k)
     1515      {
     1516        if(k.n>=int(container.size())) container.resize(k.n+1);
     1517      }
     1518      void erase(const Edge) { }
     1519     
     1520      void set(Edge n, T a) { container[n.n]=a; }
     1521      //T get(Edge n) const { return container[n.n]; }
     1522      typename std::vector<T>::reference
     1523      operator[](Edge n) { return container[n.n]; }
     1524      typename std::vector<T>::const_reference
     1525      operator[](Edge n) const { return container[n.n]; }
     1526
     1527      ///\warning There is no safety check at all!
     1528      ///Using operator = between maps attached to different graph may
     1529      ///cause serious problem.
     1530      ///\todo Is this really so?
     1531      ///\todo It can copy between different types.
     1532      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
     1533      {
     1534        container = m.container;
     1535        return *this;
     1536      }
     1537      template<typename TT>
     1538      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
     1539      {
     1540        copy(m.container.begin(), m.container.end(), container.begin());
     1541        return *this;
     1542      }
     1543     
     1544      void update() {}    //Useless for DynMaps
     1545      void update(T a) {}  //Useless for DynMaps
     1546    };
     1547
     1548  };
     1549
     1550
     1551
     1552
     1553
     1554
     1555
    7241556 
    7251557} //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.