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/labeled_graph.hpp (30914B)

// Use, modification and distribution is subject to 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_GRAPH_LABELED_GRAPH_HPP
#define BOOST_GRAPH_LABELED_GRAPH_HPP

#include <boost/config.hpp>
#include <vector>
#include <map>

#include <boost/static_assert.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/unordered_map.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_unsigned.hpp>
#include <boost/pending/container_traits.hpp>
#include <boost/graph/graph_traits.hpp>

// This file implements a utility for creating mappings from arbitrary
// identifiers to the vertices of a graph.

namespace boost
{

// A type selector that denotes the use of some default value.
struct defaultS
{
};

/** @internal */
namespace graph_detail
{
    /** Returns true if the selector is the default selector. */
    template < typename Selector >
    struct is_default : mpl::bool_< is_same< Selector, defaultS >::value >
    {
    };

/**
     * Choose the default map instance. If Label is an unsigned integral type
     * the we can use a vector to store the information.
     */
    template < typename Label, typename Vertex > struct choose_default_map
    {
        typedef typename mpl::if_< is_unsigned< Label >, std::vector< Vertex >,
            std::map< Label, Vertex > // TODO: Should use unordered_map?
            >::type type;
    };

/**
     * @name Generate Label Map
     * These type generators are responsible for instantiating an associative
     * container for the the labeled graph. Note that the Selector must be
     * select a pair associative container or a vecS, which is only valid if
     * Label is an integral type.
     */
    //@{
    template < typename Selector, typename Label, typename Vertex >
    struct generate_label_map
    {
    };

template < typename Label, typename Vertex >
    struct generate_label_map< vecS, Label, Vertex >
    {
        typedef std::vector< Vertex > type;
    };

template < typename Label, typename Vertex >
    struct generate_label_map< mapS, Label, Vertex >
    {
        typedef std::map< Label, Vertex > type;
    };

template < typename Label, typename Vertex >
    struct generate_label_map< multimapS, Label, Vertex >
    {
        typedef std::multimap< Label, Vertex > type;
    };

template < typename Label, typename Vertex >
    struct generate_label_map< hash_mapS, Label, Vertex >
    {
        typedef boost::unordered_map< Label, Vertex > type;
    };

template < typename Label, typename Vertex >
    struct generate_label_map< hash_multimapS, Label, Vertex >
    {
        typedef boost::unordered_multimap< Label, Vertex > type;
    };

template < typename Selector, typename Label, typename Vertex >
    struct choose_custom_map
    {
        typedef
            typename generate_label_map< Selector, Label, Vertex >::type type;
    };
    //@}

/**
     * Choose and instantiate an "associative" container. Note that this can
     * also choose vector.
     */
    template < typename Selector, typename Label, typename Vertex >
    struct choose_map
    {
        typedef typename mpl::eval_if< is_default< Selector >,
            choose_default_map< Label, Vertex >,
            choose_custom_map< Selector, Label, Vertex > >::type type;
    };

/** @name Insert Labeled Vertex */
    //@{
    // Tag dispatch on random access containers (i.e., vectors). This function
    // basically requires a) that Container is vector<Label> and that Label
    // is an unsigned integral value. Note that this will resize the vector
    // to accommodate indices.
    template < typename Container, typename Graph, typename Label,
        typename Prop >
    std::pair< typename graph_traits< Graph >::vertex_descriptor, bool >
    insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
        random_access_container_tag)
    {
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

// If the label is out of bounds, resize the vector to accommodate.
        // Resize by 2x the index so we don't cause quadratic insertions over
        // time.
        if (l >= c.size())
        {
            c.resize((l + 1) * 2);
        }
        Vertex v = add_vertex(p, g);
        c[l] = v;
        return std::make_pair(c[l], true);
    }

// Tag dispatch on multi associative containers (i.e. multimaps).
    template < typename Container, typename Graph, typename Label,
        typename Prop >
    std::pair< typename graph_traits< Graph >::vertex_descriptor, bool >
    insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
        multiple_associative_container_tag const&)
    {
        // Note that insertion always succeeds so we can add the vertex first
        // and then the mapping to the label.
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
        Vertex v = add_vertex(p, g);
        c.insert(std::make_pair(l, v));
        return std::make_pair(v, true);
    }

