DIMACS Format

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

DimacsDescriptor lemon::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.

void lemon::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.

void lemon::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.

void lemon::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.

void lemon::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.

void lemon::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.

void lemon::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'.