Static Graphs ( static_graph )

Definition

1.1 Motivation.

The data type static$\_$graph representing static graph is the result of two observations:

First, most graph algorithms do not change the underlying graph, they work on a constant or static graph and second, different algorithms are based on different models (we call them categories) of graph.

The LEDA data type graph represents all types of graph used in the library, such as directed, undirected, and bidirected graph, networks, planar maps, and geometric graph. It provides the operations for all of these graph in one fat interface. For efficiency reasons it makes sense to provide special graph data types for special purposes. The template data type static_graph, which is parameterized with the graph category, provides specialized implementations for some of these graph types.

1.2 Static Graphs.

A static graph consists of a fixed sequence of nodes and edges. The parameterized data type static_graph<category, node_data, edge_data> is used to represent static graph. The first template parameter category defines the graph category and is taken from {directed_graph, bidirectional_graph, opposite_graph} (see 1.3 for the details). The last two parameters are optional and can be used to define user-defined data structures to be included into the node and edge objects (see 1.4 for the details). An instance G of the parameterized data type static$\_$graph contains a sequence V of nodes and a sequence E of edges. New nodes or edges can be appended only in a construction phase which has to be started by calling G.start_construction() and terminated by G.finish_construction(). For every node or edge x we define index(x) to be equal to the rank of x in its sequence. During the construction phase, the sequence of the source node index of all inserted edges must be non-decreasing. After the construction phase both sequences V and E are fixed.

1.3 Graph Categories.

We distinguish between five categories where currently only the first three are supported by static_graph:

• Directed Graphs (directed_graph) represent the concept of a directed graph by providing the ability to iterate over all edges incident to a given node v and to ask for the target node of a given edge e.

• Bidirectional Graphs (bidirectional_graph) extend directed graph by supporting in addition iterations over all incoming edges at a given node v and to ask for the source node of a given edge e.

• Opposite Graphs (opposite_graph) are a variant of the bidirectional graph category. They do not support the computation of the source or target node of a given edge but allow walking from one terminal v of an edge e to the other opposite one.

Not yet implemented are bidirected and undirected graph.

1.4 Node and Edge Data.

Static graph support several efficient ways - efficient compared to using node_arrays, edge_arrays, node_maps, and edge_maps - to associate data with the edges and nodes of the graph.

1.4.1 Dynamic Slot Assignment:

It is possible to attach two optional template parameters data_slots<int> at compile time:

static_graph<directed_graph, data_slots<3>, data_slots<1> > G;

specifies a static directed graph G with three additional node slots and one additional edge slot. Node and edge arrays can use these data slots, instead of allocating an external array. This method is also supported for the standard LEDA data type graph. Please see the manual page for node_array resp. edge_array (esp. the operations use_node_data resp. use_edge_data) for the details.

The method is called dynamic slot assignment since the concrete arrays are assigned during runtime to the slots.

1.4.2 Static Slot Assignment:

This method is even more efficient. A variant of the node and edge arrays, the so-called node_slot and edge_slot data types, are assigned to the slots during compilation time. These types take three parameters: the element type of the array, an integer slot number, and the type of the graph:

node_slot<E, graph_t, slot>;
edge_slot<E, graph_t, slot>;

Here is an example for the use of static slot assignment in a maxflow graph algorithm. It uses three node slots for storing distance, excess, and a successor node, and two edge slots for storing the flow and capacity.

typedef static_graph<opposite_graph, data_slots<3>, data_slots<2> > maxflow_graph;
node_slot<node, maxflow_graph, 0> succ;
node_slot<int, maxflow_graph, 1> dist;
node_slot<edge, maxflow_graph, 2> excess;
edge_slot<int, maxflow_graph, 0> flow;
edge_slot<int, maxflow_graph, 1> cap;

When using the data types node_slot resp. edge_slot one has to include the files LEDA/graph/edge_slot.h.

1.4.3 Customizable Node and Edge Types:

It is also possible to pass any structure derived from data_slots<int> as second or third parameter. Thereby the nodes and edges are extended by named data members. These are added in addition to the data slots specified in the base type. In the example

struct flow_node:public data_slots<1>
{ int excess;
  int level;
}

struct flow_edge:public data_slots<2>
{ int flow;
  int cap;
}

typedef static_graph<bidirectional_graph, flow_node, flow_edge> flow_graph;

there are three data slots (one of them unnamed) associated with each node and four data slots (two of them unnamed) associated with each edge of a flow_graph.

The named slots can be used as follows:

flow_graph::node v;
forall_nodes(v, G) v->excess = 0;

#include < LEDA/graph/static_graph.h >

Creation

static$\_$graph < category, node$\_$data = data$\_$slots < 0 > , edge_data = data$\_$slots < 0 > > G;

creates an empty static graph G. category is either directed_graph, or bidirectional_graph, or opposite_graph. The use of the other parameters is explained in the section Node and Edge Data given above.

Types

static_graph::node	the node type. Note: It is different from graph::node.
static_graph::edge	the edge type. Note: It is different from graph::edge.

Operations

The interface consists of two parts. The first part - the basic interface - is independent from the actual graph category, the specified operations are common to all graph. The second part of the interface is different for every category and contains macros to iterate over incident edges or adjacent nodes and methods for traversing a given edge.

void	G.start_construction(int n, int m)
		starts the construction phase for a graph with up to n nodes and m edges.
node	G.new_node()	creates a new node, appends it to V, and returns it. The operation may only be called during construction phase and at most n times.
edge	G.new_edge(node v, node w)
		creates the edge (v, w), appends it to E, and returns it. The operation may only be called during construction phase and at most m times. Precondition All edges (u, v) of G with index(u) < index(v) have been created before.
void	G.finish_construction()	terminates the construction phase.
int	forall_nodes(v, G)	v iterates over the node sequence.
int	forall_edges(e, G)	e iterates over the edge sequence.

Static Directed Graphs (static_graph< directed_graphtex2html_wrap_inline> )

For this category the basic interface of static_graph is extended by the operations:

node	G.target(edge e)	returns the target node of e.
node	G.outdeg(node v)	returns the number of outgoing edges of v.
int	forall_out_edges(e, v)	e iterates over all edges with source(e) = v.

Static Bidirectional Graphs (static_graph< bidirectional_graphtex2html_wrap_inline> )

For this category the basic interface of static_graph is extended by the operations:

node	G.target(edge e)	returns the target node of e.
node	G.source(edge e)	returns the source node of e.
node	G.outdeg(node v)	returns the number of outgoing edges of v.
node	G.indeg(node v)	returns the number of incoming edges of v.
int	forall_out_edges(e, v)	e iterates over all edges with source(e) = v.
int	forall_in_edges(e, v)	e iterates over all edges with target(e) = v.

Static Opposite Graphs (static_graph< opposite_graphtex2html_wrap_inline> )

For this category the basic interface of static_graph is extended by the operations:

node	G.opposite(edge e, node v)
		returns the opposite to v along e.
node	G.outdeg(node v)	returns the number of outgoing edges of v.
node	G.indeg(node v)	returns the number of incoming edges of v.
int	forall_out_edges(e, v)	e iterates over all edges with source(e) = v.
int	forall_in_edges(e, v)	e iterates over all edges with target(e) = v.

Example

The simple example illustrates how to create a small graph and assign some values. To see how static graph can be used in a max flow algorithm - please see the source file mfs.c in the directory testflow.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_slot.h>
#include <LEDA/graph/edge_slot.h>
#include <LEDA/core/array.h>

using namespace leda;

struct node_weight:public data_slots<0>
{ int weight; }

struct edge_cap:public data_slots<0>
{ int cap; }

typedef static_graph<opposite_graph, node_weight, edge_cap> static_graph;
typedef static_graph::node st_node;
typedef static_graph::edge st_edge;


int main ()
{
   static_graph G;
   array<st_node> v(4);
   array<st_edge> e(4);
   G.start_construction(4,4);

   for(int i =0; i < 4; i++) v[i] = G.new_node();

   e[0] = G.new_edge(v[0], v[1]);
   e[1] = G.new_edge(v[0], v[2]);
   e[2] = G.new_edge(v[1], v[2]);
   e[3] = G.new_edge(v[3], v[1]);
   G.finish_construction();
   st_node v;
   st_edge e;
   forall_nodes(v, G) v->weight = 1;
   forall_edges(e, G) e->cap = 10;

   return 0;
}