This package provides
- fully dynamic and mutable labeled graphs
-
dynamic and mutable mappings from the nodes or edges of a graph to
arbitrary values (node arrays and edge arrays)
- dynamic and mutable node matrices and edge matrices
- basic graph algorithms
For efficiency the package is implemented in C++. The implementation of
the graph data structure permits an efficient copying of instances so
that the graph package performs well with the Mozart garbage collection
and the cloning of computation spaces.
Graphs are implemented using doubly linked lists over the nodes and
the ingoing and outgoing edges of nodes. This provides constant time
adding, removing, hiding and restoring of nodes and edges. Apart from
that a graph instance can be efficiently viewed as both, directed and
undirected. In the directed version you always consider only outgoing
edges of a node. In the undirected version you consider ingoing and
outgoing edges, incident edges for short. Similary you can view a
graph instance simultanously as its transpose simply by considering
the inedges of nodes instead of their outedges.
The package comes with a nice user interface that is similar to the
interface of LEDA graphs.
Until now the following graph algorithms are available:
- topological sorting
- weakly connected components
- 2-node connected components alias biconnected components
- 2-egde connected components
- strongly connected components
- transitive closure (reachability relation)
- acyclic transitive reduction
- isolated nodes
- isolated edges