// Tag dispatch on unique associative containers (i.e. maps).
    template < typename Container, typename Graph, typename Label,
        typename Prop >
    std::pair< typename graph_traits< Graph >::vertex_descriptor, bool >
    insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
        unique_associative_container_tag)
    {
        // Here, we actually have to try the insertion first, and only add
        // the vertex if we get a new element.
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
        typedef typename Container::iterator Iterator;
        std::pair< Iterator, bool > x = c.insert(std::make_pair(l, Vertex()));
        if (x.second)
        {
            x.first->second = add_vertex(g);
            put(boost::vertex_all, g, x.first->second, p);
        }
        return std::make_pair(x.first->second, x.second);
    }

// Dispatcher
    template < typename Container, typename Graph, typename Label,
        typename Prop >
    std::pair< typename graph_traits< Graph >::vertex_descriptor, bool >
    insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p)
    {
        return insert_labeled_vertex(c, g, l, p, container_category(c));
    }
    //@}

/** @name Find Labeled Vertex */
    //@{
    // Tag dispatch for sequential maps (i.e., vectors).
    template < typename Container, typename Graph, typename Label >
    typename graph_traits< Graph >::vertex_descriptor find_labeled_vertex(
        Container const& c, Graph const&, Label const& l,
        random_access_container_tag)
    {
        return l < c.size() ? c[l] : graph_traits< Graph >::null_vertex();
    }

// Tag dispatch for pair associative maps (more or less).
    template < typename Container, typename Graph, typename Label >
    typename graph_traits< Graph >::vertex_descriptor find_labeled_vertex(
        Container const& c, Graph const&, Label const& l,
        associative_container_tag)
    {
        typename Container::const_iterator i = c.find(l);
        return i != c.end() ? i->second : graph_traits< Graph >::null_vertex();
    }

// Dispatcher
    template < typename Container, typename Graph, typename Label >
    typename graph_traits< Graph >::vertex_descriptor find_labeled_vertex(
        Container const& c, Graph const& g, Label const& l)
    {
        return find_labeled_vertex(c, g, l, container_category(c));
    }
    //@}

/** @name Put Vertex Label */
    //@{
    // Tag dispatch on vectors.
    template < typename Container, typename Label, typename Graph,
        typename Vertex >
    bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
        random_access_container_tag)
    {
        // If the element is already occupied, then we probably don't want to
        // overwrite it.
        if (c[l] == graph_traits< Graph >::null_vertex())
            return false;
        c[l] = v;
        return true;
    }

// Attempt the insertion and return its result.
    template < typename Container, typename Label, typename Graph,
        typename Vertex >
    bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
        unique_associative_container_tag)
    {
        return c.insert(std::make_pair(l, v)).second;
    }

// Insert the pair and return true.
    template < typename Container, typename Label, typename Graph,
        typename Vertex >
    bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
        multiple_associative_container_tag)
    {
        c.insert(std::make_pair(l, v));
        return true;
    }

// Dispatcher
    template < typename Container, typename Label, typename Graph,
        typename Vertex >
    bool put_vertex_label(
        Container& c, Graph const& g, Label const& l, Vertex v)
    {
        return put_vertex_label(c, g, l, v, container_category(c));
    }
    //@}

} // namespace detail

struct labeled_graph_class_tag
{
};

/** @internal
 * This class is responsible for the deduction and declaration of type names
 * for the labeled_graph class template.
 */
template < typename Graph, typename Label, typename Selector >
struct labeled_graph_types
{
    typedef Graph graph_type;

// Label and maps
    typedef Label label_type;
    typedef typename graph_detail::choose_map< Selector, Label,
        typename graph_traits< Graph >::vertex_descriptor >::type map_type;
};

/**
 * The labeled_graph class is a graph adaptor that maintains a mapping between
 * vertex labels and vertex descriptors.
 *
 * @todo This class is somewhat redundant for adjacency_list<*, vecS>  if
 * the intended label is an unsigned int (and perhaps some other cases), but
 * it does avoid some weird ambiguities (i.e. adding a vertex with a label that
 * does not match its target index).
 *
 * @todo This needs to be reconciled with the named_graph, but since there is
 * no documentation or examples, its not going to happen.
 */
