Graph Structures

The same group on the Doxygen site.

group Graph Structures

Graph structures implemented in LEMON.

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.

Subgroups

Group

Description

Adaptor Classes for Graphs

Adaptor classes for digraphs and graphs.

Classes

Class

Description

CompactDigraph

A static directed graph class.

ListArcSet

Digraph using a node set of another digraph or graph and an own arc set.

ListEdgeSet

Graph using a node set of another digraph or graph and an own edge set.

SmartArcSet

Digraph using a node set of another digraph or graph and an own arc set.

SmartEdgeSet

Graph using a node set of another digraph or graph and an own edge set.

FullDigraph

A directed full graph class.

FullGraph

An undirected full graph class.

FullBpGraph

An undirected full bipartite graph class.

GridGraph

Grid graph class.

HypercubeGraph

Hypercube graph class.

ListDigraph

A general directed graph structure.

ListGraph

A general undirected graph structure.

ListBpGraph

A general undirected graph structure.

SmartDigraph

A smart directed graph class.

SmartGraph

A smart undirected graph class.

SmartBpGraph

A smart undirected bipartite graph class.

StaticDigraph

A static directed graph class.

StaticGraph

A static undirected graph class.

Other classes of its headers

Class

Description

CompactDigraphBase

ListArcSetBase

ListEdgeSetBase

SmartArcSetBase

SmartEdgeSetBase

FullDigraphBase

FullGraphBase

FullBpGraphBase

GridGraphBase

HypercubeGraphBase

ListDigraphBase

ListGraphBase

ListBpGraphBase

SmartDigraphBase

SmartGraphBase

SmartBpGraphBase

StaticDigraphBase

StaticGraphBase