FM / graph

/usr/include/boost/graph

Name	Size	Mode	Actions
detail/	-	0755	rm
distributed/	-	0755	rm
parallel/	-	0755	rm
planar_detail/	-	0755	rm
property_maps/	-	0755	rm
accounting.hpp	876	0644	edit dl rm
adjacency_iterator.hpp	2899	0644	edit dl rm
adjacency_list.hpp	13692	0644	edit dl rm
adjacency_list_io.hpp	11849	0644	edit dl rm
adjacency_matrix.hpp	45743	0644	edit dl rm
adj_list_serialize.hpp	4523	0644	edit dl rm
astar_search.hpp	26736	0644	edit dl rm
bandwidth.hpp	2992	0644	edit dl rm
bc_clustering.hpp	5937	0644	edit dl rm
bellman_ford_shortest_paths.hpp	8229	0644	edit dl rm
betweenness_centrality.hpp	26290	0644	edit dl rm
biconnected_components.hpp	16701	0644	edit dl rm
bipartite.hpp	13492	0644	edit dl rm
boyer_myrvold_planar_test.hpp	9849	0644	edit dl rm
boykov_kolmogorov_max_flow.hpp	47342	0644	edit dl rm
breadth_first_search.hpp	14751	0644	edit dl rm
bron_kerbosch_all_cliques.hpp	11736	0644	edit dl rm
buffer_concepts.hpp	2429	0644	edit dl rm
chrobak_payne_drawing.hpp	8641	0644	edit dl rm
circle_layout.hpp	1924	0644	edit dl rm
closeness_centrality.hpp	6057	0644	edit dl rm
clustering_coefficient.hpp	5726	0644	edit dl rm
compressed_sparse_row_graph.hpp	69887	0644	edit dl rm
connected_components.hpp	4134	0644	edit dl rm
copy.hpp	21225	0644	edit dl rm
core_numbers.hpp	13663	0644	edit dl rm
create_condensation_graph.hpp	3159	0644	edit dl rm
cuthill_mckee_ordering.hpp	5992	0644	edit dl rm
cycle_canceling.hpp	6645	0644	edit dl rm
dag_shortest_paths.hpp	6064	0644	edit dl rm
degree_centrality.hpp	4236	0644	edit dl rm
depth_first_search.hpp	15430	0644	edit dl rm
dijkstra_shortest_paths.hpp	23687	0644	edit dl rm
dijkstra_shortest_paths_no_color_map.hpp	9620	0644	edit dl rm
dimacs.hpp	10448	0644	edit dl rm
directed_graph.hpp	24214	0644	edit dl rm
dll_import_export.hpp	892	0644	edit dl rm
dominator_tree.hpp	17553	0644	edit dl rm
eccentricity.hpp	4611	0644	edit dl rm
edge_coloring.hpp	6809	0644	edit dl rm
edge_connectivity.hpp	6796	0644	edit dl rm
edge_list.hpp	9948	0644	edit dl rm
edmonds_karp_max_flow.hpp	10177	0644	edit dl rm
edmunds_karp_max_flow.hpp	982	0644	edit dl rm
erdos_renyi_generator.hpp	7257	0644	edit dl rm
exception.hpp	1466	0644	edit dl rm
exterior_property.hpp	4289	0644	edit dl rm
filtered_graph.hpp	20098	0644	edit dl rm
find_flow_cost.hpp	1859	0644	edit dl rm
floyd_warshall_shortest.hpp	8510	0644	edit dl rm
fruchterman_reingold.hpp	17325	0644	edit dl rm
geodesic_distance.hpp	8015	0644	edit dl rm
graphml.hpp	13460	0644	edit dl rm
graphviz.hpp	33503	0644	edit dl rm
graph_archetypes.hpp	11008	0644	edit dl rm
graph_as_tree.hpp	4532	0644	edit dl rm
graph_concepts.hpp	19785	0644	edit dl rm
graph_mutability_traits.hpp	4995	0644	edit dl rm
graph_selectors.hpp	1274	0644	edit dl rm
graph_stats.hpp	4394	0644	edit dl rm
graph_traits.hpp	13065	0644	edit dl rm
graph_utility.hpp	16182	0644	edit dl rm
grid_graph.hpp	33830	0644	edit dl rm
gursoy_atun_layout.hpp	13248	0644	edit dl rm
hawick_circuits.hpp	14593	0644	edit dl rm
howard_cycle_ratio.hpp	23107	0644	edit dl rm
incremental_components.hpp	8224	0644	edit dl rm
isomorphism.hpp	26308	0644	edit dl rm
is_kuratowski_subgraph.hpp	10260	0644	edit dl rm
is_straight_line_drawing.hpp	7230	0644	edit dl rm
iteration_macros.hpp	11659	0644	edit dl rm
iteration_macros_undef.hpp	673	0644	edit dl rm
johnson_all_pairs_shortest.hpp	7646	0644	edit dl rm
kamada_kawai_spring_layout.hpp	28048	0644	edit dl rm
king_ordering.hpp	12101	0644	edit dl rm
kruskal_min_spanning_tree.hpp	5743	0644	edit dl rm
labeled_graph.hpp	30914	0644	edit dl rm
leda_graph.hpp	28789	0644	edit dl rm
lookup_edge.hpp	1894	0644	edit dl rm
loop_erased_random_walk.hpp	4436	0644	edit dl rm
make_biconnected_planar.hpp	3513	0644	edit dl rm
make_connected.hpp	2645	0644	edit dl rm
make_maximal_planar.hpp	7578	0644	edit dl rm
matrix_as_graph.hpp	7227	0644	edit dl rm
maximum_adjacency_search.hpp	15125	0644	edit dl rm
maximum_weighted_matching.hpp	49722	0644	edit dl rm
max_cardinality_matching.hpp	31000	0644	edit dl rm
mcgregor_common_subgraphs.hpp	43470	0644	edit dl rm
mesh_graph_generator.hpp	5616	0644	edit dl rm
metis.hpp	10982	0644	edit dl rm
metric_tsp_approx.hpp	10809	0644	edit dl rm
minimum_degree_ordering.hpp	27087	0644	edit dl rm
named_function_params.hpp	39639	0644	edit dl rm
named_graph.hpp	20614	0644	edit dl rm
neighbor_bfs.hpp	11763	0644	edit dl rm
numeric_values.hpp	1814	0644	edit dl rm
one_bit_color_map.hpp	3277	0644	edit dl rm
overloading.hpp	1584	0644	edit dl rm
page_rank.hpp	6164	0644	edit dl rm
planar_canonical_ordering.hpp	7203	0644	edit dl rm
planar_face_traversal.hpp	6020	0644	edit dl rm
plod_generator.hpp	7708	0644	edit dl rm
point_traits.hpp	782	0644	edit dl rm
prim_minimum_spanning_tree.hpp	2960	0644	edit dl rm
profile.hpp	1327	0644	edit dl rm
properties.hpp	12417	0644	edit dl rm
property_iter_range.hpp	4345	0644	edit dl rm
push_relabel_max_flow.hpp	34737	0644	edit dl rm
random.hpp	9672	0644	edit dl rm
random_layout.hpp	988	0644	edit dl rm
random_spanning_tree.hpp	5775	0644	edit dl rm
read_dimacs.hpp	12080	0644	edit dl rm
relax.hpp	4400	0644	edit dl rm
reverse_graph.hpp	22402	0644	edit dl rm
rmat_graph_generator.hpp	19291	0644	edit dl rm
r_c_shortest_paths.hpp	30673	0644	edit dl rm
sequential_vertex_coloring.hpp	4562	0644	edit dl rm
simple_point.hpp	628	0644	edit dl rm
sloan_ordering.hpp	15540	0644	edit dl rm
smallest_last_ordering.hpp	5458	0644	edit dl rm
small_world_generator.hpp	3670	0644	edit dl rm
ssca_graph_generator.hpp	6564	0644	edit dl rm
stanford_graph.hpp	20126	0644	edit dl rm
stoer_wagner_min_cut.hpp	12415	0644	edit dl rm
strong_components.hpp	13009	0644	edit dl rm
st_connected.hpp	2852	0644	edit dl rm
subgraph.hpp	39996	0644	edit dl rm
successive_shortest_path_nonnegative_weights.hpp	10413	0644	edit dl rm
tiernan_all_cycles.hpp	12547	0644	edit dl rm
topological_sort.hpp	2611	0644	edit dl rm
topology.hpp	20389	0644	edit dl rm
transitive_closure.hpp	14260	0644	edit dl rm
transitive_reduction.hpp	5326	0644	edit dl rm
transpose_graph.hpp	1198	0644	edit dl rm
tree_traits.hpp	1338	0644	edit dl rm
two_bit_color_map.hpp	3510	0644	edit dl rm
two_graphs_common_spanning_trees.hpp	34996	0644	edit dl rm
undirected_dfs.hpp	10672	0644	edit dl rm
undirected_graph.hpp	25276	0644	edit dl rm
use_mpi.hpp	437	0644	edit dl rm
vector_as_graph.hpp	10474	0644	edit dl rm
vertex_and_edge_range.hpp	5528	0644	edit dl rm
vf2_sub_graph_iso.hpp	48585	0644	edit dl rm
visitors.hpp	11318	0644	edit dl rm
wavefront.hpp	3932	0644	edit dl rm
write_dimacs.hpp	2889	0644	edit dl rm

