Definition
The data type staticgraph 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.
We distinguish between five categories where currently only the first three are supported by static_graph:
Not yet implemented are bidirected and undirected graph.
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.
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.
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.
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
staticgraph < category, nodedata = dataslots < 0 > , edge_{d}ata = dataslots < 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.
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:
Static Opposite Graphs (static_graph< opposite_graphtex2html_wrap_inline> )
For this category the basic interface of static_graph is extended by the operations:
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; }