template < typename Graph, typename Label, typename Selector = defaultS >
class labeled_graph : protected labeled_graph_types< Graph, Label, Selector >
{
    typedef labeled_graph_types< Graph, Label, Selector > Base;

public:
    typedef labeled_graph_class_tag graph_tag;

typedef typename Base::graph_type graph_type;
    typedef typename graph_traits< graph_type >::vertex_descriptor
        vertex_descriptor;
    typedef
        typename graph_traits< graph_type >::edge_descriptor edge_descriptor;
    typedef typename graph_traits< graph_type >::directed_category
        directed_category;
    typedef typename graph_traits< graph_type >::edge_parallel_category
        edge_parallel_category;
    typedef typename graph_traits< graph_type >::traversal_category
        traversal_category;

typedef typename graph_traits< graph_type >::out_edge_iterator
        out_edge_iterator;
    typedef
        typename graph_traits< graph_type >::in_edge_iterator in_edge_iterator;
    typedef typename graph_traits< graph_type >::adjacency_iterator
        adjacency_iterator;
    typedef
        typename graph_traits< graph_type >::degree_size_type degree_size_type;

typedef
        typename graph_traits< graph_type >::vertex_iterator vertex_iterator;
    typedef typename graph_traits< graph_type >::vertices_size_type
        vertices_size_type;
    typedef typename graph_traits< graph_type >::edge_iterator edge_iterator;
    typedef
        typename graph_traits< graph_type >::edges_size_type edges_size_type;

typedef typename graph_type::graph_property_type graph_property_type;
    typedef typename graph_type::graph_bundled graph_bundled;

typedef typename graph_type::vertex_property_type vertex_property_type;
    typedef typename graph_type::vertex_bundled vertex_bundled;

typedef typename graph_type::edge_property_type edge_property_type;
    typedef typename graph_type::edge_bundled edge_bundled;

typedef typename Base::label_type label_type;
    typedef typename Base::map_type map_type;

public:
    labeled_graph(graph_property_type const& gp = graph_property_type())
    : _graph(gp), _map()
    {
    }

labeled_graph(labeled_graph const& x) : _graph(x._graph), _map(x._map) {}

// This constructor can only be used if map_type supports positional
    // range insertion (i.e. its a vector). This is the only case where we can
    // try to guess the intended labels for graph.
    labeled_graph(vertices_size_type n,
        graph_property_type const& gp = graph_property_type())
    : _graph(n, gp), _map()
    {
        std::pair< vertex_iterator, vertex_iterator > rng = vertices(_graph);
        _map.insert(_map.end(), rng.first, rng.second);
    }

// Construct a graph over n vertices, each of which receives a label from
    // the range [l, l + n). Note that the graph is not directly constructed
    // over the n vertices, but added sequentially. This constructor is
    // necessarily slower than the underlying counterpart.
    template < typename LabelIter >
    labeled_graph(vertices_size_type n, LabelIter l,
        graph_property_type const& gp = graph_property_type())
    : _graph(gp)
    {
        while (n-- > 0)
            add_vertex(*l++);
    }

// Construct the graph over n vertices each of which has a label in the
    // range [l, l + n) and a property in the range [p, p + n).
    template < typename LabelIter, typename PropIter >
    labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
        graph_property_type const& gp = graph_property_type())
    : _graph(gp)
    {
        while (n-- > 0)
            add_vertex(*l++, *p++);
    }

labeled_graph& operator=(labeled_graph const& x)
    {
        _graph = x._graph;
        _map = x._map;
        return *this;
    }

/** @name Graph Accessors */
    //@{
    graph_type& graph() { return _graph; }
    graph_type const& graph() const { return _graph; }
    //@}

/**
     * Create a new label for the given vertex, returning false, if the label
     * cannot be created.
     */
    bool label_vertex(vertex_descriptor v, Label const& l)
    {
        return graph_detail::put_vertex_label(_map, _graph, l, v);
    }

/** @name Add Vertex
     * Add a vertex to the graph, returning the descriptor. If the vertices
     * are uniquely labeled and the label already exists within the graph,
     * then no vertex is added, and the returned descriptor refers to the
     * existing vertex. A vertex property can be given as a parameter, if
     * needed.
     */
    //@{
    vertex_descriptor add_vertex(Label const& l)
    {
        return graph_detail::insert_labeled_vertex(
            _map, _graph, l, vertex_property_type())
            .first;
    }

vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
    {
        return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first;
    }
    //@}

/** @name Insert Vertex
     * Insert a vertex into the graph, returning a pair containing the
     * descriptor of a vertex and a boolean value that describes whether or not
     * a new vertex was inserted. If vertices are not uniquely labeled, then
     * insertion will always succeed.
     */
    //@{
    std::pair< vertex_descriptor, bool > insert_vertex(Label const& l)
    {
        return graph_detail::insert_labeled_vertex(
            _map, _graph, l, vertex_property_type());
    }

std::pair< vertex_descriptor, bool > insert_vertex(
        Label const& l, vertex_property_type const& p)
    {
        return graph_detail::insert_labeled_vertex(_map, _graph, l, p);
    }
    //@}

/** Remove the vertex with the given label. */
    void remove_vertex(Label const& l)
    {
        return boost::remove_vertex(vertex(l), _graph);
    }

/** Return a descriptor for the given label. */
    vertex_descriptor vertex(Label const& l) const
    {
        return graph_detail::find_labeled_vertex(_map, _graph, l);
    }

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    /** @name Bundled Properties */
    //@{
    // Lookup the requested vertex and return the bundle.
    vertex_bundled& operator[](Label const& l) { return _graph[vertex(l)]; }

vertex_bundled const& operator[](Label const& l) const
    {
        return _graph[vertex(l)];
    }

// Delegate edge lookup to the underlying graph.
    edge_bundled& operator[](edge_descriptor e) { return _graph[e]; }

edge_bundled const& operator[](edge_descriptor e) const
    {
        return _graph[e];
    }
    //@}
#endif

/** Return a null descriptor */
    static vertex_descriptor null_vertex()
    {
        return graph_traits< graph_type >::null_vertex();
    }

private:
    graph_type _graph;
    map_type _map;
};

/**
 * The partial specialization over graph pointers allows the construction
 * of temporary labeled graph objects. In this case, the labels are destructed
 * when the wrapper goes out of scope.
 */
template < typename Graph, typename Label, typename Selector >
class labeled_graph< Graph*, Label, Selector >
: protected labeled_graph_types< Graph, Label, Selector >
{
    typedef labeled_graph_types< Graph, Label, Selector > Base;

public:
    typedef labeled_graph_class_tag graph_tag;

typedef typename graph_type::vertex_property_type vertex_property_type;
    typedef typename graph_type::edge_property_type edge_property_type;
    typedef typename graph_type::graph_property_type graph_property_type;
    typedef typename graph_type::vertex_bundled vertex_bundled;
    typedef typename graph_type::edge_bundled edge_bundled;

typedef typename Base::label_type label_type;
    typedef typename Base::map_type map_type;

labeled_graph(graph_type* g) : _graph(g) {}

/** @name Graph Access */
    //@{
    graph_type& graph() { return *_graph; }
    graph_type const& graph() const { return *_graph; }
    //@}

/** @name Add Vertex */
    //@{
    vertex_descriptor add_vertex(Label const& l)
    {
        return graph_detail::insert_labeled_vertex(
            _map, *_graph, l, vertex_property_type())
            .first;
    }

vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
    {
        return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first;
    }

std::pair< vertex_descriptor, bool > insert_vertex(Label const& l)
    {
        return graph_detail::insert_labeled_vertex(
            _map, *_graph, l, vertex_property_type());
    }
    //@}

/** Try to insert a vertex with the given label. */
    std::pair< vertex_descriptor, bool > insert_vertex(
        Label const& l, vertex_property_type const& p)
    {
        return graph_detail::insert_labeled_vertex(_map, *_graph, l, p);
    }

/** Remove the vertex with the given label. */
    void remove_vertex(Label const& l)
    {
        return boost::remove_vertex(vertex(l), *_graph);
    }

/** Return a descriptor for the given label. */
    vertex_descriptor vertex(Label const& l) const
    {
        return graph_detail::find_labeled_vertex(_map, *_graph, l);
    }

vertex_bundled const& operator[](Label const& l) const
    {
        return (*_graph)[vertex(l)];
    }

// Delegate edge lookup to the underlying graph.
    edge_bundled& operator[](edge_descriptor e) { return (*_graph)[e]; }

edge_bundled const& operator[](edge_descriptor e) const
    {
        return (*_graph)[e];
    }
    //@}
#endif

static vertex_descriptor null_vertex()
    {
        return graph_traits< graph_type >::null_vertex();
    }

private:
    graph_type* _graph;
    map_type _map;
};

#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
#define LABELED_GRAPH labeled_graph< G, L, S >

/** @name Labeled Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v,
    typename LABELED_GRAPH::label_type const l, LABELED_GRAPH& g)
{
    return g.label_vertex(v, l);
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertex_descriptor vertex_by_label(
    typename LABELED_GRAPH::label_type const l, LABELED_GRAPH& g)
{
    return g.vertex(l);
}
//@}

/** @name Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool > edge(
    typename LABELED_GRAPH::vertex_descriptor const& u,
    typename LABELED_GRAPH::vertex_descriptor const& v, LABELED_GRAPH const& g)
{
    return edge(u, v, g.graph());
}

// Labeled Extensions
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool > edge_by_label(
    typename LABELED_GRAPH::label_type const& u,
    typename LABELED_GRAPH::label_type const& v, LABELED_GRAPH const& g)
{
    return edge(g.vertex(u), g.vertex(v), g);
}
//@}

/** @name Incidence Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::out_edge_iterator,
    typename LABELED_GRAPH::out_edge_iterator >
out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return out_edges(v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::degree_size_type out_degree(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return out_degree(v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertex_descriptor source(
    typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
{
    return source(e, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertex_descriptor target(
    typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
{
    return target(e, g.graph());
}
//@}

/** @name Bidirectional Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::in_edge_iterator,
    typename LABELED_GRAPH::in_edge_iterator >
in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return in_edges(v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::degree_size_type in_degree(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return in_degree(v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::degree_size_type degree(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return degree(v, g.graph());
}
//@}

/** @name Adjacency Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::adjacency_iterator,
    typename LABELED_GRAPH::adjacency_iterator >
adjacenct_vertices(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return adjacent_vertices(v, g.graph());
}
//@}

/** @name VertexListGraph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::vertex_iterator,
    typename LABELED_GRAPH::vertex_iterator >
vertices(LABELED_GRAPH const& g)
{
    return vertices(g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertices_size_type num_vertices(
    LABELED_GRAPH const& g)
{
    return num_vertices(g.graph());
}
//@}

/** @name EdgeListGraph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_iterator,
    typename LABELED_GRAPH::edge_iterator >
edges(LABELED_GRAPH const& g)
{
    return edges(g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::edges_size_type num_edges(LABELED_GRAPH const& g)
{
    return num_edges(g.graph());
}
//@}

/** @internal @name Property Lookup */
//@{
namespace graph_detail
{
    struct labeled_graph_vertex_property_selector
    {
        template < class LabeledGraph, class Property, class Tag > struct bind_
        {
            typedef typename LabeledGraph::graph_type Graph;
            typedef property_map< Graph, Tag > PropertyMap;
            typedef typename PropertyMap::type type;
            typedef typename PropertyMap::const_type const_type;
        };
    };

struct labeled_graph_edge_property_selector
    {
        template < class LabeledGraph, class Property, class Tag > struct bind_
        {
            typedef typename LabeledGraph::graph_type Graph;
            typedef property_map< Graph, Tag > PropertyMap;
            typedef typename PropertyMap::type type;
            typedef typename PropertyMap::const_type const_type;
        };
    };
}

template <> struct vertex_property_selector< labeled_graph_class_tag >
{
    typedef graph_detail::labeled_graph_vertex_property_selector type;
};

