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 Minty, 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> 23The <b>MRT</b> algorithm, based on an academic article of <b>Minty</b>, <b>Read</b> and 24<b>Tarjan</b>, is an efficient algorithm for the common spanning tree problem.<br/> 25This kind of algorithm is widely used in electronics, being the basis of the 26analysis of electrical circuits. Another area of interest may be that of the 27networking. 28</p> 29 30<p> 31The proposed algorithm receives several arguments and works with callbacks.<br/> 32The prototypes are: 33</p> 34 35<p> 36<i>// Ordered Edges List</i> 37<pre> 38template < typename Graph, typename Order, typename Func, typename Seq > 39void 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> 52template < typename Graph, typename Func, typename Seq > 53void 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> 64The problem of common spanning tree is easily described.<br/> 65Imagine we have two graphs that are represented as lists of edges. A common 66spanning tree is a set of indices that identifies a spanning tree for both 67the first and for the second of the two graphs. Despite it is easily accomplished 68with edge list representation for graphs, it is intuitively difficult to achieve 69with adjacency list representation. This is due to the fact that it is necessary 70to represent an edge with an absolute index. 71</p> 72<p> 73Note that the set of common spanning trees of the two graphs is a subset of 74the set of spanning trees of the first graph, as well as those of the second 75graph. 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> 87These are the graphs to be analyzed.<br/> 88They must comply with the concepts VertexAndEdgeListGraphConcept and IncidenceGraphConcept.<br/> 89In addition, the directed_category should be of type undirected_tag. 90</blockquote> 91 92<tt>Order iG_map, Order vG_map</tt> 93<blockquote> 94These are lists of references to edges, that define the preferred order for access to the lists of edges.<br/> 95They must comply with the concept RandomAccessContainer. 96</blockquote> 97 98<tt>Func func</tt> 99<blockquote> 100This is a callback that is invoked by the algorithm for each common spanning tree found.<br/> 101It 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> 106This is the way in which the edges are marked as belonging to the common spanning tree.<br/> 107It must comply with the concept Mutable_RandomAccessContainer. In addition, the value_type should be of type bool. 108If 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> 114The file 115<a href="../example/two_graphs_common_spanning_trees.cpp"><tt>examples/two_graphs_common_spanning_trees.cpp</tt></a> 116contains 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> 144
