Loading...
Searching...
No Matches
DIMACS Format
Input-Output

## Detailed Description

Tools to read a digraph from or write it to a file in DIMACS format data.

## Classes

struct | DimacsDescriptor
| DIMACS file type descriptor. More...

## Files

file | dimacs.h
| DIMACS file format reader.

## Functions

DimacsDescriptor | dimacsType (std::istream &is)
| Discover the type of a DIMACS file.
template<typename Digraph, typename LowerMap, typename CapacityMap, typename CostMap, typename SupplyMap>
void | readDimacsMin (std::istream &is, Digraph &g, LowerMap &lower, CapacityMap &capacity, CostMap &cost, SupplyMap &supply, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
| DIMACS minimum cost flow reader function.
template<typename Digraph, typename CapacityMap>
void | readDimacsMax (std::istream &is, Digraph &g, CapacityMap &capacity, typename Digraph::Node &s, typename Digraph::Node &t, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
| DIMACS maximum flow reader function.
template<typename Digraph, typename LengthMap>
void | readDimacsSp (std::istream &is, Digraph &g, LengthMap &length, typename Digraph::Node &s, DimacsDescriptor desc=DimacsDescriptor())
| DIMACS shortest path reader function.
template<typename Digraph, typename CapacityMap>
void | readDimacsCap (std::istream &is, Digraph &g, CapacityMap &capacity, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
| DIMACS capacitated digraph reader function.
template<typename Graph>
void | readDimacsMat (std::istream &is, Graph &g, DimacsDescriptor desc=DimacsDescriptor())
| DIMACS plain (di)graph reader function.
template<typename Digraph>
void | writeDimacsMat (std::ostream &os, const Digraph &g, std::string comment="")

## Function Documentation

## dimacsType()

DimacsDescriptor dimacsType | ( | std::istream & | is | ) |

This function starts seeking the beginning of the given file for the problem type and size info. The found data is returned in a special struct that can be evaluated and passed to the appropriate reader function.

## readDimacsMin()

template<typename Digraph, typename LowerMap, typename CapacityMap, typename CostMap, typename SupplyMap>

void readDimacsMin | ( | std::istream & | is,
|  | Digraph & | g,
|  | LowerMap & | lower,
|  | CapacityMap & | capacity,
|  | CostMap & | cost,
|  | SupplyMap & | supply,
|  | typename CapacityMap::Value | infty = 0,
|  | DimacsDescriptor | desc = DimacsDescriptor() )

This function reads a minimum cost flow instance from DIMACS format, i.e. from a DIMACS file having a line starting with

p min

At the beginning, `g` is cleared by `g.clear()`. The supply amount of the nodes are written to the `supply` node map (they are signed values). The lower bounds, capacities and costs of the arcs are written to the `lower`, `capacity` and `cost` arc maps.

If the capacity of an arc is less than the lower bound, it will be set to "infinite" instead. The actual value of "infinite" is contolled by the `infty` parameter. If it is 0 (the default value), `std::numeric_limits<Capacity>::infinity()` will be used if available, `std::numeric_limits<Capacity>::max()` otherwise. If `infty` is set to a non-zero value, that value will be used as "infinite".

If the file type was previously evaluated by dimacsType(), then the descriptor struct should be given by the `dest` parameter.

## readDimacsMax()

template<typename Digraph, typename CapacityMap>

void readDimacsMax | ( | std::istream & | is,
|  | Digraph & | g,
|  | CapacityMap & | capacity,
|  | typename Digraph::Node & | s,
|  | typename Digraph::Node & | t,
|  | typename CapacityMap::Value | infty = 0,
|  | DimacsDescriptor | desc = DimacsDescriptor() )

This function reads a maximum flow instance from DIMACS format, i.e. from a DIMACS file having a line starting with

p max

At the beginning, `g` is cleared by `g.clear()`. The arc capacities are written to the `capacity` arc map and `s` and `t` are set to the source and the target nodes.

If the capacity of an arc is negative, it will be set to "infinite" instead. The actual value of "infinite" is contolled by the `infty` parameter. If it is 0 (the default value), `std::numeric_limits<Capacity>::infinity()` will be used if available, `std::numeric_limits<Capacity>::max()` otherwise. If `infty` is set to a non-zero value, that value will be used as "infinite".

If the file type was previously evaluated by dimacsType(), then the descriptor struct should be given by the `dest` parameter.

## readDimacsSp()

template<typename Digraph, typename LengthMap>

void readDimacsSp | ( | std::istream & | is,
|  | Digraph & | g,
|  | LengthMap & | length,
|  | typename Digraph::Node & | s,
|  | DimacsDescriptor | desc = DimacsDescriptor() )

This function reads a shortest path instance from DIMACS format, i.e. from a DIMACS file having a line starting with

p sp

At the beginning, `g` is cleared by `g.clear()`. The arc lengths are written to the `length` arc map and `s` is set to the source node.

If the file type was previously evaluated by dimacsType(), then the descriptor struct should be given by the `dest` parameter.

## readDimacsCap()

template<typename Digraph, typename CapacityMap>

void readDimacsCap | ( | std::istream & | is,
|  | Digraph & | g,
|  | CapacityMap & | capacity,
|  | typename CapacityMap::Value | infty = 0,
|  | DimacsDescriptor | desc = DimacsDescriptor() )

This function reads an arc capacitated digraph instance from DIMACS 'max' or 'sp' format. At the beginning, `g` is cleared by `g.clear()` and the arc capacities/lengths are written to the `capacity` arc map.

In case of the 'max' format, if the capacity of an arc is negative, it will be set to "infinite" instead. The actual value of "infinite" is contolled by the `infty` parameter. If it is 0 (the default value), `std::numeric_limits<Capacity>::infinity()` will be used if available, `std::numeric_limits<Capacity>::max()` otherwise. If `infty` is set to a non-zero value, that value will be used as "infinite".

If the file type was previously evaluated by dimacsType(), then the descriptor struct should be given by the `dest` parameter.

## readDimacsMat()

template<typename Graph>

void readDimacsMat | ( | std::istream & | is,
|  | Graph & | g,
|  | DimacsDescriptor | desc = DimacsDescriptor() )

This function reads a plain (di)graph without any designated nodes and maps (e.g. a matching instance) from DIMACS format, i.e. from DIMACS files having a line starting with

p mat

At the beginning, `g` is cleared by `g.clear()`.

If the file type was previously evaluated by dimacsType(), then the descriptor struct should be given by the `dest` parameter.

## writeDimacsMat()

template<typename Digraph>

void writeDimacsMat | ( | std::ostream & | os,
|  | const Digraph & | g,
|  | std::string | comment = "" )

DIMACS plain digraph writer function.

This function writes a digraph without any designated nodes and maps into DIMACS format, i.e. into DIMACS file having a line starting with

p mat

If `comment` is not empty, then it will be printed in the first line prefixed by 'c'.