COIN-OR::LEMON - Graph Library

source: lemon-tutorial/undir_graphs.dox @ 47:c09d90659170

Last change on this file since 47:c09d90659170 was 47:c09d90659170, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Write a subsection about Kruskal algorithm

File size: 6.5 KB
Line 
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
19namespace lemon {
20/**
21[PAGE]sec_undir_graphs[PAGE] Undirected Graphs
22
23In \ref sec_basics, we have introduced a general digraph structure,
24\ref ListDigraph. LEMON also contains undirected graph classes,
25for example, \ref ListGraph is the undirected versions of \ref ListDigraph.
26
27[SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs
28
29The \ref concepts::Graph "undirected graphs" also fulfill the concept of
30\ref concepts::Digraph "directed graphs", in such a way that each
31undirected \e edge of a graph can also be regarded as two oppositely
32directed \e arcs. As a result, all directed graph algorithms automatically
33run on undirected graphs, as well.
34
35Undirected graphs provide an \c Edge type for the \e undirected \e edges
36and an \c Arc type for the \e directed \e arcs. The \c Arc type is
37convertible to \c Edge (or inherited from it), thus the corresponding
38edge can always be obtained from an arc.
39Of course, only nodes and edges can be added to or removed from an undirected
40graph and the corresponding arcs are added or removed automatically
41(there are twice as many arcs as edges)
42
43For 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
56Each edge has an inherent orientation, thus it can be defined whether
57an arc is forward or backward oriented in an undirected graph with respect
58to this default oriantation of the represented edge.
59The 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
63For 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
72The 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
86Similarly 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.
90However, 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
93certain node.
94
95For 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
107In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
108and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
109but with opposite direction. They are convertible to both \c Arc and
110\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
111on these edges, but it is not convertible to \c Arc, only to \c Edge.
112
113Apart from the node and arc maps, an undirected graph also defines
114a member class for constructing edge maps. These maps can be
115used in conjunction with both edges and arcs.
116
117For 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
134If you would like to design an electric network minimizing the total length
135of wires, then you might be looking for a minimum spanning tree in an
136undirected graph.
137This can be found using the \ref kruskal() "Kruskal" algorithm.
138
139Let us suppose that the network is stored in a \ref ListGraph object \c g
140with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
141a vector \c tree_vector for stroing the tree that is found by the algorithm.
142After that, we could call the \ref kruskal() function. It gives back the weight
143of the minimum spanning tree and \c tree_map or \c tree_vector
144will contain the found spanning tree.
145
146If you want to store the arcs in a \c bool valued edge map, then you can use
147the 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
163If you would like to store the edges in a standard container, you can
164do 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}
Note: See TracBrowser for help on using the repository browser.