Edit: /usr/include/boost/graph/two_graphs_common_spanning_trees.hpp (34996B)

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

#ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
#define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP

#include <boost/config.hpp>

#include <boost/bimap.hpp>
#include <boost/type_traits.hpp>
#include <boost/concept/requires.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <vector>
#include <stack>
#include <map>

namespace boost
{

namespace detail
{

template < typename TreeMap, typename PredMap, typename DistMap,
        typename LowMap, typename Buffer >
    struct bridges_visitor : public default_dfs_visitor
    {
        bridges_visitor(TreeMap tree, PredMap pred, DistMap dist, LowMap low,
            Buffer& buffer)
        : mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer)
        {
            mNum = -1;
        }

template < typename Vertex, typename Graph >
        void initialize_vertex(const Vertex& u, const Graph& g)
        {
            put(mPred, u, u);
            put(mDist, u, -1);
        }

template < typename Vertex, typename Graph >
        void discover_vertex(const Vertex& u, const Graph& g)
        {
            put(mDist, u, ++mNum);
            put(mLow, u, get(mDist, u));
        }

template < typename Edge, typename Graph >
        void tree_edge(const Edge& e, const Graph& g)
        {
            put(mPred, target(e, g), source(e, g));
            put(mTree, target(e, g), e);
        }

template < typename Edge, typename Graph >
        void back_edge(const Edge& e, const Graph& g)
        {
            put(mLow, source(e, g),
                (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g))));
        }

template < typename Vertex, typename Graph >
        void finish_vertex(const Vertex& u, const Graph& g)
        {
            Vertex parent = get(mPred, u);
            if (get(mLow, u) > get(mDist, parent))
                mBuffer.push(get(mTree, u));
            put(mLow, parent, (std::min)(get(mLow, parent), get(mLow, u)));
        }

TreeMap mTree;
        PredMap mPred;
        DistMap mDist;
        LowMap mLow;
        Buffer& mBuffer;
        int mNum;
    };

template < typename Buffer >
    struct cycle_finder : public base_visitor< cycle_finder< Buffer > >
    {
        typedef on_back_edge event_filter;
        cycle_finder() : mBuffer(0) {}
        cycle_finder(Buffer* buffer) : mBuffer(buffer) {}
        template < typename Edge, typename Graph >
        void operator()(const Edge& e, const Graph& g)
        {
            if (mBuffer)
                mBuffer->push(e);
        }
        Buffer* mBuffer;
    };

template < typename DeletedMap > struct deleted_edge_status
    {
        deleted_edge_status() {}
        deleted_edge_status(DeletedMap map) : mMap(map) {}
        template < typename Edge > bool operator()(const Edge& e) const
        {
            return (!get(mMap, e));
        }
        DeletedMap mMap;
    };

template < typename InLMap > struct inL_edge_status
    {
        inL_edge_status() {}
        inL_edge_status(InLMap map) : mMap(map) {}
        template < typename Edge > bool operator()(const Edge& e) const
        {
            return get(mMap, e);
        }
        InLMap mMap;
    };

template < typename Graph, typename Func, typename Seq, typename Map >
    void rec_two_graphs_common_spanning_trees(const Graph& iG,
        bimap< bimaps::set_of< int >,
            bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > >
            iG_bimap,
        Map aiG_inL, Map diG, const Graph& vG,
        bimap< bimaps::set_of< int >,
            bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > >
            vG_bimap,
        Map avG_inL, Map dvG, Func func, Seq inL)
    {
        typedef graph_traits< Graph > GraphTraits;

typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
        typedef typename GraphTraits::edge_descriptor edge_descriptor;

typedef typename Seq::size_type seq_size_type;

int edges = num_vertices(iG) - 1;
        //
        //  [ Michele Caini ]
        //
        //  Using the condition (edges != 0) leads to the accidental submission
        //  of
        //    sub-graphs ((V-1+1)-fake-tree, named here fat-tree).
        //  Remove this condition is a workaround for the problem of fat-trees.
        //  Please do not add that condition, even if it improves performance.
        //
        //  Here is proposed the previous guard (that was wrong):
        //     for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i)
        //
        {
            for (seq_size_type i = 0; i < inL.size(); ++i)
                if (inL[i])
                    --edges;

if (edges < 0)
                return;
        }

bool is_tree = (edges == 0);
        if (is_tree)
        {
            func(inL);
        }
        else
        {
            std::map< vertex_descriptor, default_color_type > vertex_color;
            std::map< edge_descriptor, default_color_type > edge_color;

std::stack< edge_descriptor > iG_buf, vG_buf;
            bool found = false;

seq_size_type m;
            for (seq_size_type j = 0; j < inL.size() && !found; ++j)
            {
                if (!inL[j] && !get(diG, iG_bimap.left.at(j))
                    && !get(dvG, vG_bimap.left.at(j)))
                {
                    put(aiG_inL, iG_bimap.left.at(j), true);
                    put(avG_inL, vG_bimap.left.at(j), true);

undirected_dfs(
                        make_filtered_graph(iG,
                            detail::inL_edge_status< associative_property_map<
                                std::map< edge_descriptor, bool > > >(aiG_inL)),
                        make_dfs_visitor(detail::cycle_finder<
                            std::stack< edge_descriptor > >(&iG_buf)),
                        associative_property_map<
                            std::map< vertex_descriptor, default_color_type > >(
                            vertex_color),
                        associative_property_map<
                            std::map< edge_descriptor, default_color_type > >(
                            edge_color));
                    undirected_dfs(
                        make_filtered_graph(vG,
                            detail::inL_edge_status< associative_property_map<
                                std::map< edge_descriptor, bool > > >(avG_inL)),
                        make_dfs_visitor(detail::cycle_finder<
                            std::stack< edge_descriptor > >(&vG_buf)),
                        associative_property_map<
                            std::map< vertex_descriptor, default_color_type > >(
                            vertex_color),
                        associative_property_map<
                            std::map< edge_descriptor, default_color_type > >(
                            edge_color));

if (iG_buf.empty() && vG_buf.empty())
                    {
                        inL[j] = true;
                        found = true;
                        m = j;
                    }
                    else
                    {
                        while (!iG_buf.empty())
                            iG_buf.pop();
                        while (!vG_buf.empty())
                            vG_buf.pop();
                        put(aiG_inL, iG_bimap.left.at(j), false);
                        put(avG_inL, vG_bimap.left.at(j), false);
                    }
                }
            }

if (found)
            {

std::stack< edge_descriptor > iG_buf_copy, vG_buf_copy;
                for (seq_size_type j = 0; j < inL.size(); ++j)
                {
                    if (!inL[j] && !get(diG, iG_bimap.left.at(j))
                        && !get(dvG, vG_bimap.left.at(j)))
                    {

put(aiG_inL, iG_bimap.left.at(j), true);
                        put(avG_inL, vG_bimap.left.at(j), true);

undirected_dfs(
                            make_filtered_graph(iG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    aiG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&iG_buf)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));
                        undirected_dfs(
                            make_filtered_graph(vG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    avG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&vG_buf)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));

if (!iG_buf.empty() || !vG_buf.empty())
                        {
                            while (!iG_buf.empty())
                                iG_buf.pop();
                            while (!vG_buf.empty())
                                vG_buf.pop();
                            put(diG, iG_bimap.left.at(j), true);
                            put(dvG, vG_bimap.left.at(j), true);
                            iG_buf_copy.push(iG_bimap.left.at(j));
                            vG_buf_copy.push(vG_bimap.left.at(j));
                        }

put(aiG_inL, iG_bimap.left.at(j), false);
                        put(avG_inL, vG_bimap.left.at(j), false);
                    }
                }

// REC
                detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq,
                    Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL,
                    dvG, func, inL);

while (!iG_buf_copy.empty())
                {
                    put(diG, iG_buf_copy.top(), false);
                    put(dvG,
                        vG_bimap.left.at(iG_bimap.right.at(iG_buf_copy.top())),
                        false);
                    iG_buf_copy.pop();
                }
                while (!vG_buf_copy.empty())
                {
                    put(dvG, vG_buf_copy.top(), false);
                    put(diG,
                        iG_bimap.left.at(vG_bimap.right.at(vG_buf_copy.top())),
                        false);
                    vG_buf_copy.pop();
                }

inL[m] = false;
                put(aiG_inL, iG_bimap.left.at(m), false);
                put(avG_inL, vG_bimap.left.at(m), false);

put(diG, iG_bimap.left.at(m), true);
                put(dvG, vG_bimap.left.at(m), true);

std::map< vertex_descriptor, edge_descriptor > tree_map;
                std::map< vertex_descriptor, vertex_descriptor > pred_map;
                std::map< vertex_descriptor, int > dist_map, low_map;

detail::bridges_visitor<
                    associative_property_map<
                        std::map< vertex_descriptor, edge_descriptor > >,
                    associative_property_map<
                        std::map< vertex_descriptor, vertex_descriptor > >,
                    associative_property_map<
                        std::map< vertex_descriptor, int > >,
                    associative_property_map<
                        std::map< vertex_descriptor, int > >,
                    std::stack< edge_descriptor > >
                iG_vis(associative_property_map<
                           std::map< vertex_descriptor, edge_descriptor > >(
                           tree_map),
                    associative_property_map<
                        std::map< vertex_descriptor, vertex_descriptor > >(
                        pred_map),
                    associative_property_map<
                        std::map< vertex_descriptor, int > >(dist_map),
                    associative_property_map<
                        std::map< vertex_descriptor, int > >(low_map),
                    iG_buf),
                    vG_vis(associative_property_map<
                               std::map< vertex_descriptor, edge_descriptor > >(
                               tree_map),
                        associative_property_map<
                            std::map< vertex_descriptor, vertex_descriptor > >(
                            pred_map),
                        associative_property_map<
                            std::map< vertex_descriptor, int > >(dist_map),
                        associative_property_map<
                            std::map< vertex_descriptor, int > >(low_map),
                        vG_buf);

undirected_dfs(
                    make_filtered_graph(iG,
                        detail::deleted_edge_status< associative_property_map<
                            std::map< edge_descriptor, bool > > >(diG)),
                    iG_vis,
                    associative_property_map<
                        std::map< vertex_descriptor, default_color_type > >(
                        vertex_color),
                    associative_property_map<
                        std::map< edge_descriptor, default_color_type > >(
                        edge_color));
                undirected_dfs(
                    make_filtered_graph(vG,
                        detail::deleted_edge_status< associative_property_map<
                            std::map< edge_descriptor, bool > > >(dvG)),
                    vG_vis,
                    associative_property_map<
                        std::map< vertex_descriptor, default_color_type > >(
                        vertex_color),
                    associative_property_map<
                        std::map< edge_descriptor, default_color_type > >(
                        edge_color));

found = false;
                std::stack< edge_descriptor > iG_buf_tmp, vG_buf_tmp;
                while (!iG_buf.empty() && !found)
                {
                    if (!inL[iG_bimap.right.at(iG_buf.top())])
                    {
                        put(aiG_inL, iG_buf.top(), true);
                        put(avG_inL,
                            vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
                            true);

undirected_dfs(
                            make_filtered_graph(iG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    aiG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&iG_buf_tmp)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));
                        undirected_dfs(
                            make_filtered_graph(vG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    avG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&vG_buf_tmp)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));

if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty())
                        {
                            found = true;
                        }
                        else
                        {
                            while (!iG_buf_tmp.empty())
                                iG_buf_tmp.pop();
                            while (!vG_buf_tmp.empty())
                                vG_buf_tmp.pop();
                            iG_buf_copy.push(iG_buf.top());
                        }

put(aiG_inL, iG_buf.top(), false);
                        put(avG_inL,
                            vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
                            false);
                    }
                    iG_buf.pop();
                }
                while (!vG_buf.empty() && !found)
                {
                    if (!inL[vG_bimap.right.at(vG_buf.top())])
                    {
                        put(avG_inL, vG_buf.top(), true);
                        put(aiG_inL,
                            iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
                            true);

undirected_dfs(
                            make_filtered_graph(iG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    aiG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&iG_buf_tmp)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));
                        undirected_dfs(
                            make_filtered_graph(vG,
                                detail::inL_edge_status<
                                    associative_property_map<
                                        std::map< edge_descriptor, bool > > >(
                                    avG_inL)),
                            make_dfs_visitor(detail::cycle_finder<
                                std::stack< edge_descriptor > >(&vG_buf_tmp)),
                            associative_property_map< std::map<
                                vertex_descriptor, default_color_type > >(
                                vertex_color),
                            associative_property_map< std::map< edge_descriptor,
                                default_color_type > >(edge_color));

if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty())
                        {
                            found = true;
                        }
                        else
                        {
                            while (!iG_buf_tmp.empty())
                                iG_buf_tmp.pop();
                            while (!vG_buf_tmp.empty())
                                vG_buf_tmp.pop();
                            vG_buf_copy.push(vG_buf.top());
                        }

put(avG_inL, vG_buf.top(), false);
                        put(aiG_inL,
                            iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
                            false);
                    }
                    vG_buf.pop();
                }

if (!found)
                {

while (!iG_buf_copy.empty())
                    {
                        inL[iG_bimap.right.at(iG_buf_copy.top())] = true;
                        put(aiG_inL, iG_buf_copy.top(), true);
                        put(avG_inL,
                            vG_bimap.left.at(
                                iG_bimap.right.at(iG_buf_copy.top())),
                            true);
                        iG_buf.push(iG_buf_copy.top());
                        iG_buf_copy.pop();
                    }
                    while (!vG_buf_copy.empty())
                    {
                        inL[vG_bimap.right.at(vG_buf_copy.top())] = true;
                        put(avG_inL, vG_buf_copy.top(), true);
                        put(aiG_inL,
                            iG_bimap.left.at(
                                vG_bimap.right.at(vG_buf_copy.top())),
                            true);
                        vG_buf.push(vG_buf_copy.top());
                        vG_buf_copy.pop();
                    }

// REC
                    detail::rec_two_graphs_common_spanning_trees< Graph, Func,
                        Seq, Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap,
                        aiG_inL, dvG, func, inL);

while (!iG_buf.empty())
                    {
                        inL[iG_bimap.right.at(iG_buf.top())] = false;
                        put(aiG_inL, iG_buf.top(), false);
                        put(avG_inL,
                            vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
                            false);
                        iG_buf.pop();
                    }
                    while (!vG_buf.empty())
                    {
                        inL[vG_bimap.right.at(vG_buf.top())] = false;
                        put(avG_inL, vG_buf.top(), false);
                        put(aiG_inL,
                            iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
                            false);
                        vG_buf.pop();
                    }
                }

put(diG, iG_bimap.left.at(m), false);
                put(dvG, vG_bimap.left.at(m), false);
            }
        }
    }

} // namespace detail

template < typename Coll, typename Seq > struct tree_collector
{

public:
    BOOST_CONCEPT_ASSERT((BackInsertionSequence< Coll >));
    BOOST_CONCEPT_ASSERT((RandomAccessContainer< Seq >));
    BOOST_CONCEPT_ASSERT((CopyConstructible< Seq >));

typedef typename Coll::value_type coll_value_type;
    typedef typename Seq::value_type seq_value_type;

BOOST_STATIC_ASSERT((is_same< coll_value_type, Seq >::value));
    BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value));

tree_collector(Coll& seqs) : mSeqs(seqs) {}

inline void operator()(Seq seq) { mSeqs.push_back(seq); }

private:
    Coll& mSeqs;
};

template < typename Graph, typename Order, typename Func, typename Seq >
BOOST_CONCEPT_REQUIRES(
    ((RandomAccessContainer< Order >))((IncidenceGraphConcept< Graph >))(
        (UnaryFunction< Func, void, Seq >))(
        (Mutable_RandomAccessContainer< Seq >))(
        (VertexAndEdgeListGraphConcept< Graph >)),
    (void))
two_graphs_common_spanning_trees(const Graph& iG, Order iG_map, const Graph& vG,
    Order vG_map, Func func, Seq inL)
{
    typedef graph_traits< Graph > GraphTraits;

typedef typename GraphTraits::directed_category directed_category;
    typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
    typedef typename GraphTraits::edge_descriptor edge_descriptor;

typedef typename GraphTraits::edges_size_type edges_size_type;
    typedef typename GraphTraits::edge_iterator edge_iterator;

typedef typename Seq::value_type seq_value_type;
    typedef typename Seq::size_type seq_size_type;

typedef typename Order::value_type order_value_type;
    typedef typename Order::size_type order_size_type;

BOOST_STATIC_ASSERT((is_same< order_value_type, edge_descriptor >::value));
    BOOST_CONCEPT_ASSERT((Convertible< order_size_type, edges_size_type >));

BOOST_CONCEPT_ASSERT((Convertible< seq_size_type, edges_size_type >));
    BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value));

BOOST_STATIC_ASSERT((is_same< directed_category, undirected_tag >::value));

if (num_vertices(iG) != num_vertices(vG))
        return;

if (inL.size() != num_edges(iG) || inL.size() != num_edges(vG))
        return;

if (iG_map.size() != num_edges(iG) || vG_map.size() != num_edges(vG))
        return;

typedef bimaps::bimap< bimaps::set_of< int >,
        bimaps::set_of< order_value_type > >
        bimap_type;
    typedef typename bimap_type::value_type bimap_value;

bimap_type iG_bimap, vG_bimap;
    for (order_size_type i = 0; i < iG_map.size(); ++i)
        iG_bimap.insert(bimap_value(i, iG_map[i]));
    for (order_size_type i = 0; i < vG_map.size(); ++i)
        vG_bimap.insert(bimap_value(i, vG_map[i]));

edge_iterator current, last;
    boost::tuples::tie(current, last) = edges(iG);
    for (; current != last; ++current)
        if (iG_bimap.right.find(*current) == iG_bimap.right.end())
            return;
    boost::tuples::tie(current, last) = edges(vG);
    for (; current != last; ++current)
        if (vG_bimap.right.find(*current) == vG_bimap.right.end())
            return;

std::stack< edge_descriptor > iG_buf, vG_buf;

std::map< vertex_descriptor, edge_descriptor > tree_map;
    std::map< vertex_descriptor, vertex_descriptor > pred_map;
    std::map< vertex_descriptor, int > dist_map, low_map;

detail::bridges_visitor< associative_property_map< std::map<
                                 vertex_descriptor, edge_descriptor > >,
        associative_property_map<
            std::map< vertex_descriptor, vertex_descriptor > >,
        associative_property_map< std::map< vertex_descriptor, int > >,
        associative_property_map< std::map< vertex_descriptor, int > >,
        std::stack< edge_descriptor > >
    iG_vis(associative_property_map<
               std::map< vertex_descriptor, edge_descriptor > >(tree_map),
        associative_property_map<
            std::map< vertex_descriptor, vertex_descriptor > >(pred_map),
        associative_property_map< std::map< vertex_descriptor, int > >(
            dist_map),
        associative_property_map< std::map< vertex_descriptor, int > >(low_map),
        iG_buf),
        vG_vis(associative_property_map<
                   std::map< vertex_descriptor, edge_descriptor > >(tree_map),
            associative_property_map<
                std::map< vertex_descriptor, vertex_descriptor > >(pred_map),
            associative_property_map< std::map< vertex_descriptor, int > >(
                dist_map),
            associative_property_map< std::map< vertex_descriptor, int > >(
                low_map),
            vG_buf);

std::map< vertex_descriptor, default_color_type > vertex_color;
    std::map< edge_descriptor, default_color_type > edge_color;

undirected_dfs(iG, iG_vis,
        associative_property_map<
            std::map< vertex_descriptor, default_color_type > >(vertex_color),
        associative_property_map<
            std::map< edge_descriptor, default_color_type > >(edge_color));
    undirected_dfs(vG, vG_vis,
        associative_property_map<
            std::map< vertex_descriptor, default_color_type > >(vertex_color),
        associative_property_map<
            std::map< edge_descriptor, default_color_type > >(edge_color));

while (!iG_buf.empty())
    {
        inL[iG_bimap.right.at(iG_buf.top())] = true;
        iG_buf.pop();
    }
    while (!vG_buf.empty())
    {
        inL[vG_bimap.right.at(vG_buf.top())] = true;
        vG_buf.pop();
    }

std::map< edge_descriptor, bool > iG_inL, vG_inL;
    associative_property_map< std::map< edge_descriptor, bool > > aiG_inL(
        iG_inL),
        avG_inL(vG_inL);

for (seq_size_type i = 0; i < inL.size(); ++i)
    {
        if (inL[i])
        {
            put(aiG_inL, iG_bimap.left.at(i), true);
            put(avG_inL, vG_bimap.left.at(i), true);
        }
        else
        {
            put(aiG_inL, iG_bimap.left.at(i), false);
            put(avG_inL, vG_bimap.left.at(i), false);
        }
    }

if (iG_buf.empty() && vG_buf.empty())
    {

std::map< edge_descriptor, bool > iG_deleted, vG_deleted;
        associative_property_map< std::map< edge_descriptor, bool > > diG(
            iG_deleted);
        associative_property_map< std::map< edge_descriptor, bool > > dvG(
            vG_deleted);

boost::tuples::tie(current, last) = edges(iG);
        for (; current != last; ++current)
            put(diG, *current, false);
        boost::tuples::tie(current, last) = edges(vG);
        for (; current != last; ++current)
            put(dvG, *current, false);

for (seq_size_type j = 0; j < inL.size(); ++j)
        {
            if (!inL[j])
            {
                put(aiG_inL, iG_bimap.left.at(j), true);
                put(avG_inL, vG_bimap.left.at(j), true);

undirected_dfs(
                    make_filtered_graph(iG,
                        detail::inL_edge_status< associative_property_map<
                            std::map< edge_descriptor, bool > > >(aiG_inL)),
                    make_dfs_visitor(
                        detail::cycle_finder< std::stack< edge_descriptor > >(
                            &iG_buf)),
                    associative_property_map<
                        std::map< vertex_descriptor, default_color_type > >(
                        vertex_color),
                    associative_property_map<
                        std::map< edge_descriptor, default_color_type > >(
                        edge_color));
                undirected_dfs(
                    make_filtered_graph(vG,
                        detail::inL_edge_status< associative_property_map<
                            std::map< edge_descriptor, bool > > >(avG_inL)),
                    make_dfs_visitor(
                        detail::cycle_finder< std::stack< edge_descriptor > >(
                            &vG_buf)),
                    associative_property_map<
                        std::map< vertex_descriptor, default_color_type > >(
                        vertex_color),
                    associative_property_map<
                        std::map< edge_descriptor, default_color_type > >(
                        edge_color));

put(aiG_inL, iG_bimap.left.at(j), false);
                put(avG_inL, vG_bimap.left.at(j), false);
            }
        }

int cc = 0;

std::map< vertex_descriptor, int > com_map;
        cc += connected_components(
            make_filtered_graph(iG,
                detail::deleted_edge_status< associative_property_map<
                    std::map< edge_descriptor, bool > > >(diG)),
            associative_property_map< std::map< vertex_descriptor, int > >(
                com_map));
        cc += connected_components(
            make_filtered_graph(vG,
                detail::deleted_edge_status< associative_property_map<
                    std::map< edge_descriptor, bool > > >(dvG)),
            associative_property_map< std::map< vertex_descriptor, int > >(
                com_map));

if (cc != 2)
            return;

// REC
        detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq,
            associative_property_map< std::map< edge_descriptor, bool > > >(
            iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
    }
}

template < typename Graph, typename Func, typename Seq >
BOOST_CONCEPT_REQUIRES(
    ((IncidenceGraphConcept< Graph >))((EdgeListGraphConcept< Graph >)), (void))
two_graphs_common_spanning_trees(
    const Graph& iG, const Graph& vG, Func func, Seq inL)
{
    typedef graph_traits< Graph > GraphTraits;

typedef typename GraphTraits::edge_descriptor edge_descriptor;
    typedef typename GraphTraits::edge_iterator edge_iterator;

std::vector< edge_descriptor > iGO, vGO;
    edge_iterator curr, last;

boost::tuples::tie(curr, last) = edges(iG);
    for (; curr != last; ++curr)
        iGO.push_back(*curr);

boost::tuples::tie(curr, last) = edges(vG);
    for (; curr != last; ++curr)
        vGO.push_back(*curr);

two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL);
}

} // namespace boost

#endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP

// 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 #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP #include #include #include #include #include #include #include #include #include #include #include namespace boost { namespace detail { template < typename TreeMap, typename PredMap, typename DistMap, typename LowMap, typename Buffer > struct bridges_visitor : public default_dfs_visitor { bridges_visitor(TreeMap tree, PredMap pred, DistMap dist, LowMap low, Buffer& buffer) : mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer) { mNum = -1; } template < typename Vertex, typename Graph > void initialize_vertex(const Vertex& u, const Graph& g) { put(mPred, u, u); put(mDist, u, -1); } template < typename Vertex, typename Graph > void discover_vertex(const Vertex& u, const Graph& g) { put(mDist, u, ++mNum); put(mLow, u, get(mDist, u)); } template < typename Edge, typename Graph > void tree_edge(const Edge& e, const Graph& g) { put(mPred, target(e, g), source(e, g)); put(mTree, target(e, g), e); } template < typename Edge, typename Graph > void back_edge(const Edge& e, const Graph& g) { put(mLow, source(e, g), (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g)))); } template < typename Vertex, typename Graph > void finish_vertex(const Vertex& u, const Graph& g) { Vertex parent = get(mPred, u); if (get(mLow, u) > get(mDist, parent)) mBuffer.push(get(mTree, u)); put(mLow, parent, (std::min)(get(mLow, parent), get(mLow, u))); } TreeMap mTree; PredMap mPred; DistMap mDist; LowMap mLow; Buffer& mBuffer; int mNum; }; template < typename Buffer > struct cycle_finder : public base_visitor< cycle_finder< Buffer > > { typedef on_back_edge event_filter; cycle_finder() : mBuffer(0) {} cycle_finder(Buffer* buffer) : mBuffer(buffer) {} template < typename Edge, typename Graph > void operator()(const Edge& e, const Graph& g) { if (mBuffer) mBuffer->push(e); } Buffer* mBuffer; }; template < typename DeletedMap > struct deleted_edge_status { deleted_edge_status() {} deleted_edge_status(DeletedMap map) : mMap(map) {} template < typename Edge > bool operator()(const Edge& e) const { return (!get(mMap, e)); } DeletedMap mMap; }; template < typename InLMap > struct inL_edge_status { inL_edge_status() {} inL_edge_status(InLMap map) : mMap(map) {} template < typename Edge > bool operator()(const Edge& e) const { return get(mMap, e); } InLMap mMap; }; template < typename Graph, typename Func, typename Seq, typename Map > void rec_two_graphs_common_spanning_trees(const Graph& iG, bimap< bimaps::set_of< int >, bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > > iG_bimap, Map aiG_inL, Map diG, const Graph& vG, bimap< bimaps::set_of< int >, bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > > vG_bimap, Map avG_inL, Map dvG, Func func, Seq inL) { typedef graph_traits< Graph > GraphTraits; typedef typename GraphTraits::vertex_descriptor vertex_descriptor; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename Seq::size_type seq_size_type; int edges = num_vertices(iG) - 1; // // [ Michele Caini ] // // Using the condition (edges != 0) leads to the accidental submission // of // sub-graphs ((V-1+1)-fake-tree, named here fat-tree). // Remove this condition is a workaround for the problem of fat-trees. // Please do not add that condition, even if it improves performance. // // Here is proposed the previous guard (that was wrong): // for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i) // { for (seq_size_type i = 0; i < inL.size(); ++i) if (inL[i]) --edges; if (edges < 0) return; } bool is_tree = (edges == 0); if (is_tree) { func(inL); } else { std::map< vertex_descriptor, default_color_type > vertex_color; std::map< edge_descriptor, default_color_type > edge_color; std::stack< edge_descriptor > iG_buf, vG_buf; bool found = false; seq_size_type m; for (seq_size_type j = 0; j < inL.size() && !found; ++j) { if (!inL[j] && !get(diG, iG_bimap.left.at(j)) && !get(dvG, vG_bimap.left.at(j))) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(aiG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(avG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); if (iG_buf.empty() && vG_buf.empty()) { inL[j] = true; found = true; m = j; } else { while (!iG_buf.empty()) iG_buf.pop(); while (!vG_buf.empty()) vG_buf.pop(); put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } } if (found) { std::stack< edge_descriptor > iG_buf_copy, vG_buf_copy; for (seq_size_type j = 0; j < inL.size(); ++j) { if (!inL[j] && !get(diG, iG_bimap.left.at(j)) && !get(dvG, vG_bimap.left.at(j))) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( aiG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( avG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); if (!iG_buf.empty() || !vG_buf.empty()) { while (!iG_buf.empty()) iG_buf.pop(); while (!vG_buf.empty()) vG_buf.pop(); put(diG, iG_bimap.left.at(j), true); put(dvG, vG_bimap.left.at(j), true); iG_buf_copy.push(iG_bimap.left.at(j)); vG_buf_copy.push(vG_bimap.left.at(j)); } put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } // REC detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq, Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); while (!iG_buf_copy.empty()) { put(diG, iG_buf_copy.top(), false); put(dvG, vG_bimap.left.at(iG_bimap.right.at(iG_buf_copy.top())), false); iG_buf_copy.pop(); } while (!vG_buf_copy.empty()) { put(dvG, vG_buf_copy.top(), false); put(diG, iG_bimap.left.at(vG_bimap.right.at(vG_buf_copy.top())), false); vG_buf_copy.pop(); } inL[m] = false; put(aiG_inL, iG_bimap.left.at(m), false); put(avG_inL, vG_bimap.left.at(m), false); put(diG, iG_bimap.left.at(m), true); put(dvG, vG_bimap.left.at(m), true); std::map< vertex_descriptor, edge_descriptor > tree_map; std::map< vertex_descriptor, vertex_descriptor > pred_map; std::map< vertex_descriptor, int > dist_map, low_map; detail::bridges_visitor< associative_property_map< std::map< vertex_descriptor, edge_descriptor > >, associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >, associative_property_map< std::map< vertex_descriptor, int > >, associative_property_map< std::map< vertex_descriptor, int > >, std::stack< edge_descriptor > > iG_vis(associative_property_map< std::map< vertex_descriptor, edge_descriptor > >( tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >( pred_map), associative_property_map< std::map< vertex_descriptor, int > >(dist_map), associative_property_map< std::map< vertex_descriptor, int > >(low_map), iG_buf), vG_vis(associative_property_map< std::map< vertex_descriptor, edge_descriptor > >( tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >( pred_map), associative_property_map< std::map< vertex_descriptor, int > >(dist_map), associative_property_map< std::map< vertex_descriptor, int > >(low_map), vG_buf); undirected_dfs( make_filtered_graph(iG, detail::deleted_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(diG)), iG_vis, associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); undirected_dfs( make_filtered_graph(vG, detail::deleted_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(dvG)), vG_vis, associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); found = false; std::stack< edge_descriptor > iG_buf_tmp, vG_buf_tmp; while (!iG_buf.empty() && !found) { if (!inL[iG_bimap.right.at(iG_buf.top())]) { put(aiG_inL, iG_buf.top(), true); put(avG_inL, vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( aiG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( avG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { found = true; } else { while (!iG_buf_tmp.empty()) iG_buf_tmp.pop(); while (!vG_buf_tmp.empty()) vG_buf_tmp.pop(); iG_buf_copy.push(iG_buf.top()); } put(aiG_inL, iG_buf.top(), false); put(avG_inL, vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())), false); } iG_buf.pop(); } while (!vG_buf.empty() && !found) { if (!inL[vG_bimap.right.at(vG_buf.top())]) { put(avG_inL, vG_buf.top(), true); put(aiG_inL, iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( aiG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( avG_inL)), make_dfs_visitor(detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf_tmp)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { found = true; } else { while (!iG_buf_tmp.empty()) iG_buf_tmp.pop(); while (!vG_buf_tmp.empty()) vG_buf_tmp.pop(); vG_buf_copy.push(vG_buf.top()); } put(avG_inL, vG_buf.top(), false); put(aiG_inL, iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())), false); } vG_buf.pop(); } if (!found) { while (!iG_buf_copy.empty()) { inL[iG_bimap.right.at(iG_buf_copy.top())] = true; put(aiG_inL, iG_buf_copy.top(), true); put(avG_inL, vG_bimap.left.at( iG_bimap.right.at(iG_buf_copy.top())), true); iG_buf.push(iG_buf_copy.top()); iG_buf_copy.pop(); } while (!vG_buf_copy.empty()) { inL[vG_bimap.right.at(vG_buf_copy.top())] = true; put(avG_inL, vG_buf_copy.top(), true); put(aiG_inL, iG_bimap.left.at( vG_bimap.right.at(vG_buf_copy.top())), true); vG_buf.push(vG_buf_copy.top()); vG_buf_copy.pop(); } // REC detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq, Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); while (!iG_buf.empty()) { inL[iG_bimap.right.at(iG_buf.top())] = false; put(aiG_inL, iG_buf.top(), false); put(avG_inL, vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())), false); iG_buf.pop(); } while (!vG_buf.empty()) { inL[vG_bimap.right.at(vG_buf.top())] = false; put(avG_inL, vG_buf.top(), false); put(aiG_inL, iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())), false); vG_buf.pop(); } } put(diG, iG_bimap.left.at(m), false); put(dvG, vG_bimap.left.at(m), false); } } } } // namespace detail template < typename Coll, typename Seq > struct tree_collector { public: BOOST_CONCEPT_ASSERT((BackInsertionSequence< Coll >)); BOOST_CONCEPT_ASSERT((RandomAccessContainer< Seq >)); BOOST_CONCEPT_ASSERT((CopyConstructible< Seq >)); typedef typename Coll::value_type coll_value_type; typedef typename Seq::value_type seq_value_type; BOOST_STATIC_ASSERT((is_same< coll_value_type, Seq >::value)); BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value)); tree_collector(Coll& seqs) : mSeqs(seqs) {} inline void operator()(Seq seq) { mSeqs.push_back(seq); } private: Coll& mSeqs; }; template < typename Graph, typename Order, typename Func, typename Seq > BOOST_CONCEPT_REQUIRES( ((RandomAccessContainer< Order >))((IncidenceGraphConcept< Graph >))( (UnaryFunction< Func, void, Seq >))( (Mutable_RandomAccessContainer< Seq >))( (VertexAndEdgeListGraphConcept< Graph >)), (void)) two_graphs_common_spanning_trees(const Graph& iG, Order iG_map, const Graph& vG, Order vG_map, Func func, Seq inL) { typedef graph_traits< Graph > GraphTraits; typedef typename GraphTraits::directed_category directed_category; typedef typename GraphTraits::vertex_descriptor vertex_descriptor; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename GraphTraits::edges_size_type edges_size_type; typedef typename GraphTraits::edge_iterator edge_iterator; typedef typename Seq::value_type seq_value_type; typedef typename Seq::size_type seq_size_type; typedef typename Order::value_type order_value_type; typedef typename Order::size_type order_size_type; BOOST_STATIC_ASSERT((is_same< order_value_type, edge_descriptor >::value)); BOOST_CONCEPT_ASSERT((Convertible< order_size_type, edges_size_type >)); BOOST_CONCEPT_ASSERT((Convertible< seq_size_type, edges_size_type >)); BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value)); BOOST_STATIC_ASSERT((is_same< directed_category, undirected_tag >::value)); if (num_vertices(iG) != num_vertices(vG)) return; if (inL.size() != num_edges(iG) || inL.size() != num_edges(vG)) return; if (iG_map.size() != num_edges(iG) || vG_map.size() != num_edges(vG)) return; typedef bimaps::bimap< bimaps::set_of< int >, bimaps::set_of< order_value_type > > bimap_type; typedef typename bimap_type::value_type bimap_value; bimap_type iG_bimap, vG_bimap; for (order_size_type i = 0; i < iG_map.size(); ++i) iG_bimap.insert(bimap_value(i, iG_map[i])); for (order_size_type i = 0; i < vG_map.size(); ++i) vG_bimap.insert(bimap_value(i, vG_map[i])); edge_iterator current, last; boost::tuples::tie(current, last) = edges(iG); for (; current != last; ++current) if (iG_bimap.right.find(*current) == iG_bimap.right.end()) return; boost::tuples::tie(current, last) = edges(vG); for (; current != last; ++current) if (vG_bimap.right.find(*current) == vG_bimap.right.end()) return; std::stack< edge_descriptor > iG_buf, vG_buf; std::map< vertex_descriptor, edge_descriptor > tree_map; std::map< vertex_descriptor, vertex_descriptor > pred_map; std::map< vertex_descriptor, int > dist_map, low_map; detail::bridges_visitor< associative_property_map< std::map< vertex_descriptor, edge_descriptor > >, associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >, associative_property_map< std::map< vertex_descriptor, int > >, associative_property_map< std::map< vertex_descriptor, int > >, std::stack< edge_descriptor > > iG_vis(associative_property_map< std::map< vertex_descriptor, edge_descriptor > >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >(pred_map), associative_property_map< std::map< vertex_descriptor, int > >( dist_map), associative_property_map< std::map< vertex_descriptor, int > >(low_map), iG_buf), vG_vis(associative_property_map< std::map< vertex_descriptor, edge_descriptor > >(tree_map), associative_property_map< std::map< vertex_descriptor, vertex_descriptor > >(pred_map), associative_property_map< std::map< vertex_descriptor, int > >( dist_map), associative_property_map< std::map< vertex_descriptor, int > >( low_map), vG_buf); std::map< vertex_descriptor, default_color_type > vertex_color; std::map< edge_descriptor, default_color_type > edge_color; undirected_dfs(iG, iG_vis, associative_property_map< std::map< vertex_descriptor, default_color_type > >(vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); undirected_dfs(vG, vG_vis, associative_property_map< std::map< vertex_descriptor, default_color_type > >(vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); while (!iG_buf.empty()) { inL[iG_bimap.right.at(iG_buf.top())] = true; iG_buf.pop(); } while (!vG_buf.empty()) { inL[vG_bimap.right.at(vG_buf.top())] = true; vG_buf.pop(); } std::map< edge_descriptor, bool > iG_inL, vG_inL; associative_property_map< std::map< edge_descriptor, bool > > aiG_inL( iG_inL), avG_inL(vG_inL); for (seq_size_type i = 0; i < inL.size(); ++i) { if (inL[i]) { put(aiG_inL, iG_bimap.left.at(i), true); put(avG_inL, vG_bimap.left.at(i), true); } else { put(aiG_inL, iG_bimap.left.at(i), false); put(avG_inL, vG_bimap.left.at(i), false); } } undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >(vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >( avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >(vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >(edge_color)); if (iG_buf.empty() && vG_buf.empty()) { std::map< edge_descriptor, bool > iG_deleted, vG_deleted; associative_property_map< std::map< edge_descriptor, bool > > diG( iG_deleted); associative_property_map< std::map< edge_descriptor, bool > > dvG( vG_deleted); boost::tuples::tie(current, last) = edges(iG); for (; current != last; ++current) put(diG, *current, false); boost::tuples::tie(current, last) = edges(vG); for (; current != last; ++current) put(dvG, *current, false); for (seq_size_type j = 0; j < inL.size(); ++j) { if (!inL[j]) { put(aiG_inL, iG_bimap.left.at(j), true); put(avG_inL, vG_bimap.left.at(j), true); undirected_dfs( make_filtered_graph(iG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(aiG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack< edge_descriptor > >( &iG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); undirected_dfs( make_filtered_graph(vG, detail::inL_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(avG_inL)), make_dfs_visitor( detail::cycle_finder< std::stack< edge_descriptor > >( &vG_buf)), associative_property_map< std::map< vertex_descriptor, default_color_type > >( vertex_color), associative_property_map< std::map< edge_descriptor, default_color_type > >( edge_color)); if (!iG_buf.empty() || !vG_buf.empty()) { while (!iG_buf.empty()) iG_buf.pop(); while (!vG_buf.empty()) vG_buf.pop(); put(diG, iG_bimap.left.at(j), true); put(dvG, vG_bimap.left.at(j), true); } put(aiG_inL, iG_bimap.left.at(j), false); put(avG_inL, vG_bimap.left.at(j), false); } } int cc = 0; std::map< vertex_descriptor, int > com_map; cc += connected_components( make_filtered_graph(iG, detail::deleted_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(diG)), associative_property_map< std::map< vertex_descriptor, int > >( com_map)); cc += connected_components( make_filtered_graph(vG, detail::deleted_edge_status< associative_property_map< std::map< edge_descriptor, bool > > >(dvG)), associative_property_map< std::map< vertex_descriptor, int > >( com_map)); if (cc != 2) return; // REC detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq, associative_property_map< std::map< edge_descriptor, bool > > >( iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); } } template < typename Graph, typename Func, typename Seq > BOOST_CONCEPT_REQUIRES( ((IncidenceGraphConcept< Graph >))((EdgeListGraphConcept< Graph >)), (void)) two_graphs_common_spanning_trees( const Graph& iG, const Graph& vG, Func func, Seq inL) { typedef graph_traits< Graph > GraphTraits; typedef typename GraphTraits::edge_descriptor edge_descriptor; typedef typename GraphTraits::edge_iterator edge_iterator; std::vector< edge_descriptor > iGO, vGO; edge_iterator curr, last; boost::tuples::tie(curr, last) = edges(iG); for (; curr != last; ++curr) iGO.push_back(*curr); boost::tuples::tie(curr, last) = edges(vG); for (; curr != last; ++curr) vGO.push_back(*curr); two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL); } } // namespace boost #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP