Shorter template parameter names to be more readable in Doxygen.
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/default_map.h>
18 #include <hugo/sym_map.h>
20 #include <hugo/map_defines.h>
25 /// \addtogroup graphs
28 // class SymListGraph;
30 ///A list graph class.
32 ///This is a simple and fast erasable graph implementation.
34 ///It conforms to the graph interface documented under
35 ///the description of \ref GraphSkeleton.
36 ///\sa \ref GraphSkeleton.
39 //Nodes are double linked.
40 //The free nodes are only single linked using the "next" field.
43 int first_in,first_out;
47 //Edges are double linked.
48 //The free edges are only single linked using the "next_in" field.
52 int prev_in, prev_out;
53 int next_in, next_out;
54 //FIXME: is this necessary?
55 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
58 std::vector<NodeT> nodes;
63 std::vector<EdgeT> edges;
69 typedef ListGraph Graph;
82 /// Creating map registries.
83 CREATE_MAP_REGISTRIES;
84 /// Creating node and edge maps.
85 CREATE_MAPS(DefaultMap);
90 : nodes(), first_node(-1),
91 first_free_node(-1), edges(), first_free_edge(-1) {}
93 ListGraph(const ListGraph &_g)
94 : nodes(_g.nodes), first_node(_g.first_node),
95 first_free_node(_g.first_free_node), edges(_g.edges),
96 first_free_edge(_g.first_free_edge) {}
99 int nodeNum() const { return nodes.size(); }
101 int edgeNum() const { return edges.size(); }
103 ///Set the expected maximum number of edges.
105 ///With this function, it is possible to set the expected number of edges.
106 ///The use of this fasten the building of the graph and makes
107 ///it possible to avoid the superfluous memory allocation.
108 void reserveEdge(int n) { edges.reserve(n); };
114 int maxNodeId() const { return nodes.size()-1; }
119 int maxEdgeId() const { return edges.size()-1; }
121 Node tail(Edge e) const { return edges[e.n].tail; }
122 Node head(Edge e) const { return edges[e.n].head; }
124 NodeIt& first(NodeIt& v) const {
125 v=NodeIt(*this); return v; }
126 EdgeIt& first(EdgeIt& e) const {
127 e=EdgeIt(*this); return e; }
128 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
129 e=OutEdgeIt(*this,v); return e; }
130 InEdgeIt& first(InEdgeIt& e, const Node v) const {
131 e=InEdgeIt(*this,v); return e; }
135 /// The ID of a valid Node is a nonnegative integer not greater than
136 /// \ref maxNodeId(). The range of the ID's is not surely continuous
137 /// and the greatest node ID can be actually less then \ref maxNodeId().
139 /// The ID of the \ref INVALID node is -1.
140 ///\return The ID of the node \c v.
141 static int id(Node v) { return v.n; }
144 /// The ID of a valid Edge is a nonnegative integer not greater than
145 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
146 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
148 /// The ID of the \ref INVALID edge is -1.
149 ///\return The ID of the edge \c e.
150 static int id(Edge e) { return e.n; }
152 /// Adds a new node to the graph.
154 /// \warning It adds the new node to the front of the list.
155 /// (i.e. the lastly added node becomes the first.)
159 if(first_free_node==-1)
162 nodes.push_back(NodeT());
166 first_free_node = nodes[n].next;
169 nodes[n].next = first_node;
170 if(first_node != -1) nodes[first_node].prev = n;
174 nodes[n].first_in = nodes[n].first_out = -1;
178 //Update dynamic maps
184 Edge addEdge(Node u, Node v) {
187 if(first_free_edge==-1)
190 edges.push_back(EdgeT());
194 first_free_edge = edges[n].next_in;
197 edges[n].tail = u.n; edges[n].head = v.n;
199 edges[n].next_out = nodes[u.n].first_out;
200 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
201 edges[n].next_in = nodes[v.n].first_in;
202 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
203 edges[n].prev_in = edges[n].prev_out = -1;
205 nodes[u.n].first_out = nodes[v.n].first_in = n;
209 //Update dynamic maps
215 /// Finds an edge between two nodes.
217 /// Finds an edge from node \c u to node \c v.
219 /// If \c prev is \ref INVALID (this is the default value), then
220 /// It finds the first edge from \c u to \c v. Otherwise it looks for
221 /// the next edge from \c u to \c v after \c prev.
222 /// \return The found edge or INVALID if there is no such an edge.
223 Edge findEdge(Node u,Node v, Edge prev = INVALID)
225 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
226 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
232 void eraseEdge(int n) {
234 if(edges[n].next_in!=-1)
235 edges[edges[n].next_in].prev_in = edges[n].prev_in;
236 if(edges[n].prev_in!=-1)
237 edges[edges[n].prev_in].next_in = edges[n].next_in;
238 else nodes[edges[n].head].first_in = edges[n].next_in;
240 if(edges[n].next_out!=-1)
241 edges[edges[n].next_out].prev_out = edges[n].prev_out;
242 if(edges[n].prev_out!=-1)
243 edges[edges[n].prev_out].next_out = edges[n].next_out;
244 else nodes[edges[n].tail].first_out = edges[n].next_out;
246 edges[n].next_in = first_free_edge;
249 //Update dynamic maps
257 void erase(Node nn) {
261 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
262 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
264 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
265 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
266 else first_node = nodes[n].next;
268 nodes[n].next = first_free_node;
271 //Update dynamic maps
276 void erase(Edge e) { eraseEdge(e.n); }
283 first_node=first_free_node=first_free_edge=-1;
287 friend class ListGraph;
288 template <typename T> friend class NodeMap;
291 friend class OutEdgeIt;
292 friend class InEdgeIt;
293 friend class SymEdge;
297 friend int ListGraph::id(Node v);
301 Node (Invalid) { n=-1; }
302 bool operator==(const Node i) const {return n==i.n;}
303 bool operator!=(const Node i) const {return n!=i.n;}
304 bool operator<(const Node i) const {return n<i.n;}
306 // operator bool() { return n!=-1; }
309 class NodeIt : public Node {
311 friend class ListGraph;
313 NodeIt() : Node() { }
314 NodeIt(Invalid i) : Node(i) { }
315 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
316 ///\todo Undocumented conversion Node -\> NodeIt.
317 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
318 NodeIt &operator++() {
323 // operator bool() { return Node::operator bool(); }
327 friend class ListGraph;
328 template <typename T> friend class EdgeMap;
330 //template <typename T> friend class SymListGraph::SymEdgeMap;
331 //friend Edge SymListGraph::opposite(Edge) const;
337 friend int ListGraph::id(Edge e);
340 /// An Edge with id \c n.
342 /// \bug It should be
343 /// obtained by a member function of the Graph.
347 Edge (Invalid) { n=-1; }
348 bool operator==(const Edge i) const {return n==i.n;}
349 bool operator!=(const Edge i) const {return n!=i.n;}
350 bool operator<(const Edge i) const {return n<i.n;}
351 ///\bug This is a workaround until somebody tells me how to
352 ///make class \c SymListGraph::SymEdgeMap friend of Edge
353 int &idref() {return n;}
354 const int &idref() const {return n;}
356 // operator bool() { return n!=-1; }
359 class EdgeIt : public Edge {
361 friend class ListGraph;
363 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
366 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
367 n = (m==-1)?-1:_G.nodes[m].first_in;
369 EdgeIt (Invalid i) : Edge(i) { }
370 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
371 EdgeIt() : Edge() { }
372 ///\bug This is a workaround until somebody tells me how to
373 ///make class \c SymListGraph::SymEdgeMap friend of Edge
374 int &idref() {return n;}
375 EdgeIt &operator++() {
376 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
379 for(nn=G->nodes[G->edges[n].head].next;
380 nn!=-1 && G->nodes[nn].first_in == -1;
381 nn = G->nodes[nn].next) ;
382 n = (nn==-1)?-1:G->nodes[nn].first_in;
387 // operator bool() { return Edge::operator bool(); }
390 class OutEdgeIt : public Edge {
392 friend class ListGraph;
394 OutEdgeIt() : Edge() { }
395 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
396 OutEdgeIt (Invalid i) : Edge(i) { }
398 OutEdgeIt(const ListGraph& _G,const Node v)
399 : Edge(_G.nodes[v.n].first_out), G(&_G) {}
400 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
402 // operator bool() { return Edge::operator bool(); }
405 class InEdgeIt : public Edge {
407 friend class ListGraph;
409 InEdgeIt() : Edge() { }
410 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
411 InEdgeIt (Invalid i) : Edge(i) { }
412 InEdgeIt(const ListGraph& _G,Node v)
413 : Edge(_G.nodes[v.n].first_in), G(&_G) { }
414 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
416 // operator bool() { return Edge::operator bool(); }
420 ///Graph for bidirectional edges.
422 ///The purpose of this graph structure is to handle graphs
423 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
424 ///of oppositely directed edges.
425 ///There is a new edge map type called
426 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
427 ///that complements this
429 ///storing shared values for the edge pairs. The usual
430 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
434 ///The oppositely directed edge can also be obtained easily
435 ///using \ref opposite.
437 ///Here erase(Edge) deletes a pair of edges.
439 ///\todo this date structure need some reconsiderations. Maybe it
440 ///should be implemented independently from ListGraph.
442 class SymListGraph : public ListGraph
446 typedef SymListGraph Graph;
448 /// Importing maps from the base class ListGraph.
449 KEEP_MAPS(ListGraph, SymListGraph);
451 /// Creating symmetric map registry.
452 CREATE_SYM_EDGE_MAP_REGISTRY;
453 /// Creating symmetric edge map.
454 CREATE_SYM_EDGE_MAP(DefaultMap);
456 SymListGraph() : ListGraph() { }
457 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
458 ///Adds a pair of oppositely directed edges to the graph.
459 Edge addEdge(Node u, Node v)
461 Edge e = ListGraph::addEdge(u,v);
462 Edge f = ListGraph::addEdge(v,u);
463 sym_edge_maps.add(e);
464 sym_edge_maps.add(f);
469 void erase(Node n) { ListGraph::erase(n);}
470 ///The oppositely directed edge.
472 ///Returns the oppositely directed
473 ///pair of the edge \c e.
474 static Edge opposite(Edge e)
477 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
481 ///Removes a pair of oppositely directed edges to the graph.
483 Edge f = opposite(e);
484 sym_edge_maps.erase(e);
485 sym_edge_maps.erase(f);
492 ///A graph class containing only nodes.
494 ///This class implements a graph structure without edges.
495 ///The most useful application of this class is to be the node set of an
496 ///\ref EdgeSet class.
498 ///It conforms to the graph interface documented under
499 ///the description of \ref GraphSkeleton with the exception that you cannot
500 ///add (or delete) edges. The usual edge iterators are exists, but they are
501 ///always \ref INVALID.
502 ///\sa \ref GraphSkeleton
506 //Nodes are double linked.
507 //The free nodes are only single linked using the "next" field.
510 int first_in,first_out;
515 std::vector<NodeT> nodes;
518 //The first free node
523 typedef NodeSet Graph;
535 /// Creating node map registry.
536 CREATE_NODE_MAP_REGISTRY;
537 /// Creating node maps.
538 CREATE_NODE_MAP(DefaultMap);
540 /// Creating empty map structure for edges.
541 template <typename Value>
545 EdgeMap(const Graph&) {}
546 EdgeMap(const Graph&, const Value&) {}
548 EdgeMap(const EdgeMap&) {}
549 template <typename CMap> EdgeMap(const CMap&) {}
551 EdgeMap& operator=(const EdgeMap&) {}
552 template <typename CMap> EdgeMap& operator=(const CMap&) {}
554 class ConstIterator {
556 bool operator==(const ConstIterator&) {return true;}
557 bool operator!=(const ConstIterator&) {return false;}
560 typedef ConstIterator Iterator;
562 Iterator begin() { return Iterator();}
563 Iterator end() { return Iterator();}
565 ConstIterator begin() const { return ConstIterator();}
566 ConstIterator end() const { return ConstIterator();}
572 ///Default constructor
574 : nodes(), first_node(-1), first_free_node(-1) {}
576 NodeSet(const NodeSet &_g)
577 : nodes(_g.nodes), first_node(_g.first_node),
578 first_free_node(_g.first_free_node) {}
581 int nodeNum() const { return nodes.size(); }
583 int edgeNum() const { return 0; }
589 int maxNodeId() const { return nodes.size()-1; }
594 int maxEdgeId() const { return 0; }
596 Node tail(Edge e) const { return INVALID; }
597 Node head(Edge e) const { return INVALID; }
599 NodeIt& first(NodeIt& v) const {
600 v=NodeIt(*this); return v; }
601 EdgeIt& first(EdgeIt& e) const {
602 e=EdgeIt(*this); return e; }
603 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
604 e=OutEdgeIt(*this,v); return e; }
605 InEdgeIt& first(InEdgeIt& e, const Node v) const {
606 e=InEdgeIt(*this,v); return e; }
610 /// The ID of a valid Node is a nonnegative integer not greater than
611 /// \ref maxNodeId(). The range of the ID's is not surely continuous
612 /// and the greatest node ID can be actually less then \ref maxNodeId().
614 /// The ID of the \ref INVALID node is -1.
615 ///\return The ID of the node \c v.
616 int id(Node v) const { return v.n; }
619 /// The ID of a valid Edge is a nonnegative integer not greater than
620 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
621 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
623 /// The ID of the \ref INVALID edge is -1.
624 ///\return The ID of the edge \c e.
625 int id(Edge e) const { return -1; }
627 /// Adds a new node to the graph.
629 /// \warning It adds the new node to the front of the list.
630 /// (i.e. the lastly added node becomes the first.)
634 if(first_free_node==-1)
637 nodes.push_back(NodeT());
641 first_free_node = nodes[n].next;
644 nodes[n].next = first_node;
645 if(first_node != -1) nodes[first_node].prev = n;
649 nodes[n].first_in = nodes[n].first_out = -1;
653 //Update dynamic maps
659 void erase(Node nn) {
662 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
663 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
664 else first_node = nodes[n].next;
666 nodes[n].next = first_free_node;
669 //Update dynamic maps
674 Edge findEdge(Node u,Node v, Edge prev = INVALID)
682 first_node = first_free_node = -1;
686 friend class NodeSet;
687 template <typename T> friend class NodeMap;
690 friend class OutEdgeIt;
691 friend class InEdgeIt;
695 friend int NodeSet::id(Node v) const;
699 Node (Invalid i) { n=-1; }
700 bool operator==(const Node i) const {return n==i.n;}
701 bool operator!=(const Node i) const {return n!=i.n;}
702 bool operator<(const Node i) const {return n<i.n;}
705 class NodeIt : public Node {
707 friend class NodeSet;
709 NodeIt() : Node() { }
710 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
711 NodeIt(Invalid i) : Node(i) { }
712 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
713 NodeIt &operator++() {
720 //friend class NodeSet;
721 //template <typename T> friend class EdgeMap;
723 //template <typename T> friend class SymNodeSet::SymEdgeMap;
724 //friend Edge SymNodeSet::opposite(Edge) const;
726 // friend class Node;
727 // friend class NodeIt;
729 //friend int NodeSet::id(Edge e) const;
734 bool operator==(const Edge i) const {return true;}
735 bool operator!=(const Edge i) const {return false;}
736 bool operator<(const Edge i) const {return false;}
737 ///\bug This is a workaround until somebody tells me how to
738 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
739 // int idref() {return -1;}
740 // int idref() const {return -1;}
743 class EdgeIt : public Edge {
744 //friend class NodeSet;
746 EdgeIt(const NodeSet& G) : Edge() { }
747 EdgeIt(const NodeSet&, Edge) : Edge() { }
748 EdgeIt (Invalid i) : Edge(i) { }
749 EdgeIt() : Edge() { }
750 ///\bug This is a workaround until somebody tells me how to
751 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
752 // int idref() {return -1;}
753 EdgeIt operator++() { return INVALID; }
756 class OutEdgeIt : public Edge {
757 friend class NodeSet;
759 OutEdgeIt() : Edge() { }
760 OutEdgeIt(const NodeSet&, Edge) : Edge() { }
761 OutEdgeIt (Invalid i) : Edge(i) { }
762 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
763 OutEdgeIt operator++() { return INVALID; }
766 class InEdgeIt : public Edge {
767 friend class NodeSet;
769 InEdgeIt() : Edge() { }
770 InEdgeIt(const NodeSet&, Edge) : Edge() { }
771 InEdgeIt (Invalid i) : Edge(i) { }
772 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
773 InEdgeIt operator++() { return INVALID; }
780 ///Graph structure using a node set of another graph.
782 ///This structure can be used to establish another graph over a node set
783 /// of an existing one. The node iterator will go through the nodes of the
784 /// original graph, and the NodeMap's of both graphs will convert to
787 ///\warning Adding or deleting nodes from the graph is not safe if an
788 ///\ref EdgeSet is currently attached to it!
790 ///\todo Make it possible to add/delete edges from the base graph
791 ///(and from \ref EdgeSet, as well)
793 ///\param GG The type of the graph which shares its node set with this class.
794 ///Its interface must conform with \ref GraphSkeleton.
796 ///It conforms to the graph interface documented under
797 ///the description of \ref GraphSkeleton.
798 ///\sa \ref GraphSkeleton.
800 template<typename GG>
803 typedef GG NodeGraphType;
815 typedef EdgeSet Graph;
817 int id(Node v) const;
819 class Node : public NodeGraphType::Node {
820 friend class EdgeSet;
821 // template <typename T> friend class NodeMap;
824 friend class OutEdgeIt;
825 friend class InEdgeIt;
826 friend class SymEdge;
829 friend int EdgeSet::id(Node v) const;
830 // Node(int nn) {n=nn;}
832 Node() : NodeGraphType::Node() {}
833 Node (Invalid i) : NodeGraphType::Node(i) {}
834 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
837 class NodeIt : public NodeGraphType::NodeIt {
838 friend class EdgeSet;
840 NodeIt() : NodeGraphType::NodeIt() { }
841 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
842 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
843 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
844 NodeIt(const typename NodeGraphType::NodeIt &n)
845 : NodeGraphType::NodeIt(n) {}
847 operator Node() { return Node(*this);}
849 { this->NodeGraphType::NodeIt::operator++(); return *this;}
853 //Edges are double linked.
854 //The free edges are only single linked using the "next_in" field.
857 int first_in,first_out;
858 NodeT() : first_in(-1), first_out(-1) { }
864 int prev_in, prev_out;
865 int next_in, next_out;
869 typename NodeGraphType::template NodeMap<NodeT> nodes;
871 std::vector<EdgeT> edges;
872 //The first free edge
886 /// Creating edge map registry.
887 CREATE_EDGE_MAP_REGISTRY;
888 /// Creating edge maps.
889 CREATE_EDGE_MAP(DefaultMap);
891 /// Importing node maps from the NodeGraphType.
892 IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
899 ///Construates a new graph based on the nodeset of an existing one.
900 ///\param _G the base graph.
901 ///\todo It looks like a copy constructor, but it isn't.
902 EdgeSet(NodeGraphType &_G)
903 : G(_G), nodes(_G), edges(),
904 first_free_edge(-1) {}
907 ///Makes a copy of an EdgeSet.
908 ///It will be based on the same graph.
909 EdgeSet(const EdgeSet &_g)
910 : G(_g.G), nodes(_g.G), edges(_g.edges),
911 first_free_edge(_g.first_free_edge) {}
914 int nodeNum() const { return G.nodeNum(); }
916 int edgeNum() const { return edges.size(); }
922 int maxNodeId() const { return G.maxNodeId(); }
927 int maxEdgeId() const { return edges.size()-1; }
929 Node tail(Edge e) const { return edges[e.n].tail; }
930 Node head(Edge e) const { return edges[e.n].head; }
932 NodeIt& first(NodeIt& v) const {
933 v=NodeIt(*this); return v; }
934 EdgeIt& first(EdgeIt& e) const {
935 e=EdgeIt(*this); return e; }
936 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
937 e=OutEdgeIt(*this,v); return e; }
938 InEdgeIt& first(InEdgeIt& e, const Node v) const {
939 e=InEdgeIt(*this,v); return e; }
943 /// The ID of a valid Node is a nonnegative integer not greater than
944 /// \ref maxNodeId(). The range of the ID's is not surely continuous
945 /// and the greatest node ID can be actually less then \ref maxNodeId().
947 /// The ID of the \ref INVALID node is -1.
948 ///\return The ID of the node \c v.
949 int id(Node v) { return G.id(v); }
952 /// The ID of a valid Edge is a nonnegative integer not greater than
953 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
954 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
956 /// The ID of the \ref INVALID edge is -1.
957 ///\return The ID of the edge \c e.
958 int id(Edge e) const { return e.n; }
960 /// Adds a new node to the graph.
961 Node addNode() { return G.addNode(); }
963 Edge addEdge(Node u, Node v) {
966 if(first_free_edge==-1)
969 edges.push_back(EdgeT());
973 first_free_edge = edges[n].next_in;
976 edges[n].tail = u; edges[n].head = v;
978 edges[n].next_out = nodes[u].first_out;
979 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
980 edges[n].next_in = nodes[v].first_in;
981 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
982 edges[n].prev_in = edges[n].prev_out = -1;
984 nodes[u].first_out = nodes[v].first_in = n;
988 //Update dynamic maps
994 /// Finds an edge between two nodes.
996 /// Finds an edge from node \c u to node \c v.
998 /// If \c prev is \ref INVALID (this is the default value), then
999 /// It finds the first edge from \c u to \c v. Otherwise it looks for
1000 /// the next edge from \c u to \c v after \c prev.
1001 /// \return The found edge or INVALID if there is no such an edge.
1002 Edge findEdge(Node u,Node v, Edge prev = INVALID)
1004 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
1005 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
1011 void eraseEdge(int n) {
1013 if(edges[n].next_in!=-1)
1014 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1015 if(edges[n].prev_in!=-1)
1016 edges[edges[n].prev_in].next_in = edges[n].next_in;
1017 else nodes[edges[n].head].first_in = edges[n].next_in;
1019 if(edges[n].next_out!=-1)
1020 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1021 if(edges[n].prev_out!=-1)
1022 edges[edges[n].prev_out].next_out = edges[n].next_out;
1023 else nodes[edges[n].tail].first_out = edges[n].next_out;
1025 edges[n].next_in = first_free_edge;
1026 first_free_edge = -1;
1028 //Update dynamic maps
1035 // void erase(Node nn) {
1038 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1039 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1042 void erase(Edge e) { eraseEdge(e.n); }
1044 ///Clear all edges. (Doesn't clear the nodes!)
1054 friend class EdgeSet;
1055 template <typename T> friend class EdgeMap;
1058 friend class NodeIt;
1060 ///\bug It should be at least protected
1064 friend int EdgeSet::id(Edge e) const;
1066 Edge(int nn) {n=nn;}
1069 Edge (Invalid) { n=-1; }
1070 bool operator==(const Edge i) const {return n==i.n;}
1071 bool operator!=(const Edge i) const {return n!=i.n;}
1072 bool operator<(const Edge i) const {return n<i.n;}
1073 ///\bug This is a workaround until somebody tells me how to
1074 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1075 int &idref() {return n;}
1076 const int &idref() const {return n;}
1079 class EdgeIt : public Edge {
1080 friend class EdgeSet;
1081 template <typename T> friend class EdgeMap;
1085 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1086 // typename NodeGraphType::Node m;
1089 m!=INVALID && G->nodes[m].first_in == -1; ++m);
1090 ///\bug AJJAJ! This is a non sense!!!!!!!
1091 this->n = m!=INVALID?-1:G->nodes[m].first_in;
1093 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1094 EdgeIt (Invalid i) : Edge(i) { }
1095 EdgeIt() : Edge() { }
1098 ///\bug UNIMPLEMENTED!!!!!
1100 EdgeIt &operator++() {
1103 ///\bug This is a workaround until somebody tells me how to
1104 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1105 int &idref() {return this->n;}
1108 class OutEdgeIt : public Edge {
1110 friend class EdgeSet;
1112 OutEdgeIt() : Edge() { }
1113 OutEdgeIt (Invalid i) : Edge(i) { }
1114 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1116 OutEdgeIt(const EdgeSet& _G,const Node v) :
1117 Edge(_G.nodes[v].first_out), G(&_G) { }
1118 OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
1121 class InEdgeIt : public Edge {
1123 friend class EdgeSet;
1125 InEdgeIt() : Edge() { }
1126 InEdgeIt (Invalid i) : Edge(i) { }
1127 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1128 InEdgeIt(const EdgeSet& _G,Node v)
1129 : Edge(_G.nodes[v].first_in), G(&_G) { }
1130 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
1135 template<typename GG>
1136 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1142 #endif //HUGO_LIST_GRAPH_H