27 |
27 |
28 ///A list graph class. |
28 ///A list graph class. |
29 |
29 |
30 ///This is a simple and fast erasable graph implementation. |
30 ///This is a simple and fast erasable graph implementation. |
31 /// |
31 /// |
32 ///It conforms to the graph interface documented under |
32 ///It conforms to the |
33 ///the description of |
33 ///\ref skeleton::ErasableGraph "ErasableGraph" concept. |
34 ///\ref skeleton::ErasableGraphSkeleton "ErasableGraphSkeleton". |
34 ///\sa skeleton::ErasableGraph. |
35 ///\sa skeleton::ErasableGraphSkeleton. |
|
36 class ListGraph { |
35 class ListGraph { |
37 |
36 |
38 //Nodes are double linked. |
37 //Nodes are double linked. |
39 //The free nodes are only single linked using the "next" field. |
38 //The free nodes are only single linked using the "next" field. |
40 struct NodeT |
39 struct NodeT |
310 friend class ListGraph; |
309 friend class ListGraph; |
311 public: |
310 public: |
312 NodeIt() : Node() { } |
311 NodeIt() : Node() { } |
313 NodeIt(Invalid i) : Node(i) { } |
312 NodeIt(Invalid i) : Node(i) { } |
314 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { } |
313 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) { } |
314 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { } |
317 NodeIt &operator++() { |
315 NodeIt &operator++() { |
318 n=G->nodes[n].next; |
316 n=G->nodes[n].next; |
319 return *this; |
317 return *this; |
320 } |
318 } |
424 ///There is a new edge map type called |
422 ///There is a new edge map type called |
425 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap" |
423 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap" |
426 ///that complements this |
424 ///that complements this |
427 ///feature by |
425 ///feature by |
428 ///storing shared values for the edge pairs. The usual |
426 ///storing shared values for the edge pairs. The usual |
429 ///\ref GraphSkeleton::EdgeMap "EdgeMap" |
427 ///\ref Graph::EdgeMap "EdgeMap" |
430 ///can be used |
428 ///can be used |
431 ///as well. |
429 ///as well. |
432 /// |
430 /// |
433 ///The oppositely directed edge can also be obtained easily |
431 ///The oppositely directed edge can also be obtained easily |
434 ///using \ref opposite. |
432 ///using \ref opposite. |
492 |
490 |
493 ///This class implements a graph structure without edges. |
491 ///This class implements a graph structure without edges. |
494 ///The most useful application of this class is to be the node set of an |
492 ///The most useful application of this class is to be the node set of an |
495 ///\ref EdgeSet class. |
493 ///\ref EdgeSet class. |
496 /// |
494 /// |
497 ///It conforms to the graph interface documented under |
495 ///It conforms to |
498 ///the description of \ref GraphSkeleton with the exception that you cannot |
496 ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept |
|
497 ///with the exception that you cannot |
499 ///add (or delete) edges. The usual edge iterators are exists, but they are |
498 ///add (or delete) edges. The usual edge iterators are exists, but they are |
500 ///always \ref INVALID. |
499 ///always \ref INVALID. |
501 ///\sa \ref GraphSkeleton |
500 ///\sa skeleton::ExtendableGraph |
502 ///\sa \ref EdgeSet |
501 ///\sa EdgeSet |
503 class NodeSet { |
502 class NodeSet { |
504 |
503 |
505 //Nodes are double linked. |
504 //Nodes are double linked. |
506 //The free nodes are only single linked using the "next" field. |
505 //The free nodes are only single linked using the "next" field. |
507 struct NodeT |
506 struct NodeT |
788 /// |
787 /// |
789 ///\todo Make it possible to add/delete edges from the base graph |
788 ///\todo Make it possible to add/delete edges from the base graph |
790 ///(and from \ref EdgeSet, as well) |
789 ///(and from \ref EdgeSet, as well) |
791 /// |
790 /// |
792 ///\param GG The type of the graph which shares its node set with this class. |
791 ///\param GG The type of the graph which shares its node set with this class. |
793 ///Its interface must conform with \ref GraphSkeleton. |
792 ///Its interface must conform to the |
|
793 ///\ref skeleton::StaticGraph "StaticGraph" concept. |
794 /// |
794 /// |
795 ///It conforms to the graph interface documented under |
795 ///It conforms to the |
796 ///the description of \ref GraphSkeleton. |
796 ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept. |
797 ///\sa \ref GraphSkeleton. |
797 ///\sa skeleton::ExtendableGraph. |
798 ///\sa \ref NodeSet. |
798 ///\sa NodeSet. |
799 template<typename GG> |
799 template<typename GG> |
800 class EdgeSet { |
800 class EdgeSet { |
801 |
801 |
802 typedef GG NodeGraphType; |
802 typedef GG NodeGraphType; |
803 |
803 |
895 |
895 |
896 ///Constructor |
896 ///Constructor |
897 |
897 |
898 ///Construates a new graph based on the nodeset of an existing one. |
898 ///Construates a new graph based on the nodeset of an existing one. |
899 ///\param _G the base graph. |
899 ///\param _G the base graph. |
900 ///\todo It looks like a copy constructor, but it isn't. |
900 explicit EdgeSet(NodeGraphType &_G) |
901 EdgeSet(NodeGraphType &_G) |
|
902 : G(_G), nodes(_G), edges(), |
901 : G(_G), nodes(_G), edges(), |
903 first_free_edge(-1) {} |
902 first_free_edge(-1) {} |
904 ///Copy constructor |
903 ///Copy constructor |
905 |
904 |
906 ///Makes a copy of an EdgeSet. |
905 ///Makes a copy of an EdgeSet. |
907 ///It will be based on the same graph. |
906 ///It will be based on the same graph. |
908 EdgeSet(const EdgeSet &_g) |
907 explicit EdgeSet(const EdgeSet &_g) |
909 : G(_g.G), nodes(_g.G), edges(_g.edges), |
908 : G(_g.G), nodes(_g.G), edges(_g.edges), |
910 first_free_edge(_g.first_free_edge) {} |
909 first_free_edge(_g.first_free_edge) {} |
911 |
910 |
912 ///Number of nodes. |
911 ///Number of nodes. |
913 int nodeNum() const { return G.nodeNum(); } |
912 int nodeNum() const { return G.nodeNum(); } |