Next: Static Graphs ( static_graph Up: Graphs and Related Data Previous: Graphs ( graph )   Contents   Index

# Parameterized Graphs ( GRAPH )

Definition

A parameterized graph G is a graph whose nodes and edges contain additional (user defined) data. Every node contains an element of a data type vtype, called the node type of G and every edge contains an element of a data type etype called the edge type of G. We use < v, w, y > to denote an edge (v, w) with information y and < x > to denote a node with information x.

All operations defined for the basic graph type graph are also defined on instances of any parameterized graph type GRAPH<vtype,etype>. For parameterized graph there are additional operations to access or update the information associated with its nodes and edges. Instances of a parameterized graph type can be used wherever an instance of the data type graph can be used, e.g., in assignments and as arguments to functions with formal parameters of type graph&. If a function f (graphG) is called with an argument Q of type GRAPH<vtype,etype> then inside f only the basic graph structure of Q can be accessed. The node and edge entries are hidden. This allows the design of generic graph algorithms, i.e., algorithms accepting instances of any parametrized graph type as argument.

#include < LEDA/graph/graph.h >

Types

 GRAPH::node_value_type the type of node data (vtype). GRAPH::edge_value_type the type of edge data (etype).

Creation

 GRAPH G creates an instance G of type GRAPH and initializes it to the empty graph.

Operations