Do not document registry and map defines.
3 #ifndef HUGO_LIST_GRAPH_H
4 #define HUGO_LIST_GRAPH_H
8 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
13 #include <hugo/invalid.h>
15 #include <hugo/map_registry.h>
16 #include <hugo/array_map.h>
18 #include <hugo/sym_map.h>
20 #include <hugo/map_defines.h>
25 /// \addtogroup graphs
28 ///A list graph class.
30 ///This is a simple and fast erasable graph implementation.
33 ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
34 ///\sa skeleton::ErasableGraph.
37 //Nodes are double linked.
38 //The free nodes are only single linked using the "next" field.
41 int first_in,first_out;
44 //Edges are double linked.
45 //The free edges are only single linked using the "next_in" field.
49 int prev_in, prev_out;
50 int next_in, next_out;
53 std::vector<NodeT> nodes;
58 std::vector<EdgeT> edges;
64 typedef ListGraph Graph;
77 // Create map registries.
78 CREATE_MAP_REGISTRIES;
79 /// Create node and edge maps.
80 CREATE_MAPS(ArrayMap);
85 : nodes(), first_node(-1),
86 first_free_node(-1), edges(), first_free_edge(-1) {}
88 ListGraph(const ListGraph &_g)
89 : nodes(_g.nodes), first_node(_g.first_node),
90 first_free_node(_g.first_free_node), edges(_g.edges),
91 first_free_edge(_g.first_free_edge) {}
94 int nodeNum() const { return nodes.size(); }
96 int edgeNum() const { return edges.size(); }
98 ///Set the expected maximum number of edges.
100 ///With this function, it is possible to set the expected number of edges.
101 ///The use of this fasten the building of the graph and makes
102 ///it possible to avoid the superfluous memory allocation.
103 void reserveEdge(int n) { edges.reserve(n); };
109 int maxNodeId() const { return nodes.size()-1; }
114 int maxEdgeId() const { return edges.size()-1; }
116 Node tail(Edge e) const { return edges[e.n].tail; }
117 Node head(Edge e) const { return edges[e.n].head; }
119 NodeIt& first(NodeIt& v) const {
120 v=NodeIt(*this); return v; }
121 EdgeIt& first(EdgeIt& e) const {
122 e=EdgeIt(*this); return e; }
123 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
124 e=OutEdgeIt(*this,v); return e; }
125 InEdgeIt& first(InEdgeIt& e, const Node v) const {
126 e=InEdgeIt(*this,v); return e; }
130 /// The ID of a valid Node is a nonnegative integer not greater than
131 /// \ref maxNodeId(). The range of the ID's is not surely continuous
132 /// and the greatest node ID can be actually less then \ref maxNodeId().
134 /// The ID of the \ref INVALID node is -1.
135 ///\return The ID of the node \c v.
136 static int id(Node v) { return v.n; }
139 /// The ID of a valid Edge is a nonnegative integer not greater than
140 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
141 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
143 /// The ID of the \ref INVALID edge is -1.
144 ///\return The ID of the edge \c e.
145 static int id(Edge e) { return e.n; }
147 /// Adds a new node to the graph.
149 /// \warning It adds the new node to the front of the list.
150 /// (i.e. the lastly added node becomes the first.)
154 if(first_free_node==-1)
157 nodes.push_back(NodeT());
161 first_free_node = nodes[n].next;
164 nodes[n].next = first_node;
165 if(first_node != -1) nodes[first_node].prev = n;
169 nodes[n].first_in = nodes[n].first_out = -1;
173 //Update dynamic maps
179 Edge addEdge(Node u, Node v) {
182 if(first_free_edge==-1)
185 edges.push_back(EdgeT());
189 first_free_edge = edges[n].next_in;
192 edges[n].tail = u.n; edges[n].head = v.n;
194 edges[n].next_out = nodes[u.n].first_out;
195 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
196 edges[n].next_in = nodes[v.n].first_in;
197 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
198 edges[n].prev_in = edges[n].prev_out = -1;
200 nodes[u.n].first_out = nodes[v.n].first_in = n;
204 //Update dynamic maps
210 /// Finds an edge between two nodes.
212 /// Finds an edge from node \c u to node \c v.
214 /// If \c prev is \ref INVALID (this is the default value), then
215 /// It finds the first edge from \c u to \c v. Otherwise it looks for
216 /// the next edge from \c u to \c v after \c prev.
217 /// \return The found edge or INVALID if there is no such an edge.
218 Edge findEdge(Node u,Node v, Edge prev = INVALID)
220 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
221 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
227 void eraseEdge(int n) {
229 if(edges[n].next_in!=-1)
230 edges[edges[n].next_in].prev_in = edges[n].prev_in;
231 if(edges[n].prev_in!=-1)
232 edges[edges[n].prev_in].next_in = edges[n].next_in;
233 else nodes[edges[n].head].first_in = edges[n].next_in;
235 if(edges[n].next_out!=-1)
236 edges[edges[n].next_out].prev_out = edges[n].prev_out;
237 if(edges[n].prev_out!=-1)
238 edges[edges[n].prev_out].next_out = edges[n].next_out;
239 else nodes[edges[n].tail].first_out = edges[n].next_out;
241 edges[n].next_in = first_free_edge;
244 //Update dynamic maps
252 void erase(Node nn) {
256 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
257 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
259 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
260 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
261 else first_node = nodes[n].next;
263 nodes[n].next = first_free_node;
266 //Update dynamic maps
271 void erase(Edge e) { eraseEdge(e.n); }
278 first_node=first_free_node=first_free_edge=-1;
282 friend class ListGraph;
283 template <typename T> friend class NodeMap;
286 friend class OutEdgeIt;
287 friend class InEdgeIt;
288 friend class SymEdge;
292 friend int ListGraph::id(Node v);
296 Node (Invalid) { n=-1; }
297 bool operator==(const Node i) const {return n==i.n;}
298 bool operator!=(const Node i) const {return n!=i.n;}
299 bool operator<(const Node i) const {return n<i.n;}
301 // operator bool() { return n!=-1; }
304 class NodeIt : public Node {
306 friend class ListGraph;
308 NodeIt() : Node() { }
309 NodeIt(Invalid i) : Node(i) { }
310 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
311 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
312 NodeIt &operator++() {
317 // operator bool() { return Node::operator bool(); }
321 friend class ListGraph;
322 template <typename T> friend class EdgeMap;
324 //template <typename T> friend class SymListGraph::SymEdgeMap;
325 //friend Edge SymListGraph::opposite(Edge) const;
331 friend int ListGraph::id(Edge e);
334 /// An Edge with id \c n.
336 /// \bug It should be
337 /// obtained by a member function of the Graph.
341 Edge (Invalid) { n=-1; }
342 bool operator==(const Edge i) const {return n==i.n;}
343 bool operator!=(const Edge i) const {return n!=i.n;}
344 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;}
350 // operator bool() { return n!=-1; }
353 class EdgeIt : public Edge {
355 friend class ListGraph;
357 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
360 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
361 n = (m==-1)?-1:_G.nodes[m].first_in;
363 EdgeIt (Invalid i) : Edge(i) { }
364 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
365 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++() {
370 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
373 for(nn=G->nodes[G->edges[n].head].next;
374 nn!=-1 && G->nodes[nn].first_in == -1;
375 nn = G->nodes[nn].next) ;
376 n = (nn==-1)?-1:G->nodes[nn].first_in;
381 // operator bool() { return Edge::operator bool(); }
384 class OutEdgeIt : public Edge {
386 friend class ListGraph;
388 OutEdgeIt() : Edge() { }
389 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
390 OutEdgeIt (Invalid i) : Edge(i) { }
392 OutEdgeIt(const ListGraph& _G,const Node v)
393 : Edge(_G.nodes[v.n].first_out), G(&_G) {}
394 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
396 // operator bool() { return Edge::operator bool(); }
399 class InEdgeIt : public Edge {
401 friend class ListGraph;
403 InEdgeIt() : Edge() { }
404 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
405 InEdgeIt (Invalid i) : Edge(i) { }
406 InEdgeIt(const ListGraph& _G,Node v)
407 : Edge(_G.nodes[v.n].first_in), G(&_G) { }
408 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
410 // operator bool() { return Edge::operator bool(); }
414 ///Graph for bidirectional edges.
416 ///The purpose of this graph structure is to handle graphs
417 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
418 ///of oppositely directed edges.
419 ///There is a new edge map type called
420 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
421 ///that complements this
423 ///storing shared values for the edge pairs. The usual
424 ///\ref Graph::EdgeMap "EdgeMap"
428 ///The oppositely directed edge can also be obtained easily
429 ///using \ref opposite.
431 ///Here erase(Edge) deletes a pair of edges.
433 ///\todo this date structure need some reconsiderations. Maybe it
434 ///should be implemented independently from ListGraph.
436 class SymListGraph : public ListGraph
440 typedef SymListGraph Graph;
442 // Create symmetric map registry.
443 CREATE_SYM_EDGE_MAP_REGISTRY;
444 // Create symmetric edge map.
445 CREATE_SYM_EDGE_MAP(ArrayMap);
447 SymListGraph() : ListGraph() { }
448 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
449 ///Adds a pair of oppositely directed edges to the graph.
450 Edge addEdge(Node u, Node v)
452 Edge e = ListGraph::addEdge(u,v);
453 Edge f = ListGraph::addEdge(v,u);
454 sym_edge_maps.add(e);
455 sym_edge_maps.add(f);
460 void erase(Node n) { ListGraph::erase(n);}
461 ///The oppositely directed edge.
463 ///Returns the oppositely directed
464 ///pair of the edge \c e.
465 static Edge opposite(Edge e)
468 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
472 ///Removes a pair of oppositely directed edges to the graph.
474 Edge f = opposite(e);
475 sym_edge_maps.erase(e);
476 sym_edge_maps.erase(f);
483 ///A graph class containing only nodes.
485 ///This class implements a graph structure without edges.
486 ///The most useful application of this class is to be the node set of an
487 ///\ref EdgeSet class.
490 ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
491 ///with the exception that you cannot
492 ///add (or delete) edges. The usual edge iterators are exists, but they are
493 ///always \ref INVALID.
494 ///\sa skeleton::ExtendableGraph
498 //Nodes are double linked.
499 //The free nodes are only single linked using the "next" field.
502 int first_in,first_out;
507 std::vector<NodeT> nodes;
510 //The first free node
515 typedef NodeSet Graph;
527 // Create node map registry.
528 CREATE_NODE_MAP_REGISTRY;
530 CREATE_NODE_MAP(ArrayMap);
532 /// Creating empty map structure for edges.
533 template <typename Value>
536 EdgeMap(const Graph&) {}
537 EdgeMap(const Graph&, const Value&) {}
539 EdgeMap(const EdgeMap&) {}
540 template <typename CMap> EdgeMap(const CMap&) {}
542 EdgeMap& operator=(const EdgeMap&) {}
543 template <typename CMap> EdgeMap& operator=(const CMap&) {}
545 class ConstIterator {
547 bool operator==(const ConstIterator&) {return true;}
548 bool operator!=(const ConstIterator&) {return false;}
551 typedef ConstIterator Iterator;
553 Iterator begin() { return Iterator();}
554 Iterator end() { return Iterator();}
556 ConstIterator begin() const { return ConstIterator();}
557 ConstIterator end() const { return ConstIterator();}
563 ///Default constructor
565 : nodes(), first_node(-1), first_free_node(-1) {}
567 NodeSet(const NodeSet &_g)
568 : nodes(_g.nodes), first_node(_g.first_node),
569 first_free_node(_g.first_free_node) {}
572 int nodeNum() const { return nodes.size(); }
574 int edgeNum() const { return 0; }
580 int maxNodeId() const { return nodes.size()-1; }
585 int maxEdgeId() const { return 0; }
587 Node tail(Edge e) const { return INVALID; }
588 Node head(Edge e) const { return INVALID; }
590 NodeIt& first(NodeIt& v) const {
591 v=NodeIt(*this); return v; }
592 EdgeIt& first(EdgeIt& e) const {
593 e=EdgeIt(*this); return e; }
594 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
595 e=OutEdgeIt(*this,v); return e; }
596 InEdgeIt& first(InEdgeIt& e, const Node v) const {
597 e=InEdgeIt(*this,v); return e; }
601 /// The ID of a valid Node is a nonnegative integer not greater than
602 /// \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().
605 /// The ID of the \ref INVALID node is -1.
606 ///\return The ID of the node \c v.
607 int id(Node v) const { return v.n; }
610 /// 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
612 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
614 /// The ID of the \ref INVALID edge is -1.
615 ///\return The ID of the edge \c e.
616 int id(Edge e) const { return -1; }
618 /// Adds a new node to the graph.
620 /// \warning It adds the new node to the front of the list.
621 /// (i.e. the lastly added node becomes the first.)
625 if(first_free_node==-1)
628 nodes.push_back(NodeT());
632 first_free_node = nodes[n].next;
635 nodes[n].next = first_node;
636 if(first_node != -1) nodes[first_node].prev = n;
640 nodes[n].first_in = nodes[n].first_out = -1;
644 //Update dynamic maps
650 void erase(Node nn) {
653 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
654 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
655 else first_node = nodes[n].next;
657 nodes[n].next = first_free_node;
660 //Update dynamic maps
665 Edge findEdge(Node u,Node v, Edge prev = INVALID)
673 first_node = first_free_node = -1;
677 friend class NodeSet;
678 template <typename T> friend class NodeMap;
681 friend class OutEdgeIt;
682 friend class InEdgeIt;
686 friend int NodeSet::id(Node v) const;
690 Node (Invalid i) { n=-1; }
691 bool operator==(const Node i) const {return n==i.n;}
692 bool operator!=(const Node i) const {return n!=i.n;}
693 bool operator<(const Node i) const {return n<i.n;}
696 class NodeIt : public Node {
698 friend class NodeSet;
700 NodeIt() : Node() { }
701 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
702 NodeIt(Invalid i) : Node(i) { }
703 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
704 NodeIt &operator++() {
711 //friend class NodeSet;
712 //template <typename T> friend class EdgeMap;
714 //template <typename T> friend class SymNodeSet::SymEdgeMap;
715 //friend Edge SymNodeSet::opposite(Edge) const;
717 // friend class Node;
718 // friend class NodeIt;
720 //friend int NodeSet::id(Edge e) const;
725 bool operator==(const Edge i) const {return true;}
726 bool operator!=(const Edge i) const {return false;}
727 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;}
734 class EdgeIt : public Edge {
735 //friend class NodeSet;
737 EdgeIt(const NodeSet& G) : Edge() { }
738 EdgeIt(const NodeSet&, Edge) : Edge() { }
739 EdgeIt (Invalid i) : Edge(i) { }
740 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; }
747 class OutEdgeIt : public Edge {
748 friend class NodeSet;
750 OutEdgeIt() : Edge() { }
751 OutEdgeIt(const NodeSet&, Edge) : Edge() { }
752 OutEdgeIt (Invalid i) : Edge(i) { }
753 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
754 OutEdgeIt operator++() { return INVALID; }
757 class InEdgeIt : public Edge {
758 friend class NodeSet;
760 InEdgeIt() : Edge() { }
761 InEdgeIt(const NodeSet&, Edge) : Edge() { }
762 InEdgeIt (Invalid i) : Edge(i) { }
763 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
764 InEdgeIt operator++() { return INVALID; }
771 ///Graph structure using a node set of another graph.
773 ///This structure can be used to establish another graph over a node set
774 /// of an existing one. The node iterator will go through the nodes of the
775 /// original graph, and the NodeMap's of both graphs will convert to
778 ///\warning Adding or deleting nodes from the graph is not safe if an
779 ///\ref EdgeSet is currently attached to it!
781 ///\todo Make it possible to add/delete edges from the base graph
782 ///(and from \ref EdgeSet, as well)
784 ///\param GG The type of the graph which shares its node set with this class.
785 ///Its interface must conform to the
786 ///\ref skeleton::StaticGraph "StaticGraph" concept.
788 ///It conforms to the
789 ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
790 ///\sa skeleton::ExtendableGraph.
792 template<typename GG>
795 typedef GG NodeGraphType;
807 typedef EdgeSet Graph;
809 int id(Node v) const;
811 class Node : public NodeGraphType::Node {
812 friend class EdgeSet;
813 // template <typename T> friend class NodeMap;
816 friend class OutEdgeIt;
817 friend class InEdgeIt;
818 friend class SymEdge;
821 friend int EdgeSet::id(Node v) const;
822 // Node(int nn) {n=nn;}
824 Node() : NodeGraphType::Node() {}
825 Node (Invalid i) : NodeGraphType::Node(i) {}
826 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
829 class NodeIt : public NodeGraphType::NodeIt {
830 friend class EdgeSet;
832 NodeIt() : NodeGraphType::NodeIt() { }
833 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
834 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
835 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
836 NodeIt(const typename NodeGraphType::NodeIt &n)
837 : NodeGraphType::NodeIt(n) {}
839 operator Node() { return Node(*this);}
841 { this->NodeGraphType::NodeIt::operator++(); return *this;}
845 //Edges are double linked.
846 //The free edges are only single linked using the "next_in" field.
849 int first_in,first_out;
850 NodeT() : first_in(-1), first_out(-1) { }
856 int prev_in, prev_out;
857 int next_in, next_out;
861 typename NodeGraphType::template NodeMap<NodeT> nodes;
863 std::vector<EdgeT> edges;
864 //The first free edge
878 // Create edge map registry.
879 CREATE_EDGE_MAP_REGISTRY;
881 CREATE_EDGE_MAP(ArrayMap);
883 // Import node maps from the NodeGraphType.
884 IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
891 ///Construates a new graph based on the nodeset of an existing one.
892 ///\param _G the base graph.
893 explicit EdgeSet(NodeGraphType &_G)
894 : G(_G), nodes(_G), edges(),
895 first_free_edge(-1) {}
898 ///Makes a copy of an EdgeSet.
899 ///It will be based on the same graph.
900 explicit EdgeSet(const EdgeSet &_g)
901 : G(_g.G), nodes(_g.G), edges(_g.edges),
902 first_free_edge(_g.first_free_edge) {}
905 int nodeNum() const { return G.nodeNum(); }
907 int edgeNum() const { return edges.size(); }
913 int maxNodeId() const { return G.maxNodeId(); }
918 int maxEdgeId() const { return edges.size()-1; }
920 Node tail(Edge e) const { return edges[e.n].tail; }
921 Node head(Edge e) const { return edges[e.n].head; }
923 NodeIt& first(NodeIt& v) const {
924 v=NodeIt(*this); return v; }
925 EdgeIt& first(EdgeIt& e) const {
926 e=EdgeIt(*this); return e; }
927 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
928 e=OutEdgeIt(*this,v); return e; }
929 InEdgeIt& first(InEdgeIt& e, const Node v) const {
930 e=InEdgeIt(*this,v); return e; }
934 /// The ID of a valid Node is a nonnegative integer not greater than
935 /// \ref maxNodeId(). The range of the ID's is not surely continuous
936 /// and the greatest node ID can be actually less then \ref maxNodeId().
938 /// The ID of the \ref INVALID node is -1.
939 ///\return The ID of the node \c v.
940 int id(Node v) { return G.id(v); }
943 /// The ID of a valid Edge is a nonnegative integer not greater than
944 /// \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().
947 /// The ID of the \ref INVALID edge is -1.
948 ///\return The ID of the edge \c e.
949 int id(Edge e) const { return e.n; }
951 /// Adds a new node to the graph.
952 Node addNode() { return G.addNode(); }
954 Edge addEdge(Node u, Node v) {
957 if(first_free_edge==-1)
960 edges.push_back(EdgeT());
964 first_free_edge = edges[n].next_in;
967 edges[n].tail = u; edges[n].head = v;
969 edges[n].next_out = nodes[u].first_out;
970 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
971 edges[n].next_in = nodes[v].first_in;
972 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
973 edges[n].prev_in = edges[n].prev_out = -1;
975 nodes[u].first_out = nodes[v].first_in = n;
979 //Update dynamic maps
985 /// Finds an edge between two nodes.
987 /// Finds an edge from node \c u to node \c v.
989 /// If \c prev is \ref INVALID (this is the default value), then
990 /// It finds the first edge from \c u to \c v. Otherwise it looks for
991 /// the next edge from \c u to \c v after \c prev.
992 /// \return The found edge or INVALID if there is no such an edge.
993 Edge findEdge(Node u,Node v, Edge prev = INVALID)
995 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
996 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
1002 void eraseEdge(int n) {
1004 if(edges[n].next_in!=-1)
1005 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1006 if(edges[n].prev_in!=-1)
1007 edges[edges[n].prev_in].next_in = edges[n].next_in;
1008 else nodes[edges[n].head].first_in = edges[n].next_in;
1010 if(edges[n].next_out!=-1)
1011 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1012 if(edges[n].prev_out!=-1)
1013 edges[edges[n].prev_out].next_out = edges[n].next_out;
1014 else nodes[edges[n].tail].first_out = edges[n].next_out;
1016 edges[n].next_in = first_free_edge;
1017 first_free_edge = -1;
1019 //Update dynamic maps
1026 // void erase(Node nn) {
1029 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1030 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1033 void erase(Edge e) { eraseEdge(e.n); }
1035 ///Clear all edges. (Doesn't clear the nodes!)
1045 friend class EdgeSet;
1046 template <typename T> friend class EdgeMap;
1049 friend class NodeIt;
1051 ///\bug It should be at least protected
1055 friend int EdgeSet::id(Edge e) const;
1057 Edge(int nn) {n=nn;}
1060 Edge (Invalid) { n=-1; }
1061 bool operator==(const Edge i) const {return n==i.n;}
1062 bool operator!=(const Edge i) const {return n!=i.n;}
1063 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;}
1070 class EdgeIt : public Edge {
1071 friend class EdgeSet;
1072 template <typename T> friend class EdgeMap;
1076 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1077 // typename NodeGraphType::Node m;
1080 m!=INVALID && G->nodes[m].first_in == -1; ++m);
1081 ///\bug AJJAJ! This is a non sense!!!!!!!
1082 this->n = m!=INVALID?-1:G->nodes[m].first_in;
1084 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1085 EdgeIt (Invalid i) : Edge(i) { }
1086 EdgeIt() : Edge() { }
1089 ///\bug UNIMPLEMENTED!!!!!
1091 EdgeIt &operator++() {
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;}
1099 class OutEdgeIt : public Edge {
1101 friend class EdgeSet;
1103 OutEdgeIt() : Edge() { }
1104 OutEdgeIt (Invalid i) : Edge(i) { }
1105 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1107 OutEdgeIt(const EdgeSet& _G,const Node v) :
1108 Edge(_G.nodes[v].first_out), G(&_G) { }
1109 OutEdgeIt &operator++() {
1110 Edge::n = G->edges[Edge::n].next_out;
1115 class InEdgeIt : public Edge {
1117 friend class EdgeSet;
1119 InEdgeIt() : Edge() { }
1120 InEdgeIt (Invalid i) : Edge(i) { }
1121 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1122 InEdgeIt(const EdgeSet& _G,Node v)
1123 : Edge(_G.nodes[v].first_in), G(&_G) { }
1124 InEdgeIt &operator++() {
1125 Edge::n = G->edges[Edge::n].next_in;
1132 template<typename GG>
1133 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1139 #endif //HUGO_LIST_GRAPH_H