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 graphs 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.h >

Creation

GRAPH<vtype,etype>

G

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

Operations

vtype	G.inf(node v)	returns the information of node v.
const vtype&	G[node v]	returns a reference to G.inf(v).
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, vtype x)	makes x the information of node v.
void	G.assign(edge e, etype x)	makes x the information of edge e.
node	G.new_node(vtype x)	adds a new node < x > to G and returns it.
node	G.new_node(node u, vtype x, int dir)
		adds a new node v = < x > to G and returns it. v is inserted before (dir=LEDA::before) or after (dir=LEDA::after) node u into the list of all nodes.
edge	G.new_edge(node v, node w, 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, etype x, int dir=LEDA::after)
		adds a new edge < source(e), w, x > to G by inserting it after (dir=LEDA::after) or before (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, etype x, int dir=LEDA::after)
		adds a new edge < v, target(e), x > to G by inserting it after (dir=LEDA::after) or before (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, etype x, int d1=LEDA::after, int d2=LEDA::after)
		adds a new edge x = (source(e1), target(e2), x) to G. x is inserted before (if d1=LEDA::before) or after (if d1=LEDA::after) edge e1 into adj$\_$edges(source(e1)) and before (if d2=LEDA::before) or after (if d2=LEDA::after) 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, etype x, int d1=LEDA::after, int d2=LEDA::after)
		adds a new edge (v, w, x) to G by inserting it before (if d1=LEDA::before) or after (if d1=LEDA::after) edge e1 into adj$\_$edges(v) and before (if d2=LEDA::before) or after (if d2=LEDA::after) 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, etype x, int d=LEDA::after)
		adds a new edge (v, w, x) to G by inserting it before (if d=LEDA::before) or after (if d=LEDA::after) 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(list<node> vl)
		makes vl the node list of G. Precondition vl contains exactly the nodes of G.
void	G.sort_edges(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 graphs are derived from directed graphs. All additional operations for manipulating the node and edge entries take constant time.