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