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/tiernan_all_cycles.hpp (12547B)

// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_CYCLE_HPP
#define BOOST_GRAPH_CYCLE_HPP

#include <vector>

#include <boost/config.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/concept/assert.hpp>

#include <boost/concept/detail/concept_def.hpp>
namespace boost
{
namespace concepts
{
    BOOST_concept(CycleVisitor, (Visitor)(Path)(Graph))
    {
        BOOST_CONCEPT_USAGE(CycleVisitor) { vis.cycle(p, g); }

private:
        Visitor vis;
        Graph g;
        Path p;
    };
} /* namespace concepts */
using concepts::CycleVisitorConcept;
} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>

namespace boost
{

// The implementation of this algorithm is a reproduction of the Teirnan
// approach for directed graphs: bibtex follows
//
//     @article{362819,
//         author = {James C. Tiernan},
//         title = {An efficient search algorithm to find the elementary
//         circuits of a graph}, journal = {Commun. ACM}, volume = {13}, number
//         = {12}, year = {1970}, issn = {0001-0782}, pages = {722--726}, doi =
//         {http://doi.acm.org/10.1145/362814.362819},
//             publisher = {ACM Press},
//             address = {New York, NY, USA},
//         }
//
// It should be pointed out that the author does not provide a complete analysis
// for either time or space. This is in part, due to the fact that it's a fairly
// input sensitive problem related to the density and construction of the graph,
// not just its size.
//
// I've also taken some liberties with the interpretation of the algorithm -
// I've basically modernized it to use real data structures (no more arrays and
// matrices). Oh... and there's explicit control structures - not just gotos.
//
// The problem is definitely NP-complete, an unbounded implementation of this
// will probably run for quite a while on a large graph. The conclusions
// of this paper also reference a Paton algorithm for undirected graphs as being
// much more efficient (apparently based on spanning trees). Although not
// implemented, it can be found here:
//
//     @article{363232,
//         author = {Keith Paton},
//         title = {An algorithm for finding a fundamental set of cycles of a
//         graph}, journal = {Commun. ACM}, volume = {12}, number = {9}, year =
//         {1969}, issn = {0001-0782}, pages = {514--518}, doi =
//         {http://doi.acm.org/10.1145/363219.363232},
//             publisher = {ACM Press},
//             address = {New York, NY, USA},
//         }

/**
 * The default cycle visitor provides an empty visit function for cycle
 * visitors.
 */
struct cycle_visitor
{
    template < typename Path, typename Graph >
    inline void cycle(const Path& p, const Graph& g)
    {
    }
};

/**
 * The min_max_cycle_visitor simultaneously records the minimum and maximum
 * cycles in a graph.
 */
struct min_max_cycle_visitor
{
    min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
    : minimum(min_), maximum(max_)
    {
    }

template < typename Path, typename Graph >
    inline void cycle(const Path& p, const Graph& g)
    {
        BOOST_USING_STD_MIN();
        BOOST_USING_STD_MAX();
        std::size_t len = p.size();
        minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum, len);
        maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION(maximum, len);
    }
    std::size_t& minimum;
    std::size_t& maximum;
};

inline min_max_cycle_visitor find_min_max_cycle(
    std::size_t& min_, std::size_t& max_)
{
    return min_max_cycle_visitor(min_, max_);
}

namespace detail
{
    template < typename Graph, typename Path >
    inline bool is_vertex_in_path(const Graph&,
        typename graph_traits< Graph >::vertex_descriptor v, const Path& p)
    {
        return (std::find(p.begin(), p.end(), v) != p.end());
    }

template < typename Graph, typename ClosedMatrix >
    inline bool is_path_closed(const Graph& g,
        typename graph_traits< Graph >::vertex_descriptor u,
        typename graph_traits< Graph >::vertex_descriptor v,
        const ClosedMatrix& closed)
    {
        // the path from u to v is closed if v can be found in the list
        // of closed vertices associated with u.
        typedef typename ClosedMatrix::const_reference Row;
        Row r = closed[get(vertex_index, g, u)];
        if (find(r.begin(), r.end(), v) != r.end())
        {
            return true;
        }
        return false;
    }

template < typename Graph, typename Path, typename ClosedMatrix >
    inline bool can_extend_path(const Graph& g,
        typename graph_traits< Graph >::edge_descriptor e, const Path& p,
        const ClosedMatrix& m)
    {
        BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
        BOOST_CONCEPT_ASSERT((VertexIndexGraphConcept< Graph >));
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

// get the vertices in question
        Vertex u = source(e, g), v = target(e, g);

// conditions for allowing a traversal along this edge are:
        // 1. the index of v must be greater than that at which the
        //    path is rooted (p.front()).
        // 2. the vertex v cannot already be in the path
        // 3. the vertex v cannot be closed to the vertex u

bool indices
            = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
        bool path = !is_vertex_in_path(g, v, p);
        bool closed = !is_path_closed(g, u, v, m);
        return indices && path && closed;
    }

template < typename Graph, typename Path >
    inline bool can_wrap_path(const Graph& g, const Path& p)
    {
        BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
        typedef typename graph_traits< Graph >::out_edge_iterator OutIterator;

// iterate over the out-edges of the back, looking for the
        // front of the path. also, we can't travel along the same
        // edge that we did on the way here, but we don't quite have the
        // stringent requirements that we do in can_extend_path().
        Vertex u = p.back(), v = p.front();
        OutIterator i, end;
        for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
        {
            if ((target(*i, g) == v))
            {
                return true;
            }
        }
        return false;
    }

template < typename Graph, typename Path, typename ClosedMatrix >
    inline typename graph_traits< Graph >::vertex_descriptor extend_path(
        const Graph& g, Path& p, ClosedMatrix& closed)
    {
        BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
        typedef typename graph_traits< Graph >::out_edge_iterator OutIterator;

// get the current vertex
        Vertex u = p.back();
        Vertex ret = graph_traits< Graph >::null_vertex();

// AdjacencyIterator i, end;
        OutIterator i, end;
        for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
        {
            Vertex v = target(*i, g);

// if we can actually extend along this edge,
            // then that's what we want to do
            if (can_extend_path(g, *i, p, closed))
            {
                p.push_back(v); // add the vertex to the path
                ret = v;
                break;
            }
        }
        return ret;
    }

template < typename Graph, typename Path, typename ClosedMatrix >
    inline bool exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
    {
        BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

// if there's more than one vertex in the path, this closes
        // of some possible routes and returns true. otherwise, if there's
        // only one vertex left, the vertex has been used up
        if (p.size() > 1)
        {
            // get the last and second to last vertices, popping the last
            // vertex off the path
            Vertex last, prev;
            last = p.back();
            p.pop_back();
            prev = p.back();

// reset the closure for the last vertex of the path and
            // indicate that the last vertex in p is now closed to
            // the next-to-last vertex in p
            closed[get(vertex_index, g, last)].clear();
            closed[get(vertex_index, g, prev)].push_back(last);
            return true;
        }
        else
        {
            return false;
        }
    }

template < typename Graph, typename Visitor >
    inline void all_cycles_from_vertex(const Graph& g,
        typename graph_traits< Graph >::vertex_descriptor v, Visitor vis,
        std::size_t minlen, std::size_t maxlen)
    {
        BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
        typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
        typedef std::vector< Vertex > Path;
        BOOST_CONCEPT_ASSERT((CycleVisitorConcept< Visitor, Path, Graph >));
        typedef std::vector< Vertex > VertexList;
        typedef std::vector< VertexList > ClosedMatrix;

Path p;
        ClosedMatrix closed(num_vertices(g), VertexList());
        Vertex null = graph_traits< Graph >::null_vertex();

// each path investigation starts at the ith vertex
        p.push_back(v);

while (1)
        {
            // extend the path until we've reached the end or the
            // maxlen-sized cycle
            Vertex j = null;
            while (((j = detail::extend_path(g, p, closed)) != null)
                && (p.size() < maxlen))
                ; // empty loop

// if we're done extending the path and there's an edge
            // connecting the back to the front, then we should have
            // a cycle.
            if (detail::can_wrap_path(g, p) && p.size() >= minlen)
            {
                vis.cycle(p, g);
            }

if (!detail::exhaust_paths(g, p, closed))
            {
                break;
            }
        }
    }

// Select the minimum allowable length of a cycle based on the directedness
    // of the graph - 2 for directed, 3 for undirected.
    template < typename D > struct min_cycles
    {
        enum
        {
            value = 2
        };
    };
    template <> struct min_cycles< undirected_tag >
    {
        enum
        {
            value = 3
        };
    };
} /* namespace detail */

template < typename Graph, typename Visitor >
inline void tiernan_all_cycles(
    const Graph& g, Visitor vis, std::size_t minlen, std::size_t maxlen)
{
    BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
    typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;

VertexIterator i, end;
    for (boost::tie(i, end) = vertices(g); i != end; ++i)
    {
        detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
    }
}

template < typename Graph, typename Visitor >
inline void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
{
    typedef typename graph_traits< Graph >::directed_category Dir;
    tiernan_all_cycles(g, vis, detail::min_cycles< Dir >::value, maxlen);
}

template < typename Graph, typename Visitor >
inline void tiernan_all_cycles(const Graph& g, Visitor vis)
{
    typedef typename graph_traits< Graph >::directed_category Dir;
    tiernan_all_cycles(g, vis, detail::min_cycles< Dir >::value,
        (std::numeric_limits< std::size_t >::max)());
}

template < typename Graph >
inline std::pair< std::size_t, std::size_t > tiernan_girth_and_circumference(
    const Graph& g)
{
    std::size_t min_ = (std::numeric_limits< std::size_t >::max)(), max_ = 0;
    tiernan_all_cycles(g, find_min_max_cycle(min_, max_));

// if this is the case, the graph is acyclic...
    if (max_ == 0)
        max_ = min_;

return std::make_pair(min_, max_);
}

template < typename Graph > inline std::size_t tiernan_girth(const Graph& g)
{
    return tiernan_girth_and_circumference(g).first;
}

template < typename Graph >
inline std::size_t tiernan_circumference(const Graph& g)
{
    return tiernan_girth_and_circumference(g).second;
}

} /* namespace boost */

#endif

cmd: