]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <html> |
2 | <!-- | |
3 | Copyright (C) 2012, Michele Caini. | |
4 | Distributed under the Boost Software License, Version 1.0. | |
5 | (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | Two Graphs Common Spanning Trees Algorithm | |
9 | Based on academic article of Mint, Read and Tarjan | |
10 | Efficient Algorithm for Common Spanning Tree Problem | |
11 | Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346–347 | |
12 | --> | |
13 | <head> | |
14 | <title>Boost Graph Library: Two-Graphs Common Spanning Trees</title> | |
15 | <body bgcolo="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000"> | |
16 | <img src="../../../boost.png" alt="C++ Boost" width="277" height="86"> | |
17 | ||
18 | <br clear> | |
19 | ||
20 | <h1><tt><a name="sec:two-graphs-common-spanning-trees">Two-Graphs Common Spanning Trees (MRT Algorithm)</a></tt></h1> | |
21 | ||
22 | <p> | |
23 | The <b>MRT</b> algorithm, based on an academic article of <b>Mint</b>, <b>Read</b> and | |
24 | <b>Tarjan</b>, is an efficient algorithm for the common spanning tree problem.<br/> | |
25 | This kind of algorithm is widely used in electronics, being the basis of the | |
26 | analysis of electrical circuits. Another area of interest may be that of the | |
27 | networking. | |
28 | </p> | |
29 | ||
30 | <p> | |
31 | The proposed algorithm receives several arguments and works with callbacks.<br/> | |
32 | The prototypes are: | |
33 | </p> | |
34 | ||
35 | <p> | |
36 | <i>// Ordered Edges List</i> | |
37 | <pre> | |
38 | template < typename Graph, typename Order, typename Func, typename Seq > | |
39 | void two_graphs_common_spanning_trees | |
40 | ( | |
41 | const Graph& iG, | |
42 | Order iG_map, | |
43 | const Graph& vG, | |
44 | Order vG_map, | |
45 | Func func, | |
46 | Seq inL | |
47 | ) | |
48 | </pre> | |
49 | ||
50 | <i>// Unordered Edges List</i> | |
51 | <pre> | |
52 | template < typename Graph, typename Func, typename Seq > | |
53 | void two_graphs_common_spanning_trees | |
54 | ( | |
55 | const Graph& iG, | |
56 | const Graph& vG, | |
57 | Func func, | |
58 | Seq inL | |
59 | ) | |
60 | </pre> | |
61 | </p> | |
62 | ||
63 | <p> | |
64 | The problem of common spanning tree is easily described.<br/> | |
65 | Imagine we have two graphs that are represented as lists of edges. A common | |
66 | spanning tree is a set of indices that identifies a spanning tree for both | |
67 | the first and for the second of the two graphs. Despite it is easily accomplished | |
68 | with edge list representation for graphs, it is intuitively difficult to achieve | |
69 | with adjacency list representation. This is due to the fact that it is necessary | |
70 | to represent an edge with an absolute index. | |
71 | </p> | |
72 | <p> | |
73 | Note that the set of common spanning trees of the two graphs is a subset of | |
74 | the set of spanning trees of the first graph, as well as those of the second | |
75 | graph. | |
76 | </p> | |
77 | ||
78 | <h3>Where Defined</h3> | |
79 | ||
80 | <p> | |
81 | <a href="../../../boost/graph/two_graphs_common_spanning_trees.hpp"><TT>boost/graph/two_graphs_common_spanning_trees.hpp</TT></a> | |
82 | ||
83 | <h3>Parameters</h3> | |
84 | ||
85 | <tt>const Graph& iG, const Graph& vG</tt> | |
86 | <blockquote> | |
87 | These are the graphs to be analyzed.<br/> | |
88 | They must comply with the concepts VertexAndEdgeListGraphConcept and IncidenceGraphConcept.<br/> | |
89 | In addition, the directed_category should be of type undirected_tag. | |
90 | </blockquote> | |
91 | ||
92 | <tt>Order iG_map, Order vG_map</tt> | |
93 | <blockquote> | |
94 | These are lists of references to edges, that define the preferred order for access to the lists of edges.<br/> | |
95 | They must comply with the concept RandomAccessContainer. | |
96 | </blockquote> | |
97 | ||
98 | <tt>Func func</tt> | |
99 | <blockquote> | |
100 | This is a callback that is invoked by the algorithm for each common spanning tree found.<br/> | |
101 | It must comply with the concept UnaryFunction with void as return value, and an object of type <i>typeof(inL)</i> as argument. | |
102 | </blockquote> | |
103 | ||
104 | <tt>Seq inL<a href="#1">[1]</a></tt> | |
105 | <blockquote> | |
106 | This is the way in which the edges are marked as belonging to the common spanning tree.<br/> | |
107 | It must comply with the concept Mutable_RandomAccessContainer. In addition, the value_type should be of type bool. | |
108 | If the i-th edge or <i>inL[i]</i> is true, then it belongs to the common spanning tree, otherwise it does not belong. | |
109 | </blockquote> | |
110 | ||
111 | <h3>Example</h3> | |
112 | ||
113 | <p> | |
114 | The file | |
115 | <a href="../example/two_graphs_common_spanning_trees.cpp"><tt>examples/two_graphs_common_spanning_trees.cpp</tt></a> | |
116 | contains an example of finding common spanning trees of two undirected graphs. | |
117 | </p> | |
118 | ||
119 | <h3>Notes</h3> | |
120 | ||
121 | <p> | |
122 | <a name="1">[1]</a><br/> | |
123 | The presence of <i>inL</i> may seem senseless. The algorithm can use a vector of | |
124 | placeholders internally generated. However, doing so has more flexibility on | |
125 | the callback function. Moreover, being largely involved in the electronics | |
126 | world, there are cases where some edges have to be forced in every tree (ie | |
127 | you want to search all the trees that have the same root): With this | |
128 | solution, the problem is easily solved.<br/> | |
129 | Intuitively from the above, <i>inL</i> must be of a size equal to <i>(V-1)</i>, where | |
130 | <i>V</i> is the number of vertices of the graph. | |
131 | </p> | |
132 | ||
133 | <br/> | |
134 | <hr> | |
135 | <table> | |
136 | <tr valign=top> | |
137 | <td nowrap>Copyright © 2012</td> | |
138 | <td>Michele Caini, (<a href="mailto:michele.caini@gmail.com">michele.caini@gmail.com</a>)</td> | |
139 | </tr> | |
140 | </table> | |
141 | ||
142 | </body> | |
143 | </html> |