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 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 inedges(v) to the list adjedges(v) (removing self-loops). 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
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<node>& | G.all_nodes() | returns the list V of all nodes of G. |
const list<edge>& | G.all_edges() | returns the list E of all edges of G. |
list<edge> | G.adj_edges(node v) | returns adjedges(v). |
list<edge> | G.out_edges(node v) | returns adjedges(v) if G is directed and the empty list otherwise. |
list<edge> | G.in_edges(node v) | returns inedges(v) if G is directed and the empty list otherwise. |
list<node> | 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
inedges(v)
(nil if this list is empty). |
edge | G.last_in_edge(node v) | returns the last edge of
inedges(v)
(nil if this list is empty). |
edge | G.in_succ(edge e) | returns the successor of edge e in inedges(target(e)) (nil if it does not exist). |
edge | G.in_pred(edge e) | returns the predecessor of edge e in inedges(target(e)) (nil if it does not exist). |
edge | G.cyclic_in_succ(edge e) | returns the cyclic successor of edge e in inedges(target(e)) (nil if it does not exist). |
edge | G.cyclic_in_pred(edge e) | returns the cyclic predecessor of edge e in inedges(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 adjedges(v) and to inedges(w) (if G is directed) or adjedges(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
adjedges(source(e)) and appended to
inedges(w)
(if G is directed) or
adjedges(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
adjedges(v) and inserted in front of (dir=leda::before) or
behind (dir=leda::behind) edge e into
inedges(target(e))
(if G is directed) or
adjedges(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 adjedges(source(e1)) and in front of (if d2=leda::before) or behind (if d2=leda::behind) edge e2 into inedges(target(e2)) (if G is directed) or adjedges(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<edge>& el) | |
hides all edges in el. | ||
bool | G.is_hidden(edge e) | returns true if e is hidden and false otherwise. |
list<edge> | G.hidden_edges() | returns the list of all hidden edges of G. |
void | G.restore_edge(edge e) | restores e by appending it to adjedges(source(e)) and to inedges(target(e)) ( adjedges(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<edge>& 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 adjedges(v) and inedges(v) are hidden too. |
void | G.hide_node(node v, list<edge>& 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<node> | 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<node>& L) | |
deletes all nodes in L from G. | ||
void | G.del_edges(const list<edge>& 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 adjedges(v) and to inedges(w) (if G is directed) or adjedges(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 adjedges(source(e1)) and by appending it to inedges(w) (if G is directed) or adjedges(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 adjedges(v)) and inserting it in front of (if d=leda::before) or behind (if d=leda::behind) edge e2 into inedges(target(e2)) (if G is directed) or adjedges(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 adjedges(source(e1)) and in front of (if d2=leda::before) or behind (if d2=leda::behind) edge e2 into inedges(target(e2)) (if G is directed) or adjedges(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<T>& 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<T>& 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<int>& 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<int>& 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<edge> | 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 inedges(v) to adjedges(v) for all nodes v. |
void | G.make_directed() | makes G directed by splitting adjedges(v) into outedges(v) and inedges(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<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
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(e_{1}), source(e_{2}))
and its reversal into G and returns e.
Precondition e_{1} and e_{2} 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
void | G.write(ostream& O = cout) | |
writes G to the output stream O. | ||
void | G.write(string s) | writes G to the file with name s. |
int | G.read(istream& I = cin) | reads a graph from the input stream I and assigns it to G. |
int | G.read(string s) | reads a graph from the file with name s and assigns it to G. Returns 1 if file s does not exist, 2 if the edge and node parameter types of *this and the graph in the file s do not match, 3 if file s does not contain a graph, and 0 otherwise. |
bool | G.write_gml(ostream& O = cout, void (*node_cb)(ostream& , const graph*, const node)=0, void (*edge_cb)(ostream& , const graph*, const edge)=0) | |
writes G to the output stream O in GML format ([46]). If node_cb is not equal to 0, it is called while writing a node v with output stream O, the graph and v as parameters. It can be used to write additional user defined node data. The output should conform with GML format (see manual page gml_graph). edge_cb is called while writing edges. If the operation fails, false is returned. | ||
bool | G.write_gml(string s, void (*node_cb)(ostream& , const graph*, const node)=0, void (*edge_cb)(ostream& , const graph*, const edge)=0) | |
writes G to the file with name s in GML format. For a description of node_cb and edge_cb, see above. If the operation fails, false is returned. | ||
bool | G.read_gml(string s) | reads a graph in GML format from the file with name s and assigns it to G. Returns true if the graph is successfully read; otherwise false is returned. |
bool | G.read_gml(istream& I = cin) | |
reads a graph in GML format from the input stream I and assigns it to G. Returns true if the graph is successfully read; otherwise false is returned. | ||
void | G.print_node(node v, ostream& O = cout) | |
prints node v on the output stream O. | ||
void | G.print_edge(edge e, ostream& O = cout) | |
prints edge e on the output stream O. If G is directed e is represented by an arrow pointing from source to target. If G is undirected e is printed as an undirected line segment. | ||
void | G.print(string s, ostream& O = cout) | |
prints G with header line s on the output stream O. | ||
void | G.print(ostream& O = cout) | |
prints G on the output stream O. |
g) Non-Member Functions
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" }
forall_adj_edges(e, w)
{ ``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" }
forall_adj_undirected_edges(e, w)
like forall_adj_edges on the underlying undirected graph,
no matter whether the graph is directed or undirected actually.
forall_adj_nodes(v, w)
{ ``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" }
forall_adj_faces(f, v)
{ ``the faces adjacent to node v are successively assigned to f" }
Implementation
Graphs are implemented by doubly linked lists of nodes and edges. Most operations take constant time, except for all_nodes, all_edges, del_all_nodes, del_all_edges, make_map, make_planar_map, compute_faces, all_faces, make_bidirected, clear, write, and read which take time O(n + m), and adj_edges, adj_nodes, out_edges, in_edges, and adj_faces which take time O(output size) where n is the current number of nodes and m is the current number of edges. The space requirement is O(n + m).