     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 adj edges(v) is called the adjacency list of node v and the edges in adj edges(v) are called the edges adjacent to node v. For directed graph we often use out edges(v) as a synonym for adj edges(v).

In undirected graph only the list adj edges(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 self-loops, 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 in edges(v) to the list adj edges(v) (removing self-loops). Conversely, G.make_directed() makes the undirected graph G directed by splitting for each node v the list adj edges(v) into the lists out edges(v) and in edges(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  (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

 int G.outdeg(node v) returns the number of edges adjacent to node v (|adj_edges(v)|). int G.indeg(node v) returns the number of edges ending at v (|in_edges(v)|) if G is directed and zero if G is undirected). int G.degree(node v) returns outdeg(v) + indeg(v). node G.source(edge e) returns the source node of edge e. node G.target(edge e) returns the target node of edge e. node G.opposite(node v, edge e) returns target(e) if v = source(e) and source(e) otherwise. node G.opposite(edge e, node v) same as above. int G.number_of_nodes() returns the number of nodes in G. int G.number_of_edges() returns the number of edges in G. const list& G.all_nodes() returns the list V of all nodes of G. const list& G.all_edges() returns the list E of all edges of G. list G.adj_edges(node v) returns adj edges(v). list G.out_edges(node v) returns adj edges(v) if G is directed and the empty list otherwise. list G.in_edges(node v) returns in edges(v) if G is directed and the empty list otherwise. list G.adj_nodes(node v) returns the list of all nodes adjacent to v. node G.first_node() returns the first node in V. node G.last_node() returns the last node in V. node G.choose_node() returns a random node of G (nil if G is empty). node G.succ_node(node v) returns the successor of node v in V (nil if it does not exist). node G.pred_node(node v) returns the predecessor of node v in V (nil if it does not exist). edge G.first_edge() returns the first edge in E. edge G.last_edge() returns the last edge in E. edge G.choose_edge() returns a random edge of G (nil if G is empty). edge G.succ_edge(edge e) returns the successor of edge e in E (nil if it does not exist). edge G.pred_edge(edge e) returns the predecessor of edge e in E (nil if it does not exist). edge G.first_adj_edge(node v) returns the first edge in the adjacency list of v (nil if this list is empty). edge G.last_adj_edge(node v) returns the last edge in the adjacency list of v (nil if this list is empty). edge G.adj_succ(edge e) returns the successor of edge e in the adjacency list of node source(e) (nil if it does not exist). edge G.adj_pred(edge e) returns the predecessor of edge e in the adjacency list of node source(e) (nil if it does not exist). edge G.cyclic_adj_succ(edge e) returns the cyclic successor of edge e in the adjacency list of node source(e). edge G.cyclic_adj_pred(edge e) returns the cyclic predecessor of edge e in the adjacency list of node source(e). edge G.first_in_edge(node v) returns the first edge of in edges(v) (nil if this list is empty). edge G.last_in_edge(node v) returns the last edge of in edges(v) (nil if this list is empty). edge G.in_succ(edge e) returns the successor of edge e in in edges(target(e)) (nil if it does not exist). edge G.in_pred(edge e) returns the predecessor of edge e in in edges(target(e)) (nil if it does not exist). edge G.cyclic_in_succ(edge e) returns the cyclic successor of edge e in in edges(target(e)) (nil if it does not exist). edge G.cyclic_in_pred(edge e) returns the cyclic predecessor of edge e in in edges(target(e)) (nil if it does not exist). bool G.is_directed() returns true iff G is directed. bool G.is_undirected() returns true iff G is undirected. bool G.empty() returns true iff G is empty.

b) Update operations

 node G.new_node() adds a new node to G and returns it. node G.new_node(node u, int dir) adds a new node v 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) adds a new edge (v, w) to G by appending it to adj edges(v) and to in edges(w) (if G is directed) or adj edges(w) (if G is undirected), and returns it. edge G.new_edge(edge e, node w, int dir=leda::behind) adds a new edge x = (source(e), w) to G. x is inserted in front of (dir=leda::before) or behind (dir=leda::behind) edge e into adj edges(source(e)) and appended to in edges(w) (if G is directed) or adj edges(w) (if G is undirected). Here leda::before and leda::behind are predefined constants. The operation returns the new edge x. Precondition source(e)! = w if G is undirected. edge G.new_edge(node v, edge e, int dir=leda::behind) adds a new edge x = (v, target(e)) to G. x is appended to adj edges(v) and inserted in front of (dir=leda::before) or behind (dir=leda::behind) edge e into in edges(target(e)) (if G is directed) or adj edges(target(e)) (if G is undirected). The operation returns the new edge x. Precondition target(e)! = v if G is undirected. edge G.new_edge(edge e1, edge e2, int d1=leda::behind, int d2=leda::behind) adds a new edge x = (source(e1), target(e2)) 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. node G.merge_nodes(node v1, node v2) experimental. node G.merge_nodes(edge e1, node v2) experimental. node G.split_edge(edge e, edge& e1, edge& e2) experimental void G.hide_edge(edge e) removes edge e temporarily from G until restored by G.restore_edge(e). void G.hide_edges(const list& el) hides all edges in el. bool G.is_hidden(edge e) returns true if e is hidden and false otherwise. list G.hidden_edges() returns the list of all hidden edges of G. void G.restore_edge(edge e) restores e by appending it to adj edges(source(e)) and to in edges(target(e)) ( adj edges(target(e)) if G is undirected). Precondition e is hidden and neither source(e) nor target(e) is hidden. void G.restore_edges(const list& el) restores all edges in el. void G.restore_all_edges() restores all hidden edges. void G.hide_node(node v) removes node v temporarily from G until restored by G.restore_node(v). All non-hidden edges in adj edges(v) and in edges(v) are hidden too. void G.hide_node(node v, list& h_edges) as above, in addition, the list of leaving or entering edges which are hidden as a result of hiding v are appended to h_edges. bool G.is_hidden(node v) returns true if v is hidden and false otherwise. list G.hidden_nodes() returns the list of all hidden nodes of G. void G.restore_node(node v) restores v by appending it to the list of all nodes. Note that no edge adjacent to v that was hidden by G.hide_node(v) is restored by this operation. void G.restore_all_nodes() restores all hidden nodes. void G.del_node(node v) deletes v and all edges incident to v from G. void G.del_edge(edge e) deletes the edge e from G. void G.del_nodes(const list& L) deletes all nodes in L from G. void G.del_edges(const list& L) deletes all edges in L from G. void G.del_all_nodes() deletes all nodes from G. void G.del_all_edges() deletes all edges from G. void G.del_all_faces() deletes all faces from G. void G.move_edge(edge e, node v, node w) moves edge e to source v and target w by appending it to adj edges(v) and to in edges(w) (if G is directed) or adj edges(w) (if G is undirected). void G.move_edge(edge e, edge e1, node w, int d=leda::behind) moves edge e to source source(e1) and target w by inserting it in front of (if d=leda::before) or behind (if d=leda::behind) edge e1 into adj edges(source(e1)) and by appending it to in edges(w) (if G is directed) or adj edges(w) (if G is undirected). void G.move_edge(edge e, node v, edge e2, int d=leda::behind) moves edge e to source v and target target(e2) by appending it to adj edges(v)) and inserting it in front of (if d=leda::before) or behind (if d=leda::behind) edge e2 into in edges(target(e2)) (if G is directed) or adj edges(target(e2)) (if G is undirected). void G.move_edge(edge e, edge e1, edge e2, int d1=leda::behind, int d2=leda::behind) moves edge e to source source(e1) and target target(e2) by inserting it 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). edge G.rev_edge(edge e) reverses e (move_edge(e,target(e),source(e))). void G.rev_all_edges() reverses all edges of G. void G.sort_nodes(int (*cmp)(const node& , const node& )) the nodes of G are sorted according to the ordering defined by the comparing function cmp. Subsequent executions of forall_nodes step through the nodes in this order. (cf. TOPSORT1 in section Graph and network algorithms). void G.sort_edges(int (*cmp)(const edge& , const edge& )) the edges of G and all adjacency lists are sorted according to the ordering defined by the comparing function cmp. Subsequent executions of forall_edges step through the edges in this order. (cf. TOPSORT1 in section Graph and network algorithms). void G.sort_nodes(const node_array& A) the nodes of G are sorted according to the entries of node_array A (cf. section Node Arrays). Precondition T must be numerical, i.e., number type int, float, double, integer, rational or real. void G.sort_edges(const edge_array& A) the edges of G are sorted according to the entries of edge_array A (cf. section Edge Arrays). Precondition T must be numerical, i.e., number type int, float, double, integer, rational or real. void G.bucket_sort_nodes(int l, int h, int (*ord)(const node& )) sorts the nodes of G using bucket sort Precondition l < = ord (v) < = h for all nodes v. void G.bucket_sort_edges(int l, int h, int (*ord)(const edge& )) sorts the edges of G using bucket sort Precondition l < = ord (e) < = h for all edges e. void G.bucket_sort_nodes(int (*ord)(const node& )) same as G.bucket_sort_nodes(l,h,ord) with l (h) equal to the minimal (maximal) value of ord (v). void G.bucket_sort_edges(int (*ord)(const edge& )) same as G.bucket_sort_edges(l,h,ord) with l (h) equal to the minimal (maximal) value of ord (e). void G.bucket_sort_nodes(const node_array& A) same as G.bucket_sort_nodes(ord) with ord (v) = A[v] for all nodes v of G. void G.bucket_sort_edges(const edge_array& A) same as G.bucket_sort_edges(ord) with ord (e) = A[e] for all edges e of G. void G.set_node_position(node v, node p) moves node v in the list V of all nodes such that p becomes the predecessor of v. If p = nil then v is moved to the front of V. void G.set_edge_position(edge e, edge p) moves edge e in the list E of all edges such that p becomes the predecessor of e. If p = nil then e is moved to the front of E. void G.permute_edges() the edges of G and all adjacency lists are randomly permuted. list G.insert_reverse_edges() for every edge (v, w) in G the reverse edge (w, v) is inserted into G. Returns the list of all inserted edges. Remark: the reversal information is not set by this function. void G.make_undirected() makes G undirected by appending in edges(v) to adj edges(v) for all nodes v. void G.make_directed() makes G directed by splitting adj edges(v) into out edges(v) and in edges(v). void G.clear() makes G the empty graph. void G.join(graph& H) merges H into G by moving all objects (nodes,edges, and faces) from H to G. H is empty afterwards.

c) Reversal Edges and Maps

 void G.make_bidirected() makes G bidirected by inserting missing reversal edges. void G.make_bidirected(list& 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& 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 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 () 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& G.all_faces() returns the list of all faces of G. list G.adj_faces(node v) returns the list of all faces of G adjacent to node v in counter-clockwise order. list G.adj_nodes(face f) returns the list of all nodes of G adjacent to face f in counter-clockwise order. list 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 G.triangulate_planar_map() triangulates planar map G and recomputes its list of faces

e) Operations for undirected graphs

 edge G.new_edge(node v, edge e1, node w, edge e2, int d1=leda::behind, int d2=leda::behind) adds a new edge (v, w) 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 of (if d2=leda::before) or behind (if d2=leda::behind) edge e2 into adj edges(w), and returns it. Precondition e1 is incident to v and e2 is incident to w and v! = w. edge G.new_edge(node v, edge e, node w, int d=leda::behind) adds a new edge (v, w) 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 e is incident to v and v! = w. edge G.new_edge(node v, node w, edge e, int d=leda::behind) adds a new edge (v, w) to G by appending it to to adj edges(v), and by inserting it in front of (if d=leda::before) or behind (if d=leda::behind) edge e into adj edges(w), and returns it. Precondition e is incident to w and v! = w. edge G.adj_succ(edge e, node v) returns the successor of edge e in the adjacency list of v. Precondition e is incident to v. edge G.adj_pred(edge e, node v) returns the predecessor of edge e in the adjacency list of v. Precondition e is incident to v. edge G.cyclic_adj_succ(edge e, node v) returns the cyclic successor of edge e in the adjacency list of v. Precondition e is incident to v. edge G.cyclic_adj_pred(edge e, node v) returns the cyclic predecessor of edge e in the adjacency list of v. Precondition e is incident to v.

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 in edges(w) are successively assigned to e" }

forall_inout_edges(e, w)
{ the edges of out edges(w) and in edges(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" }     