The first version of new path test program. The old became old_path_test.
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 ///A list graph class.
30 ///This is a simple and fast erasable graph implementation.
32 ///It conforms to the graph interface documented under
34 ///\ref skeleton::ErasableGraphSkeleton "ErasableGraphSkeleton".
35 ///\sa skeleton::ErasableGraphSkeleton.
38 //Nodes are double linked.
39 //The free nodes are only single linked using the "next" field.
42 int first_in,first_out;
45 //Edges are double linked.
46 //The free edges are only single linked using the "next_in" field.
50 int prev_in, prev_out;
51 int next_in, next_out;
54 std::vector<NodeT> nodes;
59 std::vector<EdgeT> edges;
65 typedef ListGraph Graph;
78 /// Creating map registries.
79 CREATE_MAP_REGISTRIES;
80 /// Creating node and edge maps.
83 /// It apears in the documentation as if it were a function definition.
84 CREATE_MAPS(DefaultMap);
89 : nodes(), first_node(-1),
90 first_free_node(-1), edges(), first_free_edge(-1) {}
92 ListGraph(const ListGraph &_g)
93 : nodes(_g.nodes), first_node(_g.first_node),
94 first_free_node(_g.first_free_node), edges(_g.edges),
95 first_free_edge(_g.first_free_edge) {}
98 int nodeNum() const { return nodes.size(); }
100 int edgeNum() const { return edges.size(); }
102 ///Set the expected maximum number of edges.
104 ///With this function, it is possible to set the expected number of edges.
105 ///The use of this fasten the building of the graph and makes
106 ///it possible to avoid the superfluous memory allocation.
107 void reserveEdge(int n) { edges.reserve(n); };
113 int maxNodeId() const { return nodes.size()-1; }
118 int maxEdgeId() const { return edges.size()-1; }
120 Node tail(Edge e) const { return edges[e.n].tail; }
121 Node head(Edge e) const { return edges[e.n].head; }
123 NodeIt& first(NodeIt& v) const {
124 v=NodeIt(*this); return v; }
125 EdgeIt& first(EdgeIt& e) const {
126 e=EdgeIt(*this); return e; }
127 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
128 e=OutEdgeIt(*this,v); return e; }
129 InEdgeIt& first(InEdgeIt& e, const Node v) const {
130 e=InEdgeIt(*this,v); return e; }
134 /// The ID of a valid Node is a nonnegative integer not greater than
135 /// \ref maxNodeId(). The range of the ID's is not surely continuous
136 /// and the greatest node ID can be actually less then \ref maxNodeId().
138 /// The ID of the \ref INVALID node is -1.
139 ///\return The ID of the node \c v.
140 static int id(Node v) { return v.n; }
143 /// The ID of a valid Edge is a nonnegative integer not greater than
144 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
145 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
147 /// The ID of the \ref INVALID edge is -1.
148 ///\return The ID of the edge \c e.
149 static int id(Edge e) { return e.n; }
151 /// Adds a new node to the graph.
153 /// \warning It adds the new node to the front of the list.
154 /// (i.e. the lastly added node becomes the first.)
158 if(first_free_node==-1)
161 nodes.push_back(NodeT());
165 first_free_node = nodes[n].next;
168 nodes[n].next = first_node;
169 if(first_node != -1) nodes[first_node].prev = n;
173 nodes[n].first_in = nodes[n].first_out = -1;
177 //Update dynamic maps
183 Edge addEdge(Node u, Node v) {
186 if(first_free_edge==-1)
189 edges.push_back(EdgeT());
193 first_free_edge = edges[n].next_in;
196 edges[n].tail = u.n; edges[n].head = v.n;
198 edges[n].next_out = nodes[u.n].first_out;
199 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
200 edges[n].next_in = nodes[v.n].first_in;
201 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
202 edges[n].prev_in = edges[n].prev_out = -1;
204 nodes[u.n].first_out = nodes[v.n].first_in = n;
208 //Update dynamic maps
214 /// Finds an edge between two nodes.
216 /// Finds an edge from node \c u to node \c v.
218 /// If \c prev is \ref INVALID (this is the default value), then
219 /// It finds the first edge from \c u to \c v. Otherwise it looks for
220 /// the next edge from \c u to \c v after \c prev.
221 /// \return The found edge or INVALID if there is no such an edge.
222 Edge findEdge(Node u,Node v, Edge prev = INVALID)
224 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
225 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
231 void eraseEdge(int n) {
233 if(edges[n].next_in!=-1)
234 edges[edges[n].next_in].prev_in = edges[n].prev_in;
235 if(edges[n].prev_in!=-1)
236 edges[edges[n].prev_in].next_in = edges[n].next_in;
237 else nodes[edges[n].head].first_in = edges[n].next_in;
239 if(edges[n].next_out!=-1)
240 edges[edges[n].next_out].prev_out = edges[n].prev_out;
241 if(edges[n].prev_out!=-1)
242 edges[edges[n].prev_out].next_out = edges[n].next_out;
243 else nodes[edges[n].tail].first_out = edges[n].next_out;
245 edges[n].next_in = first_free_edge;
248 //Update dynamic maps
256 void erase(Node nn) {
260 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
261 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
263 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
264 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
265 else first_node = nodes[n].next;
267 nodes[n].next = first_free_node;
270 //Update dynamic maps
275 void erase(Edge e) { eraseEdge(e.n); }
282 first_node=first_free_node=first_free_edge=-1;
286 friend class ListGraph;
287 template <typename T> friend class NodeMap;
290 friend class OutEdgeIt;
291 friend class InEdgeIt;
292 friend class SymEdge;
296 friend int ListGraph::id(Node v);
300 Node (Invalid) { n=-1; }
301 bool operator==(const Node i) const {return n==i.n;}
302 bool operator!=(const Node i) const {return n!=i.n;}
303 bool operator<(const Node i) const {return n<i.n;}
305 // operator bool() { return n!=-1; }
308 class NodeIt : public Node {
310 friend class ListGraph;
312 NodeIt() : Node() { }
313 NodeIt(Invalid i) : Node(i) { }
314 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
315 ///\todo Undocumented conversion Node -\> NodeIt.
316 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
317 NodeIt &operator++() {
322 // operator bool() { return Node::operator bool(); }
326 friend class ListGraph;
327 template <typename T> friend class EdgeMap;
329 //template <typename T> friend class SymListGraph::SymEdgeMap;
330 //friend Edge SymListGraph::opposite(Edge) const;
336 friend int ListGraph::id(Edge e);
339 /// An Edge with id \c n.
341 /// \bug It should be
342 /// obtained by a member function of the Graph.
346 Edge (Invalid) { n=-1; }
347 bool operator==(const Edge i) const {return n==i.n;}
348 bool operator!=(const Edge i) const {return n!=i.n;}
349 bool operator<(const Edge i) const {return n<i.n;}
350 ///\bug This is a workaround until somebody tells me how to
351 ///make class \c SymListGraph::SymEdgeMap friend of Edge
352 int &idref() {return n;}
353 const int &idref() const {return n;}
355 // operator bool() { return n!=-1; }
358 class EdgeIt : public Edge {
360 friend class ListGraph;
362 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
365 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
366 n = (m==-1)?-1:_G.nodes[m].first_in;
368 EdgeIt (Invalid i) : Edge(i) { }
369 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
370 EdgeIt() : Edge() { }
371 ///\bug This is a workaround until somebody tells me how to
372 ///make class \c SymListGraph::SymEdgeMap friend of Edge
373 int &idref() {return n;}
374 EdgeIt &operator++() {
375 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
378 for(nn=G->nodes[G->edges[n].head].next;
379 nn!=-1 && G->nodes[nn].first_in == -1;
380 nn = G->nodes[nn].next) ;
381 n = (nn==-1)?-1:G->nodes[nn].first_in;
386 // operator bool() { return Edge::operator bool(); }
389 class OutEdgeIt : public Edge {
391 friend class ListGraph;
393 OutEdgeIt() : Edge() { }
394 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
395 OutEdgeIt (Invalid i) : Edge(i) { }
397 OutEdgeIt(const ListGraph& _G,const Node v)
398 : Edge(_G.nodes[v.n].first_out), G(&_G) {}
399 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
401 // operator bool() { return Edge::operator bool(); }
404 class InEdgeIt : public Edge {
406 friend class ListGraph;
408 InEdgeIt() : Edge() { }
409 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
410 InEdgeIt (Invalid i) : Edge(i) { }
411 InEdgeIt(const ListGraph& _G,Node v)
412 : Edge(_G.nodes[v.n].first_in), G(&_G) { }
413 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
415 // operator bool() { return Edge::operator bool(); }
419 ///Graph for bidirectional edges.
421 ///The purpose of this graph structure is to handle graphs
422 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
423 ///of oppositely directed edges.
424 ///There is a new edge map type called
425 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
426 ///that complements this
428 ///storing shared values for the edge pairs. The usual
429 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
433 ///The oppositely directed edge can also be obtained easily
434 ///using \ref opposite.
436 ///Here erase(Edge) deletes a pair of edges.
438 ///\todo this date structure need some reconsiderations. Maybe it
439 ///should be implemented independently from ListGraph.
441 class SymListGraph : public ListGraph
445 typedef SymListGraph Graph;
447 /// Importing maps from the base class ListGraph.
448 KEEP_MAPS(ListGraph, SymListGraph);
450 /// Creating symmetric map registry.
451 CREATE_SYM_EDGE_MAP_REGISTRY;
452 /// Creating symmetric edge map.
453 CREATE_SYM_EDGE_MAP(DefaultMap);
455 SymListGraph() : ListGraph() { }
456 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
457 ///Adds a pair of oppositely directed edges to the graph.
458 Edge addEdge(Node u, Node v)
460 Edge e = ListGraph::addEdge(u,v);
461 Edge f = ListGraph::addEdge(v,u);
462 sym_edge_maps.add(e);
463 sym_edge_maps.add(f);
468 void erase(Node n) { ListGraph::erase(n);}
469 ///The oppositely directed edge.
471 ///Returns the oppositely directed
472 ///pair of the edge \c e.
473 static Edge opposite(Edge e)
476 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
480 ///Removes a pair of oppositely directed edges to the graph.
482 Edge f = opposite(e);
483 sym_edge_maps.erase(e);
484 sym_edge_maps.erase(f);
491 ///A graph class containing only nodes.
493 ///This class implements a graph structure without edges.
494 ///The most useful application of this class is to be the node set of an
495 ///\ref EdgeSet class.
497 ///It conforms to the graph interface documented under
498 ///the description of \ref GraphSkeleton with the exception that you cannot
499 ///add (or delete) edges. The usual edge iterators are exists, but they are
500 ///always \ref INVALID.
501 ///\sa \ref GraphSkeleton
505 //Nodes are double linked.
506 //The free nodes are only single linked using the "next" field.
509 int first_in,first_out;
514 std::vector<NodeT> nodes;
517 //The first free node
522 typedef NodeSet Graph;
534 /// Creating node map registry.
535 CREATE_NODE_MAP_REGISTRY;
536 /// Creating node maps.
537 CREATE_NODE_MAP(DefaultMap);
539 /// Creating empty map structure for edges.
540 template <typename Value>
544 EdgeMap(const Graph&) {}
545 EdgeMap(const Graph&, const Value&) {}
547 EdgeMap(const EdgeMap&) {}
548 template <typename CMap> EdgeMap(const CMap&) {}
550 EdgeMap& operator=(const EdgeMap&) {}
551 template <typename CMap> EdgeMap& operator=(const CMap&) {}
553 class ConstIterator {
555 bool operator==(const ConstIterator&) {return true;}
556 bool operator!=(const ConstIterator&) {return false;}
559 typedef ConstIterator Iterator;
561 Iterator begin() { return Iterator();}
562 Iterator end() { return Iterator();}
564 ConstIterator begin() const { return ConstIterator();}
565 ConstIterator end() const { return ConstIterator();}
571 ///Default constructor
573 : nodes(), first_node(-1), first_free_node(-1) {}
575 NodeSet(const NodeSet &_g)
576 : nodes(_g.nodes), first_node(_g.first_node),
577 first_free_node(_g.first_free_node) {}
580 int nodeNum() const { return nodes.size(); }
582 int edgeNum() const { return 0; }
588 int maxNodeId() const { return nodes.size()-1; }
593 int maxEdgeId() const { return 0; }
595 Node tail(Edge e) const { return INVALID; }
596 Node head(Edge e) const { return INVALID; }
598 NodeIt& first(NodeIt& v) const {
599 v=NodeIt(*this); return v; }
600 EdgeIt& first(EdgeIt& e) const {
601 e=EdgeIt(*this); return e; }
602 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
603 e=OutEdgeIt(*this,v); return e; }
604 InEdgeIt& first(InEdgeIt& e, const Node v) const {
605 e=InEdgeIt(*this,v); return e; }
609 /// The ID of a valid Node is a nonnegative integer not greater than
610 /// \ref maxNodeId(). The range of the ID's is not surely continuous
611 /// and the greatest node ID can be actually less then \ref maxNodeId().
613 /// The ID of the \ref INVALID node is -1.
614 ///\return The ID of the node \c v.
615 int id(Node v) const { return v.n; }
618 /// The ID of a valid Edge is a nonnegative integer not greater than
619 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
620 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
622 /// The ID of the \ref INVALID edge is -1.
623 ///\return The ID of the edge \c e.
624 int id(Edge e) const { return -1; }
626 /// Adds a new node to the graph.
628 /// \warning It adds the new node to the front of the list.
629 /// (i.e. the lastly added node becomes the first.)
633 if(first_free_node==-1)
636 nodes.push_back(NodeT());
640 first_free_node = nodes[n].next;
643 nodes[n].next = first_node;
644 if(first_node != -1) nodes[first_node].prev = n;
648 nodes[n].first_in = nodes[n].first_out = -1;
652 //Update dynamic maps
658 void erase(Node nn) {
661 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
662 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
663 else first_node = nodes[n].next;
665 nodes[n].next = first_free_node;
668 //Update dynamic maps
673 Edge findEdge(Node u,Node v, Edge prev = INVALID)
681 first_node = first_free_node = -1;
685 friend class NodeSet;
686 template <typename T> friend class NodeMap;
689 friend class OutEdgeIt;
690 friend class InEdgeIt;
694 friend int NodeSet::id(Node v) const;
698 Node (Invalid i) { n=-1; }
699 bool operator==(const Node i) const {return n==i.n;}
700 bool operator!=(const Node i) const {return n!=i.n;}
701 bool operator<(const Node i) const {return n<i.n;}
704 class NodeIt : public Node {
706 friend class NodeSet;
708 NodeIt() : Node() { }
709 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
710 NodeIt(Invalid i) : Node(i) { }
711 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
712 NodeIt &operator++() {
719 //friend class NodeSet;
720 //template <typename T> friend class EdgeMap;
722 //template <typename T> friend class SymNodeSet::SymEdgeMap;
723 //friend Edge SymNodeSet::opposite(Edge) const;
725 // friend class Node;
726 // friend class NodeIt;
728 //friend int NodeSet::id(Edge e) const;
733 bool operator==(const Edge i) const {return true;}
734 bool operator!=(const Edge i) const {return false;}
735 bool operator<(const Edge i) const {return false;}
736 ///\bug This is a workaround until somebody tells me how to
737 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
738 // int idref() {return -1;}
739 // int idref() const {return -1;}
742 class EdgeIt : public Edge {
743 //friend class NodeSet;
745 EdgeIt(const NodeSet& G) : Edge() { }
746 EdgeIt(const NodeSet&, Edge) : Edge() { }
747 EdgeIt (Invalid i) : Edge(i) { }
748 EdgeIt() : Edge() { }
749 ///\bug This is a workaround until somebody tells me how to
750 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
751 // int idref() {return -1;}
752 EdgeIt operator++() { return INVALID; }
755 class OutEdgeIt : public Edge {
756 friend class NodeSet;
758 OutEdgeIt() : Edge() { }
759 OutEdgeIt(const NodeSet&, Edge) : Edge() { }
760 OutEdgeIt (Invalid i) : Edge(i) { }
761 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
762 OutEdgeIt operator++() { return INVALID; }
765 class InEdgeIt : public Edge {
766 friend class NodeSet;
768 InEdgeIt() : Edge() { }
769 InEdgeIt(const NodeSet&, Edge) : Edge() { }
770 InEdgeIt (Invalid i) : Edge(i) { }
771 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
772 InEdgeIt operator++() { return INVALID; }
779 ///Graph structure using a node set of another graph.
781 ///This structure can be used to establish another graph over a node set
782 /// of an existing one. The node iterator will go through the nodes of the
783 /// original graph, and the NodeMap's of both graphs will convert to
786 ///\warning Adding or deleting nodes from the graph is not safe if an
787 ///\ref EdgeSet is currently attached to it!
789 ///\todo Make it possible to add/delete edges from the base graph
790 ///(and from \ref EdgeSet, as well)
792 ///\param GG The type of the graph which shares its node set with this class.
793 ///Its interface must conform with \ref GraphSkeleton.
795 ///It conforms to the graph interface documented under
796 ///the description of \ref GraphSkeleton.
797 ///\sa \ref GraphSkeleton.
799 template<typename GG>
802 typedef GG NodeGraphType;
814 typedef EdgeSet Graph;
816 int id(Node v) const;
818 class Node : public NodeGraphType::Node {
819 friend class EdgeSet;
820 // template <typename T> friend class NodeMap;
823 friend class OutEdgeIt;
824 friend class InEdgeIt;
825 friend class SymEdge;
828 friend int EdgeSet::id(Node v) const;
829 // Node(int nn) {n=nn;}
831 Node() : NodeGraphType::Node() {}
832 Node (Invalid i) : NodeGraphType::Node(i) {}
833 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
836 class NodeIt : public NodeGraphType::NodeIt {
837 friend class EdgeSet;
839 NodeIt() : NodeGraphType::NodeIt() { }
840 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
841 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
842 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
843 NodeIt(const typename NodeGraphType::NodeIt &n)
844 : NodeGraphType::NodeIt(n) {}
846 operator Node() { return Node(*this);}
848 { this->NodeGraphType::NodeIt::operator++(); return *this;}
852 //Edges are double linked.
853 //The free edges are only single linked using the "next_in" field.
856 int first_in,first_out;
857 NodeT() : first_in(-1), first_out(-1) { }
863 int prev_in, prev_out;
864 int next_in, next_out;
868 typename NodeGraphType::template NodeMap<NodeT> nodes;
870 std::vector<EdgeT> edges;
871 //The first free edge
885 /// Creating edge map registry.
886 CREATE_EDGE_MAP_REGISTRY;
887 /// Creating edge maps.
888 CREATE_EDGE_MAP(DefaultMap);
890 /// Importing node maps from the NodeGraphType.
891 IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
898 ///Construates a new graph based on the nodeset of an existing one.
899 ///\param _G the base graph.
900 ///\todo It looks like a copy constructor, but it isn't.
901 EdgeSet(NodeGraphType &_G)
902 : G(_G), nodes(_G), edges(),
903 first_free_edge(-1) {}
906 ///Makes a copy of an EdgeSet.
907 ///It will be based on the same graph.
908 EdgeSet(const EdgeSet &_g)
909 : G(_g.G), nodes(_g.G), edges(_g.edges),
910 first_free_edge(_g.first_free_edge) {}
913 int nodeNum() const { return G.nodeNum(); }
915 int edgeNum() const { return edges.size(); }
921 int maxNodeId() const { return G.maxNodeId(); }
926 int maxEdgeId() const { return edges.size()-1; }
928 Node tail(Edge e) const { return edges[e.n].tail; }
929 Node head(Edge e) const { return edges[e.n].head; }
931 NodeIt& first(NodeIt& v) const {
932 v=NodeIt(*this); return v; }
933 EdgeIt& first(EdgeIt& e) const {
934 e=EdgeIt(*this); return e; }
935 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
936 e=OutEdgeIt(*this,v); return e; }
937 InEdgeIt& first(InEdgeIt& e, const Node v) const {
938 e=InEdgeIt(*this,v); return e; }
942 /// The ID of a valid Node is a nonnegative integer not greater than
943 /// \ref maxNodeId(). The range of the ID's is not surely continuous
944 /// and the greatest node ID can be actually less then \ref maxNodeId().
946 /// The ID of the \ref INVALID node is -1.
947 ///\return The ID of the node \c v.
948 int id(Node v) { return G.id(v); }
951 /// The ID of a valid Edge is a nonnegative integer not greater than
952 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
953 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
955 /// The ID of the \ref INVALID edge is -1.
956 ///\return The ID of the edge \c e.
957 int id(Edge e) const { return e.n; }
959 /// Adds a new node to the graph.
960 Node addNode() { return G.addNode(); }
962 Edge addEdge(Node u, Node v) {
965 if(first_free_edge==-1)
968 edges.push_back(EdgeT());
972 first_free_edge = edges[n].next_in;
975 edges[n].tail = u; edges[n].head = v;
977 edges[n].next_out = nodes[u].first_out;
978 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
979 edges[n].next_in = nodes[v].first_in;
980 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
981 edges[n].prev_in = edges[n].prev_out = -1;
983 nodes[u].first_out = nodes[v].first_in = n;
987 //Update dynamic maps
993 /// Finds an edge between two nodes.
995 /// Finds an edge from node \c u to node \c v.
997 /// If \c prev is \ref INVALID (this is the default value), then
998 /// It finds the first edge from \c u to \c v. Otherwise it looks for
999 /// the next edge from \c u to \c v after \c prev.
1000 /// \return The found edge or INVALID if there is no such an edge.
1001 Edge findEdge(Node u,Node v, Edge prev = INVALID)
1003 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
1004 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
1010 void eraseEdge(int n) {
1012 if(edges[n].next_in!=-1)
1013 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1014 if(edges[n].prev_in!=-1)
1015 edges[edges[n].prev_in].next_in = edges[n].next_in;
1016 else nodes[edges[n].head].first_in = edges[n].next_in;
1018 if(edges[n].next_out!=-1)
1019 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1020 if(edges[n].prev_out!=-1)
1021 edges[edges[n].prev_out].next_out = edges[n].next_out;
1022 else nodes[edges[n].tail].first_out = edges[n].next_out;
1024 edges[n].next_in = first_free_edge;
1025 first_free_edge = -1;
1027 //Update dynamic maps
1034 // void erase(Node nn) {
1037 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1038 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1041 void erase(Edge e) { eraseEdge(e.n); }
1043 ///Clear all edges. (Doesn't clear the nodes!)
1053 friend class EdgeSet;
1054 template <typename T> friend class EdgeMap;
1057 friend class NodeIt;
1059 ///\bug It should be at least protected
1063 friend int EdgeSet::id(Edge e) const;
1065 Edge(int nn) {n=nn;}
1068 Edge (Invalid) { n=-1; }
1069 bool operator==(const Edge i) const {return n==i.n;}
1070 bool operator!=(const Edge i) const {return n!=i.n;}
1071 bool operator<(const Edge i) const {return n<i.n;}
1072 ///\bug This is a workaround until somebody tells me how to
1073 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1074 int &idref() {return n;}
1075 const int &idref() const {return n;}
1078 class EdgeIt : public Edge {
1079 friend class EdgeSet;
1080 template <typename T> friend class EdgeMap;
1084 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1085 // typename NodeGraphType::Node m;
1088 m!=INVALID && G->nodes[m].first_in == -1; ++m);
1089 ///\bug AJJAJ! This is a non sense!!!!!!!
1090 this->n = m!=INVALID?-1:G->nodes[m].first_in;
1092 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1093 EdgeIt (Invalid i) : Edge(i) { }
1094 EdgeIt() : Edge() { }
1097 ///\bug UNIMPLEMENTED!!!!!
1099 EdgeIt &operator++() {
1102 ///\bug This is a workaround until somebody tells me how to
1103 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1104 int &idref() {return this->n;}
1107 class OutEdgeIt : public Edge {
1109 friend class EdgeSet;
1111 OutEdgeIt() : Edge() { }
1112 OutEdgeIt (Invalid i) : Edge(i) { }
1113 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1115 OutEdgeIt(const EdgeSet& _G,const Node v) :
1116 Edge(_G.nodes[v].first_out), G(&_G) { }
1117 OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
1120 class InEdgeIt : public Edge {
1122 friend class EdgeSet;
1124 InEdgeIt() : Edge() { }
1125 InEdgeIt (Invalid i) : Edge(i) { }
1126 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1127 InEdgeIt(const EdgeSet& _G,Node v)
1128 : Edge(_G.nodes[v].first_in), G(&_G) { }
1129 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
1134 template<typename GG>
1135 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1141 #endif //HUGO_LIST_GRAPH_H