1 /*! |
1 /*! |
2 |
2 |
3 \page graphs How to use graphs |
3 \page graphs How to use graphs |
|
4 |
|
5 The primary data structures of HugoLib are the graph classes. They all |
|
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 |
|
8 as in incoming and outgoing edges of a given node. |
|
9 |
|
10 |
|
11 Each graph should meet the \ref ConstGraph concept. This concept does |
|
12 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 |
|
14 these graphs. |
|
15 |
|
16 The graphs meeting the \ref ExtendableGraph concept allow node and |
|
17 edge addition. You can also "clear" (i.e. erase all edges and nodes) |
|
18 such a graph. |
|
19 |
|
20 In case of graphs meeting the full feature \ref ErasableGraph concept |
|
21 you can also erase individual edges and node in arbitrary order. |
|
22 |
|
23 The implemented graph structures are the following. |
|
24 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets |
|
25 the ErasableGraph concept and it also have some convenience features. |
|
26 \li \ref hugo::SmartGraph "SmartGraph" is a more memory |
|
27 efficient version of \ref hugo::ListGraph "ListGraph". The |
|
28 price of it is that it only meets the \ref ExtendableGraph concept, |
|
29 so you cannot delete individual edges or nodes. |
|
30 \li \ref hugo::SymListGraph "SymListGraph" and |
|
31 \ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to |
|
32 \ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph". |
|
33 The difference is that whenever you add a |
|
34 new edge to the graph, it actually adds a pair of oppositely directed edges. |
|
35 They are linked together so it is possible to access the counterpart of an |
|
36 edge. An even more important feature is that using these classes you can also |
|
37 attach data to the edges in such a way that the stored data |
|
38 are shared by the edge pairs. |
|
39 \li \ref hugo::FullGraph "FullGraph" |
|
40 implements a full graph. It is a \ref ConstGraph, so you cannot |
|
41 change the number of nodes once it is constructed. It is extremely memory |
|
42 efficient: it uses constant amount of memory independently from the number of |
|
43 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and |
|
44 \ref maps "EdgeMap"'s will depend on the number of nodes. |
|
45 |
|
46 \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". |
|
48 \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 |
|
50 is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph. |
|
51 |
|
52 \todo Don't we need SmartNodeSet and SmartEdgeSet? |
|
53 \todo Some cross-refs are wrong. |
|
54 |
|
55 |
|
56 The graph structures itself can not store data attached |
|
57 to the edges and nodes. However they all provide |
|
58 \ref maps "map classes" |
|
59 to dynamically attach data the to graph components. |
|
60 |
|
61 |
|
62 |
4 |
63 |
5 The following program demonstrates the basic features of HugoLib's graph |
64 The following program demonstrates the basic features of HugoLib's graph |
6 structures. |
65 structures. |
7 |
66 |
8 \code |
67 \code |