lemon Namespace Reference

Detailed Description

The namespace of LEMON

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	ArgParser
	Command line arguments parser. 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
	A Binary Heap implementation. More...
class	BucketHeap
	A Bucket Heap implementation. More...
class	SimpleBucketHeap
	A Simplified Bucket Heap implementation. More...
class	CbcMip
	Interface for the CBC MIP solver. 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
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	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...
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...
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...
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...
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. More...
class	FullDigraph
	A full digraph class. More...
class	FullGraph
	An undirected full 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	GridGraph
	Grid graph class. More...
class	HaoOrlin
	Hao-Orlin algorithm for finding a minimum cut in a digraph. More...
class	HypercubeGraph
	Hypercube graph class. More...
class	DigraphReader
	LGF reader for directed graphs More...
class	GraphReader
	LGF reader for undirected 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 directed 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	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	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	MinCostArborescenceDefaultTraits
	Default traits class for MinCostArborescence class. More...
class	MinCostArborescence
	Minimum Cost Arborescence algorithm class. More...
class	NetworkSimplex
	Implementation of the primal Network Simplex algorithm for finding a minimum cost flow. 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...
struct	PreflowDefaultTraits
	Default traits class of Preflow class. More...
class	Preflow
	Preflow algorithm class. More...
class	RadixHeap
	A Radix Heap implementation. More...
class	Random
	Mersenne Twister random number generator. More...
class	SmartDigraphBase
	Base of SmartDigraph. More...
class	SmartDigraph
	A smart directed graph class. More...
class	SmartGraph
	A smart undirected graph class. More...
class	SoplexLp
	Interface for the SOPLEX solver. 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<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)
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	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 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 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.
bool	isNaN (double v)
	Check whether the parameter is NaN or not.
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 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.

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

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.

Random rnd

A global Mersenne Twister random number generator instance.