1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2010 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
9 | * Permission to use, modify and distribute this software is granted |
---|
10 | * provided that this copyright notice appears in all copies. For |
---|
11 | * precise terms see the accompanying LICENSE file. |
---|
12 | * |
---|
13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
14 | * express or implied, and with no claim as to its suitability for any |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | |
---|
19 | namespace lemon { |
---|
20 | /** |
---|
21 | [PAGE]sec_undir_graphs[PAGE] Undirected Graphs |
---|
22 | |
---|
23 | In \ref sec_basics, we have introduced a general digraph structure, |
---|
24 | \ref ListDigraph. LEMON also contains undirected graph classes, |
---|
25 | for example, \ref ListGraph is the undirected versions of \ref ListDigraph. |
---|
26 | |
---|
27 | [SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs |
---|
28 | |
---|
29 | The \ref concepts::Graph "undirected graphs" also fulfill the concept of |
---|
30 | \ref concepts::Digraph "directed graphs", in such a way that each |
---|
31 | undirected \e edge of a graph can also be regarded as two oppositely |
---|
32 | directed \e arcs. As a result, all directed graph algorithms automatically |
---|
33 | run on undirected graphs, as well. |
---|
34 | |
---|
35 | Undirected graphs provide an \c Edge type for the \e undirected \e edges |
---|
36 | and an \c Arc type for the \e directed \e arcs. The \c Arc type is |
---|
37 | convertible to \c Edge (or inherited from it), thus the corresponding |
---|
38 | edge can always be obtained from an arc. |
---|
39 | Of course, only nodes and edges can be added to or removed from an undirected |
---|
40 | graph and the corresponding arcs are added or removed automatically |
---|
41 | (there are twice as many arcs as edges) |
---|
42 | |
---|
43 | For example, |
---|
44 | \code |
---|
45 | ListGraph g; |
---|
46 | |
---|
47 | ListGraph::Node a = g.addNode(); |
---|
48 | ListGraph::Node b = g.addNode(); |
---|
49 | ListGraph::Node c = g.addNode(); |
---|
50 | |
---|
51 | ListGraph::Edge e = g.addEdge(a,b); |
---|
52 | g.addEdge(b,c); |
---|
53 | g.addEdge(c,a); |
---|
54 | \endcode |
---|
55 | |
---|
56 | Each edge has an inherent orientation, thus it can be defined whether |
---|
57 | an arc is forward or backward oriented in an undirected graph with respect |
---|
58 | to this default oriantation of the represented edge. |
---|
59 | The direction of an arc can be obtained and set using the functions |
---|
60 | \ref concepts::Graph::direction() "direction()" and |
---|
61 | \ref concepts::Graph::direct() "direct()", respectively. |
---|
62 | |
---|
63 | For example, |
---|
64 | \code |
---|
65 | ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc |
---|
66 | ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc |
---|
67 | |
---|
68 | if (a2 == g.oppositeArc(a1)) |
---|
69 | std::cout << "a2 is the opposite of a1" << std::endl; |
---|
70 | \endcode |
---|
71 | |
---|
72 | The end nodes of an edge can be obtained using the functions |
---|
73 | \ref concepts::Graph::source() "u()" and |
---|
74 | \ref concepts::Graph::target() "v()", while the |
---|
75 | \ref concepts::Graph::source() "source()" and |
---|
76 | \ref concepts::Graph::target() "target()" can be used for arcs. |
---|
77 | |
---|
78 | \code |
---|
79 | std::cout << "Edge " << g.id(e) << " connects node " |
---|
80 | << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl; |
---|
81 | |
---|
82 | std::cout << "Arc " << g.id(a2) << " goes from node " |
---|
83 | << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl; |
---|
84 | \endcode |
---|
85 | |
---|
86 | Similarly to the digraphs, the undirected graphs also provide iterators |
---|
87 | \ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt", |
---|
88 | \ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt |
---|
89 | "InArcIt", which can be used the same way. |
---|
90 | However, they also have iterator classes for edges. |
---|
91 | \ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and |
---|
92 | \ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a |
---|
93 | certain node. |
---|
94 | |
---|
95 | For example, the degree of each node can be printed out like this: |
---|
96 | |
---|
97 | \code |
---|
98 | for (ListGraph::NodeIt n(g); n != INVALID; ++n) { |
---|
99 | int cnt = 0; |
---|
100 | for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) { |
---|
101 | cnt++; |
---|
102 | } |
---|
103 | std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl; |
---|
104 | } |
---|
105 | \endcode |
---|
106 | |
---|
107 | In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt" |
---|
108 | and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges |
---|
109 | but with opposite direction. They are convertible to both \c Arc and |
---|
110 | \c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates |
---|
111 | on these edges, but it is not convertible to \c Arc, only to \c Edge. |
---|
112 | |
---|
113 | Apart from the node and arc maps, an undirected graph also defines |
---|
114 | a member class for constructing edge maps. These maps can be |
---|
115 | used in conjunction with both edges and arcs. |
---|
116 | |
---|
117 | For example, |
---|
118 | \code |
---|
119 | ListGraph::EdgeMap cost(g); |
---|
120 | cost[e] = 10; |
---|
121 | std::cout << cost[e] << std::endl; |
---|
122 | std::cout << cost[a1] << ", " << cost[a2] << std::endl; |
---|
123 | |
---|
124 | ListGraph::ArcMap arc_cost(g); |
---|
125 | arc_cost[a1] = cost[a1]; |
---|
126 | arc_cost[a2] = 2 * cost[a2]; |
---|
127 | // std::cout << arc_cost[e] << std::endl; // this is not valid |
---|
128 | std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl; |
---|
129 | \endcode |
---|
130 | |
---|
131 | |
---|
132 | [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms |
---|
133 | |
---|
134 | If you would like to design an electric network minimizing the total length |
---|
135 | of wires, then you might be looking for a minimum spanning tree in an |
---|
136 | undirected graph. |
---|
137 | This can be found using the \ref kruskal() "Kruskal" algorithm. |
---|
138 | |
---|
139 | Let us suppose that the network is stored in a \ref ListGraph object \c g |
---|
140 | with a cost map \c cost. We create a \c bool valued edge map \c tree_map or |
---|
141 | a vector \c tree_vector for stroing the tree that is found by the algorithm. |
---|
142 | After that, we could call the \ref kruskal() function. It gives back the weight |
---|
143 | of the minimum spanning tree and \c tree_map or \c tree_vector |
---|
144 | will contain the found spanning tree. |
---|
145 | |
---|
146 | If you want to store the arcs in a \c bool valued edge map, then you can use |
---|
147 | the function as follows. |
---|
148 | |
---|
149 | \code |
---|
150 | // Kruskal algorithm with edge map |
---|
151 | ListGraph::EdgeMap<bool> tree_map(g); |
---|
152 | std::cout << "The weight of the minimum spanning tree is " |
---|
153 | << kruskal(g, cost_map, tree_map) << std::endl; |
---|
154 | |
---|
155 | // Print the results |
---|
156 | std::cout << "Edges of the tree: " << std::endl; |
---|
157 | for (ListGraph::EdgeIt e(g); e != INVALID; ++e) { |
---|
158 | if (!tree_map[e]) continue; |
---|
159 | std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; |
---|
160 | } |
---|
161 | \endcode |
---|
162 | |
---|
163 | If you would like to store the edges in a standard container, you can |
---|
164 | do it like this. |
---|
165 | |
---|
166 | \code |
---|
167 | // Kruskal algorithm with edge vector |
---|
168 | std::vector<ListGraph::Edge> tree_vector; |
---|
169 | std::cout << "The weight of the minimum spanning tree is " |
---|
170 | << kruskal(g, cost_map, tree_vector) << std::endl; |
---|
171 | |
---|
172 | // Print the results |
---|
173 | std::cout << "Edges of the tree: " << std::endl; |
---|
174 | for (unsigned i = 0; i != tree_vector.size(); ++i) { |
---|
175 | Edge e = tree_vector[i]; |
---|
176 | std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; |
---|
177 | } |
---|
178 | \endcode |
---|
179 | |
---|
180 | \todo \ref matching "matching algorithms". |
---|
181 | |
---|
182 | [TRAILER] |
---|
183 | */ |
---|
184 | } |
---|