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