1 | /*! |
---|
2 | |
---|
3 | \page graphs How to use graphs |
---|
4 | |
---|
5 | The following program demonstrates the basic features of HugoLib's graph |
---|
6 | structures. |
---|
7 | |
---|
8 | \code |
---|
9 | #include <iostream> |
---|
10 | #include <hugo/list_graph.h> |
---|
11 | |
---|
12 | using namespace hugo; |
---|
13 | |
---|
14 | int main() |
---|
15 | { |
---|
16 | typedef ListGraph Graph; |
---|
17 | \endcode |
---|
18 | |
---|
19 | ListGraph is one of HugoLib's graph classes. It is based on linked lists, |
---|
20 | therefore iterating throuh its edges and nodes is fast. |
---|
21 | |
---|
22 | \code |
---|
23 | typedef Graph::Edge Edge; |
---|
24 | typedef Graph::InEdgeIt InEdgeIt; |
---|
25 | typedef Graph::OutEdgeIt OutEdgeIt; |
---|
26 | typedef Graph::EdgeIt EdgeIt; |
---|
27 | typedef Graph::Node Node; |
---|
28 | typedef Graph::NodeIt NodeIt; |
---|
29 | |
---|
30 | Graph g; |
---|
31 | |
---|
32 | for (int i = 0; i < 3; i++) |
---|
33 | g.addNode(); |
---|
34 | |
---|
35 | for (NodeIt i(g); g.valid(i); g.next(i)) |
---|
36 | for (NodeIt j(g); g.valid(j); g.next(j)) |
---|
37 | if (i != j) g.addEdge(i, j); |
---|
38 | \endcode |
---|
39 | |
---|
40 | After some convenience typedefs we create a graph and add three nodes to it. |
---|
41 | Then we add edges to it to form a full graph. |
---|
42 | |
---|
43 | \code |
---|
44 | std::cout << "Nodes:"; |
---|
45 | for (NodeIt i(g); g.valid(i); g.next(i)) |
---|
46 | std::cout << " " << g.id(i); |
---|
47 | std::cout << std::endl; |
---|
48 | \endcode |
---|
49 | |
---|
50 | Here we iterate through all nodes of the graph. We use a constructor of the |
---|
51 | node iterator to initialize it to the first node. The next member function is |
---|
52 | used to step to the next node, and valid is used to check if we have passed the |
---|
53 | last one. |
---|
54 | |
---|
55 | \code |
---|
56 | std::cout << "Nodes:"; |
---|
57 | NodeIt n; |
---|
58 | for (g.first(n); n != INVALID; g.next(n)) |
---|
59 | std::cout << " " << g.id(n); |
---|
60 | std::cout << std::endl; |
---|
61 | \endcode |
---|
62 | |
---|
63 | Here you can see an alternative way to iterate through all nodes. Here we use a |
---|
64 | member function of the graph to initialize the node iterator to the first node |
---|
65 | of the graph. Using next on the iterator pointing to the last node invalidates |
---|
66 | the iterator i.e. sets its value to INVALID. Checking for this value is |
---|
67 | equivalent to using the valid member function. |
---|
68 | |
---|
69 | Both of the previous code fragments print out the same: |
---|
70 | |
---|
71 | \code |
---|
72 | Nodes: 2 1 0 |
---|
73 | \endcode |
---|
74 | |
---|
75 | \code |
---|
76 | std::cout << "Edges:"; |
---|
77 | for (EdgeIt i(g); g.valid(i); g.next(i)) |
---|
78 | std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; |
---|
79 | std::cout << std::endl; |
---|
80 | \endcode |
---|
81 | |
---|
82 | \code |
---|
83 | Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0) |
---|
84 | \endcode |
---|
85 | |
---|
86 | We can also iterate through all edges of the graph very similarly. The head and |
---|
87 | tail member functions can be used to access the endpoints of an edge. |
---|
88 | |
---|
89 | \code |
---|
90 | NodeIt first_node(g); |
---|
91 | |
---|
92 | std::cout << "Out-edges of node " << g.id(first_node) << ":"; |
---|
93 | for (OutEdgeIt i(g, first_node); g.valid(i); g.next(i)) |
---|
94 | std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; |
---|
95 | std::cout << std::endl; |
---|
96 | |
---|
97 | std::cout << "In-edges of node " << g.id(first_node) << ":"; |
---|
98 | for (InEdgeIt i(g, first_node); g.valid(i); g.next(i)) |
---|
99 | std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; |
---|
100 | std::cout << std::endl; |
---|
101 | \endcode |
---|
102 | |
---|
103 | \code |
---|
104 | Out-edges of node 2: (2,0) (2,1) |
---|
105 | In-edges of node 2: (0,2) (1,2) |
---|
106 | \endcode |
---|
107 | |
---|
108 | We can also iterate through the in and out-edges of a node. In the above |
---|
109 | example we print out the in and out-edges of the first node of the graph. |
---|
110 | |
---|
111 | \code |
---|
112 | Graph::EdgeMap<int> m(g); |
---|
113 | |
---|
114 | for (EdgeIt e(g); g.valid(e); g.next(e)) |
---|
115 | m.set(e, 10 - g.id(e)); |
---|
116 | |
---|
117 | std::cout << "Id Edge Value" << std::endl; |
---|
118 | for (EdgeIt e(g); g.valid(e); g.next(e)) |
---|
119 | std::cout << g.id(e) << " (" << g.id(g.tail(e)) << "," << g.id(g.head(e)) |
---|
120 | << ") " << m[e] << std::endl; |
---|
121 | \endcode |
---|
122 | |
---|
123 | \code |
---|
124 | Id Edge Value |
---|
125 | 4 (0,2) 6 |
---|
126 | 2 (1,2) 8 |
---|
127 | 5 (0,1) 5 |
---|
128 | 0 (2,1) 10 |
---|
129 | 3 (1,0) 7 |
---|
130 | 1 (2,0) 9 |
---|
131 | \endcode |
---|
132 | |
---|
133 | In generic graph optimization programming graphs are not containers rather |
---|
134 | incidence structures which are iterable in many ways. HugoLib introduces |
---|
135 | concepts that allow us to attach containers to graphs. These containers are |
---|
136 | called maps. |
---|
137 | |
---|
138 | In the example above we create an EdgeMap which assigns an int value to all |
---|
139 | edges of the graph. We use the set member function of the map to write values |
---|
140 | into the map and the operator[] to retrieve them. |
---|
141 | |
---|
142 | Here we used the maps provided by the ListGraph class, but you can also write |
---|
143 | your own maps. You can read more about using maps \ref maps "here". |
---|
144 | |
---|
145 | */ |
---|