Namespaces | Classes | Typedefs | Functions | Variables

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.

A global Mersenne Twister random number generator instance.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines