Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/hugo/list_graph.h
changeset 905 5be029d19c98
parent 904 b40afcf42a4d
child 906 17f31d280385
equal deleted inserted replaced
22:ecbf2b74cd9f 23:30d8cd105160 
    74     class OutEdgeIt;
 
    74     class OutEdgeIt;
 
    75     class InEdgeIt;
 
    75     class InEdgeIt;
 
    76 
    76 
    77     // Create map registries.
 
    77     // Create map registries.
 
    78     CREATE_MAP_REGISTRIES;
 
    78     CREATE_MAP_REGISTRIES;
 
    79     /// Create node and edge maps.
 
    79     // Create node and edge maps.
 
    80     CREATE_MAPS(ArrayMap);
 
    80     CREATE_MAPS(ArrayMap);
 
    81 
    81 
    82   public:
 
    82   public:
 
    83 
    83 
    84     ListGraph() 
    84     ListGraph() 
   319 
   319 
   320     class Edge {
 
   320     class Edge {
 
   321       friend class ListGraph;
 
   321       friend class ListGraph;
 
   322       template <typename T> friend class EdgeMap;
 
   322       template <typename T> friend class EdgeMap;
 
   323 
   323 
   324       //template <typename T> friend class SymListGraph::SymEdgeMap;      
   324       friend class SymListGraph;
 
   325       //friend Edge SymListGraph::opposite(Edge) const;
 
       
   326       
   325       
   327       friend class Node;
 
   326       friend class Node;
 
   328       friend class NodeIt;
 
   327       friend class NodeIt;
 
   329     protected:
 
   328     protected:
 
   330       int n;
 
   329       int n;
 
   340       Edge() { }
 
   339       Edge() { }
 
   341       Edge (Invalid) { n=-1; }
 
   340       Edge (Invalid) { n=-1; }
 
   342       bool operator==(const Edge i) const {return n==i.n;}
 
   341       bool operator==(const Edge i) const {return n==i.n;}
 
   343       bool operator!=(const Edge i) const {return n!=i.n;}
 
   342       bool operator!=(const Edge i) const {return n!=i.n;}
 
   344       bool operator<(const Edge i) const {return n<i.n;}
 
   343       bool operator<(const Edge i) const {return n<i.n;}
 
   345       ///\bug This is a workaround until somebody tells me how to
 
       
   346       ///make class \c SymListGraph::SymEdgeMap friend of Edge
 
       
   347       int &idref() {return n;}
 
       
   348       const int &idref() const {return n;} 
       
   349       //      ///Validity check
 
   344       //      ///Validity check
 
   350       //      operator bool() { return n!=-1; }
 
   345       //      operator bool() { return n!=-1; }
 
   351    };
 
   346    };
 
   352     
   347     
   353     class EdgeIt : public Edge {
 
   348     class EdgeIt : public Edge {
 
   361 	n = (m==-1)?-1:_G.nodes[m].first_in;
 
   356 	n = (m==-1)?-1:_G.nodes[m].first_in;
 
   362       }
 
   357       }
 
   363       EdgeIt (Invalid i) : Edge(i) { }
 
   358       EdgeIt (Invalid i) : Edge(i) { }
 
   364       EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
 
   359       EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
 
   365       EdgeIt() : Edge() { }
 
   360       EdgeIt() : Edge() { }
 
   366       ///\bug This is a workaround until somebody tells me how to
 
       
   367       ///make class \c SymListGraph::SymEdgeMap friend of Edge
 
       
   368       int &idref() {return n;}
 
       
   369       EdgeIt &operator++() {
 
   361       EdgeIt &operator++() {
 
   370 	if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
 
   362 	if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
 
   371 	else {
 
   363 	else {
 
   372 	  int nn;
 
   364 	  int nn;
 
   373 	  for(nn=G->nodes[G->edges[n].head].next;
 
   365 	  for(nn=G->nodes[G->edges[n].head].next;
 
   463     ///Returns the oppositely directed
 
   455     ///Returns the oppositely directed
 
   464     ///pair of the edge \c e.
 
   456     ///pair of the edge \c e.
 
   465     static Edge opposite(Edge e)
 
   457     static Edge opposite(Edge e)
 
   466     {
 
   458     {
 
   467       Edge f;
 
   459       Edge f;
 
   468       f.idref() = e.idref() - 2*(e.idref()%2) + 1;
 
   460       f.n = e.n - 2*(e.n%2) + 1;
 
   469       return f;
 
   461       return f;
 
   470     }
 
   462     }
 
   471     
   463     
   472     ///Removes a pair of oppositely directed edges to the graph.
 
   464     ///Removes a pair of oppositely directed edges to the graph.
 
   473     void erase(Edge e) {
 
   465     void erase(Edge e) {
 
   602     /// \ref maxNodeId(). The range of the ID's is not surely continuous
 
   594     /// \ref maxNodeId(). The range of the ID's is not surely continuous
 
   603     /// and the greatest node ID can be actually less then \ref maxNodeId().
 
   595     /// and the greatest node ID can be actually less then \ref maxNodeId().
 
   604     ///
 
   596     ///
 
   605     /// The ID of the \ref INVALID node is -1.
 
   597     /// The ID of the \ref INVALID node is -1.
 
   606     ///\return The ID of the node \c v. 
   598     ///\return The ID of the node \c v. 
   607     int id(Node v) const { return v.n; }
 
   599     static int id(Node v) { return v.n; }
 
   608     /// Edge ID.
 
   600     /// Edge ID.
 
   609     
   601     
   610     /// The ID of a valid Edge is a nonnegative integer not greater than
 
   602     /// The ID of a valid Edge is a nonnegative integer not greater than
 
   611     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
 
   603     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
 
   612     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
 
   604     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
 
   613     ///
 
   605     ///
 
   614     /// The ID of the \ref INVALID edge is -1.
 
   606     /// The ID of the \ref INVALID edge is -1.
 
   615     ///\return The ID of the edge \c e. 
   607     ///\return The ID of the edge \c e. 
   616     int id(Edge e) const { return -1; }
 
   608     static int id(Edge e) { return -1; }
 
   617 
   609 
   618     /// Adds a new node to the graph.
 
   610     /// Adds a new node to the graph.
 
   619 
   611 
   620     /// \warning It adds the new node to the front of the list.
 
   612     /// \warning It adds the new node to the front of the list.
 
   621     /// (i.e. the lastly added node becomes the first.)
 
   613     /// (i.e. the lastly added node becomes the first.)
 
   681       friend class OutEdgeIt;
 
   673       friend class OutEdgeIt;
 
   682       friend class InEdgeIt;
 
   674       friend class InEdgeIt;
 
   683 
   675 
   684     protected:
 
   676     protected:
 
   685       int n;
 
   677       int n;
 
   686       friend int NodeSet::id(Node v) const; 
   678       friend int NodeSet::id(Node v); 
   687       Node(int nn) {n=nn;}
 
   679       Node(int nn) {n=nn;}
 
   688     public:
 
   680     public:
 
   689       Node() {}
 
   681       Node() {}
 
   690       Node (Invalid i) { n=-1; }
 
   682       Node (Invalid i) { n=-1; }
 
   691       bool operator==(const Node i) const {return n==i.n;}
 
   683       bool operator==(const Node i) const {return n==i.n;}
 
   706 	return *this; 
   698 	return *this; 
   707       }
 
   699       }
 
   708     };
 
   700     };
 
   709 
   701 
   710     class Edge {
 
   702     class Edge {
 
   711       //friend class NodeSet;
 
       
   712       //template <typename T> friend class EdgeMap;
 
       
   713 
       
   714       //template <typename T> friend class SymNodeSet::SymEdgeMap;      
       
   715       //friend Edge SymNodeSet::opposite(Edge) const;
 
       
   716       
       
   717       //      friend class Node;
 
       
   718       //      friend class NodeIt;
 
       
   719     protected:
 
       
   720       //friend int NodeSet::id(Edge e) const;
 
       
   721       //      Edge(int nn) {}
 
       
   722     public:
 
   703     public:
 
   723       Edge() { }
 
   704       Edge() { }
 
   724       Edge (Invalid) { }
 
   705       Edge (Invalid) { }
 
   725       bool operator==(const Edge i) const {return true;}
 
   706       bool operator==(const Edge i) const {return true;}
 
   726       bool operator!=(const Edge i) const {return false;}
 
   707       bool operator!=(const Edge i) const {return false;}
 
   727       bool operator<(const Edge i) const {return false;}
 
   708       bool operator<(const Edge i) const {return false;}
 
   728       ///\bug This is a workaround until somebody tells me how to
 
       
   729       ///make class \c SymNodeSet::SymEdgeMap friend of Edge
 
       
   730       //      int idref() {return -1;}
 
       
   731       //      int idref() const {return -1;}
 
       
   732     };
 
   709     };
 
   733     
   710     
   734     class EdgeIt : public Edge {
 
   711     class EdgeIt : public Edge {
 
   735       //friend class NodeSet;
 
       
   736     public:
 
   712     public:
 
   737       EdgeIt(const NodeSet& G) : Edge() { }
 
   713       EdgeIt(const NodeSet& G) : Edge() { }
 
   738       EdgeIt(const NodeSet&, Edge) : Edge() { }
 
   714       EdgeIt(const NodeSet&, Edge) : Edge() { }
 
   739       EdgeIt (Invalid i) : Edge(i) { }
 
   715       EdgeIt (Invalid i) : Edge(i) { }
 
   740       EdgeIt() : Edge() { }
 
   716       EdgeIt() : Edge() { }
 
   741       ///\bug This is a workaround until somebody tells me how to
 
       
   742       ///make class \c SymNodeSet::SymEdgeMap friend of Edge
 
       
   743       //      int idref() {return -1;}
 
       
   744       EdgeIt operator++() { return INVALID; }
 
   717       EdgeIt operator++() { return INVALID; }
 
   745     };
 
   718     };
 
   746     
   719     
   747     class OutEdgeIt : public Edge {
 
   720     class OutEdgeIt : public Edge {
 
   748       friend class NodeSet;
 
   721       friend class NodeSet;
 
   808 
   781 
   809     int id(Node v) const; 
   782     int id(Node v) const; 
   810 
   783 
   811     class Node : public NodeGraphType::Node {
 
   784     class Node : public NodeGraphType::Node {
 
   812       friend class EdgeSet;
 
   785       friend class EdgeSet;
 
   813       //      template <typename T> friend class NodeMap;
 
       
   814       
   786       
   815       friend class Edge;
 
   787       friend class Edge;
 
   816       friend class OutEdgeIt;
 
   788       friend class OutEdgeIt;
 
   817       friend class InEdgeIt;
 
   789       friend class InEdgeIt;
 
   818       friend class SymEdge;
 
   790       friend class SymEdge;
 
   819 
   791 
   820     public:
 
   792     public:
 
   821       friend int EdgeSet::id(Node v) const; 
   793       friend int EdgeSet::id(Node v) const; 
   822       //      Node(int nn) {n=nn;}
 
       
   823     public:
 
   794     public:
 
   824       Node() : NodeGraphType::Node() {}
 
   795       Node() : NodeGraphType::Node() {}
 
   825       Node (Invalid i) : NodeGraphType::Node(i) {}
 
   796       Node (Invalid i) : NodeGraphType::Node(i) {}
 
   826       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
 
   797       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
 
   827     };
 
   798     };
 
   944     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
 
   915     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
 
   945     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
 
   916     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
 
   946     ///
 
   917     ///
 
   947     /// The ID of the \ref INVALID edge is -1.
 
   918     /// The ID of the \ref INVALID edge is -1.
 
   948     ///\return The ID of the edge \c e. 
   919     ///\return The ID of the edge \c e. 
   949     int id(Edge e) const { return e.n; }
 
   920     static int id(Edge e) { return e.n; }
 
   950 
   921 
   951     /// Adds a new node to the graph.
 
   922     /// Adds a new node to the graph.
 
   952     Node addNode() { return G.addNode(); }
 
   923     Node addNode() { return G.addNode(); }
 
   953     
   924     
   954     Edge addEdge(Node u, Node v) {
 
   925     Edge addEdge(Node u, Node v) {
 
  1021       edge_maps.erase(e);
 
   992       edge_maps.erase(e);
 
  1022     }
 
   993     }
 
  1023       
   994       
  1024   public:
 
   995   public:
 
  1025 
   996 
  1026 //     void erase(Node nn) {
 
       
  1027 //       int n=nn.n;
 
       
  1028 //       int m;
 
       
  1029 //       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
 
       
  1030 //       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
 
       
  1031 //     }
 
       
  1032     
       
  1033     void erase(Edge e) { eraseEdge(e.n); }
 
   997     void erase(Edge e) { eraseEdge(e.n); }
 
  1034 
   998 
  1035     ///Clear all edges. (Doesn't clear the nodes!)
 
   999     ///Clear all edges. (Doesn't clear the nodes!)
 
  1036     void clear() {
 
  1000     void clear() {
 
  1037       edge_maps.clear();
 
  1001       edge_maps.clear();
 
  1045       friend class EdgeSet;
 
  1009       friend class EdgeSet;
 
  1046       template <typename T> friend class EdgeMap;
 
  1010       template <typename T> friend class EdgeMap;
 
  1047 
  1011 
  1048       friend class Node;
 
  1012       friend class Node;
 
  1049       friend class NodeIt;
 
  1013       friend class NodeIt;
 
  1050     public:
 
  1014     protected:
 
  1051       ///\bug It should be at least protected
 
       
  1052       ///
 
       
  1053       int n;
 
  1015       int n;
 
  1054     protected:
 
       
  1055       friend int EdgeSet::id(Edge e) const;
 
  1016       friend int EdgeSet::id(Edge e) const;
 
  1056 
  1017 
  1057       Edge(int nn) {n=nn;}
 
  1018       Edge(int nn) {n=nn;}
 
  1058     public:
 
  1019     public:
 
  1059       Edge() { }
 
  1020       Edge() { }
 
  1060       Edge (Invalid) { n=-1; }
 
  1021       Edge (Invalid) { n=-1; }
 
  1061       bool operator==(const Edge i) const {return n==i.n;}
 
  1022       bool operator==(const Edge i) const {return n==i.n;}
 
  1062       bool operator!=(const Edge i) const {return n!=i.n;}
 
  1023       bool operator!=(const Edge i) const {return n!=i.n;}
 
  1063       bool operator<(const Edge i) const {return n<i.n;}
 
  1024       bool operator<(const Edge i) const {return n<i.n;}
 
  1064       ///\bug This is a workaround until somebody tells me how to
 
       
  1065       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
 
       
  1066       int &idref() {return n;}
 
       
  1067       const int &idref() const {return n;}
 
       
  1068     };
 
  1025     };
 
  1069     
  1026     
  1070     class EdgeIt : public Edge {
 
  1027     class EdgeIt : public Edge {
 
  1071       friend class EdgeSet;
 
  1028       friend class EdgeSet;
 
  1072       template <typename T> friend class EdgeMap;
 
  1029       template <typename T> friend class EdgeMap;
 
  1073     
  1030     
  1074       const EdgeSet *G;
 
  1031       const EdgeSet *G;
 
  1075     public:
 
  1032     public:
 
  1076       EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
 
  1033       EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
 
  1077 	//      	typename NodeGraphType::Node m;
 
       
  1078         NodeIt m;
 
  1034         NodeIt m;
 
  1079 	for(G->first(m);
 
  1035 	for(G->first(m);
 
  1080 	    m!=INVALID && G->nodes[m].first_in == -1;  ++m);
 
  1036 	    m!=INVALID && G->nodes[m].first_in == -1;  ++m);
 
  1081 	///\bug AJJAJ! This is a non sense!!!!!!!
 
  1037 	///\bug AJJAJ! This is a non sense!!!!!!!
 
  1082 	this->n = m!=INVALID?-1:G->nodes[m].first_in;
 
  1038 	this->n = m!=INVALID?-1:G->nodes[m].first_in;
 
  1089       ///\bug UNIMPLEMENTED!!!!!
 
  1045       ///\bug UNIMPLEMENTED!!!!!
 
  1090       //
 
  1046       //
 
  1091       EdgeIt &operator++() {
 
  1047       EdgeIt &operator++() {
 
  1092 	return *this;
 
  1048 	return *this;
 
  1093       }
 
  1049       }
 
  1094        ///\bug This is a workaround until somebody tells me how to
 
       
  1095       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
 
       
  1096       int &idref() {return this->n;}
 
       
  1097     };
 
  1050     };
 
  1098     
  1051     
  1099     class OutEdgeIt : public Edge {
 
  1052     class OutEdgeIt : public Edge {
 
  1100       const EdgeSet *G;
 
  1053       const EdgeSet *G;
 
  1101       friend class EdgeSet;
 
  1054       friend class EdgeSet;
lemon-0.x