Printer Friendly

A versatile data structure for edge-oriented graph algorithms.

A VERSATILE DATA STRUCTURE FOR EDGE-ORIENTED GRAPH ALGORITHMS It is widely accepted that graphs are a useful medium for modeling relevant parts of reality in computer programs. Graphs are rather natural models for road maps, electrical networks, chemical structure formulas, data and control flow of computer programs, state spaces of discrete games, sociological diagrams, timetables, etc. In addition, many discrete problems in several areas (e.g., formal languages theory, automata theory, compiler construction, operating-systems theory, operations research) can be transformed into equivalent graph problems and then solved using graph algorithms.

Representation greatly influences the efficiency of graph algorithms. Often, linearity can only be achieved through appropriate storage of adjacency information (see, e.g., [6]). There are several different ways of internally representing graphs in procedural languages, including adjacency matrices, sequential or linked adjacency lists, and edge lists (cf. [2]). On the other hand, good and clear algorithm design is greatly enhanced by rather abstract graph representations that include operations on the graph, as well as control statements (e.g., for-loops) triggered by the graph.

In this article we describe an abstract module for graph handling that is especially suited for the edge-oriented paradigm of programming graph algorithms, and show how this module can be implemented efficiently in Algol-like languages. This graph realization is of the adjacency-list type and is suitable for directed and undirected graphs (with multiple edges allowed). Undirected graphs are represented as directed graphs through arbitrary assignment of directions to every edge (and not through storage of the corresponding symmetric graph). This representation has been used successfully in a number of applications; for instance, it has been used as a tool for representing the graphs in the EMS project on the implementation of functional languages [3].

GRAPHS

There is a large variety of graph types. Depending on the area of application, graphs can be directed or undirected, weighted or unweighted, and ordered or unordered. Multiple edges and loops are either permitted or forbidden. Here, we present a graph representation that is suitable to all of these variants ([1] and [5] are introductory books on graph theory; [2] and [4] introduce graph algorithms).

Using a very general type of graph definition, a (finite) directed graph G = (V, E, [alpha], [omega]) consists of a finite nonempty set V of vertices, a finite set E of edges (with V [omega] E = [phil]), and two functions [alpha]: E * V (denoting the start vertex) and [omega]: E * V (denoting the end vertex of each edge). If there is an edge e with vertices v = [alpha](e and w = [omega](e), then w is a successor of v and v is a predecessor of w. Those edges e with v = [alpha](e) ("e goes out of v") constitute the forward star of v. Analogously, the backward star of v consists of those edges e with v = [omega](e) ("e goes into v").

On the other hand, a (finite) undirected graph G = (V, E, *) contains only one function *:E *[W * V 1 [is less than or= W [is less than or =] 2], assigning up to two vertices to every edge. A self-loop is an edge e with *(e) = 1. If v [epsilon] *(e), we say v and e are incident. The star of a vertex v consists of those edges that are incident with v. The degree [gamma](v) of v is the number of edges incident with v, where self-loops are counted twice.

For a directed graph G = (V, E, [alpha], [omega]), the underlying undirected graph H = (V, E, *) is given by *(e) = [[alpha](e), [omega](e)]. Thus, all concepts and algorithms defined for undirected graphs can also be used for directed graphs through simple reference to their underlying undirected graphs. Thus, an edge e and a vertex v are incident if v = [alpha](e) or v = [omega](e), and e is a self-loop if [alpha](e) = [omega](e).

With the implementation given below, the representation of the underlying undirected graph is identical to the representation of the graph itself. Thus, algorithms that were designed for undirected graphs (e.g., algorithms for finding spanning trees, testing (bi-)connectivity) can be executed on directed graphs without further adaptation.

EDGE-ORIENTED GRAPH ALGORITHMS

The graph module described here strongly supports an edge-oriented way of handling graphs. This paradigm makes programming more secure and is at the same time suitable for handling graphs with multiple edges.

The following conventions apply to edge-oriented programming of graph algorithms:

(1) Neighborhoods of vertices are traversed by reference to the edges incident with a given vertex.

(2) Edges are regarded as objects having two states. They may be pointing outwards (positive sign) or pointing inwards (negative sign).

Thus, for processing the successors of a given vertex v, one must proceed as follows: for all edges e out of v do let w be the other vertex of e; process w od.

The sign of the edges makes it possible to talk about the "other" vertex.

Using loops over edges and giving a state to the edges allow a straightforward translation for for-loops into a combination of a while-loop and some standard function calls, since signed edges contain enough information to (re)enter a while-loop to process the next edge. This is not possible for loops over (e.g., successor) vertices. Furthermore, traversing neighborhoods by explicitly looking at all incident edges clarifies the fact that successors are listed more than once, if multiple edges exist. (A vertex-oriented for-loop is often valid only for graphs without multiple edges.)

In addition, the sign on the edges allows sufficient information to be kept for deferred processing, if--as in some search algorithms--edges are stored for later use in an intermediate data structure. When an edge is retrieved, its sign helps to deduce its provenance. Assigning directions (signs) to edges also helps to distinguish incoming from outgoing edges during undirected searches in directed graphs. Furthermore it helps to describe the direction of edges in (undirected) cycles and/or cuts of directed graphs.

As an example, Figure 1 shows an edge-oriented pseudocode version of a bridge detection algorithm (derivable from [6]). Note that this algorithm works on undirected graphs, though the input graph might be directed. Here, the PARENT-entries, which denote a spanning tree in a multigraph, contain edges (instead of vertices), since there is at most one incoming tree edge for every vertex.

GRAPH OPERATIONS

We now give the description of a module (in the sense of an abstract data structure) for implementing edge-oriented algorithms in Algol-like languages.

For programming a pseudostatement like the for-loop over the outward star from above, we use traversal functions first out and next out and an auxiliary function omega according to the following: e : = first out (v); while e <> 0 do w : = omega (e); process w; e : = next out (e) od.

Note that this is a very straightforward way of translating for-loops, which is made possible by the "direction" (sign) assigned to every edge value. Since the edges denoted by e point outward, it is possible to identify the "next" edge as the next one going out of the same start vertex.

Figure 2 lists the traversal functions necessary for the translation of the pseudocode for-statements.

Note that these functions assume an arbitrary but fixed order on all sets. For handling "signed" edges, some auxiliary transfer functions like those listed in Figure 3 are necessary. Figure 4 shows how the bridge detection algorithm of Figure 1 can be programmed using these procedures. Note that this program, though designed for undirected graphs, also handles directed graphs without any further action or adaptation.

Since edges are signed objects, some care has to be taken in testing edge equality. In the line marked with a star (*) in Figure 4, both sides of the inequality sign were simply normalized.

The next section shows that all operations used thus far can be implemented efficiently. A great number of graph algorithms can be formulated using only the operations described here. In [2], for instance, it is shown that all the generally used efficient graph algorithsm can be based on the operations described here (except for the class of all-pair-shortest-path algorithms, which usually use some kind of is edge (v, w)-test).

GRAPH REPRESENTATION

Adjacency lists are usually used to store the successors of every vertex by means of linked lists. We store the predecessors, as well, to enable algorithms on the underlying undirected graph. Using some practical "tricks," we get a storage schema, which implements all the operations of our graph module in an efficient way.

Let G = (V, E, [alpha], [omega]) be a given directed graph with V = n and E = m. We number the vertices in V from 1 to n, and the edges in E from 1 to m.

All concrete information about the vertices and edges (e.g., names, weights, lengths, markings) can now be stored separately in arrays of length n or m, respectively. (Note that this is one of the main advantages of adjacency list representations over adjacency matrices, at least when the graph is sparse.) Thus, values of vertices and edges have only to be stored once, even for undirected graphs.

We use these numbers as names for the corresponding objects. But we take care not to confuse vertex i with edge i (for 1 [is less than or =] i [is less than or =] min (n, m)). Thus, we take vertex = 0 .. n edge = --m .. m as types, with the integer sign as the direction indicator for edges and with zero as a nil-value for vertices and edges. vertex procedure create.sub.-.vertex ( ); v := FIRST[0] - LARGE; FIRST[0] := FIRST[v]; FIRST[v] := LAST[v] := 0; n := n + 1; return v. procedure delete.sub.-.vertex (v : vertex); while FIRST[v] <> 0 do delete.sub.-.edge (FIRST[v]) od; FIRST[v] := FIRST[0]; FIRST[0] := v + LARGE; n := n - 1. edge procedure create.sub.-.edge (v, w : vertex); e := NEXY[0] - LARGEf NEXT[0] := NEXT[e]; NEXT[e] := 0; m := m + 1; create.sub.-.entry v, e); create.sub.-.entry (w, -e); return e. procedure delete.sub.-.edge (e : edge); e := abs (e); delete.sub.-.entry (NODE[-e], e); delete.sub.-.delete.sub.-.entry (NODE[e]. -e); NODE[-e] := NODe[e] := NEXT[-e] := 0; NEXT[e] := NEXT[0]; NEXT[0] := e + LARGE; m := m - 1.

FIGURE 11. Implementation of the Creation and Deletion

Procedures, Assuming Validity if Input Parameters

and without Checking Overflow Conditions procedure create.sub.-.entry (v : vertex, e : edge); if FIRST[v] = 0 then FIRST[v] := e else NEXT[LAST[v]] := e fi; LAST[v] := e; NODE[-e] := v. procedure delete.sub.-.entry (v : vertex, e : edge); if FIRST[v] = e then FIRST[v] := NEXT[e]; if LAST[v] = e then LAST[v' := 0 fi else i := FIRST[v]; while NEXT[i] <> e do i := NEXT[i] od; NEXT[i] := NEXT[e]; if LAST[v] = e then LAST[v] := i fi fi.

FIGURE 12. Auxiliary Creation and Deletion Procedures

CONCLUSION

Following the paradigm of edge orientation, our software module for general graphs and their implementation on von Neumann machines allows for easy and secure programming of a great number of graph algorithms, since traversal of forward and backward stars as well as edge enumeration is particularly easy. Since there is no distinction between a directed graph and its underlying undirected graph, our module allows a very straightforward transliteration of published algorithms into concrete programming code.

The module has successfully been used in various applications. A version written in the C language is one of the basic cornerstones of the EMS system for the implementation of functional languages by graphs.
COPYRIGHT 1987 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1987 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ebert, Jurgen
Publication:Communications of the ACM
Article Type:technical
Date:Jun 1, 1987
Words:1930
Previous Article:Systems analysis: a systemic analysis of a conceptual model.
Next Article:Arithmetic coding for data compression.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters