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/subgraph.hpp (39996B)

#ifndef BOOST_SUBGRAPH_HPP
#define BOOST_SUBGRAPH_HPP

// UNDER CONSTRUCTION

#include <boost/config.hpp>
#include <list>
#include <vector>
#include <map>
#include <boost/assert.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_mutability_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/iterator/indirect_iterator.hpp>

#include <boost/static_assert.hpp>
#include <boost/assert.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/or.hpp>

namespace boost
{

struct subgraph_tag
{
};

/** @name Property Lookup
 * The local_property and global_property functions are used to create
 * structures that determine the lookup strategy for properties in subgraphs.
 * Note that the nested kind member is used to help interoperate with actual
 * Property types.
 */
//@{
template < typename T > struct local_property
{
    typedef T kind;
    local_property(T x) : value(x) {}
    T value;
};

template < typename T > inline local_property< T > local(T x)
{
    return local_property< T >(x);
}

template < typename T > struct global_property
{
    typedef T kind;
    global_property(T x) : value(x) {}
    T value;
};

template < typename T > inline global_property< T > global(T x)
{
    return global_property< T >(x);
}
//@}

// Invariants of an induced subgraph:
//   - If vertex u is in subgraph g, then u must be in g.parent().
//   - If edge e is in subgraph g, then e must be in g.parent().
//   - If edge e=(u,v) is in the root graph, then edge e
//     is also in any subgraph that contains both vertex u and v.

// The Graph template parameter must have a vertex_index and edge_index
// internal property. It is assumed that the vertex indices are assigned
// automatically by the graph during a call to add_vertex(). It is not
// assumed that the edge vertices are assigned automatically, they are
// explicitly assigned here.

template < typename Graph > class subgraph
{
    typedef graph_traits< Graph > Traits;
    typedef std::list< subgraph< Graph >* > ChildrenList;

public:
    // Graph requirements
    typedef typename Traits::vertex_descriptor vertex_descriptor;
    typedef typename Traits::edge_descriptor edge_descriptor;
    typedef typename Traits::directed_category directed_category;
    typedef typename Traits::edge_parallel_category edge_parallel_category;
    typedef typename Traits::traversal_category traversal_category;

// IncidenceGraph requirements
    typedef typename Traits::out_edge_iterator out_edge_iterator;
    typedef typename Traits::degree_size_type degree_size_type;

// AdjacencyGraph requirements
    typedef typename Traits::adjacency_iterator adjacency_iterator;

// VertexListGraph requirements
    typedef typename Traits::vertex_iterator vertex_iterator;
    typedef typename Traits::vertices_size_type vertices_size_type;

// EdgeListGraph requirements
    typedef typename Traits::edge_iterator edge_iterator;
    typedef typename Traits::edges_size_type edges_size_type;

typedef typename Traits::in_edge_iterator in_edge_iterator;

typedef typename edge_property_type< Graph >::type edge_property_type;
    typedef typename vertex_property_type< Graph >::type vertex_property_type;
    typedef subgraph_tag graph_tag;
    typedef Graph graph_type;
    typedef typename graph_property_type< Graph >::type graph_property_type;

// Create the main graph, the root of the subgraph tree
    subgraph() : m_parent(0), m_edge_counter(0) {}

subgraph(const graph_property_type& p)
    : m_graph(p), m_parent(0), m_edge_counter(0)
    {
    }

subgraph(vertices_size_type n,
        const graph_property_type& p = graph_property_type())
    : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
    {
        typename Graph::vertex_iterator v, v_end;
        vertices_size_type i = 0;
        for (boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
            m_global_vertex[i++] = *v;
    }

// copy constructor
    subgraph(const subgraph& x) : m_parent(x.m_parent), m_edge_counter(0)
    {
        if (x.is_root())
        {
            m_graph = x.m_graph;
            m_edge_counter = x.m_edge_counter;
            m_global_vertex = x.m_global_vertex;
            m_global_edge = x.m_global_edge;
        }
        else
        {
            get_property(*this) = get_property(x);
            typename subgraph< Graph >::vertex_iterator vi, vi_end;
            boost::tie(vi, vi_end) = vertices(x);
            for (; vi != vi_end; ++vi)
            {
                add_vertex(x.local_to_global(*vi), *this);
            }
        }
        // Do a deep copy (recursive).
        // Only the root graph is copied, the subgraphs contain
        // only references to the global vertices they own.
        typename subgraph< Graph >::children_iterator i, i_end;
        boost::tie(i, i_end) = x.children();
        for (; i != i_end; ++i)
        {
            m_children.push_back(new subgraph< Graph >(*i));
            m_children.back()->m_parent = this;
        }
    }

~subgraph()
    {
        for (typename ChildrenList::iterator i = m_children.begin();
             i != m_children.end(); ++i)
        {
            delete *i;
        }
    }

// Return a null vertex descriptor for the graph.
    static vertex_descriptor null_vertex() { return Traits::null_vertex(); }

// Create a subgraph
    subgraph< Graph >& create_subgraph()
    {
        m_children.push_back(new subgraph< Graph >());
        m_children.back()->m_parent = this;
        return *m_children.back();
    }

// Create a subgraph with the specified vertex set.
    template < typename VertexIterator >
    subgraph< Graph >& create_subgraph(
        VertexIterator first, VertexIterator last)
    {
        m_children.push_back(new subgraph< Graph >());
        m_children.back()->m_parent = this;
        for (; first != last; ++first)
        {
            add_vertex(*first, *m_children.back());
        }
        return *m_children.back();
    }

// local <-> global descriptor conversion functions
    vertex_descriptor local_to_global(vertex_descriptor u_local) const
    {
        return is_root() ? u_local : m_global_vertex[u_local];
    }

vertex_descriptor global_to_local(vertex_descriptor u_global) const
    {
        vertex_descriptor u_local;
        bool in_subgraph;
        if (is_root())
            return u_global;
        boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
        BOOST_ASSERT(in_subgraph == true);
        return u_local;
    }

edge_descriptor local_to_global(edge_descriptor e_local) const
    {
        return is_root()
            ? e_local
            : m_global_edge[get(get(edge_index, m_graph), e_local)];
    }

edge_descriptor global_to_local(edge_descriptor e_global) const
    {
        return is_root() ? e_global
                         : (*m_local_edge.find(
                                get(get(edge_index, root().m_graph), e_global)))
                               .second;
    }

// Is vertex u (of the root graph) contained in this subgraph?
    // If so, return the matching local vertex.
    std::pair< vertex_descriptor, bool > find_vertex(
        vertex_descriptor u_global) const
    {
        if (is_root())
            return std::make_pair(u_global, true);
        typename LocalVertexMap::const_iterator i
            = m_local_vertex.find(u_global);
        bool valid = i != m_local_vertex.end();
        return std::make_pair((valid ? (*i).second : null_vertex()), valid);
    }

// Is edge e (of the root graph) contained in this subgraph?
    // If so, return the matching local edge.
    std::pair< edge_descriptor, bool > find_edge(edge_descriptor e_global) const
    {
        if (is_root())
            return std::make_pair(e_global, true);
        typename LocalEdgeMap::const_iterator i
            = m_local_edge.find(get(get(edge_index, root().m_graph), e_global));
        bool valid = i != m_local_edge.end();
        return std::make_pair((valid ? (*i).second : edge_descriptor()), valid);
    }

// Return the parent graph.
    subgraph& parent() { return *m_parent; }
    const subgraph& parent() const { return *m_parent; }

// Return true if this is the root subgraph
    bool is_root() const { return m_parent == 0; }

// Return the root graph of the subgraph tree.
    subgraph& root() { return is_root() ? *this : m_parent->root(); }

const subgraph& root() const
    {
        return is_root() ? *this : m_parent->root();
    }

// Return the children subgraphs of this graph/subgraph.
    // Use a list of pointers because the VC++ std::list doesn't like
    // storing incomplete type.
    typedef indirect_iterator< typename ChildrenList::const_iterator,
        subgraph< Graph >, std::bidirectional_iterator_tag >
        children_iterator;

typedef indirect_iterator< typename ChildrenList::const_iterator,
        subgraph< Graph > const, std::bidirectional_iterator_tag >
        const_children_iterator;

std::pair< const_children_iterator, const_children_iterator >
    children() const
    {
        return std::make_pair(const_children_iterator(m_children.begin()),
            const_children_iterator(m_children.end()));
    }

std::pair< children_iterator, children_iterator > children()
    {
        return std::make_pair(children_iterator(m_children.begin()),
            children_iterator(m_children.end()));
    }

std::size_t num_children() const { return m_children.size(); }

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Defualt property access delegates the lookup to global properties.
    template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type&
    operator[](Descriptor x)
    {
        return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
    }

template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type const&
    operator[](Descriptor x) const
    {
        return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)];
    }

// Local property access returns the local property of the given descripor.
    template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type&
    operator[](local_property< Descriptor > x)
    {
        return m_graph[x.value];
    }

template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type const&
    operator[](local_property< Descriptor > x) const
    {
        return m_graph[x.value];
    }

// Global property access returns the global property associated with the
    // given descriptor. This is an alias for the default bundled property
    // access operations.
    template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type&
    operator[](global_property< Descriptor > x)
    {
        return (*this)[x.value];
    }

template < typename Descriptor >
    typename graph::detail::bundled_result< Graph, Descriptor >::type const&
    operator[](global_property< Descriptor > x) const
    {
        return (*this)[x.value];
    }

#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

//  private:
    typedef typename property_map< Graph, edge_index_t >::type EdgeIndexMap;
    typedef
        typename property_traits< EdgeIndexMap >::value_type edge_index_type;
    BOOST_STATIC_ASSERT((!is_same< edge_index_type,
                         boost::detail::error_property_not_found >::value));

private:
    typedef std::vector< vertex_descriptor > GlobalVertexList;
    typedef std::vector< edge_descriptor > GlobalEdgeList;
    typedef std::map< vertex_descriptor, vertex_descriptor > LocalVertexMap;
    typedef std::map< edge_index_type, edge_descriptor > LocalEdgeMap;
    // TODO: Should the LocalVertexMap be: map<index_type, descriptor>?
    // TODO: Can we relax the indexing requirement if both descriptors are
    // LessThanComparable?
    // TODO: Should we really be using unorderd_map for improved lookup times?

public: // Probably shouldn't be public....
    Graph m_graph;
    subgraph< Graph >* m_parent;
    edge_index_type m_edge_counter; // for generating unique edge indices
    ChildrenList m_children;
    GlobalVertexList m_global_vertex; // local -> global
    LocalVertexMap m_local_vertex; // global -> local
    GlobalEdgeList m_global_edge; // local -> global
    LocalEdgeMap m_local_edge; // global -> local

edge_descriptor local_add_edge(vertex_descriptor u_local,
        vertex_descriptor v_local, edge_descriptor e_global)
    {
        edge_descriptor e_local;
        bool inserted;
        boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
        put(edge_index, m_graph, e_local, m_edge_counter++);
        m_global_edge.push_back(e_global);
        m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
        return e_local;
    }
};

template < typename Graph >
struct vertex_bundle_type< subgraph< Graph > > : vertex_bundle_type< Graph >
{
};

template < typename Graph >
struct edge_bundle_type< subgraph< Graph > > : edge_bundle_type< Graph >
{
};

template < typename Graph >
struct graph_bundle_type< subgraph< Graph > > : graph_bundle_type< Graph >
{
};

//===========================================================================
// Functions special to the Subgraph Class

template < typename G >
typename subgraph< G >::vertex_descriptor add_vertex(
    typename subgraph< G >::vertex_descriptor u_global, subgraph< G >& g)
{
    BOOST_ASSERT(!g.is_root());
    typename subgraph< G >::vertex_descriptor u_local;
    bool exists_local;
    boost::tie(u_local, exists_local) = g.find_vertex(u_global);

if (!exists_local)
    {
        typename subgraph< G >::vertex_descriptor v_global;
        typename subgraph< G >::edge_descriptor e_global;
        // call recursion for parent subgraph
        if (!g.parent().is_root())
            add_vertex(u_global, g.parent());

u_local = add_vertex(g.m_graph);
        g.m_global_vertex.push_back(u_global);
        g.m_local_vertex[u_global] = u_local;

subgraph< G >& r = g.root();

// remember edge global and local maps
        {
            typename subgraph< G >::out_edge_iterator ei, ei_end;
            for (boost::tie(ei, ei_end) = out_edges(u_global, r); ei != ei_end;
                 ++ei)
            {
                e_global = *ei;
                v_global = target(e_global, r);
                if (g.find_vertex(v_global).second == true)
                    g.local_add_edge(
                        u_local, g.global_to_local(v_global), e_global);
            }
        }
        if (is_directed(g))
        { // not necessary for undirected graph
            typename subgraph< G >::vertex_iterator vi, vi_end;
            typename subgraph< G >::out_edge_iterator ei, ei_end;
            for (boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi)
            {
                v_global = *vi;
                if (v_global == u_global)
                    continue; // don't insert self loops twice!
                if (!g.find_vertex(v_global).second)
                    continue; // not a subgraph vertex => try next one
                for (boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end;
                     ++ei)
                {
                    e_global = *ei;
                    if (target(e_global, r) == u_global)
                    {
                        g.local_add_edge(
                            g.global_to_local(v_global), u_local, e_global);
                    }
                }
            }
        }
    }
    return u_local;
}

// NOTE: Descriptors are local unless otherwise noted.

//===========================================================================
// Functions required by the IncidenceGraph concept

template < typename G >
std::pair< typename graph_traits< G >::out_edge_iterator,
    typename graph_traits< G >::out_edge_iterator >
out_edges(
    typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return out_edges(v, g.m_graph);
}

template < typename G >
typename graph_traits< G >::degree_size_type out_degree(
    typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return out_degree(v, g.m_graph);
}

template < typename G >
typename graph_traits< G >::vertex_descriptor source(
    typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
{
    return source(e, g.m_graph);
}

template < typename G >
typename graph_traits< G >::vertex_descriptor target(
    typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g)
{
    return target(e, g.m_graph);
}

//===========================================================================
// Functions required by the BidirectionalGraph concept

template < typename G >
std::pair< typename graph_traits< G >::in_edge_iterator,
    typename graph_traits< G >::in_edge_iterator >
in_edges(
    typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return in_edges(v, g.m_graph);
}

template < typename G >
typename graph_traits< G >::degree_size_type in_degree(
    typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return in_degree(v, g.m_graph);
}

template < typename G >
typename graph_traits< G >::degree_size_type degree(
    typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return degree(v, g.m_graph);
}

//===========================================================================
// Functions required by the AdjacencyGraph concept

template < typename G >
std::pair< typename subgraph< G >::adjacency_iterator,
    typename subgraph< G >::adjacency_iterator >
adjacent_vertices(
    typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return adjacent_vertices(v, g.m_graph);
}

//===========================================================================
// Functions required by the VertexListGraph concept

template < typename G >
std::pair< typename subgraph< G >::vertex_iterator,
    typename subgraph< G >::vertex_iterator >
vertices(const subgraph< G >& g)
{
    return vertices(g.m_graph);
}

template < typename G >
typename subgraph< G >::vertices_size_type num_vertices(const subgraph< G >& g)
{
    return num_vertices(g.m_graph);
}

//===========================================================================
// Functions required by the EdgeListGraph concept

template < typename G >
std::pair< typename subgraph< G >::edge_iterator,
    typename subgraph< G >::edge_iterator >
edges(const subgraph< G >& g)
{
    return edges(g.m_graph);
}

template < typename G >
typename subgraph< G >::edges_size_type num_edges(const subgraph< G >& g)
{
    return num_edges(g.m_graph);
}

//===========================================================================
// Functions required by the AdjacencyMatrix concept

template < typename G >
std::pair< typename subgraph< G >::edge_descriptor, bool > edge(
    typename subgraph< G >::vertex_descriptor u,
    typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g)
{
    return edge(u, v, g.m_graph);
}

//===========================================================================
// Functions required by the MutableGraph concept

namespace detail
{

template < typename Vertex, typename Edge, typename Graph >
    void add_edge_recur_down(
        Vertex u_global, Vertex v_global, Edge e_global, subgraph< Graph >& g);

template < typename Vertex, typename Edge, typename Children, typename G >
    void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
        Children& c, subgraph< G >* orig)
    {
        for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        {
            if ((*i)->find_vertex(u_global).second
                && (*i)->find_vertex(v_global).second)
            {
                add_edge_recur_down(u_global, v_global, e_global, **i, orig);
            }
        }
    }

template < typename Vertex, typename Edge, typename Graph >
    void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global,
        subgraph< Graph >& g, subgraph< Graph >* orig)
    {
        if (&g != orig)
        {
            // add local edge only if u_global and v_global are in subgraph g
            Vertex u_local, v_local;
            bool u_in_subgraph, v_in_subgraph;
            boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
            boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
            if (u_in_subgraph && v_in_subgraph)
            {
                g.local_add_edge(u_local, v_local, e_global);
            }
        }
        children_add_edge(u_global, v_global, e_global, g.m_children, orig);
    }

template < typename Vertex, typename Graph >
    std::pair< typename subgraph< Graph >::edge_descriptor, bool >
    add_edge_recur_up(Vertex u_global, Vertex v_global,
        const typename Graph::edge_property_type& ep, subgraph< Graph >& g,
        subgraph< Graph >* orig)
    {
        if (g.is_root())
        {
            typename subgraph< Graph >::edge_descriptor e_global;
            bool inserted;
            boost::tie(e_global, inserted)
                = add_edge(u_global, v_global, ep, g.m_graph);
            put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
            g.m_global_edge.push_back(e_global);
            children_add_edge(u_global, v_global, e_global, g.m_children, orig);
            return std::make_pair(e_global, inserted);
        }
        else
        {
            return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
        }
    }

} // namespace detail

// Add an edge to the subgraph g, specified by the local vertex descriptors u
// and v. In addition, the edge will be added to any (all) other subgraphs that
// contain vertex descriptors u and v.

template < typename G >
std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge(
    typename subgraph< G >::vertex_descriptor u,
    typename subgraph< G >::vertex_descriptor v,
    const typename G::edge_property_type& ep, subgraph< G >& g)
{
    if (g.is_root())
    {
        // u and v are really global
        return detail::add_edge_recur_up(u, v, ep, g, &g);
    }
    else
    {
        typename subgraph< G >::edge_descriptor e_local, e_global;
        bool inserted;
        boost::tie(e_global, inserted) = detail::add_edge_recur_up(
            g.local_to_global(u), g.local_to_global(v), ep, g, &g);
        e_local = g.local_add_edge(u, v, e_global);
        return std::make_pair(e_local, inserted);
    }
}

namespace detail
{
    //-------------------------------------------------------------------------
    // implementation of remove_edge(u,v,g)
    template < typename Vertex, typename Graph >
    void remove_edge_recur_down(
        Vertex u_global, Vertex v_global, subgraph< Graph >& g);

template < typename Vertex, typename Children >
    void children_remove_edge(Vertex u_global, Vertex v_global, Children& c)
    {
        for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        {
            if ((*i)->find_vertex(u_global).second
                && (*i)->find_vertex(v_global).second)
            {
                remove_edge_recur_down(u_global, v_global, **i);
            }
        }
    }

template < typename Vertex, typename Graph >
    void remove_edge_recur_down(
        Vertex u_global, Vertex v_global, subgraph< Graph >& g)
    {
        Vertex u_local, v_local;
        u_local = g.m_local_vertex[u_global];
        v_local = g.m_local_vertex[v_global];
        remove_edge(u_local, v_local, g.m_graph);
        children_remove_edge(u_global, v_global, g.m_children);
    }

template < typename Vertex, typename Graph >
    void remove_edge_recur_up(
        Vertex u_global, Vertex v_global, subgraph< Graph >& g)
    {
        if (g.is_root())
        {
            remove_edge(u_global, v_global, g.m_graph);
            children_remove_edge(u_global, v_global, g.m_children);
        }
        else
        {
            remove_edge_recur_up(u_global, v_global, *g.m_parent);
        }
    }

//-------------------------------------------------------------------------
    // implementation of remove_edge(e,g)

template < typename G, typename Edge, typename Children >
    void children_remove_edge(Edge e_global, Children& c)
    {
        for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        {
            std::pair< typename subgraph< G >::edge_descriptor, bool > found
                = (*i)->find_edge(e_global);
            if (!found.second)
            {
                continue;
            }
            children_remove_edge< G >(e_global, (*i)->m_children);
            remove_edge(found.first, (*i)->m_graph);
        }
    }

} // namespace detail

template < typename G >
void remove_edge(typename subgraph< G >::vertex_descriptor u,
    typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
{
    if (g.is_root())
    {
        detail::remove_edge_recur_up(u, v, g);
    }
    else
    {
        detail::remove_edge_recur_up(
            g.local_to_global(u), g.local_to_global(v), g);
    }
}

template < typename G >
void remove_edge(typename subgraph< G >::edge_descriptor e, subgraph< G >& g)
{
    typename subgraph< G >::edge_descriptor e_global = g.local_to_global(e);
#ifndef NDEBUG
    std::pair< typename subgraph< G >::edge_descriptor, bool > fe
        = g.find_edge(e_global);
    BOOST_ASSERT(fe.second && fe.first == e);
#endif // NDEBUG
    subgraph< G >& root = g.root(); // chase to root
    detail::children_remove_edge< G >(e_global, root.m_children);
    remove_edge(e_global, root.m_graph); // kick edge from root
}

// This is slow, but there may not be a good way to do it safely otherwise
template < typename Predicate, typename G >
void remove_edge_if(Predicate p, subgraph< G >& g)
{
    while (true)
    {
        bool any_removed = false;
        typedef typename subgraph< G >::edge_iterator ei_type;
        for (std::pair< ei_type, ei_type > ep = edges(g); ep.first != ep.second;
             ++ep.first)
        {
            if (p(*ep.first))
            {
                any_removed = true;
                remove_edge(*ep.first, g);
                break; /* Since iterators may be invalidated */
            }
        }
        if (!any_removed)
            break;
    }
}

template < typename G >
void clear_vertex(typename subgraph< G >::vertex_descriptor v, subgraph< G >& g)
{
    while (true)
    {
        typedef typename subgraph< G >::out_edge_iterator oei_type;
        std::pair< oei_type, oei_type > p = out_edges(v, g);
        if (p.first == p.second)
            break;
        remove_edge(*p.first, g);
    }
}

namespace detail
{
    template < typename G >
    typename subgraph< G >::vertex_descriptor add_vertex_recur_up(
        subgraph< G >& g)
    {
        typename subgraph< G >::vertex_descriptor u_local, u_global;
        if (g.is_root())
        {
            u_global = add_vertex(g.m_graph);
            g.m_global_vertex.push_back(u_global);
        }
        else
        {
            u_global = add_vertex_recur_up(*g.m_parent);
            u_local = add_vertex(g.m_graph);
            g.m_global_vertex.push_back(u_global);
            g.m_local_vertex[u_global] = u_local;
        }
        return u_global;
    }
} // namespace detail

template < typename G >
typename subgraph< G >::vertex_descriptor add_vertex(subgraph< G >& g)
{
    typename subgraph< G >::vertex_descriptor u_local, u_global;
    if (g.is_root())
    {
        u_global = add_vertex(g.m_graph);
        g.m_global_vertex.push_back(u_global);
        u_local = u_global;
    }
    else
    {
        u_global = detail::add_vertex_recur_up(g.parent());
        u_local = add_vertex(g.m_graph);
        g.m_global_vertex.push_back(u_global);
        g.m_local_vertex[u_global] = u_local;
    }
    return u_local;
}

#if 0
// TODO: Under Construction
template <typename G>
void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
{ BOOST_ASSERT(false); }
#endif

//===========================================================================
// Functions required by the PropertyGraph concept

/**
 * The global property map returns the global properties associated with local
 * descriptors.
 */
template < typename GraphPtr, typename PropertyMap, typename Tag >
class subgraph_global_property_map
: public put_get_helper< typename property_traits< PropertyMap >::reference,
      subgraph_global_property_map< GraphPtr, PropertyMap, Tag > >
{
    typedef property_traits< PropertyMap > Traits;

public:
    typedef typename mpl::if_<
        is_const< typename remove_pointer< GraphPtr >::type >,
        readable_property_map_tag, typename Traits::category >::type category;
    typedef typename Traits::value_type value_type;
    typedef typename Traits::key_type key_type;
    typedef typename Traits::reference reference;

subgraph_global_property_map() {}

subgraph_global_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}

reference operator[](key_type e) const
    {
        PropertyMap pmap = get(m_tag, m_g->root().m_graph);
        return m_g->is_root() ? pmap[e] : pmap[m_g->local_to_global(e)];
    }

GraphPtr m_g;
    Tag m_tag;
};

/**
 * The local property map returns the local property associated with the local
 * descriptors.
 */
template < typename GraphPtr, typename PropertyMap, typename Tag >
class subgraph_local_property_map
: public put_get_helper< typename property_traits< PropertyMap >::reference,
      subgraph_local_property_map< GraphPtr, PropertyMap, Tag > >
{
    typedef property_traits< PropertyMap > Traits;

typedef Tag tag;
    typedef PropertyMap pmap;

subgraph_local_property_map() {}

subgraph_local_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {}

reference operator[](key_type e) const
    {
        // Get property map on the underlying graph.
        PropertyMap pmap = get(m_tag, m_g->m_graph);
        return pmap[e];
    }

GraphPtr m_g;
    Tag m_tag;
};

namespace detail
{
    // Extract the actual tags from local or global property maps so we don't
    // try to find non-properties.
    template < typename P > struct extract_lg_tag
    {
        typedef P type;
    };
    template < typename P > struct extract_lg_tag< local_property< P > >
    {
        typedef P type;
    };
    template < typename P > struct extract_lg_tag< global_property< P > >
    {
        typedef P type;
    };

// NOTE: Mysterious Property template parameter unused in both metafunction
    // classes.
    struct subgraph_global_pmap
    {
        template < class Tag, class SubGraph, class Property > struct bind_
        {
            typedef typename SubGraph::graph_type Graph;
            typedef SubGraph* SubGraphPtr;
            typedef const SubGraph* const_SubGraphPtr;
            typedef typename extract_lg_tag< Tag >::type TagType;
            typedef typename property_map< Graph, TagType >::type PMap;
            typedef
                typename property_map< Graph, TagType >::const_type const_PMap;

public:
            typedef subgraph_global_property_map< SubGraphPtr, PMap, TagType >
                type;
            typedef subgraph_global_property_map< const_SubGraphPtr, const_PMap,
                TagType >
                const_type;
        };
    };

struct subgraph_local_pmap
    {
        template < class Tag, class SubGraph, class Property > struct bind_
        {
            typedef typename SubGraph::graph_type Graph;
            typedef SubGraph* SubGraphPtr;
            typedef const SubGraph* const_SubGraphPtr;
            typedef typename extract_lg_tag< Tag >::type TagType;
            typedef typename property_map< Graph, TagType >::type PMap;
            typedef
                typename property_map< Graph, TagType >::const_type const_PMap;

public:
            typedef subgraph_local_property_map< SubGraphPtr, PMap, TagType >
                type;
            typedef subgraph_local_property_map< const_SubGraphPtr, const_PMap,
                TagType >
                const_type;
        };
    };

// These metafunctions select the corresponding metafunctions above, and
    // are used by the choose_pmap metafunction below to specialize the choice
    // of local/global property map. By default, we defer to the global
    // property.
    template < class Tag > struct subgraph_choose_pmap_helper
    {
        typedef subgraph_global_pmap type;
    };
    template < class Tag >
    struct subgraph_choose_pmap_helper< local_property< Tag > >
    {
        typedef subgraph_local_pmap type;
    };
    template < class Tag >
    struct subgraph_choose_pmap_helper< global_property< Tag > >
    {
        typedef subgraph_global_pmap type;
    };

// As above, unless we're requesting vertex_index_t. Then it's always a
    // local property map. This enables the correct translation of descriptors
    // between local and global layers.
    template <> struct subgraph_choose_pmap_helper< vertex_index_t >
    {
        typedef subgraph_local_pmap type;
    };
    template <>
    struct subgraph_choose_pmap_helper< local_property< vertex_index_t > >
    {
        typedef subgraph_local_pmap type;
    };
    template <>
    struct subgraph_choose_pmap_helper< global_property< vertex_index_t > >
    {
        typedef subgraph_local_pmap type;
    };

// Determine the kind of property. If SameType<Tag, vertex_index_t>, then
    // the property lookup is always local. Otherwise, the lookup is global.
    // NOTE: Property parameter is basically unused.
    template < class Tag, class Graph, class Property >
    struct subgraph_choose_pmap
    {
        typedef typename subgraph_choose_pmap_helper< Tag >::type Helper;
        typedef typename Helper::template bind_< Tag, Graph, Property > Bind;
        typedef typename Bind::type type;
        typedef typename Bind::const_type const_type;
    };

// Used by the vertex/edge property selectors to determine the kind(s) of
    // property maps used by the property_map type generator.
    struct subgraph_property_generator
    {
        template < class SubGraph, class Property, class Tag > struct bind_
        {
            typedef subgraph_choose_pmap< Tag, SubGraph, Property > Choice;
            typedef typename Choice::type type;
            typedef typename Choice::const_type const_type;
        };
    };

} // namespace detail

template <> struct vertex_property_selector< subgraph_tag >
{
    typedef detail::subgraph_property_generator type;
};

template <> struct edge_property_selector< subgraph_tag >
{
    typedef detail::subgraph_property_generator type;
};

// ==================================================
// get(p, g), get(p, g, k), and put(p, g, k, v)
// ==================================================
template < typename G, typename Property >
typename property_map< subgraph< G >, Property >::type get(
    Property p, subgraph< G >& g)
{
    typedef typename property_map< subgraph< G >, Property >::type PMap;
    return PMap(&g, p);
}

template < typename G, typename Property >
typename property_map< subgraph< G >, Property >::const_type get(
    Property p, const subgraph< G >& g)
{
    typedef typename property_map< subgraph< G >, Property >::const_type PMap;
    return PMap(&g, p);
}

template < typename G, typename Property, typename Key >
typename property_traits<
    typename property_map< subgraph< G >, Property >::const_type >::value_type
get(Property p, const subgraph< G >& g, const Key& k)
{
    typedef typename property_map< subgraph< G >, Property >::const_type PMap;
    PMap pmap(&g, p);
    return pmap[k];
}

template < typename G, typename Property, typename Key, typename Value >
void put(Property p, subgraph< G >& g, const Key& k, const Value& val)
{
    typedef typename property_map< subgraph< G >, Property >::type PMap;
    PMap pmap(&g, p);
    pmap[k] = val;
}

// ==================================================
// get(global(p), g)
// NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported
// ==================================================
template < typename G, typename Property >
typename property_map< subgraph< G >, global_property< Property > >::type get(
    global_property< Property > p, subgraph< G >& g)
{
    typedef typename property_map< subgraph< G >,
        global_property< Property > >::type Map;
    return Map(&g, p.value);
}

template < typename G, typename Property >
typename property_map< subgraph< G >, global_property< Property > >::const_type
get(global_property< Property > p, const subgraph< G >& g)
{
    typedef typename property_map< subgraph< G >,
        global_property< Property > >::const_type Map;
    return Map(&g, p.value);
}

// ==================================================
// get(local(p), g)
// NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported
// ==================================================
template < typename G, typename Property >
typename property_map< subgraph< G >, local_property< Property > >::type get(
    local_property< Property > p, subgraph< G >& g)
{
    typedef
        typename property_map< subgraph< G >, local_property< Property > >::type
            Map;
    return Map(&g, p.value);
}

template < typename G, typename Property >
typename property_map< subgraph< G >, local_property< Property > >::const_type
get(local_property< Property > p, const subgraph< G >& g)
{
    typedef typename property_map< subgraph< G >,
        local_property< Property > >::const_type Map;
    return Map(&g, p.value);
}

template < typename G, typename Tag >
inline typename graph_property< G, Tag >::type& get_property(
    subgraph< G >& g, Tag tag)
{
    return get_property(g.m_graph, tag);
}

template < typename G, typename Tag >
inline const typename graph_property< G, Tag >::type& get_property(
    const subgraph< G >& g, Tag tag)
{
    return get_property(g.m_graph, tag);
}

//===========================================================================
// Miscellaneous Functions

template < typename G >
typename subgraph< G >::vertex_descriptor vertex(
    typename subgraph< G >::vertices_size_type n, const subgraph< G >& g)
{
    return vertex(n, g.m_graph);
}

//===========================================================================
// Mutability Traits
// Just pull the mutability traits form the underlying graph. Note that this
// will probably fail (badly) for labeled graphs.
template < typename G > struct graph_mutability_traits< subgraph< G > >
{
    typedef typename graph_mutability_traits< G >::category category;
};

} // namespace boost

#endif // BOOST_SUBGRAPH_HPP

//======================================================================= // Copyright 2001 University of Notre Dame. // Authors: Jeremy G. Siek and Lie-Quan Lee // // 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) //======================================================================= #ifndef BOOST_SUBGRAPH_HPP #define BOOST_SUBGRAPH_HPP // UNDER CONSTRUCTION #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace boost { struct subgraph_tag { }; /** @name Property Lookup * The local_property and global_property functions are used to create * structures that determine the lookup strategy for properties in subgraphs. * Note that the nested kind member is used to help interoperate with actual * Property types. */ //@{ template < typename T > struct local_property { typedef T kind; local_property(T x) : value(x) {} T value; }; template < typename T > inline local_property< T > local(T x) { return local_property< T >(x); } template < typename T > struct global_property { typedef T kind; global_property(T x) : value(x) {} T value; }; template < typename T > inline global_property< T > global(T x) { return global_property< T >(x); } //@} // Invariants of an induced subgraph: // - If vertex u is in subgraph g, then u must be in g.parent(). // - If edge e is in subgraph g, then e must be in g.parent(). // - If edge e=(u,v) is in the root graph, then edge e // is also in any subgraph that contains both vertex u and v. // The Graph template parameter must have a vertex_index and edge_index // internal property. It is assumed that the vertex indices are assigned // automatically by the graph during a call to add_vertex(). It is not // assumed that the edge vertices are assigned automatically, they are // explicitly assigned here. template < typename Graph > class subgraph { typedef graph_traits< Graph > Traits; typedef std::list< subgraph< Graph >* > ChildrenList; public: // Graph requirements typedef typename Traits::vertex_descriptor vertex_descriptor; typedef typename Traits::edge_descriptor edge_descriptor; typedef typename Traits::directed_category directed_category; typedef typename Traits::edge_parallel_category edge_parallel_category; typedef typename Traits::traversal_category traversal_category; // IncidenceGraph requirements typedef typename Traits::out_edge_iterator out_edge_iterator; typedef typename Traits::degree_size_type degree_size_type; // AdjacencyGraph requirements typedef typename Traits::adjacency_iterator adjacency_iterator; // VertexListGraph requirements typedef typename Traits::vertex_iterator vertex_iterator; typedef typename Traits::vertices_size_type vertices_size_type; // EdgeListGraph requirements typedef typename Traits::edge_iterator edge_iterator; typedef typename Traits::edges_size_type edges_size_type; typedef typename Traits::in_edge_iterator in_edge_iterator; typedef typename edge_property_type< Graph >::type edge_property_type; typedef typename vertex_property_type< Graph >::type vertex_property_type; typedef subgraph_tag graph_tag; typedef Graph graph_type; typedef typename graph_property_type< Graph >::type graph_property_type; // Create the main graph, the root of the subgraph tree subgraph() : m_parent(0), m_edge_counter(0) {} subgraph(const graph_property_type& p) : m_graph(p), m_parent(0), m_edge_counter(0) { } subgraph(vertices_size_type n, const graph_property_type& p = graph_property_type()) : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n) { typename Graph::vertex_iterator v, v_end; vertices_size_type i = 0; for (boost::tie(v, v_end) = vertices(m_graph); v != v_end; ++v) m_global_vertex[i++] = *v; } // copy constructor subgraph(const subgraph& x) : m_parent(x.m_parent), m_edge_counter(0) { if (x.is_root()) { m_graph = x.m_graph; m_edge_counter = x.m_edge_counter; m_global_vertex = x.m_global_vertex; m_global_edge = x.m_global_edge; } else { get_property(*this) = get_property(x); typename subgraph< Graph >::vertex_iterator vi, vi_end; boost::tie(vi, vi_end) = vertices(x); for (; vi != vi_end; ++vi) { add_vertex(x.local_to_global(*vi), *this); } } // Do a deep copy (recursive). // Only the root graph is copied, the subgraphs contain // only references to the global vertices they own. typename subgraph< Graph >::children_iterator i, i_end; boost::tie(i, i_end) = x.children(); for (; i != i_end; ++i) { m_children.push_back(new subgraph< Graph >(*i)); m_children.back()->m_parent = this; } } ~subgraph() { for (typename ChildrenList::iterator i = m_children.begin(); i != m_children.end(); ++i) { delete *i; } } // Return a null vertex descriptor for the graph. static vertex_descriptor null_vertex() { return Traits::null_vertex(); } // Create a subgraph subgraph< Graph >& create_subgraph() { m_children.push_back(new subgraph< Graph >()); m_children.back()->m_parent = this; return *m_children.back(); } // Create a subgraph with the specified vertex set. template < typename VertexIterator > subgraph< Graph >& create_subgraph( VertexIterator first, VertexIterator last) { m_children.push_back(new subgraph< Graph >()); m_children.back()->m_parent = this; for (; first != last; ++first) { add_vertex(*first, *m_children.back()); } return *m_children.back(); } // local <-> global descriptor conversion functions vertex_descriptor local_to_global(vertex_descriptor u_local) const { return is_root() ? u_local : m_global_vertex[u_local]; } vertex_descriptor global_to_local(vertex_descriptor u_global) const { vertex_descriptor u_local; bool in_subgraph; if (is_root()) return u_global; boost::tie(u_local, in_subgraph) = this->find_vertex(u_global); BOOST_ASSERT(in_subgraph == true); return u_local; } edge_descriptor local_to_global(edge_descriptor e_local) const { return is_root() ? e_local : m_global_edge[get(get(edge_index, m_graph), e_local)]; } edge_descriptor global_to_local(edge_descriptor e_global) const { return is_root() ? e_global : (*m_local_edge.find( get(get(edge_index, root().m_graph), e_global))) .second; } // Is vertex u (of the root graph) contained in this subgraph? // If so, return the matching local vertex. std::pair< vertex_descriptor, bool > find_vertex( vertex_descriptor u_global) const { if (is_root()) return std::make_pair(u_global, true); typename LocalVertexMap::const_iterator i = m_local_vertex.find(u_global); bool valid = i != m_local_vertex.end(); return std::make_pair((valid ? (*i).second : null_vertex()), valid); } // Is edge e (of the root graph) contained in this subgraph? // If so, return the matching local edge. std::pair< edge_descriptor, bool > find_edge(edge_descriptor e_global) const { if (is_root()) return std::make_pair(e_global, true); typename LocalEdgeMap::const_iterator i = m_local_edge.find(get(get(edge_index, root().m_graph), e_global)); bool valid = i != m_local_edge.end(); return std::make_pair((valid ? (*i).second : edge_descriptor()), valid); } // Return the parent graph. subgraph& parent() { return *m_parent; } const subgraph& parent() const { return *m_parent; } // Return true if this is the root subgraph bool is_root() const { return m_parent == 0; } // Return the root graph of the subgraph tree. subgraph& root() { return is_root() ? *this : m_parent->root(); } const subgraph& root() const { return is_root() ? *this : m_parent->root(); } // Return the children subgraphs of this graph/subgraph. // Use a list of pointers because the VC++ std::list doesn't like // storing incomplete type. typedef indirect_iterator< typename ChildrenList::const_iterator, subgraph< Graph >, std::bidirectional_iterator_tag > children_iterator; typedef indirect_iterator< typename ChildrenList::const_iterator, subgraph< Graph > const, std::bidirectional_iterator_tag > const_children_iterator; std::pair< const_children_iterator, const_children_iterator > children() const { return std::make_pair(const_children_iterator(m_children.begin()), const_children_iterator(m_children.end())); } std::pair< children_iterator, children_iterator > children() { return std::make_pair(children_iterator(m_children.begin()), children_iterator(m_children.end())); } std::size_t num_children() const { return m_children.size(); } #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES // Defualt property access delegates the lookup to global properties. template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type& operator[](Descriptor x) { return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; } template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type const& operator[](Descriptor x) const { return is_root() ? m_graph[x] : root().m_graph[local_to_global(x)]; } // Local property access returns the local property of the given descripor. template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type& operator[](local_property< Descriptor > x) { return m_graph[x.value]; } template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type const& operator[](local_property< Descriptor > x) const { return m_graph[x.value]; } // Global property access returns the global property associated with the // given descriptor. This is an alias for the default bundled property // access operations. template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type& operator[](global_property< Descriptor > x) { return (*this)[x.value]; } template < typename Descriptor > typename graph::detail::bundled_result< Graph, Descriptor >::type const& operator[](global_property< Descriptor > x) const { return (*this)[x.value]; } #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES // private: typedef typename property_map< Graph, edge_index_t >::type EdgeIndexMap; typedef typename property_traits< EdgeIndexMap >::value_type edge_index_type; BOOST_STATIC_ASSERT((!is_same< edge_index_type, boost::detail::error_property_not_found >::value)); private: typedef std::vector< vertex_descriptor > GlobalVertexList; typedef std::vector< edge_descriptor > GlobalEdgeList; typedef std::map< vertex_descriptor, vertex_descriptor > LocalVertexMap; typedef std::map< edge_index_type, edge_descriptor > LocalEdgeMap; // TODO: Should the LocalVertexMap be: map? // TODO: Can we relax the indexing requirement if both descriptors are // LessThanComparable? // TODO: Should we really be using unorderd_map for improved lookup times? public: // Probably shouldn't be public.... Graph m_graph; subgraph< Graph >* m_parent; edge_index_type m_edge_counter; // for generating unique edge indices ChildrenList m_children; GlobalVertexList m_global_vertex; // local -> global LocalVertexMap m_local_vertex; // global -> local GlobalEdgeList m_global_edge; // local -> global LocalEdgeMap m_local_edge; // global -> local edge_descriptor local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local, edge_descriptor e_global) { edge_descriptor e_local; bool inserted; boost::tie(e_local, inserted) = add_edge(u_local, v_local, m_graph); put(edge_index, m_graph, e_local, m_edge_counter++); m_global_edge.push_back(e_global); m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local; return e_local; } }; template < typename Graph > struct vertex_bundle_type< subgraph< Graph > > : vertex_bundle_type< Graph > { }; template < typename Graph > struct edge_bundle_type< subgraph< Graph > > : edge_bundle_type< Graph > { }; template < typename Graph > struct graph_bundle_type< subgraph< Graph > > : graph_bundle_type< Graph > { }; //=========================================================================== // Functions special to the Subgraph Class template < typename G > typename subgraph< G >::vertex_descriptor add_vertex( typename subgraph< G >::vertex_descriptor u_global, subgraph< G >& g) { BOOST_ASSERT(!g.is_root()); typename subgraph< G >::vertex_descriptor u_local; bool exists_local; boost::tie(u_local, exists_local) = g.find_vertex(u_global); if (!exists_local) { typename subgraph< G >::vertex_descriptor v_global; typename subgraph< G >::edge_descriptor e_global; // call recursion for parent subgraph if (!g.parent().is_root()) add_vertex(u_global, g.parent()); u_local = add_vertex(g.m_graph); g.m_global_vertex.push_back(u_global); g.m_local_vertex[u_global] = u_local; subgraph< G >& r = g.root(); // remember edge global and local maps { typename subgraph< G >::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u_global, r); ei != ei_end; ++ei) { e_global = *ei; v_global = target(e_global, r); if (g.find_vertex(v_global).second == true) g.local_add_edge( u_local, g.global_to_local(v_global), e_global); } } if (is_directed(g)) { // not necessary for undirected graph typename subgraph< G >::vertex_iterator vi, vi_end; typename subgraph< G >::out_edge_iterator ei, ei_end; for (boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) { v_global = *vi; if (v_global == u_global) continue; // don't insert self loops twice! if (!g.find_vertex(v_global).second) continue; // not a subgraph vertex => try next one for (boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) { e_global = *ei; if (target(e_global, r) == u_global) { g.local_add_edge( g.global_to_local(v_global), u_local, e_global); } } } } } return u_local; } // NOTE: Descriptors are local unless otherwise noted. //=========================================================================== // Functions required by the IncidenceGraph concept template < typename G > std::pair< typename graph_traits< G >::out_edge_iterator, typename graph_traits< G >::out_edge_iterator > out_edges( typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g) { return out_edges(v, g.m_graph); } template < typename G > typename graph_traits< G >::degree_size_type out_degree( typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g) { return out_degree(v, g.m_graph); } template < typename G > typename graph_traits< G >::vertex_descriptor source( typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g) { return source(e, g.m_graph); } template < typename G > typename graph_traits< G >::vertex_descriptor target( typename graph_traits< G >::edge_descriptor e, const subgraph< G >& g) { return target(e, g.m_graph); } //=========================================================================== // Functions required by the BidirectionalGraph concept template < typename G > std::pair< typename graph_traits< G >::in_edge_iterator, typename graph_traits< G >::in_edge_iterator > in_edges( typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g) { return in_edges(v, g.m_graph); } template < typename G > typename graph_traits< G >::degree_size_type in_degree( typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g) { return in_degree(v, g.m_graph); } template < typename G > typename graph_traits< G >::degree_size_type degree( typename graph_traits< G >::vertex_descriptor v, const subgraph< G >& g) { return degree(v, g.m_graph); } //=========================================================================== // Functions required by the AdjacencyGraph concept template < typename G > std::pair< typename subgraph< G >::adjacency_iterator, typename subgraph< G >::adjacency_iterator > adjacent_vertices( typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g) { return adjacent_vertices(v, g.m_graph); } //=========================================================================== // Functions required by the VertexListGraph concept template < typename G > std::pair< typename subgraph< G >::vertex_iterator, typename subgraph< G >::vertex_iterator > vertices(const subgraph< G >& g) { return vertices(g.m_graph); } template < typename G > typename subgraph< G >::vertices_size_type num_vertices(const subgraph< G >& g) { return num_vertices(g.m_graph); } //=========================================================================== // Functions required by the EdgeListGraph concept template < typename G > std::pair< typename subgraph< G >::edge_iterator, typename subgraph< G >::edge_iterator > edges(const subgraph< G >& g) { return edges(g.m_graph); } template < typename G > typename subgraph< G >::edges_size_type num_edges(const subgraph< G >& g) { return num_edges(g.m_graph); } //=========================================================================== // Functions required by the AdjacencyMatrix concept template < typename G > std::pair< typename subgraph< G >::edge_descriptor, bool > edge( typename subgraph< G >::vertex_descriptor u, typename subgraph< G >::vertex_descriptor v, const subgraph< G >& g) { return edge(u, v, g.m_graph); } //=========================================================================== // Functions required by the MutableGraph concept namespace detail { template < typename Vertex, typename Edge, typename Graph > void add_edge_recur_down( Vertex u_global, Vertex v_global, Edge e_global, subgraph< Graph >& g); template < typename Vertex, typename Edge, typename Children, typename G > void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global, Children& c, subgraph< G >* orig) { for (typename Children::iterator i = c.begin(); i != c.end(); ++i) { if ((*i)->find_vertex(u_global).second && (*i)->find_vertex(v_global).second) { add_edge_recur_down(u_global, v_global, e_global, **i, orig); } } } template < typename Vertex, typename Edge, typename Graph > void add_edge_recur_down(Vertex u_global, Vertex v_global, Edge e_global, subgraph< Graph >& g, subgraph< Graph >* orig) { if (&g != orig) { // add local edge only if u_global and v_global are in subgraph g Vertex u_local, v_local; bool u_in_subgraph, v_in_subgraph; boost::tie(u_local, u_in_subgraph) = g.find_vertex(u_global); boost::tie(v_local, v_in_subgraph) = g.find_vertex(v_global); if (u_in_subgraph && v_in_subgraph) { g.local_add_edge(u_local, v_local, e_global); } } children_add_edge(u_global, v_global, e_global, g.m_children, orig); } template < typename Vertex, typename Graph > std::pair< typename subgraph< Graph >::edge_descriptor, bool > add_edge_recur_up(Vertex u_global, Vertex v_global, const typename Graph::edge_property_type& ep, subgraph< Graph >& g, subgraph< Graph >* orig) { if (g.is_root()) { typename subgraph< Graph >::edge_descriptor e_global; bool inserted; boost::tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph); put(edge_index, g.m_graph, e_global, g.m_edge_counter++); g.m_global_edge.push_back(e_global); children_add_edge(u_global, v_global, e_global, g.m_children, orig); return std::make_pair(e_global, inserted); } else { return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig); } } } // namespace detail // Add an edge to the subgraph g, specified by the local vertex descriptors u // and v. In addition, the edge will be added to any (all) other subgraphs that // contain vertex descriptors u and v. template < typename G > std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge( typename subgraph< G >::vertex_descriptor u, typename subgraph< G >::vertex_descriptor v, const typename G::edge_property_type& ep, subgraph< G >& g) { if (g.is_root()) { // u and v are really global return detail::add_edge_recur_up(u, v, ep, g, &g); } else { typename subgraph< G >::edge_descriptor e_local, e_global; bool inserted; boost::tie(e_global, inserted) = detail::add_edge_recur_up( g.local_to_global(u), g.local_to_global(v), ep, g, &g); e_local = g.local_add_edge(u, v, e_global); return std::make_pair(e_local, inserted); } } template < typename G > std::pair< typename subgraph< G >::edge_descriptor, bool > add_edge( typename subgraph< G >::vertex_descriptor u, typename subgraph< G >::vertex_descriptor v, subgraph< G >& g) { return add_edge(u, v, typename G::edge_property_type(), g); } namespace detail { //------------------------------------------------------------------------- // implementation of remove_edge(u,v,g) template < typename Vertex, typename Graph > void remove_edge_recur_down( Vertex u_global, Vertex v_global, subgraph< Graph >& g); template < typename Vertex, typename Children > void children_remove_edge(Vertex u_global, Vertex v_global, Children& c) { for (typename Children::iterator i = c.begin(); i != c.end(); ++i) { if ((*i)->find_vertex(u_global).second && (*i)->find_vertex(v_global).second) { remove_edge_recur_down(u_global, v_global, **i); } } } template < typename Vertex, typename Graph > void remove_edge_recur_down( Vertex u_global, Vertex v_global, subgraph< Graph >& g) { Vertex u_local, v_local; u_local = g.m_local_vertex[u_global]; v_local = g.m_local_vertex[v_global]; remove_edge(u_local, v_local, g.m_graph); children_remove_edge(u_global, v_global, g.m_children); } template < typename Vertex, typename Graph > void remove_edge_recur_up( Vertex u_global, Vertex v_global, subgraph< Graph >& g) { if (g.is_root()) { remove_edge(u_global, v_global, g.m_graph); children_remove_edge(u_global, v_global, g.m_children); } else { remove_edge_recur_up(u_global, v_global, *g.m_parent); } } //------------------------------------------------------------------------- // implementation of remove_edge(e,g) template < typename G, typename Edge, typename Children > void children_remove_edge(Edge e_global, Children& c) { for (typename Children::iterator i = c.begin(); i != c.end(); ++i) { std::pair< typename subgraph< G >::edge_descriptor, bool > found = (*i)->find_edge(e_global); if (!found.second) { continue; } children_remove_edge< G >(e_global, (*i)->m_children); remove_edge(found.first, (*i)->m_graph); } } } // namespace detail template < typename G > void remove_edge(typename subgraph< G >::vertex_descriptor u, typename subgraph< G >::vertex_descriptor v, subgraph< G >& g) { if (g.is_root()) { detail::remove_edge_recur_up(u, v, g); } else { detail::remove_edge_recur_up( g.local_to_global(u), g.local_to_global(v), g); } } template < typename G > void remove_edge(typename subgraph< G >::edge_descriptor e, subgraph< G >& g) { typename subgraph< G >::edge_descriptor e_global = g.local_to_global(e); #ifndef NDEBUG std::pair< typename subgraph< G >::edge_descriptor, bool > fe = g.find_edge(e_global); BOOST_ASSERT(fe.second && fe.first == e); #endif // NDEBUG subgraph< G >& root = g.root(); // chase to root detail::children_remove_edge< G >(e_global, root.m_children); remove_edge(e_global, root.m_graph); // kick edge from root } // This is slow, but there may not be a good way to do it safely otherwise template < typename Predicate, typename G > void remove_edge_if(Predicate p, subgraph< G >& g) { while (true) { bool any_removed = false; typedef typename subgraph< G >::edge_iterator ei_type; for (std::pair< ei_type, ei_type > ep = edges(g); ep.first != ep.second; ++ep.first) { if (p(*ep.first)) { any_removed = true; remove_edge(*ep.first, g); break; /* Since iterators may be invalidated */ } } if (!any_removed) break; } } template < typename G > void clear_vertex(typename subgraph< G >::vertex_descriptor v, subgraph< G >& g) { while (true) { typedef typename subgraph< G >::out_edge_iterator oei_type; std::pair< oei_type, oei_type > p = out_edges(v, g); if (p.first == p.second) break; remove_edge(*p.first, g); } } namespace detail { template < typename G > typename subgraph< G >::vertex_descriptor add_vertex_recur_up( subgraph< G >& g) { typename subgraph< G >::vertex_descriptor u_local, u_global; if (g.is_root()) { u_global = add_vertex(g.m_graph); g.m_global_vertex.push_back(u_global); } else { u_global = add_vertex_recur_up(*g.m_parent); u_local = add_vertex(g.m_graph); g.m_global_vertex.push_back(u_global); g.m_local_vertex[u_global] = u_local; } return u_global; } } // namespace detail template < typename G > typename subgraph< G >::vertex_descriptor add_vertex(subgraph< G >& g) { typename subgraph< G >::vertex_descriptor u_local, u_global; if (g.is_root()) { u_global = add_vertex(g.m_graph); g.m_global_vertex.push_back(u_global); u_local = u_global; } else { u_global = detail::add_vertex_recur_up(g.parent()); u_local = add_vertex(g.m_graph); g.m_global_vertex.push_back(u_global); g.m_local_vertex[u_global] = u_local; } return u_local; } #if 0 // TODO: Under Construction template void remove_vertex(typename subgraph::vertex_descriptor u, subgraph& g) { BOOST_ASSERT(false); } #endif //=========================================================================== // Functions required by the PropertyGraph concept /** * The global property map returns the global properties associated with local * descriptors. */ template < typename GraphPtr, typename PropertyMap, typename Tag > class subgraph_global_property_map : public put_get_helper< typename property_traits< PropertyMap >::reference, subgraph_global_property_map< GraphPtr, PropertyMap, Tag > > { typedef property_traits< PropertyMap > Traits; public: typedef typename mpl::if_< is_const< typename remove_pointer< GraphPtr >::type >, readable_property_map_tag, typename Traits::category >::type category; typedef typename Traits::value_type value_type; typedef typename Traits::key_type key_type; typedef typename Traits::reference reference; subgraph_global_property_map() {} subgraph_global_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {} reference operator[](key_type e) const { PropertyMap pmap = get(m_tag, m_g->root().m_graph); return m_g->is_root() ? pmap[e] : pmap[m_g->local_to_global(e)]; } GraphPtr m_g; Tag m_tag; }; /** * The local property map returns the local property associated with the local * descriptors. */ template < typename GraphPtr, typename PropertyMap, typename Tag > class subgraph_local_property_map : public put_get_helper< typename property_traits< PropertyMap >::reference, subgraph_local_property_map< GraphPtr, PropertyMap, Tag > > { typedef property_traits< PropertyMap > Traits; public: typedef typename mpl::if_< is_const< typename remove_pointer< GraphPtr >::type >, readable_property_map_tag, typename Traits::category >::type category; typedef typename Traits::value_type value_type; typedef typename Traits::key_type key_type; typedef typename Traits::reference reference; typedef Tag tag; typedef PropertyMap pmap; subgraph_local_property_map() {} subgraph_local_property_map(GraphPtr g, Tag tag) : m_g(g), m_tag(tag) {} reference operator[](key_type e) const { // Get property map on the underlying graph. PropertyMap pmap = get(m_tag, m_g->m_graph); return pmap[e]; } GraphPtr m_g; Tag m_tag; }; namespace detail { // Extract the actual tags from local or global property maps so we don't // try to find non-properties. template < typename P > struct extract_lg_tag { typedef P type; }; template < typename P > struct extract_lg_tag< local_property< P > > { typedef P type; }; template < typename P > struct extract_lg_tag< global_property< P > > { typedef P type; }; // NOTE: Mysterious Property template parameter unused in both metafunction // classes. struct subgraph_global_pmap { template < class Tag, class SubGraph, class Property > struct bind_ { typedef typename SubGraph::graph_type Graph; typedef SubGraph* SubGraphPtr; typedef const SubGraph* const_SubGraphPtr; typedef typename extract_lg_tag< Tag >::type TagType; typedef typename property_map< Graph, TagType >::type PMap; typedef typename property_map< Graph, TagType >::const_type const_PMap; public: typedef subgraph_global_property_map< SubGraphPtr, PMap, TagType > type; typedef subgraph_global_property_map< const_SubGraphPtr, const_PMap, TagType > const_type; }; }; struct subgraph_local_pmap { template < class Tag, class SubGraph, class Property > struct bind_ { typedef typename SubGraph::graph_type Graph; typedef SubGraph* SubGraphPtr; typedef const SubGraph* const_SubGraphPtr; typedef typename extract_lg_tag< Tag >::type TagType; typedef typename property_map< Graph, TagType >::type PMap; typedef typename property_map< Graph, TagType >::const_type const_PMap; public: typedef subgraph_local_property_map< SubGraphPtr, PMap, TagType > type; typedef subgraph_local_property_map< const_SubGraphPtr, const_PMap, TagType > const_type; }; }; // These metafunctions select the corresponding metafunctions above, and // are used by the choose_pmap metafunction below to specialize the choice // of local/global property map. By default, we defer to the global // property. template < class Tag > struct subgraph_choose_pmap_helper { typedef subgraph_global_pmap type; }; template < class Tag > struct subgraph_choose_pmap_helper< local_property< Tag > > { typedef subgraph_local_pmap type; }; template < class Tag > struct subgraph_choose_pmap_helper< global_property< Tag > > { typedef subgraph_global_pmap type; }; // As above, unless we're requesting vertex_index_t. Then it's always a // local property map. This enables the correct translation of descriptors // between local and global layers. template <> struct subgraph_choose_pmap_helper< vertex_index_t > { typedef subgraph_local_pmap type; }; template <> struct subgraph_choose_pmap_helper< local_property< vertex_index_t > > { typedef subgraph_local_pmap type; }; template <> struct subgraph_choose_pmap_helper< global_property< vertex_index_t > > { typedef subgraph_local_pmap type; }; // Determine the kind of property. If SameType, then // the property lookup is always local. Otherwise, the lookup is global. // NOTE: Property parameter is basically unused. template < class Tag, class Graph, class Property > struct subgraph_choose_pmap { typedef typename subgraph_choose_pmap_helper< Tag >::type Helper; typedef typename Helper::template bind_< Tag, Graph, Property > Bind; typedef typename Bind::type type; typedef typename Bind::const_type const_type; }; // Used by the vertex/edge property selectors to determine the kind(s) of // property maps used by the property_map type generator. struct subgraph_property_generator { template < class SubGraph, class Property, class Tag > struct bind_ { typedef subgraph_choose_pmap< Tag, SubGraph, Property > Choice; typedef typename Choice::type type; typedef typename Choice::const_type const_type; }; }; } // namespace detail template <> struct vertex_property_selector< subgraph_tag > { typedef detail::subgraph_property_generator type; }; template <> struct edge_property_selector< subgraph_tag > { typedef detail::subgraph_property_generator type; }; // ================================================== // get(p, g), get(p, g, k), and put(p, g, k, v) // ================================================== template < typename G, typename Property > typename property_map< subgraph< G >, Property >::type get( Property p, subgraph< G >& g) { typedef typename property_map< subgraph< G >, Property >::type PMap; return PMap(&g, p); } template < typename G, typename Property > typename property_map< subgraph< G >, Property >::const_type get( Property p, const subgraph< G >& g) { typedef typename property_map< subgraph< G >, Property >::const_type PMap; return PMap(&g, p); } template < typename G, typename Property, typename Key > typename property_traits< typename property_map< subgraph< G >, Property >::const_type >::value_type get(Property p, const subgraph< G >& g, const Key& k) { typedef typename property_map< subgraph< G >, Property >::const_type PMap; PMap pmap(&g, p); return pmap[k]; } template < typename G, typename Property, typename Key, typename Value > void put(Property p, subgraph< G >& g, const Key& k, const Value& val) { typedef typename property_map< subgraph< G >, Property >::type PMap; PMap pmap(&g, p); pmap[k] = val; } // ================================================== // get(global(p), g) // NOTE: get(global(p), g, k) and put(global(p), g, k, v) not supported // ================================================== template < typename G, typename Property > typename property_map< subgraph< G >, global_property< Property > >::type get( global_property< Property > p, subgraph< G >& g) { typedef typename property_map< subgraph< G >, global_property< Property > >::type Map; return Map(&g, p.value); } template < typename G, typename Property > typename property_map< subgraph< G >, global_property< Property > >::const_type get(global_property< Property > p, const subgraph< G >& g) { typedef typename property_map< subgraph< G >, global_property< Property > >::const_type Map; return Map(&g, p.value); } // ================================================== // get(local(p), g) // NOTE: get(local(p), g, k) and put(local(p), g, k, v) not supported // ================================================== template < typename G, typename Property > typename property_map< subgraph< G >, local_property< Property > >::type get( local_property< Property > p, subgraph< G >& g) { typedef typename property_map< subgraph< G >, local_property< Property > >::type Map; return Map(&g, p.value); } template < typename G, typename Property > typename property_map< subgraph< G >, local_property< Property > >::const_type get(local_property< Property > p, const subgraph< G >& g) { typedef typename property_map< subgraph< G >, local_property< Property > >::const_type Map; return Map(&g, p.value); } template < typename G, typename Tag > inline typename graph_property< G, Tag >::type& get_property( subgraph< G >& g, Tag tag) { return get_property(g.m_graph, tag); } template < typename G, typename Tag > inline const typename graph_property< G, Tag >::type& get_property( const subgraph< G >& g, Tag tag) { return get_property(g.m_graph, tag); } //=========================================================================== // Miscellaneous Functions template < typename G > typename subgraph< G >::vertex_descriptor vertex( typename subgraph< G >::vertices_size_type n, const subgraph< G >& g) { return vertex(n, g.m_graph); } //=========================================================================== // Mutability Traits // Just pull the mutability traits form the underlying graph. Note that this // will probably fail (badly) for labeled graphs. template < typename G > struct graph_mutability_traits< subgraph< G > > { typedef typename graph_mutability_traits< G >::category category; }; } // namespace boost #endif // BOOST_SUBGRAPH_HPP