Graph Structures

Detailed Description

The implementation of combinatorial algorithms heavily relies on efficient graph implementations. LEMON offers data structures which are planned to be easily used in an experimental phase of implementation studies, and thereafter the program code can be made efficient by small modifications.

The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of graph we require to handle, memory or time usage limitations or in the set of operations through which the graph can be accessed. LEMON provides several physical graph structures to meet the diverging requirements of the possible users. In order to save on running time or on memory usage, some structures may fail to provide some graph features like arc/edge or node deletion.

Alteration of standard containers need a very limited number of operations, these together satisfy the everyday requirements. In the case of graph structures, different operations are needed which do not alter the physical graph, but gives another view. If some nodes or arcs have to be hidden or the reverse oriented graph have to be used, then this is the case. It also may happen that in a flow implementation the residual graph can be accessed by another algorithm, or a node-set is to be shrunk for another algorithm. LEMON also provides a variety of graphs for these requirements called graph adaptors. Adaptors cannot be used alone but only in conjunction with other graph representations.

You are free to use the graph structure that fit your requirements the best, most graph algorithms and auxiliary data structures can be used with any graph structure.

See also: Graph Structure Concepts.

Classes
class	ListArcSet< GR >
	Digraph using a node set of another digraph or graph and an own arc set. More...
class	ListEdgeSet< GR >
	Graph using a node set of another digraph or graph and an own edge set. More...
class	SmartArcSet< GR >
	Digraph using a node set of another digraph or graph and an own arc set. More...
class	SmartEdgeSet< GR >
	Graph using a node set of another digraph or graph and an own edge set. More...
class	FullDigraph
	A directed full graph class. More...
class	FullGraph
	An undirected full graph class. More...
class	FullBpGraph
	An undirected full bipartite graph class. More...
class	GridGraph
	Grid graph class. More...
class	HypercubeGraph
	Hypercube graph class. More...
class	ListDigraph
	A general directed graph structure. More...
class	ListGraph
	A general undirected graph structure. More...
class	ListBpGraph
	A general undirected graph structure. More...
class	SmartDigraph
	A smart directed graph class. More...
class	SmartGraph
	A smart undirected graph class. More...
class	SmartBpGraph
	A smart undirected bipartite graph class. More...
class	StaticDigraph
	A static directed graph class. More...
class	GridGraph::ColMap
class	GridGraph::IndexMap
class	GridGraph::RowMap
class	HypercubeGraph::HyperMap< T, BF >
	Linear combination map. More...
class	ListDigraph::Snapshot
	Class to make a snapshot of the digraph and restore it later. More...
class	ListGraph::Snapshot
	Class to make a snapshot of the graph and restore it later. More...
class	ListBpGraph::Snapshot
	Class to make a snapshot of the graph and restore it later. More...
class	SmartDigraph::Snapshot
	Class to make a snapshot of the digraph and to restore it later. More...
class	SmartGraph::Snapshot
	Class to make a snapshot of the graph and to restore it later. More...
class	SmartBpGraph::Snapshot
	Class to make a snapshot of the graph and to restore it later. More...

Modules
	Adaptor Classes for Graphs
	Adaptor classes for digraphs and graphs.

Files
file	edge_set.h
	ArcSet and EdgeSet classes.
file	full_graph.h
	FullDigraph and FullGraph classes.
file	grid_graph.h
	GridGraph class.
file	hypercube_graph.h
	HypercubeGraph class.
file	list_graph.h
	ListDigraph and ListGraph classes.
file	smart_graph.h
	SmartDigraph and SmartGraph classes.
file	static_graph.h
	StaticDigraph class.