template <> struct edge_property_selector< labeled_graph_class_tag >
{
    typedef graph_detail::labeled_graph_edge_property_selector type;
};
//@}

/** @name Property Graph */
//@{
template < LABELED_GRAPH_PARAMS, typename Prop >
inline typename property_map< LABELED_GRAPH, Prop >::type get(
    Prop p, LABELED_GRAPH& g)
{
    return get(p, g.graph());
}

template < LABELED_GRAPH_PARAMS, typename Prop >
inline typename property_map< LABELED_GRAPH, Prop >::const_type get(
    Prop p, LABELED_GRAPH const& g)
{
    return get(p, g.graph());
}

template < LABELED_GRAPH_PARAMS, typename Prop, typename Key >
inline typename property_traits< typename property_map<
    typename LABELED_GRAPH::graph_type, Prop >::const_type >::value_type
get(Prop p, LABELED_GRAPH const& g, const Key& k)
{
    return get(p, g.graph(), k);
}

template < LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value >
inline void put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v)
{
    put(p, g.graph(), k, v);
}
//@}

/** @name Mutable Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool > add_edge(
    typename LABELED_GRAPH::vertex_descriptor const& u,
    typename LABELED_GRAPH::vertex_descriptor const& v, LABELED_GRAPH& g)
{
    return add_edge(u, v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool > add_edge(
    typename LABELED_GRAPH::vertex_descriptor const& u,
    typename LABELED_GRAPH::vertex_descriptor const& v,
    typename LABELED_GRAPH::edge_property_type const& p, LABELED_GRAPH& g)
{
    return add_edge(u, v, p, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline void clear_vertex(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
{
    return clear_vertex(v, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline void remove_edge(
    typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g)
{
    return remove_edge(e, g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline void remove_edge(typename LABELED_GRAPH::vertex_descriptor u,
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
{
    return remove_edge(u, v, g.graph());
}

// Labeled extensions
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool >
add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
    typename LABELED_GRAPH::label_type const& v, LABELED_GRAPH& g)
{
    return add_edge(g.vertex(u), g.vertex(v), g);
}

template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::edge_descriptor, bool >
add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
    typename LABELED_GRAPH::label_type const& v,
    typename LABELED_GRAPH::edge_property_type const& p, LABELED_GRAPH& g)
{
    return add_edge(g.vertex(u), g.vertex(v), p, g);
}

template < LABELED_GRAPH_PARAMS >
inline void clear_vertex_by_label(
    typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
{
    clear_vertex(g.vertex(l), g.graph());
}

template < LABELED_GRAPH_PARAMS >
inline void remove_edge_by_label(typename LABELED_GRAPH::label_type const& u,
    typename LABELED_GRAPH::label_type const& v, LABELED_GRAPH& g)
{
    remove_edge(g.vertex(u), g.vertex(v), g.graph());
}
//@}

/** @name Labeled Mutable Graph
 * The labeled mutable graph hides the add_ and remove_ vertex functions from
 * the mutable graph concept. Note that the remove_vertex is hidden because
 * removing the vertex without its key could leave a dangling reference in
 * the map.
 */
//@{
template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertex_descriptor add_vertex(
    typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
{
    return g.add_vertex(l);
}

// MutableLabeledPropertyGraph::add_vertex(l, vp, g)
template < LABELED_GRAPH_PARAMS >
inline typename LABELED_GRAPH::vertex_descriptor add_vertex(
    typename LABELED_GRAPH::label_type const& l,
    typename LABELED_GRAPH::vertex_property_type const& p, LABELED_GRAPH& g)
{
    return g.add_vertex(l, p);
}

template < LABELED_GRAPH_PARAMS >
inline void remove_vertex(
    typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
{
    g.remove_vertex(l);
}
//@}

#undef LABELED_GRAPH_PARAMS
#undef LABELED_GRAPH

} // namespace boost

// Pull the labeled graph traits
#include <boost/graph/detail/labeled_graph_traits.hpp>

#endif // BOOST_GRAPH_LABELED_GRAPH_HPP

cmd: