[ceph.git] / ceph / src / boost / libs / graph / doc / two_graphs_common_spanning_trees.html

<html>
<!--
          Copyright (C) 2012, Michele Caini.
 Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at
          http://www.boost.org/LICENSE_1_0.txt)

          Two Graphs Common Spanning Trees Algorithm
      Based on academic article of Mint, Read and Tarjan
     Efficient Algorithm for Common Spanning Tree Problem
 Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346–347
-->
<head>
<title>Boost Graph Library: Two-Graphs Common Spanning Trees</title>
<body bgcolo="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000">
<img src="../../../boost.png" alt="C++ Boost" width="277" height="86">

<br clear>

<h1><tt><a name="sec:two-graphs-common-spanning-trees">Two-Graphs Common Spanning Trees (MRT Algorithm)</a></tt></h1>

<p>
The <b>MRT</b> algorithm, based on an academic article of <b>Mint</b>, <b>Read</b> and
<b>Tarjan</b>, is an efficient algorithm for the common spanning tree problem.<br/>
This kind of algorithm is widely used in electronics, being the basis of the
analysis of electrical circuits. Another area of interest may be that of the
networking.
</p>

<p>
The proposed algorithm receives several arguments and works with callbacks.<br/>
The prototypes are:
</p>

<p>
<i>// Ordered Edges List</i>
<pre>
template &lt; typename Graph, typename Order, typename Func, typename Seq &gt;
void two_graphs_common_spanning_trees
  (
    const Graph&amp; iG,
    Order iG_map,
    const Graph&amp; vG,
    Order vG_map,
    Func func,
    Seq inL
  )
</pre>

<i>// Unordered Edges List</i>
<pre>
template &lt; typename Graph, typename Func, typename Seq &gt;
void two_graphs_common_spanning_trees
  (
    const Graph&amp; iG,
    const Graph&amp; vG,
    Func func,
    Seq inL
  )
</pre>
</p>

<p>
The problem of common spanning tree is easily described.<br/>
Imagine we have two graphs that are represented as lists of edges. A common
spanning tree is a set of indices that identifies a spanning tree for both
the first and for the second of the two graphs. Despite it is easily accomplished
with edge list representation for graphs, it is intuitively difficult to achieve
with adjacency list representation. This is due to the fact that it is necessary
to represent an edge with an absolute index.
</p>
<p>
Note that the set of common spanning trees of the two graphs is a subset of
the set of spanning trees of the first graph, as well as those of the second
graph.
</p>

<h3>Where Defined</h3>

<p>
<a href="../../../boost/graph/two_graphs_common_spanning_trees.hpp"><TT>boost/graph/two_graphs_common_spanning_trees.hpp</TT></a>

<h3>Parameters</h3>

<tt>const Graph& iG, const Graph& vG</tt>
<blockquote>
These are the graphs to be analyzed.<br/>
They must comply with the concepts VertexAndEdgeListGraphConcept and IncidenceGraphConcept.<br/>
In addition, the directed_category should be of type undirected_tag.
</blockquote>

<tt>Order iG_map, Order vG_map</tt>
<blockquote>
These are lists of references to edges, that define the preferred order for access to the lists of edges.<br/>
They must comply with the concept RandomAccessContainer.
</blockquote>

<tt>Func func</tt>
<blockquote>
This is a callback that is invoked by the algorithm for each common spanning tree found.<br/>
It must comply with the concept UnaryFunction with void as return value, and an object of type <i>typeof(inL)</i> as argument.
</blockquote>

<tt>Seq inL<a href="#1">[1]</a></tt>
<blockquote>
This is the way in which the edges are marked as belonging to the common spanning tree.<br/>
It must comply with the concept Mutable_RandomAccessContainer. In addition, the value_type should be of type bool.
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.
</blockquote>

<h3>Example</h3>

<p>
The file
<a href="../example/two_graphs_common_spanning_trees.cpp"><tt>examples/two_graphs_common_spanning_trees.cpp</tt></a>
contains an example of finding common spanning trees of two undirected graphs.
</p>

<h3>Notes</h3>

<p>
<a name="1">[1]</a><br/>
  The presence of <i>inL</i> may seem senseless. The algorithm can use a vector of
  placeholders internally generated. However, doing so has more flexibility on
  the callback function. Moreover, being largely involved in the electronics
  world, there are cases where some edges have to be forced in every tree (ie
  you want to search all the trees that have the same root): With this
  solution, the problem is easily solved.<br/>
  Intuitively from the above, <i>inL</i> must be of a size equal to <i>(V-1)</i>, where
  <i>V</i> is the number of vertices of the graph.
</p>

<br/>
<hr>
<table>
<tr valign=top>
<td nowrap>Copyright &copy; 2012</td>
<td>Michele Caini, (<a href="mailto:michele.caini@gmail.com">michele.caini@gmail.com</a>)</td>
</tr>
</table>

</body>
</html>
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>