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 (graph& G) 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<vtype,etype>::node_value_type	the type of node data (vtype).
GRAPH<vtype,etype>::edge_value_type	the type of edge data (etype).

Creation

GRAPH<vtype,etype>

G

creates an instance G of type GRAPH<vtype,etype> and initializes it to the empty graph.

Operations

const vtype&	G.inf(node v)	returns the information of node v.
const vtype&	G[node v]	returns a reference to G.inf(v).
const etype&	G.inf(edge e)	returns the information of edge e.
const etype&	G[edge e]	returns a reference to G.inf(e).
node_array<vtype>&	G.node_data()	makes the information associated with the nodes of G available as a node array of type node_array<vtype>.
edge_array<etype>&	G.edge_data()	makes the information associated with the edges of G available as an edge array of type edge_array<etype>.
void	G.assign(node v, const vtype& x)
		makes x the information of node v.
void	G.assign(edge e, const etype& x)
		makes x the information of edge e.
node	G.new_node(const vtype& x)
		adds a new node < x > to G and returns it.
node	G.new_node(node u, const vtype& x, int dir)
		adds a new node v = < x > to G and returns it. v is inserted in front of (dir=leda::before) or behind (dir=leda::behind) node u into the list of all nodes.
edge	G.new_edge(node v, node w, const etype& x)
		adds a new edge < v, w, x > to G by appending it to adj$\_$edges(v) and to in$\_$edges(w) and returns it.
edge	G.new_edge(edge e, node w, const etype& x, int dir=leda::behind)
		adds a new edge < source(e), w, x > to G by inserting it behind (dir=leda::behind) or in front of (dir=leda::before) edge e into adj$\_$edges(source(e)) and appending it to in$\_$edges(w). Returns the new edge.
edge	G.new_edge(node v, edge e, const etype& x, int dir=leda::behind)
		adds a new edge < v, target(e), x > to G by inserting it behind (dir=leda::behind) or in front of (dir=leda::before) edge e into in$\_$edges(target(e)) and appending it to adj$\_$edges(v). Returns the new edge.
edge	G.new_edge(edge e1, edge e2, const etype& x, int d1=leda::behind, int d2=leda::behind)
		adds a new edge x = (source(e1), target(e2), x) to G. x is inserted in front of (if d1=leda::before) or behind (if d1=leda::behind) edge e1 into adj$\_$edges(source(e1)) and in front of (if d2=leda::before) or behind (if d2=leda::behind) edge e2 into in$\_$edges(target(e2)) (if G is directed) or adj$\_$edges(target(e2)) (if G is undirected). The operation returns the new edge x.
edge	G.new_edge(node v, edge e1, node w, edge e2, const etype& x, int d1=leda::behind, int d2=leda::behind)
		adds a new edge (v, w, x) to G by inserting it in front of (if d1=leda::before) or behind (if d1=leda::behind) edge e1 into adj$\_$edges(v) and in front (if d2=leda::before) or behind (if d2=leda::behind) edge e2 into adj$\_$edges(w), and returns it. Precondition G is undirected, v! = w, e1 is incident to v, and e2 is incident to w.
edge	G.new_edge(node v, edge e, node w, const etype& x, int d=leda::behind)
		adds a new edge (v, w, x) to G by inserting it in front of (if d=leda::before) or behind (if d=leda::behind) edge e into adj$\_$edges(v) and appending it to adj$\_$edges(w), and returns it. Precondition G is undirected, v! = w, e1 is incident to v, and e is incident to v.
void	G.sort_nodes(const list<node>& vl)
		makes vl the node list of G. Precondition vl contains exactly the nodes of G.
void	G.sort_edges(const list<edge>& el)
		makes el the edge list of G. Precondition el contains exactly the edges of G.
void	G.sort_nodes()	the nodes of G are sorted increasingly according to their contents. Precondition vtype is linearly ordered.
void	G.sort_edges()	the edges of G are sorted increasingly according to their contents. Precondition etype is linearly ordered.
void	G.write(string fname)	writes G to the file with name fname. The output operators operator«(ostream&, const vtype&) and operator«(ostream&, const etype&)(cf. section 1.6) must be defined.
int	G.read(string fname)	reads G from the file with name fname. The input operators operator»(istream&,vtype&) and operator»(istream&,etype&) (cf. section 1.6) must be defined. Returns error code 1     if file fname does not exist 2     if graph is not of type GRAPH<vtype,etype> 3     if file fname does not contain a graph 0     if reading was successful.

Implementation

Parameterized graph are derived from directed graph. All additional operations for manipulating the node and edge entries take constant time.