Loading...
Searching...
No Matches
lemon Namespace Reference
Data Structures » Heap Structures | General Optimization Tools » LP and MIP Solvers | Data Structures » Maps

## 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.