1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 [PAGE]sec_undir_graphs[PAGE] Undirected Graphs
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.
27 [SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs
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.
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)
47 ListGraph::Node a = g.addNode();
48 ListGraph::Node b = g.addNode();
49 ListGraph::Node c = g.addNode();
51 ListGraph::Edge e = g.addEdge(a,b);
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 orientation 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.
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
68 if (a2 == g.oppositeArc(a1))
69 std::cout << "a2 is the opposite of a1" << std::endl;
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.
79 std::cout << "Edge " << g.id(e) << " connects node "
80 << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
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;
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
95 For example, the degree of each node can be printed out like this:
98 for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
100 for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
103 std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;
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.
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.
119 ListGraph::EdgeMap cost(g);
121 std::cout << cost[e] << std::endl;
122 std::cout << cost[a1] << ", " << cost[a2] << std::endl;
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;
132 [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorithms
134 \todo This subsection is under construction.
136 If you would like to design an electric network minimizing the total length
137 of wires, then you might be looking for a minimum spanning tree in an
139 This can be found using the \ref kruskal() "Kruskal" algorithm.
141 Let us suppose that the network is stored in a \ref ListGraph object \c g
142 with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
143 a vector \c tree_vector for storing the tree that is found by the algorithm.
144 After that, we could call the \ref kruskal() function. It gives back the weight
145 of the minimum spanning tree and \c tree_map or \c tree_vector
146 will contain the found spanning tree.
148 If you want to store the arcs in a \c bool valued edge map, then you can use
149 the function as follows.
152 // Kruskal algorithm with edge map
153 ListGraph::EdgeMap<bool> tree_map(g);
154 std::cout << "The weight of the minimum spanning tree is "
155 << kruskal(g, cost_map, tree_map) << std::endl;
158 std::cout << "Edges of the tree: " << std::endl;
159 for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {
160 if (!tree_map[e]) continue;
161 std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
165 If you would like to store the edges in a standard container, you can
169 // Kruskal algorithm with edge vector
170 std::vector<ListGraph::Edge> tree_vector;
171 std::cout << "The weight of the minimum spanning tree is "
172 << kruskal(g, cost_map, std::back_inserter(tree_vector))
176 std::cout << "Edges of the tree: " << std::endl;
177 for (unsigned i = 0; i != tree_vector.size(); ++i) {
178 Edge e = tree_vector[i];
179 std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
183 \todo \ref matching "matching algorithms".