Classes | |
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 used by BellmanFordWizard. More... | |
class | BellmanFordWizard |
A class to make the usage of BellmanFord algorithm easier. 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 used by BfsWizard. More... | |
class | BfsWizard |
A class to make the usage of Bfs algorithm easier. More... | |
class | BinHeap |
A Binary Heap implementation. More... | |
class | Counter |
A counter class. More... | |
class | NoCounter |
'Do nothing' version of Counter More... | |
struct | DagShortestPathDefaultOperationTraits |
Default OperationTraits for the DagShortestPath algorithm class. More... | |
struct | DagShortestPathDefaultTraits |
Default traits class of DagShortestPath class. More... | |
struct | DagLongestPathOperationTraits |
Inverse OperationTraits for the DagShortestPath algorithm class. More... | |
struct | DagLongestPathTraits |
Inverse traits class of DagShortestPath class. More... | |
class | DagShortestPath |
DagShortestPath algorithm class. More... | |
struct | DagShortestPathWizardDefaultTraits |
Default traits class of DagShortestPath function. More... | |
class | DagShortestPathWizardBase |
Default traits used by DagShortestPathWizard. More... | |
class | DagShortestPathWizard |
A class to make the usage of DagShortestPath algorithm easier. 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 used by DfsWizard. More... | |
class | DfsWizard |
A class to make the usage of the Dfs algorithm easier. More... | |
struct | DfsVisitor |
Visitor class for dfs. More... | |
struct | DfsVisitDefaultTraits |
Default traits class of DfsVisit class. More... | |
class | DfsVisit |
DFS Visit 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 used by DijkstraWizard. More... | |
class | DijkstraWizard |
A class to make the usage of Dijkstra algorithm easier. More... | |
class | ListEdgeSet |
Graph using a node set of another graph and an own edge set. More... | |
class | ListUEdgeSet |
Graph using a node set of another graph and an own uedge set. More... | |
class | ExceptionMember |
Exception safe wrapper class. More... | |
class | ErrorMessage |
Exception-safe convenient "error message" class. More... | |
class | Exception |
Generic exception class. More... | |
class | LogicError |
One of the two main subclasses of Exception. More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... | |
class | RuntimeError |
One of the two main subclasses of Exception. More... | |
class | RangeError |
More... | |
class | IOError |
More... | |
class | DataFormatError |
More... | |
class | FileOpenError |
More... | |
class | AssertionFailedError |
More... | |
class | EulerIt |
Euler iterator for directed graphs. More... | |
class | UEulerIt |
Euler iterator for undirected graphs. More... | |
class | FibHeap |
Fibonacci Heap. More... | |
struct | FloydWarshallDefaultOperationTraits |
Default OperationTraits for the FloydWarshall algorithm class. More... | |
struct | FloydWarshallDefaultTraits |
Default traits class of FloydWarshall class. More... | |
class | FloydWarshall |
FloydWarshall algorithm class. More... | |
struct | FredmanTarjanDefaultTraits |
Default traits class of FredmanTarjan class. More... | |
class | FredmanTarjan |
FredmanTarjan algorithm class to find a minimum spanning tree. More... | |
class | FullGraph |
A full graph class. More... | |
class | FullUGraph |
An undirected full graph class. More... | |
class | FullBpUGraph |
An undirected full bipartite graph class. More... | |
class | GraphAdaptorBase |
Base type for the Graph Adaptors
Base type for the Graph Adaptors. More... | |
class | RevGraphAdaptor |
A graph adaptor which reverses the orientation of the edges. More... | |
class | SubGraphAdaptor |
A graph adaptor for hiding nodes and edges from a graph. More... | |
class | NodeSubGraphAdaptor |
An adaptor for hiding nodes from a graph. More... | |
class | EdgeSubGraphAdaptor |
An adaptor for hiding edges from a graph. More... | |
class | UGraphAdaptor |
An undirected graph is made from a directed graph by an adaptor
Undocumented, untested!!! If somebody knows nice demo application, let's polulate it. More... | |
class | GraphReader |
The graph reader class. More... | |
class | UGraphReader |
The undirected graph reader class. More... | |
class | Color |
Data structure representing RGB colors. More... | |
class | ColorSet |
Maps int s to different Colors. More... | |
struct | DefaultGraphToEpsTraits |
Default traits class of GraphToEps. More... | |
class | GraphToEps |
Helper class to implement the named parameters of graphToEps(). More... | |
class | ConEdgeIt |
Iterator for iterating on edges connected the same nodes. More... | |
class | ConUEdgeIt |
Iterator for iterating on uedges connected the same nodes. More... | |
class | GraphCopy |
Class to copy a graph. More... | |
class | UGraphCopy |
Class to copy an undirected graph. More... | |
class | IdMap |
Provides an immutable and unique id for each item in the graph. More... | |
class | InvertableMap |
General invertable graph-map type. More... | |
class | DescriptorMap |
Provides a mutable, continuous and unique descriptor for each item in the graph. More... | |
class | SourceMap |
Returns the source of the given edge. More... | |
class | TargetMap |
Returns the target of the given edge. More... | |
class | ForwardMap |
Returns the "forward" directed edge view of an undirected edge. More... | |
class | BackwardMap |
Returns the "backward" directed edge view of an undirected edge. More... | |
class | PotentialDifferenceMap |
Potential difference map. More... | |
class | InDegMap |
Map of the node in-degrees. More... | |
class | OutDegMap |
Map of the node out-degrees. More... | |
class | GraphWriter |
The graph writer class. More... | |
class | UGraphWriter |
The undirected graph writer class. More... | |
class | GridGraphBase |
Base graph for GridGraph. More... | |
class | GridGraph |
Grid graph class. More... | |
class | HyperCubeGraphBase |
Base graph for HyperCubeGraph. More... | |
class | HyperCubeGraph |
HyperCube graph class. More... | |
struct | Invalid |
See INVALID, how to use it. More... | |
class | IterableBoolMap |
Dynamic iterable bool map. More... | |
class | IterableIntMap |
Dynamic iterable integer map. More... | |
class | IterableValueMap |
Dynamic iterable map for comparable values. More... | |
struct | JohnsonDefaultOperationTraits |
Default OperationTraits for the Johnson algorithm class. More... | |
struct | JohnsonDefaultTraits |
Default traits class of Johnson class. More... | |
class | Johnson |
Johnson algorithm class. More... | |
class | NonConstMapWr |
Helper class for calling kruskal with "constant" output map. More... | |
class | KruskalMapInput |
Kruskal's input source. More... | |
class | KruskalSequenceOutput |
A writable bool-map that makes a sequence of "true" keys. More... | |
class | LemonReader |
Lemon Format reader class. More... | |
class | NodeSetReader |
SectionReader for reading a graph's nodeset. More... | |
class | EdgeSetReader |
SectionReader for reading a graph's edgeset. More... | |
class | UEdgeSetReader |
SectionReader for reading a undirected graph's edgeset. More... | |
class | NodeReader |
SectionReader for reading labeled nodes. More... | |
class | EdgeReader |
SectionReader for reading labeled edges. More... | |
class | UEdgeReader |
SectionReader for reading labeled undirected edges. More... | |
class | AttributeReader |
SectionReader for attributes. More... | |
class | ContentReader |
SectionReader for retrieve what is in the file. More... | |
class | LemonWriter |
Lemon Format writer class. More... | |
class | NodeSetWriter |
SectionWriter for writing a graph's nodeset. More... | |
class | EdgeSetWriter |
SectionWriter for writing a graph's edgesets. More... | |
class | UEdgeSetWriter |
SectionWriter for writing a undirected edgeset. More... | |
class | NodeWriter |
SectionWriter for writing named nodes. More... | |
class | EdgeWriter |
SectionWriter for writing named edges. More... | |
class | UEdgeWriter |
SectionWriter for writing named undirected edges. More... | |
class | AttributeWriter |
SectionWriter for attributes. More... | |
class | LinearHeap |
A Linear Heap implementation. More... | |
class | ListGraph |
A list graph class. More... | |
class | ListUGraph |
An undirected list graph class. More... | |
class | _FixId |
class | LpSolverBase |
Common base class for LP solvers. More... | |
class | LpCplex |
Interface for the CPLEX solver. More... | |
class | LpGlpk |
Interface for the GLPK LP solver. More... | |
class | LpSkeleton |
A skeleton class to implement LP solver interfaces. More... | |
class | MapIt |
Iterator for maps with possibility of changing values. More... | |
class | ConstMapIt |
Iterator for maps with possibility of getting values. More... | |
class | FilterMapIt |
Iterator for maps which filters items by the values. More... | |
class | MapBase |
Base class of maps. More... | |
class | NullMap |
Null map. (a.k.a. DoNothingMap). More... | |
class | ConstMap |
Constant map. More... | |
class | StdMap |
std::map wrapper More... | |
class | IdentityMap |
Identity mapping. More... | |
class | ConvertMap |
Convert the Value of a map to another type. More... | |
class | AddMap |
Sum of two maps. More... | |
class | ShiftMap |
Shift a map with a constant. More... | |
class | SubMap |
Difference of two maps. More... | |
class | MulMap |
Product of two maps. More... | |
class | ScaleMap |
Scales a maps with a constant. More... | |
class | DivMap |
Quotient of two maps. More... | |
class | ComposeMap |
Composition of two maps. More... | |
class | CombineMap |
Combines of two maps using an STL (binary) functor. More... | |
class | NegMap |
Negative value of a map. More... | |
class | AbsMap |
Absolute value of a map. More... | |
class | FunctorMap |
Converts an STL style functor to a map. More... | |
class | MapFunctor |
Converts a map to an STL style (unary) functor. More... | |
class | ForkMap |
Applies all map setting operations to two maps. More... | |
class | NotMap |
Logical 'not' of a map. More... | |
class | StoreBoolMap |
Writable bool map for store each true assigned elements. More... | |
class | BackInserterBoolMap |
Writable bool map for store each true assigned elements in a back insertable container. More... | |
class | FrontInserterBoolMap |
Writable bool map for store each true assigned elements in a front insertable container. More... | |
class | InserterBoolMap |
Writable bool map for store each true assigned elements in an insertable container. More... | |
class | FillBoolMap |
Fill the true setted elements with a given value. More... | |
class | SettingOrderBoolMap |
Writable bool map which stores for each true assigned elements the setting order number. More... | |
class | MatrixRowMap |
Map for the coloumn view of the matrix. More... | |
class | ConstMatrixRowMap |
Map for the row view of the matrix. More... | |
class | MatrixColMap |
Map for the row view of the matrix. More... | |
class | ConstMatrixColMap |
Map for the col view of the matrix. More... | |
class | DynamicMatrixMap |
Container for store values for each ordered pair of graph items. More... | |
class | DynamicSymMatrixMap |
Container for store values for each unordered pair of graph items. More... | |
class | MaxMatching |
Edmonds' alternating forest maximum matching algorithm. More... | |
class | MinCostFlow |
Implementation of an algorithm for finding a flow of value k (for small values of k ) having minimal total cost between 2 nodes. More... | |
class | DirPath |
A structure for representing directed paths in a graph. More... | |
class | UPath |
A structure for representing undirected path in a graph. More... | |
class | Preflow |
Preflow algorithms class. More... | |
struct | PrimDefaultTraits |
Default traits class of Prim class. More... | |
class | Prim |
Prim algorithm class to find a minimum spanning tree. More... | |
class | UnderFlowPriorityError |
Exception thrown by RadixHeap. More... | |
class | RadixHeap |
A Radix Heap implementation. More... | |
class | ControllerBase |
A base class for controllers. More... | |
class | EntityBase |
Skeleton of an entity class. More... | |
class | SimAnnBase |
Simulated annealing abstract base class. Can be used to derive a custom simulated annealing class if SimAnn doesn't fit your needs. More... | |
class | SimAnn |
Simulated annealing class. More... | |
class | SimpleController |
A simple controller for the simulated annealing class. This controller starts from a given initial temperature and evenly decreases it. More... | |
class | AdvancedController |
A controller with preset running time for the simulated annealing class. With this controller you can set the running time of the annealing process in advance. It works the following way: the controller measures a kind of divergence. The divergence is the difference of the average cost of the recently found solutions the cost of the best found one. In case this divergence is greater than a given threshold, then we decrease the annealing factor, that is we cool the system faster. In case the divergence is lower than the threshold, then we increase the temperature. The threshold is a function of the elapsed time which reaches zero at the desired end time. More... | |
class | SmartGraphBase |
Base of SmartGraph. More... | |
class | SmartGraph |
A smart graph class. More... | |
class | SmartUGraph |
A smart undirected graph class. More... | |
class | SmartBpUGraph |
A smart bipartite undirected graph class. More... | |
class | SubGraphBase |
Base for the SubGraph. More... | |
class | SubGraph |
Graph which uses a subset of an other graph's nodes and edges. More... | |
class | EdgeSubGraphBase |
Base for the EdgeSubGraph. More... | |
class | EdgeSubGraph |
Graph which uses a subset of an other graph's edges. More... | |
class | Suurballe |
Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes of minimal 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 | Tolerance< int > |
Integer specialization of Tolerance. More... | |
class | Tolerance< long long int > |
Long long integer 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... | |
struct | True |
Basic type for defining "tags". A "YES" condition for enable_if . More... | |
struct | False |
Basic type for defining "tags". A "NO" condition for enable_if . More... | |
class | xy |
A simple two dimensional vector (plainvector) implementation. More... | |
class | BoundingBox |
A class to calculate or store the bounding box of plainvectors. More... | |
class | XMap |
Map of x-coordinates of an xy<>-map. More... | |
class | ConstXMap |
Constant (read only) version of XMap. More... | |
class | YMap |
Map of y-coordinates of an xy<>-map. More... | |
class | ConstYMap |
Constant (read only) version of YMap. More... | |
class | NormSquareMap |
Map of the normSquare() of an xy-map. More... | |
class | AlterationNotifier |
Registry class to register objects observes alterations in the graph. More... | |
class | AlterableGraphExtender |
Class to extend a graph with the functionality of alteration observing. More... | |
class | AlterableUGraphExtender |
Class to extend an undirected graph with the functionality of alteration observing. More... | |
class | ArrayMap |
Graph map based on the array storage. More... | |
class | DefaultMap |
More... | |
class | MappableGraphExtender |
More... | |
class | MappableEdgeSetExtender |
More... | |
class | MappableUGraphExtender |
More... | |
class | MappableUEdgeSetExtender |
More... | |
class | QuotedStringReader |
Reader class for quoted strings. More... | |
class | PushBackReader |
Reader for standard containers. More... | |
class | InsertReader |
Reader for standard containers. More... | |
class | ParsedStringReader |
Reader for parsed string. More... | |
class | LineReader |
Reader for read the whole line. More... | |
class | PairReader |
Reader for std::pair. More... | |
class | DefaultReader |
The default item reader template class. More... | |
class | DefaultSkipper |
The default item reader for skipping a value in the stream. More... | |
struct | DefaultReaderTraits |
Standard ReaderTraits for the GraphReader class. More... | |
class | QuotedStringWriter |
Writer class for quoted strings. More... | |
class | QuotedCharArrayWriter |
Writer class for quoted char array. More... | |
class | IterableWriter |
Writer for standard containers. More... | |
class | PairWriter |
Writer for standard pairs. More... | |
class | DefaultWriter |
The default item writer template class. More... | |
struct | DefaultWriterTraits |
Standard WriterTraits for the section writers. More... | |
class | StaticMap |
Graph map with static sized storage. More... | |
class | StaticMappableGraphExtender |
More... | |
class | StaticMappableUGraphExtender |
More... | |
class | VectorMap |
Graph map based on the std::vector storage. More... | |
class | TightEdgeFilterMap |
A map for filtering the edge-set to those edges which are tight w.r.t. a node-potential and edge-distance. More... | |
Namespaces | |
namespace | concept |
The namespace of LEMON concepts and concept checking classes. | |
Typedefs | |
typedef LpGlpk | Lp |
The default LP solver. | |
Functions | |
template<class _Graph, class _LengthMap> | |
BellmanFordWizard< BellmanFordWizardBase< _Graph, _LengthMap > > | bellmanFord (const _Graph &graph, const _LengthMap &length, typename _Graph::Node source=INVALID) |
Function type interface for BellmanFord algorithm. | |
template<class GR> | |
BfsWizard< BfsWizardBase< GR > > | bfs (const GR &g, typename GR::Node s=INVALID) |
Function type interface for Bfs algorithm. | |
template<class _Graph, class _LengthMap> | |
DagShortestPathWizard< DagShortestPathWizardBase< _Graph, _LengthMap > > | dagShortestPath (const _Graph &graph, const _LengthMap &length, typename _Graph::Node source=INVALID) |
Function type interface for DagShortestPath algorithm. | |
template<class GR> | |
DfsWizard< DfsWizardBase< GR > > | dfs (const GR &g, typename GR::Node s=INVALID) |
Function type interface for Dfs algorithm. | |
template<class GR, class LM> | |
DijkstraWizard< DijkstraWizardBase< GR, LM > > | dijkstra (const GR &g, const LM &l, typename GR::Node s=INVALID) |
Function type interface for Dijkstra algorithm. | |
template<typename Graph, typename CapacityMap, typename CostMap> | |
void | readDimacs (std::istream &is, Graph &g, CapacityMap &capacity, typename Graph::Node &s, typename Graph::Node &t, CostMap &cost) |
Dimacs min cost flow reader function. | |
template<typename Graph, typename CapacityMap> | |
void | readDimacs (std::istream &is, Graph &g, CapacityMap &capacity, typename Graph::Node &s, typename Graph::Node &t) |
Dimacs max flow reader function. | |
template<typename Graph, typename CapacityMap> | |
void | readDimacs (std::istream &is, Graph &g, CapacityMap &capacity, typename Graph::Node &s) |
Dimacs shortest path reader function. | |
template<typename Graph, typename CapacityMap> | |
void | readDimacs (std::istream &is, Graph &g, CapacityMap &capacity) |
Dimacs capacitated graph reader function. | |
template<typename Graph> | |
void | readDimacs (std::istream &is, Graph &g) |
Dimacs plain graph reader function. | |
template<typename Graph> | |
void | writeDimacs (std::ostream &os, const Graph &g) |
write matching problem | |
template<class Graph> | |
bool | euler (const Graph &g) |
Checks if the graph is Euler. | |
template<class Graph, class CostMap, class TreeMap> | |
void | fredmanTarjan (const Graph &graph, const CostMap &cost, TreeMap &tree) |
Function type interface for FredmanTarjan algorithm. | |
template<typename Graph> | |
GraphReader< Graph > | graphReader (std::istream &is, Graph &g) |
Read a graph from the input. | |
template<typename Graph> | |
GraphReader< Graph > | graphReader (const std::string &fn, Graph &g) |
Read a graph from the input. | |
template<typename Graph> | |
UGraphReader< Graph > | uGraphReader (std::istream &is, Graph &g) |
Read an undirected graph from the input. | |
template<typename Graph> | |
UGraphReader< Graph > | uGraphReader (const std::string &fn, Graph &g) |
Read an undirected graph from the input. | |
Color | distantColor (const Color &c) |
Returns a visible distinct Color. | |
Color | distantBW (const Color &c) |
Returns black for light colors and white for the dark ones. | |
template<class G> | |
GraphToEps< DefaultGraphToEpsTraits< G > > | graphToEps (G &g, std::ostream &os=std::cout) |
Generates an EPS file from a graph. | |
template<class G> | |
GraphToEps< DefaultGraphToEpsTraits< G > > | graphToEps (G &g, const char *file_name) |
Generates an EPS file from a graph. | |
template<class G> | |
GraphToEps< DefaultGraphToEpsTraits< G > > | graphToEps (G &g, const std::string &file_name) |
Generates an EPS file from a graph. | |
template<typename Graph, typename ItemIt> | |
int | countItems (const Graph &g) |
Function to count the items in the graph. | |
template<typename Graph> | |
int | countNodes (const Graph &g) |
Function to count the nodes in the graph. | |
template<typename Graph> | |
int | countEdges (const Graph &g) |
Function to count the edges in the graph. | |
template<typename Graph> | |
int | countUEdges (const Graph &g) |
Function to count the undirected edges in the graph. | |
template<typename Graph> | |
int | countOutEdges (const Graph &_g, const typename Graph::Node &_n) |
Function to count the number of the out-edges from node n . | |
template<typename Graph> | |
int | countInEdges (const Graph &_g, const typename Graph::Node &_n) |
Function to count the number of the in-edges 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 Graph> | |
Graph::Edge | findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev=INVALID) |
Finds an edge between two nodes of a graph. | |
template<typename Graph> | |
Graph::UEdge | findUEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::UEdge prev=INVALID) |
Finds an uedge between two nodes of a graph. | |
template<typename Target, typename Source, typename ItemIt, typename Ref> | |
void | copyMap (Target &target, const Source &source, ItemIt it, const Ref &ref) |
Copy a map. | |
template<typename Target, typename Source, typename ItemIt> | |
void | copyMap (Target &target, const Source &source, ItemIt it) |
Copy the source map to the target map. | |
template<typename Target, typename Source> | |
GraphCopy< Target, Source > | copyGraph (Target &target, const Source &source) |
Copy a graph to an other graph. | |
template<typename Target, typename Source> | |
UGraphCopy< Target, Source > | copyUGraph (Target &target, const Source &source) |
Copy a graph to an other graph. | |
template<typename Graph> | |
GraphWriter< Graph > | graphWriter (std::ostream &os, const Graph &g) |
Write a graph to the output. | |
template<typename Graph> | |
GraphWriter< Graph > | graphWriter (const std::string &fn, const Graph &g) |
Write a graph to the output. | |
template<typename Graph> | |
UGraphWriter< Graph > | uGraphWriter (std::ostream &os, const Graph &g) |
Write an undirected graph to the output. | |
template<typename Graph> | |
UGraphWriter< Graph > | uGraphWriter (const std::string &fn, const Graph &g) |
Write an undirected graph to the output. | |
GridGraph::IndexMap | indexMap (const GridGraph &graph) |
Index map of the grid graph. | |
GridGraph::RowMap | rowMap (const GridGraph &graph) |
Row map of the grid graph. | |
GridGraph::ColMap | colMap (const GridGraph &graph) |
Column map of the grid graph. | |
template<class GR, class IN, class OUT> | |
IN::value_type::second_type | kruskal (GR const &g, IN const &in, OUT &out) |
Kruskal's algorithm to find a minimum cost tree of a graph. | |
template<class GR, class Map> | |
KruskalMapInput< GR, Map > | makeKruskalMapInput (const GR &g, const Map &m) |
Creates a KruskalMapInput object for kruskal(). | |
template<typename MatrixMap> | |
MatrixRowMap< MatrixMap > | matrixRowMap (MatrixMap &matrixMap, typename MatrixMap::FirstKey row) |
Gives back a row view of the matrix map. | |
template<typename MatrixMap> | |
MatrixColMap< MatrixMap > | matrixColMap (MatrixMap &matrixMap, typename MatrixMap::SecondKey col) |
Gives back a col view of the matrix map. | |
template<class GR, class CM, class FM> | |
Preflow< GR, typename CM::Value, CM, FM > | preflow (const GR &g, typename GR::Node source, typename GR::Node target, const CM &cap, FM &flow) |
Function type interface for Preflow algorithm. | |
template<class Graph, class CostMap, class TreeMap> | |
void | prim (const Graph &graph, const CostMap &cost, TreeMap &tree) |
Function type interface for Prim algorithm. | |
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 | counterSort (Iterator first, Iterator last, Functor functor) |
Sorts stable the stl compatible range into ascending order. | |
template<class F> | |
TimeStamp | runningTimeTest (F f, double min_time=10, int *num=NULL, TimeStamp *full_time=NULL) |
Tool to measure the running time more exactly. | |
template<typename UGraph> | |
bool | connected (const UGraph &graph) |
Check that the given undirected graph is connected. | |
template<typename UGraph> | |
int | countConnectedComponents (const UGraph &graph) |
Count the number of connected components of an undirected graph. | |
template<class UGraph, class NodeMap> | |
int | connectedComponents (const UGraph &graph, NodeMap &compMap) |
Find the connected components of an undirected graph. | |
template<typename Graph> | |
bool | stronglyConnected (const Graph &graph) |
Check that the given directed graph is strongly connected. | |
template<typename Graph> | |
int | countStronglyConnectedComponents (const Graph &graph) |
Count the strongly connected components of a directed graph. | |
template<typename Graph, typename NodeMap> | |
int | stronglyConnectedComponents (const Graph &graph, NodeMap &compMap) |
Find the strongly connected components of a directed graph. | |
template<typename Graph, typename EdgeMap> | |
int | stronglyConnectedCutEdges (const Graph &graph, EdgeMap &cutMap) |
Find the cut edges of the strongly connected components. | |
template<typename UGraph> | |
int | countBiNodeConnectedComponents (const UGraph &graph) |
Count the biconnected components. | |
template<typename UGraph> | |
bool | biNodeConnected (const UGraph &graph) |
Checks the graph is bi-node-connected. | |
template<typename UGraph, typename UEdgeMap> | |
int | biNodeConnectedComponents (const UGraph &graph, UEdgeMap &compMap) |
Find the bi-node-connected components. | |
template<typename UGraph, typename NodeMap> | |
int | biNodeConnectedCutNodes (const UGraph &graph, NodeMap &cutMap) |
Find the bi-node-connected cut nodes. | |
template<typename UGraph> | |
bool | biEdgeConnected (const UGraph &graph) |
Checks that the graph is bi-edge-connected. | |
template<typename UGraph> | |
int | countBiEdgeConnectedComponents (const UGraph &graph) |
Count the bi-edge-connected components. | |
template<typename UGraph, typename NodeMap> | |
int | biEdgeConnectedComponents (const UGraph &graph, NodeMap &compMap) |
Find the bi-edge-connected components. | |
template<typename UGraph, typename UEdgeMap> | |
int | biEdgeConnectedCutEdges (const UGraph &graph, UEdgeMap &cutMap) |
Find the bi-edge-connected cut edges. | |
template<typename Graph, typename NodeMap> | |
void | topologicalSort (const Graph &graph, NodeMap &order) |
Sort the nodes of a DAG into topolgical order. | |
template<typename Graph, typename NodeMap> | |
bool | checkedTopologicalSort (const Graph &graph, NodeMap &order) |
Sort the nodes of a DAG into topolgical order. | |
template<typename Graph> | |
bool | dag (const Graph &graph) |
Check that the given directed graph is a DAG. | |
template<typename UGraph> | |
bool | acyclic (const UGraph &graph) |
Check that the given undirected graph is acyclic. | |
template<typename UGraph> | |
bool | tree (const UGraph &graph) |
Check that the given undirected graph is tree. | |
template<typename UGraph> | |
bool | bipartite (const UGraph &graph) |
Check if the given undirected graph is bipartite or not. | |
template<typename UGraph, typename NodeMap> | |
bool | bipartitePartitions (const UGraph &graph, NodeMap &partMap) |
Check if the given undirected graph is bipartite or not. | |
Variables | |
const Invalid | INVALID = Invalid() |
Invalid iterators. | |
const CapacityMap & | _capacity |
An adaptor for composing a subgraph of a bidirected graph made from a directed one.
An adaptor for composing a subgraph of a bidirected graph made from a directed one. An adaptor for composing bidirected graph from a directed one. / / /. | |
const Invalid | INVALID |
Invalid iterators. | |
const char | default_solver_name [] = "SOLVER" |
The default LP solver identifier string. |
|
Returns a Color which is as different from the given parameter as it is possible. |
|
Just returns an IndexMap for the grid graph. |
|
Just returns a RowMap for the grid graph. |
|
Just returns a ColMap for the grid graph. |
|
It makes easier to use KruskalMapInput by making it unnecessary to explicitly give the type of the parameters. In most cases you possibly want to use kruskal() instead.
|
|
Gives back a row view of the matrix map. |
|
Gives back a col view of the matrix map. |
|
Invalid is a global type that converts to each iterator in such a way that the value of the target iterator will be 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. |