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/read_dimacs.hpp (12080B)

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Jeremy G. Siek, Andrew Lumsdaine, 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)
//=======================================================================

/*
  Reads maximal flow problem in extended DIMACS format.
  This works, but could use some polishing.
*/

/* ----------------------------------------------------------------- */

#ifndef BOOST_GRAPH_READ_DIMACS_HPP
#define BOOST_GRAPH_READ_DIMACS_HPP

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <boost/graph/graph_traits.hpp>

namespace boost
{

namespace detail
{

template < class Graph, class CapacityMap, class ReverseEdgeMap >
    int read_dimacs_max_flow_internal(Graph& g, CapacityMap capacity,
        ReverseEdgeMap reverse_edge,
        typename graph_traits< Graph >::vertex_descriptor& src,
        typename graph_traits< Graph >::vertex_descriptor& sink,
        std::istream& in, bool require_source_and_sink,
        const std::string& problem_type)
    {
        //  const int MAXLINE = 100;      /* max line length in the input file
        //  */
        const int ARC_FIELDS = 3; /* no of fields in arc line  */
        const int NODE_FIELDS = 2; /* no of fields in node line  */
        const int P_FIELDS = 3; /* no of fields in problem line */

typedef
            typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
        typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;

std::vector< vertex_descriptor > verts;

long m, n, /*  number of edges and nodes */
            i, head, tail, cap;

long no_lines = 0, /* no of current input line */
            no_plines = 0, /* no of problem-lines */
            no_nslines = 0, /* no of node-source-lines */
            no_nklines = 0, /* no of node-source-lines */
            no_alines = 0; /* no of arc-lines */

std::string in_line; /* for reading input line */
        char pr_type[4]; /* for reading type of the problem */
        char nd; /* source (s) or sink (t) */

int k, /* temporary */
            err_no; /* no of detected error */

/* -------------- error numbers & error messages ---------------- */
        const int EN1 = 0;
        const int EN2 = 1;
        const int EN3 = 2;
        const int EN4 = 3;
        //  const int EN6   = 4;
        //  const int EN10  = 5;
        //  const int EN7   = 6;
        const int EN8 = 7;
        const int EN9 = 8;
        const int EN11 = 9;
        const int EN12 = 10;
        //  const int EN13 = 11;
        const int EN14 = 12;
        const int EN16 = 13;
        const int EN15 = 14;
        const int EN17 = 15;
        const int EN18 = 16;
        const int EN21 = 17;
        const int EN19 = 18;
        const int EN20 = 19;
        const int EN22 = 20;

static const char* err_message[] = {
            /* 0*/ "more than one problem line.",
            /* 1*/ "wrong number of parameters in the problem line.",
            /* 2*/ "it is not a Max Flow problem line.",
            /* 3*/ "bad value of a parameter in the problem line.",
            /* 4*/ "can't obtain enough memory to solve this problem.",
            /* 5*/ "more than one line with the problem name.",
            /* 6*/ "can't read problem name.",
            /* 7*/ "problem description must be before node description.",
            /* 8*/ "this parser doesn't support multiply sources and sinks.",
            /* 9*/ "wrong number of parameters in the node line.",
            /*10*/ "wrong value of parameters in the node line.",
            /*11*/ " ",
            /*12*/
            "source and sink descriptions must be before arc descriptions.",
            /*13*/ "too many arcs in the input.",
            /*14*/ "wrong number of parameters in the arc line.",
            /*15*/ "wrong value of parameters in the arc line.",
            /*16*/ "unknown line type in the input.",
            /*17*/ "reading error.",
            /*18*/ "not enough arcs in the input.",
            /*19*/ "source or sink doesn't have incident arcs.",
            /*20*/ "can't read anything from the input file."
        };
        /* --------------------------------------------------------------- */

/* The main loop:
           -  reads the line of the input,
           -  analyses its type,
           -  checks correctness of parameters,
           -  puts data to the arrays,
           -  does service functions
        */

while (std::getline(in, in_line))
        {
            ++no_lines;

switch (in_line[0])
            {
            case 'c': /* skip lines with comments */
            case '\n': /* skip empty lines   */
            case '\0': /* skip empty lines at the end of file */
                break;

case 'p': /* problem description      */
                if (no_plines > 0)
                /* more than one problem line */
                {
                    err_no = EN1;
                    goto error;
                }

no_plines = 1;

if (
                    /* reading problem line: type of problem, no of nodes, no of
                       arcs */
                    std::sscanf(
                        in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m)
                    != P_FIELDS)
                /*wrong number of parameters in the problem line*/
                {
                    err_no = EN2;
                    goto error;
                }

if (pr_type != problem_type)
                /*wrong problem type*/
                {
                    err_no = EN3;
                    goto error;
                }

if (n <= 0 || m <= 0)
                /*wrong value of no of arcs or nodes*/
                {
                    err_no = EN4;
                    goto error;
                }

{
                    for (long vi = 0; vi < n; ++vi)
                        verts.push_back(add_vertex(g));
                }
                break;

case 'n': /* source(s) description */
                if (no_plines == 0)
                /* there was not problem line above */
                {
                    err_no = EN8;
                    goto error;
                }

/* reading source  or sink */
                k = std::sscanf(in_line.c_str(), "%*c %ld %c", &i, &nd);
                --i; // index from 0
                if (k < NODE_FIELDS)
                /* node line is incorrect */
                {
                    err_no = EN11;
                    goto error;
                }

if (i < 0 || i > n)
                /* wrong value of node */
                {
                    err_no = EN12;
                    goto error;
                }

switch (nd)
                {
                case 's': /* source line */

if (no_nslines != 0)
                    /* more than one source line */
                    {
                        err_no = EN9;
                        goto error;
                    }

no_nslines = 1;
                    src = verts[i];
                    break;

case 't': /* sink line */

if (no_nklines != 0)
                    /* more than one sink line */
                    {
                        err_no = EN9;
                        goto error;
                    }

no_nklines = 1;
                    sink = verts[i];
                    break;

default:
                    /* wrong type of node-line */
                    err_no = EN12;
                    goto error;
                }
                break;

case 'a': /* arc description */
                if (require_source_and_sink
                    && (no_nslines == 0 || no_nklines == 0))
                /* there was not source and sink description above */
                {
                    err_no = EN14;
                    goto error;
                }

if (no_alines >= m)
                /*too many arcs on input*/
                {
                    err_no = EN16;
                    goto error;
                }

if (
                    /* reading an arc description */
                    std::sscanf(
                        in_line.c_str(), "%*c %ld %ld %ld", &tail, &head, &cap)
                    != ARC_FIELDS)
                /* arc description is not correct */
                {
                    err_no = EN15;
                    goto error;
                }

--tail; // index from 0, not 1
                --head;
                if (tail < 0 || tail > n || head < 0 || head > n)
                /* wrong value of nodes */
                {
                    err_no = EN17;
                    goto error;
                }

{
                    edge_descriptor e1, e2;
                    bool in1, in2;
                    boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g);
                    boost::tie(e2, in2) = add_edge(verts[head], verts[tail], g);
                    if (!in1 || !in2)
                    {
                        std::cerr << "unable to add edge (" << head << ","
                                  << tail << ")" << std::endl;
                        return -1;
                    }
                    capacity[e1] = cap;
                    capacity[e2] = 0;
                    reverse_edge[e1] = e2;
                    reverse_edge[e2] = e1;
                }
                ++no_alines;
                break;

default:
                /* unknown type of line */
                err_no = EN18;
                goto error;

} /* end of switch */
        } /* end of input loop */

/* ----- all is red  or  error while reading ----- */

if (in.eof() == 0) /* reading error */
        {
            err_no = EN21;
            goto error;
        }

if (no_lines == 0) /* empty input */
        {
            err_no = EN22;
            goto error;
        }

if (no_alines < m) /* not enough arcs */
        {
            err_no = EN19;
            goto error;
        }

if (require_source_and_sink
            && (out_degree(src, g) == 0 || out_degree(sink, g) == 0))
        /* no arc goes out of the source */
        {
            err_no = EN20;
            goto error;
        }

/* Thanks God! all is done */
        return (0);

/* ---------------------------------- */
    error: /* error found reading input */

std::printf(
            "\nline %ld of input - %s\n", no_lines, err_message[err_no]);

return -1;
    }
    /* --------------------   end of parser  -------------------*/

} // namespace detail

template < class Graph, class CapacityMap, class ReverseEdgeMap >
int read_dimacs_max_flow(Graph& g, CapacityMap capacity,
    ReverseEdgeMap reverse_edge,
    typename graph_traits< Graph >::vertex_descriptor& src,
    typename graph_traits< Graph >::vertex_descriptor& sink,
    std::istream& in = std::cin)
{
    return detail::read_dimacs_max_flow_internal(
        g, capacity, reverse_edge, src, sink, in, true, "max");
}

template < class Graph, class CapacityMap, class ReverseEdgeMap >
int read_dimacs_min_cut(Graph& g, CapacityMap capacity,
    ReverseEdgeMap reverse_edge, std::istream& in = std::cin)
{
    typename graph_traits< Graph >::vertex_descriptor dummy_src,
        dummy_sink; // Not filled in
    return detail::read_dimacs_max_flow_internal(
        g, capacity, reverse_edge, dummy_src, dummy_sink, in, false, "cut");
}

} // namespace boost

#endif // BOOST_GRAPH_READ_DIMACS_HPP

cmd: