lemon Namespace Reference

Detailed Description

The concept of paths.

The concept of maps.

The concept of heaps.

The concepts of graph components.

The concept of directed graphs.

The concept of undirected graphs.

A basic tool to handle the anomalies of calculation with floating point numbers.

Tools for measuring cpu usage.

An algorithm for finding arc-disjoint paths between two nodes having minimum total length.

StaticDigraph class.

Implementation of the LEMON-SOPLEX lp solver interface.

SmartDigraph and SmartGraph classes.

Mersenne Twister random number generator.

Instantiation of the Random class.

Radix heap implementation.

Fourary (quaternary) heap implementation.

Classes for representing paths in digraphs.

Pairing heap implementation.

Minimum Cost Arborescence algorithm.

Some extensions to the standard cmath library.

Maximum matching algorithms in general graphs.

Miscellaneous property maps.

Skeleton file to implement LP/MIP solver interfaces.

A skeleton file to implement LP solver interfaces.

The interface of the LP solver interface.

The implementation of the LP solver interface.

Defines a default LP solver.

ListDigraph and ListGraph classes.

LEMON Graph Format writer.

LEMON Graph Format reader.

Kruskal's algorithm to compute a minimum cost spanning tree.

HypercubeGraph class.

GridGraph class.

A well configurable tool for visualizing graphs.

Header of the LEMON-GLPK lp solver interface.

Implementation of the LEMON GLPK LP and MIP solver interface.

FullDigraph and FullGraph classes.

Fractional matching algorithms in general graphs.

Fibonacci heap implementation.

Elevator class.

A simple two dimensional vector and a bounding box implementation.

Dijkstra algorithm.

D-ary heap implementation.

DFS algorithm.

Implementation of the LEMON-CPLEX lp solver interface.

Tools for counting steps and events.

LEMON core utilities.

Basic utilities for concept checking.

Tools to manage RGB colors.

Color constants.

Push-relabel algorithm for finding a feasible circulation.

Implementation of the CBC MIP solver interface.

Bucket heap implementation.

Binomial Heap implementation.

Binary heap implementation.

BFS algorithm.

Some basic non-inline functions and static global data.

A tool to parse command line arguments.

The namespace of LEMON

This header file contains core utilities for LEMON. It is automatically included by all graph types, therefore it usually do not have to be included directly.

Elevator class implements an efficient data structure for labeling items in push-relabel type algorithms.

The classes in this file do nothing, but they can serve as skeletons when implementing an interface to new solvers.

Some extensions to the standard cmath library.

This file includes the standard math library (cmath).

Namespaces
namespace	concepts
	The namespace of LEMON concepts and concept checking classes.
namespace	dim2
	Tools for handling two dimensional coordinates.

Classes
class	ReverseDigraph
	Adaptor class for reversing the orientation of the arcs in a digraph. More...
class	SubDigraph
	Adaptor class for hiding nodes and arcs in a digraph. More...
class	SubGraph
	Adaptor class for hiding nodes and edges in an undirected graph. More...
class	FilterNodes
	Adaptor class for hiding nodes in a digraph or a graph. More...
class	FilterArcs
	Adaptor class for hiding arcs in a digraph. More...
class	FilterEdges
	Adaptor class for hiding edges in a graph. More...
class	Undirector
	Adaptor class for viewing a digraph as an undirected graph. More...
class	Orienter
	Adaptor class for orienting the edges of a graph to get a digraph. More...
class	ResidualDigraph
	Adaptor class for composing the residual digraph for directed flow and circulation problems. More...
class	SplitNodes
	Adaptor class for splitting the nodes of a digraph. More...
class	ArgParserException
	Exception used by ArgParser. More...
class	ArgParser
	Command line arguments parser. More...
struct	BellmanFordDefaultOperationTraits
	Default OperationTraits for the BellmanFord algorithm class. More...
struct	BellmanFordDefaultTraits
	Default traits class of BellmanFord class. More...
class	BellmanFord
	BellmanFord algorithm class. More...
struct	BellmanFordWizardDefaultTraits
	Default traits class of bellmanFord() function. More...
class	BellmanFordWizardBase
	Default traits class used by BellmanFordWizard. More...
class	BellmanFordWizard
	Auxiliary class for the function-type interface of the Bellman-Ford algorithm. More...
struct	BfsDefaultTraits
	Default traits class of Bfs class. More...
class	Bfs
	BFS algorithm class. More...
struct	BfsWizardDefaultTraits
	Default traits class of bfs() function. More...
class	BfsWizardBase
	Default traits class used by BfsWizard. More...
class	BfsWizard
	Auxiliary class for the function-type interface of BFS algorithm. More...
struct	BfsVisitor
	Visitor class for BFS. More...
struct	BfsVisitDefaultTraits
	Default traits class of BfsVisit class. More...
class	BfsVisit
	BFS algorithm class with visitor interface. More...
class	BinHeap
	Binary heap data structure. More...
class	BinomialHeap
	Binomial heap data structure. More...
class	BucketHeap
	Bucket heap data structure. More...
class	SimpleBucketHeap
	Simplified bucket heap data structure. More...
struct	CapacityScalingDefaultTraits
	Default traits class of CapacityScaling algorithm. More...
class	CapacityScaling
	Implementation of the Capacity Scaling algorithm for finding a minimum cost flow. More...
class	CbcMip
	Interface for the CBC MIP solver. More...
class	ChristofidesTsp
	Christofides algorithm for symmetric TSP. More...
struct	CirculationDefaultTraits
	Default traits class of Circulation class. More...
class	Circulation
	Push-relabel algorithm for the network circulation problem. More...
class	ClpLp
	Interface for the CLP solver. More...
class	Color
	Data structure representing RGB colors. More...
class	Palette
	Map ints to different Colors. More...
struct	Invalid
	Dummy type to make it easier to create invalid iterators. More...
class	DigraphCopy
	Class to copy a digraph. More...
class	GraphCopy
	Class to copy a graph. More...
class	BpGraphCopy
	Class to copy a bipartite graph. More...
class	ConArcIt
	Iterator for iterating on parallel arcs connecting the same nodes. More...
class	ConEdgeIt
	Iterator for iterating on parallel edges connecting the same nodes. More...
class	DynArcLookUp
	Dynamic arc look-up between given endpoints. More...
class	ArcLookUp
	Fast arc look-up between given endpoints. More...
class	AllArcLookUp
	Fast look-up of all arcs between given endpoints. More...
struct	CostScalingDefaultTraits
	Default traits class of CostScaling algorithm. More...
class	CostScaling
	Implementation of the Cost Scaling algorithm for finding a minimum cost flow. More...
class	Counter
	A counter class. More...
class	NoCounter
	'Do nothing' version of Counter. More...
class	CplexEnv
	Reference counted wrapper around cpxenv pointer. More...
class	CplexBase
	Base interface for the CPLEX LP and MIP solver. More...
class	CplexLp
	Interface for the CPLEX LP solver. More...
class	CplexMip
	Interface for the CPLEX MIP solver. More...
class	CycleCanceling
	Implementation of cycle-canceling algorithms for finding a minimum cost flow. More...
struct	DfsDefaultTraits
	Default traits class of Dfs class. More...
class	Dfs
	DFS algorithm class. More...
struct	DfsWizardDefaultTraits
	Default traits class of dfs() function. More...
class	DfsWizardBase
	Default traits class used by DfsWizard. More...
class	DfsWizard
	Auxiliary class for the function-type interface of DFS algorithm. More...
struct	DfsVisitor
	Visitor class for DFS. More...
struct	DfsVisitDefaultTraits
	Default traits class of DfsVisit class. More...
class	DfsVisit
	DFS algorithm class with visitor interface. More...
class	DHeap
	D-ary heap data structure. More...
struct	DijkstraDefaultOperationTraits
	Default operation traits for the Dijkstra algorithm class. More...
struct	DijkstraDefaultTraits
	Default traits class of Dijkstra class. More...
class	Dijkstra
	Dijkstra algorithm class. More...
struct	DijkstraWizardDefaultTraits
	Default traits class of dijkstra() function. More...
class	DijkstraWizardBase
	Default traits class used by DijkstraWizard. More...
class	DijkstraWizard
	Auxiliary class for the function-type interface of Dijkstra algorithm. More...
struct	DimacsDescriptor
	DIMACS file type descriptor. More...
class	ListArcSet
	Digraph using a node set of another digraph or graph and an own arc set. More...
class	ListEdgeSet
	Graph using a node set of another digraph or graph and an own edge set. More...
class	SmartArcSet
	Digraph using a node set of another digraph or graph and an own arc set. More...
class	SmartEdgeSet
	Graph using a node set of another digraph or graph and an own edge set. More...
struct	EdmondsKarpDefaultTraits
	Default traits class of EdmondsKarp class. More...
class	EdmondsKarp
	Edmonds-Karp algorithms class. More...
class	Elevator
	Class for handling "labels" in push-relabel type algorithms. More...
class	LinkedElevator
	Class for handling "labels" in push-relabel type algorithms. More...
class	Exception
	Generic exception class. More...
class	IoError
	Input-Output error. More...
class	FormatError
	Format error. More...
class	DiEulerIt
	Euler tour iterator for digraphs. More...
class	EulerIt
	Euler tour iterator for graphs. More...
class	FibHeap
	Fibonacci heap data structure. More...
struct	MaxFractionalMatchingDefaultTraits
	Default traits class of MaxFractionalMatching class. More...
class	MaxFractionalMatching
	Max cardinality fractional matching. More...
class	MaxWeightedFractionalMatching
	Weighted fractional matching in general graphs. More...
class	MaxWeightedPerfectFractionalMatching
	Weighted fractional perfect matching in general graphs. More...
class	FullDigraph
	A directed full graph class. More...
class	FullGraph
	An undirected full graph class. More...
class	FullBpGraph
	An undirected full bipartite graph class. More...
class	GlpkBase
	Base interface for the GLPK LP and MIP solver. More...
class	GlpkLp
	Interface for the GLPK LP solver. More...
class	GlpkMip
	Interface for the GLPK MIP solver. More...
class	GomoryHu
	Gomory-Hu cut tree algorithm. More...
struct	DefaultGraphToEpsTraits
	Default traits class of GraphToEps. More...
class	GraphToEps
	Auxiliary class to implement the named parameters of graphToEps(). More...
class	GreedyTsp
	Greedy algorithm for symmetric TSP. More...
class	GridGraph
	Grid graph class. More...
class	GrossoLocatelliPullanMc
	Implementation of the iterated local search algorithm of Grosso, Locatelli, and Pullan for the maximum clique problem. More...
class	HaoOrlin
	Hao-Orlin algorithm for finding a minimum cut in a digraph. More...
struct	HartmannOrlinMmcDefaultTraits
	Default traits class of HartmannOrlinMmc class. More...
class	HartmannOrlinMmc
	Implementation of the Hartmann-Orlin algorithm for finding a minimum mean cycle. More...
struct	HowardMmcDefaultTraits
	Default traits class of HowardMmc class. More...
class	HowardMmc
	Implementation of Howard's algorithm for finding a minimum mean cycle. More...
class	HypercubeGraph
	Hypercube graph class. More...
class	InsertionTsp
	Insertion algorithm for symmetric TSP. More...
struct	KarpMmcDefaultTraits
	Default traits class of KarpMmc class. More...
class	KarpMmc
	Implementation of Karp's algorithm for finding a minimum mean cycle. More...
class	DigraphReader
	LGF reader for directed graphs More...
class	GraphReader
	LGF reader for undirected graphs More...
class	BpGraphReader
	LGF reader for bipartite graphs More...
class	SectionReader
	Section reader class. More...
class	LgfContents
	Reader for the contents of the LGF file. More...
class	DigraphWriter
	LGF writer for directed graphs More...
class	GraphWriter
	LGF writer for undirected graphs More...
class	BpGraphWriter
	LGF writer for undirected bipartite graphs More...
class	SectionWriter
	Section writer class. More...
class	ListDigraph
	A general directed graph structure. More...
class	ListGraph
	A general undirected graph structure. More...
class	ListBpGraph
	A general undirected graph structure. More...
class	LpBase
	Common base class for LP and MIP solvers. More...
class	LpSolver
	Common base class for LP solvers. More...
class	MipSolver
	Common base class for MIP solvers. More...
class	SkeletonSolverBase
	A skeleton class to implement LP/MIP solver base interface. More...
class	LpSkeleton
	Skeleton class for an LP solver interface. More...
class	MipSkeleton
	Skeleton class for a MIP solver interface. More...
class	MapBase
	Base class of maps. More...
class	NullMap
	Null map. (a.k.a. DoNothingMap). More...
class	ConstMap
	Constant map. More...
class	ConstMap< K, Const< V, v > >
	Constant map with inlined constant value. More...
class	IdentityMap
	Identity map. More...
class	RangeMap
	Map for storing values for integer keys from the range [0..size-1]. More...
class	SparseMap
	Map type based on std::map. More...
class	ComposeMap
	Composition of two maps. More...
class	CombineMap
	Combination of two maps using an STL (binary) functor. More...
class	FunctorToMap
	Converts an STL style (unary) functor to a map. More...
class	MapToFunctor
	Converts a map to an STL style (unary) functor. More...
class	ConvertMap
	Map adaptor to convert the Value type of a map to another type using the default conversion. More...
class	ForkMap
	Applies all map setting operations to two maps. More...
class	AddMap
	Sum of two maps. More...
class	SubMap
	Difference of two maps. More...
class	MulMap
	Product of two maps. More...
class	DivMap
	Quotient of two maps. More...
class	ShiftMap
	Shifts a map with a constant. More...
class	ShiftWriteMap
	Shifts a map with a constant (read-write version). More...
class	ScaleMap
	Scales a map with a constant. More...
class	ScaleWriteMap
	Scales a map with a constant (read-write version). More...
class	NegMap
	Negative of a map. More...
class	NegWriteMap
	Negative of a map (read-write version). More...
class	AbsMap
	Absolute value of a map. More...
class	TrueMap
	Constant true map. More...
class	FalseMap
	Constant false map. More...
class	AndMap
	Logical 'and' of two maps. More...
class	OrMap
	Logical 'or' of two maps. More...
class	NotMap
	Logical 'not' of a map. More...
class	NotWriteMap
	Logical 'not' of a map (read-write version). More...
class	EqualMap
	Combination of two maps using the == operator. More...
class	LessMap
	Combination of two maps using the < operator. More...
class	LoggerBoolMap
	Writable bool map for logging each true assigned element. More...
class	IdMap
	Provides an immutable and unique id for each item in a graph. More...
class	CrossRefMap
	General cross reference graph map type. More...
class	RangeIdMap
	Provides continuous and unique id for the items of a graph. More...
class	IterableBoolMap
	Dynamic iterable bool map. More...
class	IterableIntMap
	Dynamic iterable integer map. More...
class	IterableValueMap
	Dynamic iterable map for comparable values. More...
class	SourceMap
	Map of the source nodes of arcs in a digraph. More...
class	TargetMap
	Map of the target nodes of arcs in a digraph. More...
class	ForwardMap
	Map of the "forward" directed arc view of edges in a graph. More...
class	BackwardMap
	Map of the "backward" directed arc view of edges in a graph. More...
class	InDegMap
	Map of the in-degrees of nodes in a digraph. More...
class	OutDegMap
	Map of the out-degrees of nodes in a digraph. More...
class	PotentialDifferenceMap
	Potential difference map. More...
class	MaxMatching
	Maximum cardinality matching in general graphs. More...
class	MaxWeightedMatching
	Weighted matching in general graphs. More...
class	MaxWeightedPerfectMatching
	Weighted perfect matching in general graphs. More...
struct	MaxCardinalitySearchDefaultTraits
	Default traits class of MaxCardinalitySearch class. More...
class	MaxCardinalitySearch
	Maximum Cardinality Search algorithm class. More...
struct	MinCostArborescenceDefaultTraits
	Default traits class for MinCostArborescence class. More...
class	MinCostArborescence
	Minimum Cost Arborescence algorithm class. More...
struct	NagamochiIbarakiDefaultTraits
	Default traits class for NagamochiIbaraki class. More...
class	NagamochiIbaraki
	Calculates the minimum cut in an undirected graph. More...
class	NearestNeighborTsp
	Nearest neighbor algorithm for symmetric TSP. More...
class	NetworkSimplex
	Implementation of the primal Network Simplex algorithm for finding a minimum cost flow. More...
class	Opt2Tsp
	2-opt algorithm for symmetric TSP. More...
class	PairingHeap
	Pairing Heap. More...
class	Path
	A structure for representing directed paths in a digraph. More...
class	SimplePath
	A structure for representing directed paths in a digraph. More...
class	ListPath
	A structure for representing directed paths in a digraph. More...
class	StaticPath
	A structure for representing directed paths in a digraph. More...
class	PathNodeIt
	Class which helps to iterate through the nodes of a path. More...
class	PlanarEmbedding
	Planar embedding of an undirected simple graph. More...
class	PlanarDrawing
	Schnyder's planar drawing algorithm. More...
class	PlanarColoring
	Coloring planar graphs. More...
struct	PreflowDefaultTraits
	Default traits class of Preflow class. More...
class	Preflow
	Preflow algorithm class. More...
class	QuadHeap
	Fourary (quaternary) heap data structure. More...
class	RadixHeap
	Radix heap data structure. More...
class	Random
	Mersenne Twister random number generator. More...
class	SmartDigraph
	A smart directed graph class. More...
class	SmartGraph
	A smart undirected graph class. More...
class	SmartBpGraph
	A smart undirected bipartite graph class. More...
class	SoplexLp
	Interface for the SOPLEX solver. More...
class	StaticDigraph
	A static directed graph class. More...
struct	SuurballeDefaultTraits
	Default traits class of Suurballe algorithm. More...
class	Suurballe
	Algorithm for finding arc-disjoint paths between two nodes having minimum total length. More...
class	TimeStamp
	A class to store (cpu)time instances. More...
class	Timer
	Class for measuring the cpu time and real time usage of the process. More...
class	TimeReport
	Same as Timer but prints a report on destruction. More...
class	NoTimeReport
	'Do nothing' version of TimeReport More...
class	Tolerance
	A class to provide a basic way to handle the comparison of numbers that are obtained as a result of a probably inexact computation. More...
class	Tolerance< float >
	Float specialization of Tolerance. More...
class	Tolerance< double >
	Double specialization of Tolerance. More...
class	Tolerance< long double >
	Long double specialization of Tolerance. More...
class	UnionFind
	A Union-Find data structure implementation. More...
class	UnionFindEnum
	A Union-Find data structure implementation which is able to enumerate the components. More...
class	ExtendFindEnum
	A Extend-Find data structure implementation which is able to enumerate the components. More...
class	HeapUnionFind
	A Union-Find data structure implementation which is able to store a priority for each item and retrieve the minimum of each class. More...

Typedefs
typedef GlpkLp	Lp
	The default LP solver.
typedef GlpkMip	Mip
	The default MIP solver.

Functions
template<typename GR, typename LEN>
BellmanFordWizard< BellmanFordWizardBase< GR, LEN > >	bellmanFord (const GR &digraph, const LEN &length)
	Function type interface for the Bellman-Ford algorithm.
template<class GR>
BfsWizard< BfsWizardBase< GR > >	bfs (const GR &digraph)
	Function-type interface for BFS algorithm.
Color	distantColor (const Color &c)
	Returns a visibly distinct Color.
Color	distantBW (const Color &c)
	Returns black for light colors and white for the dark ones.
template<class Concept>
void	function_requires ()
template<typename Concept, typename Type>
void	checkConcept ()
template<typename Graph>
bool	connected (const Graph &graph)
	Check whether an undirected graph is connected.
template<typename Graph>
int	countConnectedComponents (const Graph &graph)
	Count the number of connected components of an undirected graph.
template<class Graph, class NodeMap>
int	connectedComponents (const Graph &graph, NodeMap &compMap)
	Find the connected components of an undirected graph.
template<typename Digraph>
bool	stronglyConnected (const Digraph &digraph)
	Check whether a directed graph is strongly connected.
template<typename Digraph>
int	countStronglyConnectedComponents (const Digraph &digraph)
	Count the number of strongly connected components of a directed graph.
template<typename Digraph, typename NodeMap>
int	stronglyConnectedComponents (const Digraph &digraph, NodeMap &compMap)
	Find the strongly connected components of a directed graph.
template<typename Digraph, typename ArcMap>
int	stronglyConnectedCutArcs (const Digraph &digraph, ArcMap &cutMap)
	Find the cut arcs of the strongly connected components.
template<typename Graph>
int	countBiNodeConnectedComponents (const Graph &graph)
	Count the number of bi-node-connected components of an undirected graph.
template<typename Graph>
bool	biNodeConnected (const Graph &graph)
	Check whether an undirected graph is bi-node-connected.
template<typename Graph, typename EdgeMap>
int	biNodeConnectedComponents (const Graph &graph, EdgeMap &compMap)
	Find the bi-node-connected components of an undirected graph.
template<typename Graph, typename NodeMap>
int	biNodeConnectedCutNodes (const Graph &graph, NodeMap &cutMap)
	Find the bi-node-connected cut nodes in an undirected graph.
template<typename Graph>
int	countBiEdgeConnectedComponents (const Graph &graph)
	Count the number of bi-edge-connected components of an undirected graph.
template<typename Graph>
bool	biEdgeConnected (const Graph &graph)
	Check whether an undirected graph is bi-edge-connected.
template<typename Graph, typename NodeMap>
int	biEdgeConnectedComponents (const Graph &graph, NodeMap &compMap)
	Find the bi-edge-connected components of an undirected graph.
template<typename Graph, typename EdgeMap>
int	biEdgeConnectedCutEdges (const Graph &graph, EdgeMap &cutMap)
	Find the bi-edge-connected cut edges in an undirected graph.
template<typename Digraph>
bool	dag (const Digraph &digraph)
	Check whether a digraph is DAG.
template<typename Digraph, typename NodeMap>
void	topologicalSort (const Digraph &digraph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Digraph, typename NodeMap>
bool	checkedTopologicalSort (const Digraph &digraph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Graph>
bool	acyclic (const Graph &graph)
	Check whether an undirected graph is acyclic.
template<typename Graph>
bool	tree (const Graph &graph)
	Check whether an undirected graph is tree.
template<typename Graph>
bool	bipartite (const Graph &graph)
	Check whether an undirected graph is bipartite.
template<typename Graph, typename NodeMap>
bool	bipartitePartitions (const Graph &graph, NodeMap &partMap)
	Find the bipartite partitions of an undirected graph.
template<typename Graph>
bool	loopFree (const Graph &graph)
	Check whether the given graph contains no loop arcs/edges.
template<typename Graph>
bool	parallelFree (const Graph &graph)
	Check whether the given graph contains no parallel arcs/edges.
template<typename Graph>
bool	simpleGraph (const Graph &graph)
	Check whether the given graph is simple.
template<typename Graph, typename Item>
int	countItems (const Graph &g)
	Function to count the items in a graph.
template<typename Graph>
int	countNodes (const Graph &g)
	Function to count the nodes in the graph.
template<typename Graph>
int	countRedNodes (const Graph &g)
	Function to count the red nodes in the graph.
template<typename Graph>
int	countBlueNodes (const Graph &g)
	Function to count the blue nodes in the graph.
template<typename Graph>
int	countArcs (const Graph &g)
	Function to count the arcs in the graph.
template<typename Graph>
int	countEdges (const Graph &g)
	Function to count the edges in the graph.
template<typename Graph>
int	countOutArcs (const Graph &g, const typename Graph::Node &n)
	Function to count the number of the out-arcs from node n.
template<typename Graph>
int	countInArcs (const Graph &g, const typename Graph::Node &n)
	Function to count the number of the in-arcs to node n.
template<typename Graph>
int	countIncEdges (const Graph &g, const typename Graph::Node &n)
	Function to count the number of the inc-edges to node n.
template<typename GR>
bool	undirected (const GR &g)
	Check whether a graph is undirected.
template<typename From, typename To>
DigraphCopy< From, To >	digraphCopy (const From &from, To &to)
	Copy a digraph to another digraph.
template<typename From, typename To>
GraphCopy< From, To >	graphCopy (const From &from, To &to)
	Copy a graph to another graph.
template<typename From, typename To>
BpGraphCopy< From, To >	bpGraphCopy (const From &from, To &to)
	Copy a graph to another graph.
template<typename Graph>
Graph::Arc	findArc (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Arc prev=INVALID)
	Find an arc between two nodes of a digraph.
template<typename Graph>
Graph::Edge	findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge p=INVALID)
	Find an edge between two nodes of a graph.
template<class GR>
DfsWizard< DfsWizardBase< GR > >	dfs (const GR &digraph)
	Function-type interface for DFS algorithm.
template<typename GR, typename LEN>
DijkstraWizard< DijkstraWizardBase< GR, LEN > >	dijkstra (const GR &digraph, const LEN &length)
	Function-type interface for Dijkstra algorithm.
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="")
template<typename GR>
bool	eulerian (const GR &g)
	Check if the given graph is Eulerian.
template<class GR>
GraphToEps< DefaultGraphToEpsTraits< GR > >	graphToEps (GR &g, std::ostream &os=std::cout)
	Generates an EPS file from a graph.
template<class GR>
GraphToEps< DefaultGraphToEpsTraits< GR > >	graphToEps (GR &g, const char *file_name)
	Generates an EPS file from a graph.
template<class GR>
GraphToEps< DefaultGraphToEpsTraits< GR > >	graphToEps (GR &g, const std::string &file_name)
	Generates an EPS file from a graph.
template<typename Graph, typename In, typename Out>
Value	kruskal (const Graph &g, const In &in, Out &out)
	Kruskal's algorithm for finding a minimum cost spanning tree of a graph.
template<typename GR, typename From, typename To>
void	mapCopy (const GR &gr, const From &from, To &to)
	Copy the values of a graph map to another map.
template<typename GR, typename Map1, typename Map2>
bool	mapCompare (const GR &gr, const Map1 &map1, const Map2 &map2)
	Compare two graph maps.
template<typename GR, typename Map>
Map::Key	mapMin (const GR &gr, const Map &map)
	Return an item having minimum value of a graph map.
template<typename GR, typename Map, typename Comp>
Map::Key	mapMin (const GR &gr, const Map &map, const Comp &comp)
	Return an item having minimum value of a graph map.
template<typename GR, typename Map>
Map::Key	mapMax (const GR &gr, const Map &map)
	Return an item having maximum value of a graph map.
template<typename GR, typename Map, typename Comp>
Map::Key	mapMax (const GR &gr, const Map &map, const Comp &comp)
	Return an item having maximum value of a graph map.
template<typename GR, typename Map>
Map::Value	mapMinValue (const GR &gr, const Map &map)
	Return the minimum value of a graph map.
template<typename GR, typename Map, typename Comp>
Map::Value	mapMinValue (const GR &gr, const Map &map, const Comp &comp)
	Return the minimum value of a graph map.
template<typename GR, typename Map>
Map::Value	mapMaxValue (const GR &gr, const Map &map)
	Return the maximum value of a graph map.
template<typename GR, typename Map, typename Comp>
Map::Value	mapMaxValue (const GR &gr, const Map &map, const Comp &comp)
	Return the maximum value of a graph map.
template<typename GR, typename Map>
Map::Key	mapFind (const GR &gr, const Map &map, const typename Map::Value &val)
	Return an item having a specified value in a graph map.
template<typename GR, typename Map, typename Pred>
Map::Key	mapFindIf (const GR &gr, const Map &map, const Pred &pred)
	Return an item having value for which a certain predicate is true in a graph map.
template<typename GR, typename Map>
int	mapCount (const GR &gr, const Map &map, const typename Map::Value &val)
	Return the number of items having a specified value in a graph map.
template<typename GR, typename Map, typename Pred>
int	mapCountIf (const GR &gr, const Map &map, const Pred &pred)
	Return the number of items having values for which a certain predicate is true in a graph map.
template<typename GR, typename Map>
void	mapFill (const GR &gr, Map &map, const typename Map::Value &val)
	Fill a graph map with a certain value.
bool	isNaN (double v)
	Check whether the parameter is NaN or not.
double	round (double r)
	Round a value to its closest integer.
template<typename Digraph, typename CostMap, typename ArborescenceMap>
CostMap::Value	minCostArborescence (const Digraph &digraph, const CostMap &cost, typename Digraph::Node source, ArborescenceMap &arborescence)
	Function type interface for MinCostArborescence algorithm.
template<typename Graph>
std::istream &	readNautyGraph (Graph &graph, std::istream &is=std::cin)
	Nauty file reader.
template<typename From, typename To>
void	pathCopy (const From &from, To &to)
	Make a copy of a path.
template<typename To, typename From>
void	copyPath (To &to, const From &from)
	Deprecated version of pathCopy().
template<typename Digraph, typename Path>
bool	checkPath (const Digraph &digraph, const Path &path)
	Check the consistency of a path.
template<typename Digraph, typename Path>
Digraph::Node	pathSource (const Digraph &digraph, const Path &path)
	The source of a path.
template<typename Digraph, typename Path>
Digraph::Node	pathTarget (const Digraph &digraph, const Path &path)
	The target of a path.
template<typename GR>
bool	checkPlanarity (const GR &graph)
	Planarity checking of an undirected simple graph.
template<typename Iterator, typename Functor>
void	radixSort (Iterator first, Iterator last, Functor functor)
	Sorts the STL compatible range into ascending order.
template<typename Iterator, typename Functor>
void	stableRadixSort (Iterator first, Iterator last, Functor functor)
	Sorts the STL compatible range into ascending order in a stable way.
template<class F>
TimeStamp	runningTimeTest (F f, double min_time=10, unsigned int *num=NULL, TimeStamp *full_time=NULL)
	Tool to measure the running time more exactly.
template<typename DGR>
ReverseDigraph< const DGR >	reverseDigraph (const DGR &digraph)
	Returns a read-only ReverseDigraph adaptor.
template<typename DGR, typename NF, typename AF>
SubDigraph< const DGR, NF, AF >	subDigraph (const DGR &digraph, NF &node_filter, AF &arc_filter)
	Returns a read-only SubDigraph adaptor.
template<typename GR, typename NF, typename EF>
SubGraph< const GR, NF, EF >	subGraph (const GR &graph, NF &node_filter, EF &edge_filter)
	Returns a read-only SubGraph adaptor.
template<typename GR, typename NF>
FilterNodes< const GR, NF >	filterNodes (const GR &graph, NF &node_filter)
	Returns a read-only FilterNodes adaptor.
template<typename DGR, typename AF>
FilterArcs< const DGR, AF >	filterArcs (const DGR &digraph, AF &arc_filter)
	Returns a read-only FilterArcs adaptor.
template<typename GR, typename EF>
FilterEdges< const GR, EF >	filterEdges (const GR &graph, EF &edge_filter)
	Returns a read-only FilterEdges adaptor.
template<typename DGR>
Undirector< const DGR >	undirector (const DGR &digraph)
	Returns a read-only Undirector adaptor.
template<typename GR, typename DM>
Orienter< const GR, DM >	orienter (const GR &graph, DM &direction)
	Returns a read-only Orienter adaptor.
template<typename DGR, typename CM, typename FM>
ResidualDigraph< DGR, CM, FM >	residualDigraph (const DGR &digraph, const CM &capacity_map, FM &flow_map)
	Returns a (read-only) Residual adaptor.
template<typename DGR>
SplitNodes< DGR >	splitNodes (const DGR &digraph)
	Returns a (read-only) SplitNodes adaptor.
template<typename TDGR>
DigraphReader< TDGR >	digraphReader (TDGR &digraph, std::istream &is)
	Return a DigraphReader class.
template<typename TDGR>
DigraphReader< TDGR >	digraphReader (TDGR &digraph, const std::string &fn)
	Return a DigraphReader class.
template<typename TDGR>
DigraphReader< TDGR >	digraphReader (TDGR &digraph, const char *fn)
	Return a DigraphReader class.
template<typename TGR>
GraphReader< TGR >	graphReader (TGR &graph, std::istream &is)
	Return a GraphReader class.
template<typename TGR>
GraphReader< TGR >	graphReader (TGR &graph, const std::string &fn)
	Return a GraphReader class.
template<typename TGR>
GraphReader< TGR >	graphReader (TGR &graph, const char *fn)
	Return a GraphReader class.
template<typename TBGR>
BpGraphReader< TBGR >	bpGraphReader (TBGR &graph, std::istream &is)
	Return a BpGraphReader class.
template<typename TBGR>
BpGraphReader< TBGR >	bpGraphReader (TBGR &graph, const std::string &fn)
	Return a BpGraphReader class.
template<typename TBGR>
BpGraphReader< TBGR >	bpGraphReader (TBGR &graph, const char *fn)
	Return a BpGraphReader class.
SectionReader	sectionReader (std::istream &is)
	Return a SectionReader class.
SectionReader	sectionReader (const std::string &fn)
	Return a SectionReader class.
SectionReader	sectionReader (const char *fn)
	Return a SectionReader class.
template<typename TDGR>
DigraphWriter< TDGR >	digraphWriter (const TDGR &digraph, std::ostream &os)
	Return a DigraphWriter class.
template<typename TDGR>
DigraphWriter< TDGR >	digraphWriter (const TDGR &digraph, const std::string &fn)
	Return a DigraphWriter class.
template<typename TDGR>
DigraphWriter< TDGR >	digraphWriter (const TDGR &digraph, const char *fn)
	Return a DigraphWriter class.
template<typename TGR>
GraphWriter< TGR >	graphWriter (const TGR &graph, std::ostream &os)
	Return a GraphWriter class.
template<typename TGR>
GraphWriter< TGR >	graphWriter (const TGR &graph, const std::string &fn)
	Return a GraphWriter class.
template<typename TGR>
GraphWriter< TGR >	graphWriter (const TGR &graph, const char *fn)
	Return a GraphWriter class.
template<typename TBGR>
BpGraphWriter< TBGR >	bpGraphWriter (const TBGR &graph, std::ostream &os)
	Return a BpGraphWriter class.
template<typename TBGR>
BpGraphWriter< TBGR >	bpGraphWriter (const TBGR &graph, const std::string &fn)
	Return a BpGraphWriter class.
template<typename TBGR>
BpGraphWriter< TBGR >	bpGraphWriter (const TBGR &graph, const char *fn)
	Return a BpGraphWriter class.
SectionWriter	sectionWriter (std::ostream &os)
	Return a SectionWriter class.
SectionWriter	sectionWriter (const std::string &fn)
	Return a SectionWriter class.
SectionWriter	sectionWriter (const char *fn)
	Return a SectionWriter class.
template<typename K, typename V>
NullMap< K, V >	nullMap ()
	Returns a NullMap class.
template<typename K, typename V>
ConstMap< K, V >	constMap (const V &v)
	Returns a ConstMap class.
template<typename K, typename V, V v>
ConstMap< K, Const< V, v > >	constMap ()
	Returns a ConstMap class with inlined constant value.
template<typename T>
IdentityMap< T >	identityMap ()
	Returns an IdentityMap class.
template<typename V>
RangeMap< V >	rangeMap (int size=0, const V &value=V())
	Returns a RangeMap class.
template<typename V>
RangeMap< V >	rangeMap (const std::vector< V > &vector)
	Returns a RangeMap class created from an appropriate std::vector.
template<typename K, typename V, typename Compare>
SparseMap< K, V, Compare >	sparseMap (const V &value=V())
	Returns a SparseMap class.
template<typename K, typename V, typename Compare>
SparseMap< K, V, Compare >	sparseMap (const std::map< K, V, Compare > &map, const V &value=V())
	Returns a SparseMap class created from an appropriate std::map.
template<typename M1, typename M2>
ComposeMap< M1, M2 >	composeMap (const M1 &m1, const M2 &m2)
	Returns a ComposeMap class.
template<typename M1, typename M2, typename F, typename V>
CombineMap< M1, M2, F, V >	combineMap (const M1 &m1, const M2 &m2, const F &f)
	Returns a CombineMap class.
template<typename K, typename V, typename F>
FunctorToMap< F, K, V >	functorToMap (const F &f)
	Returns a FunctorToMap class.
template<typename M>
MapToFunctor< M >	mapToFunctor (const M &m)
	Returns a MapToFunctor class.
template<typename V, typename M>
ConvertMap< M, V >	convertMap (const M &map)
	Returns a ConvertMap class.
template<typename M1, typename M2>
ForkMap< M1, M2 >	forkMap (M1 &m1, M2 &m2)
	Returns a ForkMap class.
template<typename M1, typename M2>
AddMap< M1, M2 >	addMap (const M1 &m1, const M2 &m2)
	Returns an AddMap class.
template<typename M1, typename M2>
SubMap< M1, M2 >	subMap (const M1 &m1, const M2 &m2)
	Returns a SubMap class.
template<typename M1, typename M2>
MulMap< M1, M2 >	mulMap (const M1 &m1, const M2 &m2)
	Returns a MulMap class.
template<typename M1, typename M2>
DivMap< M1, M2 >	divMap (const M1 &m1, const M2 &m2)
	Returns a DivMap class.
template<typename M, typename C>
ShiftMap< M, C >	shiftMap (const M &m, const C &v)
	Returns a ShiftMap class.
template<typename M, typename C>
ShiftWriteMap< M, C >	shiftWriteMap (M &m, const C &v)
	Returns a ShiftWriteMap class.
template<typename M, typename C>
ScaleMap< M, C >	scaleMap (const M &m, const C &v)
	Returns a ScaleMap class.
template<typename M, typename C>
ScaleWriteMap< M, C >	scaleWriteMap (M &m, const C &v)
	Returns a ScaleWriteMap class.
template<typename M>
NegMap< M >	negMap (const M &m)
	Returns a NegMap class.
template<typename M>
NegWriteMap< M >	negWriteMap (M &m)
	Returns a NegWriteMap class.
template<typename M>
AbsMap< M >	absMap (const M &m)
	Returns an AbsMap class.
template<typename K>
TrueMap< K >	trueMap ()
	Returns a TrueMap class.
template<typename K>
FalseMap< K >	falseMap ()
	Returns a FalseMap class.
template<typename M1, typename M2>
AndMap< M1, M2 >	andMap (const M1 &m1, const M2 &m2)
	Returns an AndMap class.
template<typename M1, typename M2>
OrMap< M1, M2 >	orMap (const M1 &m1, const M2 &m2)
	Returns an OrMap class.
template<typename M>
NotMap< M >	notMap (const M &m)
	Returns a NotMap class.
template<typename M>
NotWriteMap< M >	notWriteMap (M &m)
	Returns a NotWriteMap class.
template<typename M1, typename M2>
EqualMap< M1, M2 >	equalMap (const M1 &m1, const M2 &m2)
	Returns an EqualMap class.
template<typename M1, typename M2>
LessMap< M1, M2 >	lessMap (const M1 &m1, const M2 &m2)
	Returns an LessMap class.
template<typename Iterator>
LoggerBoolMap< Iterator >	loggerBoolMap (Iterator it)
	Returns a LoggerBoolMap class.
template<typename K, typename GR>
IdMap< GR, K >	idMap (const GR &graph)
	Returns an IdMap class.
template<typename K, typename GR>
RangeIdMap< GR, K >	rangeIdMap (const GR &graph)
	Returns a RangeIdMap class.
template<typename GR>
SourceMap< GR >	sourceMap (const GR &graph)
	Returns a SourceMap class.
template<typename GR>
TargetMap< GR >	targetMap (const GR &graph)
	Returns a TargetMap class.
template<typename GR>
ForwardMap< GR >	forwardMap (const GR &graph)
	Returns a ForwardMap class.
template<typename GR>
BackwardMap< GR >	backwardMap (const GR &graph)
	Returns a BackwardMap class.
template<typename GR, typename POT>
PotentialDifferenceMap< GR, POT >	potentialDifferenceMap (const GR &gr, const POT &potential)
	Returns a PotentialDifferenceMap.
std::ostream &	operator<< (std::ostream &os, const TimeStamp &t)
	Prints the time counters.

Variables
const Invalid	INVALID = Invalid()
	Invalid iterators.
const Color	WHITE (1, 1, 1)
	White color constant.
const Color	BLACK (0, 0, 0)
	Black color constant.
const Color	RED (1, 0, 0)
	Red color constant.
const Color	GREEN (0, 1, 0)
	Green color constant.
const Color	BLUE (0, 0, 1)
	Blue color constant.
const Color	YELLOW (1, 1, 0)
	Yellow color constant.
const Color	MAGENTA (1, 0, 1)
	Magenta color constant.
const Color	CYAN (0, 1, 1)
	Cyan color constant.
const Color	GREY (0, 0, 0)
	Grey color constant.
const Color	DARK_RED (.5, 0, 0)
	Dark red color constant.
const Color	DARK_GREEN (0,.5, 0)
	Dark green color constant.
const Color	DARK_BLUE (0, 0,.5)
	Drak blue color constant.
const Color	DARK_YELLOW (.5,.5, 0)
	Dark yellow color constant.
const Color	DARK_MAGENTA (.5, 0,.5)
	Dark magenta color constant.
const Color	DARK_CYAN (0,.5,.5)
	Dark cyan color constant.
const long double	E = 2.7182818284590452353602874713526625L
	The Euler constant.
const long double	LOG2E = 1.4426950408889634073599246810018921L
	log_2(e)
const long double	LOG10E = 0.4342944819032518276511289189166051L
	log_10(e)
const long double	LN2 = 0.6931471805599453094172321214581766L
	ln(2)
const long double	LN10 = 2.3025850929940456840179914546843642L
	ln(10)
const long double	PI = 3.1415926535897932384626433832795029L
	pi
const long double	PI_2 = 1.5707963267948966192313216916397514L
	pi/2
const long double	PI_4 = 0.7853981633974483096156608458198757L
	pi/4
const long double	SQRT2 = 1.4142135623730950488016887242096981L
	sqrt(2)
const long double	SQRT1_2 = 0.7071067811865475244008443621048490L
	1/sqrt(2)
Random	rnd
	Global random number generator instance.

Variable Documentation

INVALID

const Invalid INVALID = Invalid()

Invalid is a global type that converts to each iterator in such a way that the value of the target iterator will be invalid.

rnd

Random rnd

A global Mersenne Twister random number generator instance.