graph_wrappers now pass the tests.
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.
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 /// Creating map registries.
78 CREATE_MAP_REGISTRIES;
79 /// Creating node and edge maps.
82 /// It apears in the documentation as if it were a function definition.
83 CREATE_MAPS(DefaultMap);
88 : nodes(), first_node(-1),
89 first_free_node(-1), edges(), first_free_edge(-1) {}
91 ListGraph(const ListGraph &_g)
92 : nodes(_g.nodes), first_node(_g.first_node),
93 first_free_node(_g.first_free_node), edges(_g.edges),
94 first_free_edge(_g.first_free_edge) {}
97 int nodeNum() const { return nodes.size(); }
99 int edgeNum() const { return edges.size(); }
101 ///Set the expected maximum number of edges.
103 ///With this function, it is possible to set the expected number of edges.
104 ///The use of this fasten the building of the graph and makes
105 ///it possible to avoid the superfluous memory allocation.
106 void reserveEdge(int n) { edges.reserve(n); };
112 int maxNodeId() const { return nodes.size()-1; }
117 int maxEdgeId() const { return edges.size()-1; }
119 Node tail(Edge e) const { return edges[e.n].tail; }
120 Node head(Edge e) const { return edges[e.n].head; }
122 NodeIt& first(NodeIt& v) const {
123 v=NodeIt(*this); return v; }
124 EdgeIt& first(EdgeIt& e) const {
125 e=EdgeIt(*this); return e; }
126 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
127 e=OutEdgeIt(*this,v); return e; }
128 InEdgeIt& first(InEdgeIt& e, const Node v) const {
129 e=InEdgeIt(*this,v); return e; }
133 /// The ID of a valid Node is a nonnegative integer not greater than
134 /// \ref maxNodeId(). The range of the ID's is not surely continuous
135 /// and the greatest node ID can be actually less then \ref maxNodeId().
137 /// The ID of the \ref INVALID node is -1.
138 ///\return The ID of the node \c v.
139 static int id(Node v) { return v.n; }
142 /// The ID of a valid Edge is a nonnegative integer not greater than
143 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
144 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
146 /// The ID of the \ref INVALID edge is -1.
147 ///\return The ID of the edge \c e.
148 static int id(Edge e) { return e.n; }
150 /// Adds a new node to the graph.
152 /// \warning It adds the new node to the front of the list.
153 /// (i.e. the lastly added node becomes the first.)
157 if(first_free_node==-1)
160 nodes.push_back(NodeT());
164 first_free_node = nodes[n].next;
167 nodes[n].next = first_node;
168 if(first_node != -1) nodes[first_node].prev = n;
172 nodes[n].first_in = nodes[n].first_out = -1;
176 //Update dynamic maps
182 Edge addEdge(Node u, Node v) {
185 if(first_free_edge==-1)
188 edges.push_back(EdgeT());
192 first_free_edge = edges[n].next_in;
195 edges[n].tail = u.n; edges[n].head = v.n;
197 edges[n].next_out = nodes[u.n].first_out;
198 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
199 edges[n].next_in = nodes[v.n].first_in;
200 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
201 edges[n].prev_in = edges[n].prev_out = -1;
203 nodes[u.n].first_out = nodes[v.n].first_in = n;
207 //Update dynamic maps
213 /// Finds an edge between two nodes.
215 /// Finds an edge from node \c u to node \c v.
217 /// If \c prev is \ref INVALID (this is the default value), then
218 /// It finds the first edge from \c u to \c v. Otherwise it looks for
219 /// the next edge from \c u to \c v after \c prev.
220 /// \return The found edge or INVALID if there is no such an edge.
221 Edge findEdge(Node u,Node v, Edge prev = INVALID)
223 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
224 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
230 void eraseEdge(int n) {
232 if(edges[n].next_in!=-1)
233 edges[edges[n].next_in].prev_in = edges[n].prev_in;
234 if(edges[n].prev_in!=-1)
235 edges[edges[n].prev_in].next_in = edges[n].next_in;
236 else nodes[edges[n].head].first_in = edges[n].next_in;
238 if(edges[n].next_out!=-1)
239 edges[edges[n].next_out].prev_out = edges[n].prev_out;
240 if(edges[n].prev_out!=-1)
241 edges[edges[n].prev_out].next_out = edges[n].next_out;
242 else nodes[edges[n].tail].first_out = edges[n].next_out;
244 edges[n].next_in = first_free_edge;
247 //Update dynamic maps
255 void erase(Node nn) {
259 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
260 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
262 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
263 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
264 else first_node = nodes[n].next;
266 nodes[n].next = first_free_node;
269 //Update dynamic maps
274 void erase(Edge e) { eraseEdge(e.n); }
281 first_node=first_free_node=first_free_edge=-1;
285 friend class ListGraph;
286 template <typename T> friend class NodeMap;
289 friend class OutEdgeIt;
290 friend class InEdgeIt;
291 friend class SymEdge;
295 friend int ListGraph::id(Node v);
299 Node (Invalid) { n=-1; }
300 bool operator==(const Node i) const {return n==i.n;}
301 bool operator!=(const Node i) const {return n!=i.n;}
302 bool operator<(const Node i) const {return n<i.n;}
304 // operator bool() { return n!=-1; }
307 class NodeIt : public Node {
309 friend class ListGraph;
311 NodeIt() : Node() { }
312 NodeIt(Invalid i) : Node(i) { }
313 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
314 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
315 NodeIt &operator++() {
320 // operator bool() { return Node::operator bool(); }
324 friend class ListGraph;
325 template <typename T> friend class EdgeMap;
327 //template <typename T> friend class SymListGraph::SymEdgeMap;
328 //friend Edge SymListGraph::opposite(Edge) const;
334 friend int ListGraph::id(Edge e);
337 /// An Edge with id \c n.
339 /// \bug It should be
340 /// obtained by a member function of the Graph.
344 Edge (Invalid) { n=-1; }
345 bool operator==(const Edge i) const {return n==i.n;}
346 bool operator!=(const Edge i) const {return n!=i.n;}
347 bool operator<(const Edge i) const {return n<i.n;}
348 ///\bug This is a workaround until somebody tells me how to
349 ///make class \c SymListGraph::SymEdgeMap friend of Edge
350 int &idref() {return n;}
351 const int &idref() const {return n;}
353 // operator bool() { return n!=-1; }
356 class EdgeIt : public Edge {
358 friend class ListGraph;
360 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
363 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
364 n = (m==-1)?-1:_G.nodes[m].first_in;
366 EdgeIt (Invalid i) : Edge(i) { }
367 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
368 EdgeIt() : Edge() { }
369 ///\bug This is a workaround until somebody tells me how to
370 ///make class \c SymListGraph::SymEdgeMap friend of Edge
371 int &idref() {return n;}
372 EdgeIt &operator++() {
373 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
376 for(nn=G->nodes[G->edges[n].head].next;
377 nn!=-1 && G->nodes[nn].first_in == -1;
378 nn = G->nodes[nn].next) ;
379 n = (nn==-1)?-1:G->nodes[nn].first_in;
384 // operator bool() { return Edge::operator bool(); }
387 class OutEdgeIt : public Edge {
389 friend class ListGraph;
391 OutEdgeIt() : Edge() { }
392 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
393 OutEdgeIt (Invalid i) : Edge(i) { }
395 OutEdgeIt(const ListGraph& _G,const Node v)
396 : Edge(_G.nodes[v.n].first_out), G(&_G) {}
397 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
399 // operator bool() { return Edge::operator bool(); }
402 class InEdgeIt : public Edge {
404 friend class ListGraph;
406 InEdgeIt() : Edge() { }
407 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
408 InEdgeIt (Invalid i) : Edge(i) { }
409 InEdgeIt(const ListGraph& _G,Node v)
410 : Edge(_G.nodes[v.n].first_in), G(&_G) { }
411 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
413 // operator bool() { return Edge::operator bool(); }
417 ///Graph for bidirectional edges.
419 ///The purpose of this graph structure is to handle graphs
420 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
421 ///of oppositely directed edges.
422 ///There is a new edge map type called
423 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
424 ///that complements this
426 ///storing shared values for the edge pairs. The usual
427 ///\ref Graph::EdgeMap "EdgeMap"
431 ///The oppositely directed edge can also be obtained easily
432 ///using \ref opposite.
434 ///Here erase(Edge) deletes a pair of edges.
436 ///\todo this date structure need some reconsiderations. Maybe it
437 ///should be implemented independently from ListGraph.
439 class SymListGraph : public ListGraph
443 typedef SymListGraph Graph;
445 /// Creating symmetric map registry.
446 CREATE_SYM_EDGE_MAP_REGISTRY;
447 /// Creating symmetric edge map.
448 CREATE_SYM_EDGE_MAP(DefaultMap);
450 SymListGraph() : ListGraph() { }
451 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
452 ///Adds a pair of oppositely directed edges to the graph.
453 Edge addEdge(Node u, Node v)
455 Edge e = ListGraph::addEdge(u,v);
456 Edge f = ListGraph::addEdge(v,u);
457 sym_edge_maps.add(e);
458 sym_edge_maps.add(f);
463 void erase(Node n) { ListGraph::erase(n);}
464 ///The oppositely directed edge.
466 ///Returns the oppositely directed
467 ///pair of the edge \c e.
468 static Edge opposite(Edge e)
471 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
475 ///Removes a pair of oppositely directed edges to the graph.
477 Edge f = opposite(e);
478 sym_edge_maps.erase(e);
479 sym_edge_maps.erase(f);
486 ///A graph class containing only nodes.
488 ///This class implements a graph structure without edges.
489 ///The most useful application of this class is to be the node set of an
490 ///\ref EdgeSet class.
493 ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
494 ///with the exception that you cannot
495 ///add (or delete) edges. The usual edge iterators are exists, but they are
496 ///always \ref INVALID.
497 ///\sa skeleton::ExtendableGraph
501 //Nodes are double linked.
502 //The free nodes are only single linked using the "next" field.
505 int first_in,first_out;
510 std::vector<NodeT> nodes;
513 //The first free node
518 typedef NodeSet Graph;
530 /// Creating node map registry.
531 CREATE_NODE_MAP_REGISTRY;
532 /// Creating node maps.
533 CREATE_NODE_MAP(DefaultMap);
535 /// Creating empty map structure for edges.
536 template <typename Value>
540 EdgeMap(const Graph&) {}
541 EdgeMap(const Graph&, const Value&) {}
543 EdgeMap(const EdgeMap&) {}
544 template <typename CMap> EdgeMap(const CMap&) {}
546 EdgeMap& operator=(const EdgeMap&) {}
547 template <typename CMap> EdgeMap& operator=(const CMap&) {}
549 class ConstIterator {
551 bool operator==(const ConstIterator&) {return true;}
552 bool operator!=(const ConstIterator&) {return false;}
555 typedef ConstIterator Iterator;
557 Iterator begin() { return Iterator();}
558 Iterator end() { return Iterator();}
560 ConstIterator begin() const { return ConstIterator();}
561 ConstIterator end() const { return ConstIterator();}
567 ///Default constructor
569 : nodes(), first_node(-1), first_free_node(-1) {}
571 NodeSet(const NodeSet &_g)
572 : nodes(_g.nodes), first_node(_g.first_node),
573 first_free_node(_g.first_free_node) {}
576 int nodeNum() const { return nodes.size(); }
578 int edgeNum() const { return 0; }
584 int maxNodeId() const { return nodes.size()-1; }
589 int maxEdgeId() const { return 0; }
591 Node tail(Edge e) const { return INVALID; }
592 Node head(Edge e) const { return INVALID; }
594 NodeIt& first(NodeIt& v) const {
595 v=NodeIt(*this); return v; }
596 EdgeIt& first(EdgeIt& e) const {
597 e=EdgeIt(*this); return e; }
598 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
599 e=OutEdgeIt(*this,v); return e; }
600 InEdgeIt& first(InEdgeIt& e, const Node v) const {
601 e=InEdgeIt(*this,v); return e; }
605 /// The ID of a valid Node is a nonnegative integer not greater than
606 /// \ref maxNodeId(). The range of the ID's is not surely continuous
607 /// and the greatest node ID can be actually less then \ref maxNodeId().
609 /// The ID of the \ref INVALID node is -1.
610 ///\return The ID of the node \c v.
611 int id(Node v) const { return v.n; }
614 /// The ID of a valid Edge is a nonnegative integer not greater than
615 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
616 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
618 /// The ID of the \ref INVALID edge is -1.
619 ///\return The ID of the edge \c e.
620 int id(Edge e) const { return -1; }
622 /// Adds a new node to the graph.
624 /// \warning It adds the new node to the front of the list.
625 /// (i.e. the lastly added node becomes the first.)
629 if(first_free_node==-1)
632 nodes.push_back(NodeT());
636 first_free_node = nodes[n].next;
639 nodes[n].next = first_node;
640 if(first_node != -1) nodes[first_node].prev = n;
644 nodes[n].first_in = nodes[n].first_out = -1;
648 //Update dynamic maps
654 void erase(Node nn) {
657 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
658 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
659 else first_node = nodes[n].next;
661 nodes[n].next = first_free_node;
664 //Update dynamic maps
669 Edge findEdge(Node u,Node v, Edge prev = INVALID)
677 first_node = first_free_node = -1;
681 friend class NodeSet;
682 template <typename T> friend class NodeMap;
685 friend class OutEdgeIt;
686 friend class InEdgeIt;
690 friend int NodeSet::id(Node v) const;
694 Node (Invalid i) { n=-1; }
695 bool operator==(const Node i) const {return n==i.n;}
696 bool operator!=(const Node i) const {return n!=i.n;}
697 bool operator<(const Node i) const {return n<i.n;}
700 class NodeIt : public Node {
702 friend class NodeSet;
704 NodeIt() : Node() { }
705 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
706 NodeIt(Invalid i) : Node(i) { }
707 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
708 NodeIt &operator++() {
715 //friend class NodeSet;
716 //template <typename T> friend class EdgeMap;
718 //template <typename T> friend class SymNodeSet::SymEdgeMap;
719 //friend Edge SymNodeSet::opposite(Edge) const;
721 // friend class Node;
722 // friend class NodeIt;
724 //friend int NodeSet::id(Edge e) const;
729 bool operator==(const Edge i) const {return true;}
730 bool operator!=(const Edge i) const {return false;}
731 bool operator<(const Edge i) const {return false;}
732 ///\bug This is a workaround until somebody tells me how to
733 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
734 // int idref() {return -1;}
735 // int idref() const {return -1;}
738 class EdgeIt : public Edge {
739 //friend class NodeSet;
741 EdgeIt(const NodeSet& G) : Edge() { }
742 EdgeIt(const NodeSet&, Edge) : Edge() { }
743 EdgeIt (Invalid i) : Edge(i) { }
744 EdgeIt() : Edge() { }
745 ///\bug This is a workaround until somebody tells me how to
746 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
747 // int idref() {return -1;}
748 EdgeIt operator++() { return INVALID; }
751 class OutEdgeIt : public Edge {
752 friend class NodeSet;
754 OutEdgeIt() : Edge() { }
755 OutEdgeIt(const NodeSet&, Edge) : Edge() { }
756 OutEdgeIt (Invalid i) : Edge(i) { }
757 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
758 OutEdgeIt operator++() { return INVALID; }
761 class InEdgeIt : public Edge {
762 friend class NodeSet;
764 InEdgeIt() : Edge() { }
765 InEdgeIt(const NodeSet&, Edge) : Edge() { }
766 InEdgeIt (Invalid i) : Edge(i) { }
767 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
768 InEdgeIt operator++() { return INVALID; }
775 ///Graph structure using a node set of another graph.
777 ///This structure can be used to establish another graph over a node set
778 /// of an existing one. The node iterator will go through the nodes of the
779 /// original graph, and the NodeMap's of both graphs will convert to
782 ///\warning Adding or deleting nodes from the graph is not safe if an
783 ///\ref EdgeSet is currently attached to it!
785 ///\todo Make it possible to add/delete edges from the base graph
786 ///(and from \ref EdgeSet, as well)
788 ///\param GG The type of the graph which shares its node set with this class.
789 ///Its interface must conform to the
790 ///\ref skeleton::StaticGraph "StaticGraph" concept.
792 ///It conforms to the
793 ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
794 ///\sa skeleton::ExtendableGraph.
796 template<typename GG>
799 typedef GG NodeGraphType;
811 typedef EdgeSet Graph;
813 int id(Node v) const;
815 class Node : public NodeGraphType::Node {
816 friend class EdgeSet;
817 // template <typename T> friend class NodeMap;
820 friend class OutEdgeIt;
821 friend class InEdgeIt;
822 friend class SymEdge;
825 friend int EdgeSet::id(Node v) const;
826 // Node(int nn) {n=nn;}
828 Node() : NodeGraphType::Node() {}
829 Node (Invalid i) : NodeGraphType::Node(i) {}
830 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
833 class NodeIt : public NodeGraphType::NodeIt {
834 friend class EdgeSet;
836 NodeIt() : NodeGraphType::NodeIt() { }
837 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
838 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
839 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
840 NodeIt(const typename NodeGraphType::NodeIt &n)
841 : NodeGraphType::NodeIt(n) {}
843 operator Node() { return Node(*this);}
845 { this->NodeGraphType::NodeIt::operator++(); return *this;}
849 //Edges are double linked.
850 //The free edges are only single linked using the "next_in" field.
853 int first_in,first_out;
854 NodeT() : first_in(-1), first_out(-1) { }
860 int prev_in, prev_out;
861 int next_in, next_out;
865 typename NodeGraphType::template NodeMap<NodeT> nodes;
867 std::vector<EdgeT> edges;
868 //The first free edge
882 /// Creates edge map registry.
883 CREATE_EDGE_MAP_REGISTRY;
884 /// Creates edge maps.
885 CREATE_EDGE_MAP(DefaultMap);
887 /// Imports node maps from the NodeGraphType.
888 IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
895 ///Construates a new graph based on the nodeset of an existing one.
896 ///\param _G the base graph.
897 explicit EdgeSet(NodeGraphType &_G)
898 : G(_G), nodes(_G), edges(),
899 first_free_edge(-1) {}
902 ///Makes a copy of an EdgeSet.
903 ///It will be based on the same graph.
904 explicit EdgeSet(const EdgeSet &_g)
905 : G(_g.G), nodes(_g.G), edges(_g.edges),
906 first_free_edge(_g.first_free_edge) {}
909 int nodeNum() const { return G.nodeNum(); }
911 int edgeNum() const { return edges.size(); }
917 int maxNodeId() const { return G.maxNodeId(); }
922 int maxEdgeId() const { return edges.size()-1; }
924 Node tail(Edge e) const { return edges[e.n].tail; }
925 Node head(Edge e) const { return edges[e.n].head; }
927 NodeIt& first(NodeIt& v) const {
928 v=NodeIt(*this); return v; }
929 EdgeIt& first(EdgeIt& e) const {
930 e=EdgeIt(*this); return e; }
931 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
932 e=OutEdgeIt(*this,v); return e; }
933 InEdgeIt& first(InEdgeIt& e, const Node v) const {
934 e=InEdgeIt(*this,v); return e; }
938 /// The ID of a valid Node is a nonnegative integer not greater than
939 /// \ref maxNodeId(). The range of the ID's is not surely continuous
940 /// and the greatest node ID can be actually less then \ref maxNodeId().
942 /// The ID of the \ref INVALID node is -1.
943 ///\return The ID of the node \c v.
944 int id(Node v) { return G.id(v); }
947 /// The ID of a valid Edge is a nonnegative integer not greater than
948 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
949 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
951 /// The ID of the \ref INVALID edge is -1.
952 ///\return The ID of the edge \c e.
953 int id(Edge e) const { return e.n; }
955 /// Adds a new node to the graph.
956 Node addNode() { return G.addNode(); }
958 Edge addEdge(Node u, Node v) {
961 if(first_free_edge==-1)
964 edges.push_back(EdgeT());
968 first_free_edge = edges[n].next_in;
971 edges[n].tail = u; edges[n].head = v;
973 edges[n].next_out = nodes[u].first_out;
974 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
975 edges[n].next_in = nodes[v].first_in;
976 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
977 edges[n].prev_in = edges[n].prev_out = -1;
979 nodes[u].first_out = nodes[v].first_in = n;
983 //Update dynamic maps
989 /// Finds an edge between two nodes.
991 /// Finds an edge from node \c u to node \c v.
993 /// If \c prev is \ref INVALID (this is the default value), then
994 /// It finds the first edge from \c u to \c v. Otherwise it looks for
995 /// the next edge from \c u to \c v after \c prev.
996 /// \return The found edge or INVALID if there is no such an edge.
997 Edge findEdge(Node u,Node v, Edge prev = INVALID)
999 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
1000 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
1006 void eraseEdge(int n) {
1008 if(edges[n].next_in!=-1)
1009 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1010 if(edges[n].prev_in!=-1)
1011 edges[edges[n].prev_in].next_in = edges[n].next_in;
1012 else nodes[edges[n].head].first_in = edges[n].next_in;
1014 if(edges[n].next_out!=-1)
1015 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1016 if(edges[n].prev_out!=-1)
1017 edges[edges[n].prev_out].next_out = edges[n].next_out;
1018 else nodes[edges[n].tail].first_out = edges[n].next_out;
1020 edges[n].next_in = first_free_edge;
1021 first_free_edge = -1;
1023 //Update dynamic maps
1030 // void erase(Node nn) {
1033 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1034 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1037 void erase(Edge e) { eraseEdge(e.n); }
1039 ///Clear all edges. (Doesn't clear the nodes!)
1049 friend class EdgeSet;
1050 template <typename T> friend class EdgeMap;
1053 friend class NodeIt;
1055 ///\bug It should be at least protected
1059 friend int EdgeSet::id(Edge e) const;
1061 Edge(int nn) {n=nn;}
1064 Edge (Invalid) { n=-1; }
1065 bool operator==(const Edge i) const {return n==i.n;}
1066 bool operator!=(const Edge i) const {return n!=i.n;}
1067 bool operator<(const Edge i) const {return n<i.n;}
1068 ///\bug This is a workaround until somebody tells me how to
1069 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1070 int &idref() {return n;}
1071 const int &idref() const {return n;}
1074 class EdgeIt : public Edge {
1075 friend class EdgeSet;
1076 template <typename T> friend class EdgeMap;
1080 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1081 // typename NodeGraphType::Node m;
1084 m!=INVALID && G->nodes[m].first_in == -1; ++m);
1085 ///\bug AJJAJ! This is a non sense!!!!!!!
1086 this->n = m!=INVALID?-1:G->nodes[m].first_in;
1088 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1089 EdgeIt (Invalid i) : Edge(i) { }
1090 EdgeIt() : Edge() { }
1093 ///\bug UNIMPLEMENTED!!!!!
1095 EdgeIt &operator++() {
1098 ///\bug This is a workaround until somebody tells me how to
1099 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1100 int &idref() {return this->n;}
1103 class OutEdgeIt : public Edge {
1105 friend class EdgeSet;
1107 OutEdgeIt() : Edge() { }
1108 OutEdgeIt (Invalid i) : Edge(i) { }
1109 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1111 OutEdgeIt(const EdgeSet& _G,const Node v) :
1112 Edge(_G.nodes[v].first_out), G(&_G) { }
1113 OutEdgeIt &operator++() {
1114 Edge::n = G->edges[Edge::n].next_out;
1119 class InEdgeIt : public Edge {
1121 friend class EdgeSet;
1123 InEdgeIt() : Edge() { }
1124 InEdgeIt (Invalid i) : Edge(i) { }
1125 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1126 InEdgeIt(const EdgeSet& _G,Node v)
1127 : Edge(_G.nodes[v].first_in), G(&_G) { }
1128 InEdgeIt &operator++() {
1129 Edge::n = G->edges[Edge::n].next_in;
1136 template<typename GG>
1137 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1143 #endif //HUGO_LIST_GRAPH_H