6 provide a node list - edge list interface, i.e. they have |
6 provide a node list - edge list interface, i.e. they have |
7 functionalities to list the nodes and the edges of the graph as well |
7 functionalities to list the nodes and the edges of the graph as well |
8 as in incoming and outgoing edges of a given node. |
8 as in incoming and outgoing edges of a given node. |
9 |
9 |
10 |
10 |
11 Each graph should meet the \ref ConstGraph concept. This concept does |
11 Each graph should meet the |
|
12 \ref hugo::skeleton::StaticGraphSkeleton "StaticGraph" concept. |
|
13 This concept does not |
12 makes it possible to change the graph (i.e. it is not possible to add |
14 makes it possible to change the graph (i.e. it is not possible to add |
13 or delete edges or nodes). Most of the graph algorithms will run on |
15 or delete edges or nodes). Most of the graph algorithms will run on |
14 these graphs. |
16 these graphs. |
15 |
17 |
16 The graphs meeting the \ref ExtendableGraph concept allow node and |
18 The graphs meeting the |
|
19 \ref hugo::skeleton::ExtendableGraphSkeleton "ExtendableGraph" |
|
20 concept allow node and |
17 edge addition. You can also "clear" (i.e. erase all edges and nodes) |
21 edge addition. You can also "clear" (i.e. erase all edges and nodes) |
18 such a graph. |
22 such a graph. |
19 |
23 |
20 In case of graphs meeting the full feature \ref ErasableGraph concept |
24 In case of graphs meeting the full feature |
|
25 \ref hugo::skeleton::ErasableGraphSkeleton "ErasableGraph" |
|
26 concept |
21 you can also erase individual edges and node in arbitrary order. |
27 you can also erase individual edges and node in arbitrary order. |
22 |
28 |
23 The implemented graph structures are the following. |
29 The implemented graph structures are the following. |
24 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets |
30 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets |
25 the ErasableGraph concept and it also have some convenience features. |
31 the hugo::skeleton::ErasableGraphSkeleton "ErasableGraph" concept |
|
32 and it also have some convenience features. |
26 \li \ref hugo::SmartGraph "SmartGraph" is a more memory |
33 \li \ref hugo::SmartGraph "SmartGraph" is a more memory |
27 efficient version of \ref hugo::ListGraph "ListGraph". The |
34 efficient version of \ref hugo::ListGraph "ListGraph". The |
28 price of it is that it only meets the \ref ExtendableGraph concept, |
35 price of it is that it only meets the |
|
36 \ref hugo::skeleton::ExtendableGraphSkeleton "ExtendableGraph" concept, |
29 so you cannot delete individual edges or nodes. |
37 so you cannot delete individual edges or nodes. |
30 \li \ref hugo::SymListGraph "SymListGraph" and |
38 \li \ref hugo::SymListGraph "SymListGraph" and |
31 \ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to |
39 \ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to |
32 \ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph". |
40 \ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph". |
33 The difference is that whenever you add a |
41 The difference is that whenever you add a |
44 \ref maps "EdgeMap"'s will depend on the number of nodes. |
52 \ref maps "EdgeMap"'s will depend on the number of nodes. |
45 |
53 |
46 \li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class |
54 \li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class |
47 can be used as a base class of \ref hugo::EdgeSet "EdgeSet". |
55 can be used as a base class of \ref hugo::EdgeSet "EdgeSet". |
48 \li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on |
56 \li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on |
49 the edge set of another graph. The base graph can be an arbitrary graph and it |
57 the node set of another graph. The base graph can be an arbitrary graph and it |
50 is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph. |
58 is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph. |
51 |
59 |
52 \todo Don't we need SmartNodeSet and SmartEdgeSet? |
60 \todo Don't we need SmartNodeSet and SmartEdgeSet? |
53 \todo Some cross-refs are wrong. |
61 \todo Some cross-refs are wrong. |
54 |
62 |
55 \bug This file must be updated accordig to the new stile iterators. |
63 \bug This file must be updated accordig to the new style iterators. |
56 |
64 |
57 The graph structures itself can not store data attached |
65 The graph structures itself can not store data attached |
58 to the edges and nodes. However they all provide |
66 to the edges and nodes. However they all provide |
59 \ref maps "map classes" |
67 \ref maps "map classes" |
60 to dynamically attach data the to graph components. |
68 to dynamically attach data the to graph components. |
61 |
|
62 |
|
63 |
|
64 |
69 |
65 The following program demonstrates the basic features of HugoLib's graph |
70 The following program demonstrates the basic features of HugoLib's graph |
66 structures. |
71 structures. |
67 |
72 |
68 \code |
73 \code |