Next: Parameterized Graphs ( GRAPH Up: Graphs and Related Data Previous: Graphs and Related Data   Contents   Index

# Graphs ( graph )

Definition

An instance G of the data type graph consists of a list V of nodes and a list E of edges (node and edge are item types). Distinct graph have disjoint node and edge lists. The value of a variable of type node is either the node of some graph, or the special value nil (which is distinct from all nodes), or is undefined (before the first assignment to the variable). A corresponding statement is true for the variables of type edge.

A graph with empty node list is called empty. A pair of nodes (v, w) V x V is associated with every edge e E ; v is called the source of e and w is called the target of e , and v and w are called endpoints of e . The edge e is said to be incident to its endpoints.

A graph is either directed or undirected. The difference between directed and undirected graph is the way the edges incident to a node are stored and how the concept adjacent is defined.

In directed graph two lists of edges are associated with every node v : adj_edges(v) = {e E | v = source(e)} , i.e., the list of edges starting in v , and in_edges(v) = {e E | v = target(e)} , i.e., the list of edges ending in v . The list adjedges(v) is called the adjacency list of node v and the edges in adjedges(v) are called the edges adjacent to node v . For directed graph we often use outedges(v) as a synonym for adjedges(v) .

In undirected graph only the list adjedges(v) is defined for every every node v . Here it contains all edges incident to v , i.e., adj_edges(v) = {e E | v {source(e), target(e)}} . An undirected graph may not contain selfloops, i.e., it may not contain an edge whose source is equal to its target.

In a directed graph an edge is adjacent to its source and in an undirected graph it is adjacent to its source and target. In a directed graph a node w is adjacent to a node v if there is an edge (v, w) E ; in an undirected graph w is adjacent to v if there is an edge (v, w) or (w, v) in the graph.

A directed graph can be made undirected and vice versa: G .make_undirected() makes the directed graph G undirected by appending for each node v the list inedges(v) to the list adjedges(v) (removing selfloops). Conversely, G .make_directed() makes the undirected graph G directed by splitting for each node v the list adjedges(v) into the lists outedges(v) and inedges(v) . Note that these two operations are not exactly inverse to each other. The data type ugraph (cf. section Undirected Graphs) can only represent undirected graph.

Reversal Information, Maps and Faces

The reversal information of an edge e is accessed through G.reversal(e), it has type edge and may or may not be defined (=nil). Assume that G.reversal(e) is defined and let e' = G.reversal(e) . Then e = (v, w) and e' = (w, v) for some nodes v and w , G.reversal(e') is defined and e = G.reversal(e') . In addtion, e e' . In other words, reversal deserves its name.

We call a directed graph bidirected if the reversal information can be properly defined for all edges in G , resp. if there exists a bijective function rev : E E with the properties of reversal as described above and we call a bidirected graph a map if all edges have their reversal information defined. Maps are the data structure of choice for embedded graph. For an edge e of a map G let face_cycle_succ(e) = cyclic_adj_pred(reversal(e)) and consider the sequence e , face_cycle_succ(e), face_cycle_succ(face_cycle_succ(e)), ... . The first edge to repeat in this sequence is e (why?) and the set of edges appearing in this sequence is called the face cycle containing e . Each edge is contained in some face cycle and face cycles are pairwise disjoint. Let f be the number of face cycles, n be the number of (non-isolated) nodes, m be the number of edges, and let c be the number of (non-singleton) connected components. Then g = (m/2 - n - f )/2 + c is called the genus of the map [89] (note that m/2 is the number of edges in the underlying undirected graph). The genus is zero if and only if the map is planar, i.e., there is an embedding of G into the plane such that for every node v the counter-clockwise ordering of the edges around v agrees with the cyclic ordering of v 's adjacency list. (In order to check whether a map is planar, you may use the function Is_Plane_Map() in Miscellaneous Graph Functions.)

If a graph G is a map the faces of G can be constructed explicitly by G.compute_faces(). Afterwards, the faces of G can be traversed by different iterators, e.g., forall_faces(f,G) iterates over all faces , forall_adj_faces(v) iterates over all faces adjacent to node v . By using face maps or arrays (data types face_map and face_array) additional information can be associated with the faces of a graph. Note that any update operation performed on G invalidates the list of faces. See the section on face operations for a complete list of available operations for faces.

#include < LEDA/graph/graph.h >

Creation

 graph G creates an object G of type graph and initializes it to the empty directed graph. graph G(int n_slots, int e_slots) this constructor specifies the numbers of free data slots in the nodes and edges of G that can be used for storing the entries of node and edge arrays. See also the description of the use_node_data() and use_edge_data() operations in Node Arrays and Edge Arrays.

Operations

 void G.init(int n, int m) this operation has to be called for semi-dynamic graph (if compiled with -DGRAPH_REP=2) immediately after the constructor to specify upper bounds n and m for the number of nodes and edges respectively. This operation has no effect if called for the (fully-dynamic) standard graph representation.

a) Access operations

b) Update operations

c) Reversal Edges and Maps

 void G.make_bidirected() makes G bidirected by inserting missing reversal edges. void G.make_bidirected(list< edge> & R) makes G bidirected by inserting missing reversal edges. Appends all inserted edges to list R . bool G.is_bidirected() returns true if every edge has a reversal and false otherwise. bool G.make_map() sets the reversal information of a maximal number of edges of G. Returns true if G is bidirected and false otherwise. void G.make_map(list< edge> & R) makes G bidirected by inserting missing reversal edges and then turns it into a map setting the reversals for all edges. Appends all inserted edges to list R . bool G.is_map() tests whether G is a map. edge G.reversal(edge e) returns the reversal information of edge e (nil if not defined). void G.set_reversal(edge e, edge r) makes r the reversal of e and vice versa. If the reversal information of e was defined prior to the operation, say as e', the reversal information of e' is set to nil. The same holds for r. Precondition e = (v, w) and r = (w, v) for some nodes v and w . edge G.face_cycle_succ(edge e) returns the cyclic adjacency predecessor of reversal(e). Precondition reversal(e) is defined. edge G.face_cycle_pred(edge e) returns the reversal of the cyclic adjacency successor s of e . Precondition reversal(s) is defined. edge G.split_map_edge(edge e) splits edge e = (v, w) and its reversal r = (w, v) into edges (v, u) , (u, w) , (w, u) , and (u, v) . Returns the edge (u, w) . edge G.new_map_edge(edge e1, edge e2) inserts a new edge e = (source(e1), source(e2) after e1 into the adjacency list of source(e1) and an edge r reversal to e after e2 into the adjacency list of source(e2) . list< edge> G.triangulate_map() triangulates the map G by inserting additional edges. The list of inserted edges is returned. Precondition G must be connected. The algorithm ([47]) has running time O(| V| + | E|) . void G.dual_map(graph& D) constructs the dual of G in D . The algorithm has linear running time. Precondition G must be a map.

For backward compatibility

 edge G.reverse(edge e) returns reversal(e) (historical). edge G.succ_face_edge(edge e) returns face_cycle_succ(e) (historical). edge G.next_face_edge(edge e) returns face_cycle_succ(e) (historical). edge G.pred_face_edge(edge e) returns face_cycle_pred(e) (historical).

d) Faces and Planar Maps

 void G.compute_faces() constructs the list of face cycles of G. Precondition G is a map. face G.face_of(edge e) returns the face of G to the left of edge e . face G.adj_face(edge e) returns G.face_of(e). void G.print_face(face f) prints face f . int G.number_of_faces() returns the number of faces of G. face G.first_face() returns the first face of G . (nil if empty). face G.last_face() returns the last face of G . face G.choose_face() returns a random face of G (nil if G is empty). face G.succ_face(face f) returns the successor of face f in the face list of G (nil if it does not exist). face G.pred_face(face f) returns the predecessor of face f in the face list of G (nil if it does not exist). const list< face> & G.all_faces() returns the list of all faces of G. list< face> G.adj_faces(node v) returns the list of all faces of G adjacent to node v in counter-clockwise order. list< node> G.adj_nodes(face f) returns the list of all nodes of G adjacent to face f in counter-clockwise order. list< edge> G.adj_edges(face) returns the list of all edges of G bounding face f in counter-clockwise order. int G.size(face f) returns the number of edges bounding face f . edge G.first_face_edge(face f) returns the first edge of face f in G. edge G.split_face(edge e1, edge e2) inserts the edge e = (source(e1), source(e2)) and its reversal into G and returns e . Precondition e1 and e2 are bounding the same face F . The operation splits F into two new faces. face G.join_faces(edge e) deletes edge e and its reversal r and updates the list of faces accordingly. The function returns a face that is affected by the operations (see the LEDA book for details). void G.make_planar_map() makes G a planar map by reordering the edges such that for every node v the ordering of the edges in the adjacency list of v corresponds to the counter-clockwise ordering of these edges around v for some planar embedding of G and constructs the list of faces. Precondition G is a planar bidirected graph (map). list< edge> G.triangulate_planar_map() triangulates planar map G and recomputes its list of faces

e) Operations for undirected graphs

f) I/O Operations

g) Non-Member Functions

 node source(edge e) returns the source node of edge e . node target(edge e) returns the target node of edge e . graph* graph_of(node v) returns a pointer to the graph that v belongs to. graph* graph_of(edge e) returns a pointer to the graph that e belongs to. graph* graph_of(face f) returns a pointer to the graph that f belongs to. face face_of(edge e) returns the face of edge e .

h) Iteration

All iteration macros listed in this section traverse the corresponding node and edge lists of the graph, i.e. they visit nodes and edges in the order in which they are stored in these lists.

forall_nodes(v, G )
{ the nodes of G are successively assigned to v " }

forall_edges(e, G )
{ the edges of G are successively assigned to e " }

forall_rev_nodes(v, G )
{ the nodes of G are successively assigned to v in reverse order" }

forall_rev_edges(e, G )
{ the edges of G are successively assigned to e in reverse order" }

forall_hidden_edges(e, G )
{ all hidden edges of G are successively assigned to e " }

{ the edges adjacent to node w are successively assigned to e " }

forall_out_edges(e, w )
a faster version of forall_adj_edges for directed graph.

forall_in_edges(e, w )
{ the edges of inedges(w) are successively assigned to e " }

forall_inout_edges(e, w )
{ the edges of outedges(w) and inedges(w) are successively assigned to e " }

like forall_adj_edges on the underlying undirected graph, no matter whether the graph is directed or undirected actually.

{ the nodes adjacent to node w are successively assigned to v" }

Faces

Before using any of the following face iterators the list of faces has to be computed by calling G.compute_faces(). Note, that any update operation invalidates this list.

forall_faces(f, M )
{ the faces of M are successively assigned to f " }

forall_face_edges(e, f )
{ the edges of face f are successively assigned to e " }

{ the faces adjacent to node v are successively assigned to f " }