A Note on Graphs
Vector 20:4, page 55
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 55
This is a short note on a large subject:
“A graph is a set of vertices (V), together with a set of connecting edges (E).”
In general, edges have a direction (V1…V2). Here is a simple graph:
┌─────A←────┐ 5 vertices: A B C D E
│ │ │
↓ ↓ │ 8 edges: A→B A→C B→C C→B
B←───→C────→D C→D D→A D→E E→C
↑ │
│ ↓
└─────E
We can represent graphs in a number of ways. Two of these are the adjacency matrix and the adjacency vector:
An adjacency matrix for the above graph would be:
A B C D E
┌───────── ⍝ Adjacency matrix for graph "a" above.
A│0 1 1 0 0
B│0 0 1 0 0
C│0 1 0 1 0 ⍝ Third row shows two edges: C→B C→D.
D│1 0 0 0 1
E│0 0 1 0 0
… and an adjacency vector would be:
(2 3) (3) (2 4) (1 5) (3) ⍝ Adjacency vector for graph "a".
A B C D E
└───────────── ⍝ Third item shows two edges: 3→(2 4): C→B C→D.
The above origin-1 vector can be changed to an origin-0 vector, merely by subtracting 1 from the nested array. All of the graph functions shown here are origin independent.
In general, the boolean adjacency matrix is better for dense graphs, where most vertices are connected to most others; and the adjacency vector is better for sparse graphs.
We can convert between the forms using:
Graphs are useful in a surprising number of applications. Examples include modelling transportation networks, job scheduling, resource allocation and determining the minimum number of postage stamps to stick on a letter!
Classical Breadth-First Search¶
We might want to explore the vertices of a graph in an orderly way. The classical breadth-first search algorithm maintains a queue of yet-to-be-visited vertices. Items are taken one at a time from the front of the queue, and vertices reachable from the head item are added to the back of the queue. The algorithm terminates when the queue is empty.
An APL coding of the classical algorithm might look like this:
bfs_c←{ ⍝ Breadth-first search (classical).
graph←⍺ ⍝ graph.
⍬{ ⍝ no vertices visited.
⍵≡⍬:⍺ ⍝ no vertices left: done.
head←1↑⍵ ⋄ tail←1↓⍵ ⍝ next and remaining vertices in queue.
next←head⊃graph ⍝ vertices adjacent to head.
(⍺,head)∇(tail∪next)~⍺ ⍝ accumulate visited vertices.
}⍵ ⍝ from starting vertex.
}
The inner tail-recursive function uses ⍺ as an accumulator for vertices already visited, and ⍵ as a queue for those still to be visited. By appending new vertices to the back of the queue and removing them from the front, we are assured of visiting nearer vertices before more remote ones.
Searching the simple graph from above, starting from vertex 5, yields:
Using the following graph as a slightly larger example:
graph←(2 5)(1 3 6)(2 4 7)(3 8)(1 6 9)(2 5)(3 8)(4 7 12),⎕
⎕: (5 10 13)(9 14)(12 15)(8 11 16)(9 14)(10 13 15)(11 14 16)(12 15)
1────────2────────3────────4 Graph Vertex numbers:
| | | |
| | | |
5────────6 7────────8
| |
| |
9────────10 11───────12
| | | |
| | | |
13───────14───────15───────16
Breadth-first search from vertex 1 visits vertices in the following order:
[1]──────[2]──────[4]──────[7] BREADTH-first order of visits:
| | | |
| | | |
[3]──────[5] [8]──────[11]
| |
| |
[6]──────[9] [15]─────[13]
| | | |
| | | |
[10]─────[12]─────[14]─────[16]
The function may be changed to produce a depth-first search, by prefixing new vertices to the queue, which then operates as a stack.
dfs_c←{ ⍝ Depth-first search (classical).
...
(⍺,head)∇(next∪tail)~⍺ ⍝ accumulate visited vertices.
...
}
[1]──────[2]──────[3]──────[4] DEPTH-first order of visits:
| | | |
| | | |
[13]─────[14] [6]──────[5]
| |
| |
[12]─────[11] [8]──────[7]
| | | |
| | | |
[15]─────[10]─────[9]──────[16]
Parallel Breath-First Search¶
In APL we can do a little better than the classical breadth-first search by processing ALL vertices at the same distance from the starting vertex in parallel. For non-trivial graphs, this leads to a significant performance improvement. Conceptually, starting from the originating vertext ⍵, the algorithm generates a “wave” (sometimes called a “fringe”), which ripples in all possible directions outwards through the graph; at each pass of the algorithm, the wave is advanced one step further from the starting vertex.
bfs←{ ⍝ Parallel breadth-first search.
graph←⍺ ⍝ ⍺ is graph vector.
⍵{ ⍝ from starting vertex.
⍵≡⍬:⍺ ⍝ no unvisited vertices: done.
adjv←graph[⍵] ⍝ nested vector of ALL adjacent vertices.
next←∪(↑,/adjv)~⍺ ⍝ simple vector of next unvisited vertices.
(⍺,next)∇ next ⍝ advance wave of visited vertices.
}⍵ ⍝ from starting vertex.
}
Using graph as above:
[1]──────[2]──────[3]──────[4] PARALLEL BREADTH-first order of visits:
| | | |
| | | |
[2]──────[3] [4]──────[5]
| |
| |
[3]──────[4] [7]──────[6]
| | | |
| | | |
[4]──────[5]──────[6]──────[7]
Spanning Trees¶
When searching a graph, our routes from the starting vertex to each visited vertex form a “spanning tree”. A breadth-first spanning tree for the above graph would look like this:
1────────2────────3────────4 Breadth-first spanning tree from vertex [1]
| |
| |
5────────6 7────────8
| |
| |
9────────10 11 12
| |
| |
13───────14───────15───────16
span←{ ⍝ Spanning tree for graph ⍺ from vertex(ices) ⍵.
graph←⍺ ⍝ ⍺ is graph vector.
tree←¯2+(⍳⍴⍺)∊⍵ ⍝ initial spanning tree.
free←{(¯2=tree[⍵])/⍵} ⍝ free vertices in ⍵.
{ ⍝ graph is left operand.
⍵≡⍬:tree ⍝ no vertices: done.
next←free¨graph[⍵] ⍝ next vertices to visit.
back←↑,/⍵+0×next ⍝ back links.
wave←↑,/next ⍝ wave front.
tree[wave]←back ⍝ set back links in tree
∇∪wave ⍝ advance wave front.
}⍵ ⍝ from starting vertex.
}
We can use the spanning tree to find a shortest path to any vertex:
stpath←{ ⍝ Path through spanning tree ⍺ to vertex ⍵.
tree←⍺ ⍝ (partial) spanning tree.
⍬{ ⍝ path accumulator.
⍵<0:(⍵=¯2)↓⍺ ⍝ root or unvisited vertex: finished.
(⍵,⍺)∇ ⍵⊃tree ⍝ otherwise: prefix previous (parent) vertex.
}⍵
}
… and combine the tree generation and path extraction into a single function:
path←{ ⍝ Shortest path from/to ⍵ in graph ⍺.
graph←⍺ ⍝ ⍺ is graph vector.
fm to←⍵ ⍝ starting and target vertex(ices).
tree←¯2+(⍳⍴⍺)∊fm ⍝ initial spanning tree.
free←{(¯2=tree[⍵])/⍵} ⍝ free vertices in ⍵.
⍬{ ⍝ path accumulator.
⍵<0:(⍵=¯2)↓⍺ ⍝ root or unvisited vertex: finished.
(⍵,⍺)∇ ⍵⊃tree ⍝ otherwise: prefix previous (parent) vertex.
}{ ⍝ find partial spanning tree:
⍵≡⍬:¯1 ⍝ no vertices left: stitched.
1∊to∊⍵:1↑⍵∩to ⍝ found target: finished.
next←free¨graph[⍵] ⍝ next vertices to visit.
back←↑,/⍵+0×next ⍝ back links.
wave←↑,/next ⍝ vertex wave front.
tree[wave]←back ⍝ set back links in tree.
∇∪wave ⍝ advance wave front.
}fm ⍝ from starting vertex.
}
graph path 1 11
1 5 9 13 14 15 11
Postage Stamps¶
An example of an application of graphs is to determine the smallest number of postage stamps to stick on a package. Suppose stamps are available in denominations of 1 5 6 10 26 39 43 and we need a total value of 51. One way to solve this problem is to repeatedly subtract the largest possible stamp from the remaining value:
… giving (43 5 1 1 1). However, on closer examination, (39 6 6) is a better solution.
We can solve this problem by making a graph whose vertices are the values 0, 1 … up to the required postage, and whose edges connect each vertex to those vertices it is possible to reach by adding a stamp.
For the denominations above, the graph starts:
(1 5 6 10 26 39 43)(2 6 7 11 27 40 44)…
stamps←{ ⍝ Postage stamps to the value of ⍵.
⍺←1 5 6 10 26 39 43 ⍝ Default UK stamp denominations.
graph←⍺{⍵∘∩¨⍵+⊂⍺}⍳⍵+1 ⍝ values: 0 ·· ⍵.
spath←graph path ⎕IO+0 ⍵ ⍝ shortest path 0→⍵.
¯2-/spath ⍝ best-fit stamps.
}
Then:
display stamps¨51 52 53
┌→─────────────────────────┐
│ ┌→─────┐ ┌→────┐ ┌→────┐ │
│ │39 6 6│ │26 26│ │43 10│ │
│ └~─────┘ └~────┘ └~────┘ │
└∊─────────────────────────┘
Further Reading¶
For more on Graphs, see: www.dyalog.com/dfnsdws/n_Graphs.htm
For a larger example, see: www.dyalog.com/dfnsdws/tube_n_index.htm
(For the moment, you will need to use IE6 as a browser in order to see the font correctly).