This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

DIMACS

Read and write graphs in the extended DIMACS max-flow format.

Read: <boost/graph/read_dimacs.hpp>
Write: <boost/graph/write_dimacs.hpp>
Linking: header-only

This format is designed for network flow benchmarks. Each edge carries a capacity, and the file specifies source and sink vertices.

read_dimacs_max_flow automatically adds a reverse edge (with capacity 0) for every edge in the file. The output graph has twice as many edges as the input file.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/write_dimacs.hpp>
#include <iostream>
#include <sstream>

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS,
        no_property,
        property<edge_capacity_t, long,
            property<edge_residual_capacity_t, long,
                property<edge_reverse_t,
                    graph_traits<adjacency_list<vecS, vecS, directedS,
                        no_property,
                        property<edge_capacity_t, long,
                            property<edge_residual_capacity_t, long,
                                property<edge_reverse_t, void*>>>>>::edge_descriptor>>>>;

    // DIMACS max-flow input
    std::string dimacs_input =
        "c This is a comment\n"
        "p max 4 5\n"
        "n 1 s\n"
        "n 4 t\n"
        "a 1 2 10\n"
        "a 1 3 20\n"
        "a 2 3 5\n"
        "a 2 4 15\n"
        "a 3 4 10\n";

    // --- Read ---
    Graph g;
    auto capacity = get(edge_capacity, g);
    auto reverse_edge = get(edge_reverse, g);
    graph_traits<Graph>::vertex_descriptor src, sink;

    std::istringstream in(dimacs_input);
    read_dimacs_max_flow(g, capacity, reverse_edge, src, sink, in);

    std::cout << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";
    std::cout << "source=" << src << " sink=" << sink << "\n";

    // --- Write ---
    std::cout << "\n=== DIMACS output ===\n";
    write_dimacs_max_flow(g, capacity, get(vertex_index, g),
                          src, sink, std::cout);
}
4 vertices, 10 edges
source=0 sink=3

=== DIMACS output ===
c DIMACS max-flow file generated from boost::write_dimacs_max_flow
p max 4 10
n 1 s
n 4 t
a 1 2 10
a 1 3 20
a 2 1 0
a 2 3 5
a 2 4 15
a 3 1 0
a 3 2 0
a 3 4 10
a 4 2 0
a 4 3 0

read_dimacs_max_flow

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);
Direction Parameter Description

OUT

Graph& g

Populated graph. Must model IncidenceGraph and MutableGraph.

OUT

CapacityMap capacity

Mutable Lvalue property map. Edge descriptor → capacity value.

OUT

ReverseEdgeMap reverse_edge

Mutable Lvalue property map. Edge descriptor → reverse edge descriptor.

OUT

vertex_descriptor& src

Set to the source vertex from the DIMACS file.

OUT

vertex_descriptor& sink

Set to the sink vertex from the DIMACS file.

IN

std::istream& in

DIMACS-formatted input. Default: std::cin.

Returns 0 on success.

read_dimacs_min_cut

template <class Graph, class CapacityMap, class ReverseEdgeMap>
int read_dimacs_min_cut(Graph& g,
                        CapacityMap capacity,
                        ReverseEdgeMap reverse_edge,
                        std::istream& in = std::cin);

Same as read_dimacs_max_flow but without source/sink output parameters.

write_dimacs_max_flow

template <class Graph, class CapacityMap, class IndexMap>
void write_dimacs_max_flow(const Graph& g,
                           CapacityMap capacity,
                           IndexMap idx,
                           typename graph_traits<Graph>::vertex_descriptor src,
                           typename graph_traits<Graph>::vertex_descriptor sink,
                           std::ostream& out);
Direction Parameter Description

IN

const Graph& g

Must model VertexListGraph and EdgeListGraph.

IN

CapacityMap capacity

Readable property map. Edge descriptor → capacity value.

IN

IndexMap idx

Readable property map. Vertex descriptor → integer index.

IN

src, sink

Source and sink vertex descriptors.

OUT

std::ostream& out

Output stream.
Cannot be used with filtered_graph because num_vertices() and num_edges() return counts for the unfiltered graph.

DIMACS format

c comment line
p max NODES EDGES
n NODE_ID s          (source)
n NODE_ID t          (sink)
a FROM TO CAPACITY   (arc)

Node IDs are 1-based in the file but 0-based in BGL.

Edit this Page