Two-Graphs Common Spanning Trees (MRT Algorithm)

The MRT algorithm, based on an academic article of Minty, Read and Tarjan, is an efficient algorithm for the common spanning tree problem.
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.

The proposed algorithm receives several arguments and works with callbacks.
The prototypes are:

// Ordered Edges List

template < typename Graph, typename Order, typename Func, typename Seq >
void two_graphs_common_spanning_trees
  (
    const Graph& iG,
    Order iG_map,
    const Graph& vG,
    Order vG_map,
    Func func,
    Seq inL
  )

template < typename Graph, typename Func, typename Seq >
void two_graphs_common_spanning_trees
  (
    const Graph& iG,
    const Graph& vG,
    Func func,
    Seq inL
  )

The problem of common spanning tree is easily described.
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.

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.

Where Defined

boost/graph/two_graphs_common_spanning_trees.hpp

Parameters

These are the graphs to be analyzed.
They must comply with the concepts VertexAndEdgeListGraphConcept and IncidenceGraphConcept.
In addition, the directed_category should be of type undirected_tag.

These are lists of references to edges, that define the preferred order for access to the lists of edges.
They must comply with the concept RandomAccessContainer.

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

This is the way in which the edges are marked as belonging to the common spanning tree.
It must comply with the concept Mutable_RandomAccessContainer. In addition, the value_type should be of type bool. If the i-th edge or inL[i] is true, then it belongs to the common spanning tree, otherwise it does not belong.

Example

The file examples/two_graphs_common_spanning_trees.cpp contains an example of finding common spanning trees of two undirected graphs.

Notes

[1]
The presence of inL 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.
Intuitively from the above, inL must be of a size equal to (V-1), where V is the number of vertices of the graph.