──────
Graphs
──────
A  graph is a set of nodes called _vertices_, connected by links called _edges_.
The graph is said to be "weighted" if each edge has an associated weight. Other-
wise, it is "unweighted".  Similarly, a graph is said to be "directed"  if  each
edge has an associated direction, otherwise it is "undirected". For a discussion
of weighted graphs, see: →wGraphs←.

The following diagram represents a simple unweighted, directed graph.

      Graph "a".
    ┌─────A←────┐
    │     │     │   5 vertices: A B C D E
    ↓     ↓     │
    B←───→C────→D   8 edges:    A→B  A→C  B→C  C→B
          ↑     │               C→D  D→A  D→E  E→C
          │     ↓
          └─────E

Notice that there is an edge from C to B, as well as from B to C.

A  directed  graph  is a generalisation of a tree. A tree is a graph where every
vertex  has  at  most  one edge leading to it. All trees are graphs, but not all
graphs  are trees. This means that the data structures and functions over graphs
in the following, also apply to trees.

Graphs can be used to model many structures found in everyday life.

dw  Example of Graph                            Vertex         Edge         Note
--  ----------------                            ------         ----         ----
dw  A transportation system such as a subway.   station        track         [a]
uu  A fishing net.                              knot           twine
du  The World Wide Web (a large graph!).        page           link
du  A game of chess.                            position       move          [b]
du  This workspace's internal memory structure. memory block   pointer
uu  The "Six Degrees of Kevin Bacon" game.      actor          starred with  [c]
uu  A "Word Ladder" puzzle.                     word           letter swap   [d]
du  Finding which stamps to stick on a letter.  total value    stick stamp   [e]
uu  Who dated whom at college.                  student        dated
uu  The Maze at Hampton Court.                  intersection   path          [f]
du  The "See also" links used in these notes.   note           see also      [g]
uu  Adjacency of regions in a planar map.       region         adjancent to  [h]
dw  A job scheduling network.                   task           dependency
││
│└─ w:weighted, u:unweighted.
└── d:directed, u:undirected.

[a]  Most  stylised  maps of subway systems treat the network as an _unweighted_
graph:  there  is no attempt to indicate the relative journey times or costs be-
tween  stations. Subways can generally be represented by _undirected_ graphs un-
less  they  contain any one-way sections, as is the case with London's Picadilly
line.

[b]  A Pawn can't move backwards, so its moves must be represented by a directed
graph.  Notice  that  despite the Queen's versatility, her _undirected_ graph is
relatively _sparse_; at best she can move to only 27 out of 64 board positions.

[c]  In  the The Six Degrees of Kevin Bacon game, start with any movie actor and
try to establish a connection with Kevin Bacon in six or fewer moves. An example
might be: "Sigourney Weaver":

    Sigourney Weaver  was in Copycat with
    Holly Hunter, who was in The Firm with
    Gene Hackman, who was in The Birdcage with
    Dianne Weist, who was in Footloose with
    Kevin Bacon.

    ... 4 degrees (edges), 5 vertices.

[d]  A Word Ladder puzzle has two n-letter words, drawn at the top and bottom of
a picture of a ladder. The task is to write n-letter words on each of the inter-
vening rungs, so that adjacent words differ by exactly one letter. Some examples
might be:

     Puzzle  Solution      Puzzle   Solution       Puzzle   Solution

    ├beard┤   ├beard┤      ├tooth┤   ├tooth┤      ├water┤   ├water┤
    ├─────┤   ├bears┤      ├─────┤   ├sooth┤      ├─────┤   ├wader┤
    ├─────┤   ├beams┤      ├─────┤   ├sloth┤      ├─────┤   ├wades┤
    ├─────┤   ├seams┤      ├─────┤   ├slosh┤      ├─────┤   ├wares┤
    ├─────┤   ├shams┤      ├─────┤   ├slush┤      ├─────┤   ├warns┤
    ├─────┤   ├shame┤      ├─────┤   ├blush┤      ├─────┤   ├wains┤
    ├shave┤   ├shave┤      ├brush┤   ├brush┤      ├─────┤   ├whins┤
                                                  ├whine┤   ├whine┤

[e] See →stamps←.

[f] See →hampton←

[g] See example at the end of these notes.

[h] See →konigsberg← and →uksfr←

Two  common  ways to represent graphs, are as a boolean "adjacency matrix" or as
an "adjacency vector" of vectors:

Adjacency matrix M has a 1 at M[i;j] if there is an edge from i to j.

      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

Adjacency vector V is an index vector of all edges from i to i⊃V.

      (2 3) (3) (2 4) (1 5) (3) ⍝ Adjacency structure for graph "a".
       A     B   C     D     E
                 └───────────── ⍝ Third item shows two edges: 3→(2 4): C→B C→D.

The matrix representation is better for dense graphs (who didn't date whom), and
the  vector  representation,  better  for sparse graphs such as links across the
World  Wide  Web. Workspace tube.dws models the subway systems of various cities
using  vector  representation.  In the case of the London Underground, which has
over  1,200  vertices, the graph is smaller (uses less workspace) than the equi-
valent matrix representation, by a factor of 6.

At either end of the sparse-to-dense continuum are the "order-N null graph", and
the "order-N complete graph". An order-N  _null_ graph contains N vertices and 0
edges  (who  dated whom in the cricket team). The order-N _complete_ graph cont-
ains N vertices and n*2 edges (who attended college with whom at college).

A _complete_, weighted, directed graph may conveniently be represented just by a
_matrix_  of  each  vertex-to-vertex cost. Function →assign← expects such a rep-
resentation.

Functions to convert between matrix and vector forms of unweighted graphs:

    {{⍵/⍳⍴⍵}¨↓⍵}    ⍝ vector from matrix form.

    {⍉(⍳⍴⍵)∘.∊⍵}    ⍝ matrix from vector form.

The following boolean functions indicate whether their graph argument is direct-
ed:

    {⍵≢⍉⍵}                              ⍝ _matrix_ form is directed.
    {~∧/{∨/⍺∊¨⍵[⍺⊃⍵]}∘⍵¨⍳⍴⍵}            ⍝ _vector_ form is directed.

and  the following graph-valued functions remove the asymmetry of direction from
their argument graphs:

    {⍵∨⍉⍵}                              ⍝ remove direction from _matrix_ form.
    {{⍵/⍳⍴⍵}¨↓⍵}∘{⍵∨⍉⍵}∘{⍉(⍳⍴⍵)∘.∊⍵}    ⍝ remove direction from _vector_ form.

The  latter  function  removes direction by converting vector to matrix and back
again. The following alternative is slower but uses less workspace and preserves
the order of edges within each vertex:

    {{(⍺⊃⍵)∪(⍺{∨/⍺∊⍵}¨⍵)/⍳⍴⍵}∘⍵¨⍳⍴⍵}        ⍝ remove direction from vector form.

A vector of the edge-pairs for a (vector form) undirected graph is given by:

    {↓[⎕IO]{(<⌿⍵)/⍵}↑,/⍵,[⎕IO-0.5]¨⍳⍴⍵}     ⍝ edge vector for undirected graph.

Related graphs:

The  "transitive closure" of a graph has an edge (u v) if there is a _path_ from
u to v in the original. In other words, the transitive closure shows where it is
possible  to get from u to v, no matter how long the path. The following derived
functions return the transitive  closures for matrix and vector representations,
respectively.

    tcm←{⍵∨⍵∨.∧⍵}⍣≡                         ⍝ transitive closure (matrix).
    tcm←(⊢ ∨ ∨.∧⍨)⍣≡                        ⍝   ..      .. (using a train).

    tcv←{⍵{(⍳⍴⍵)∩⍺,∊⍺⊃¨⊂⍵}¨⊂⍵}⍣≡            ⍝ vector transitive closure (SL).

The "complement" of a graph has the same number of vertices but edges only where
there  were  none  before.  For  graphs that represent relationships between the
vertices (who dated whom), the complement graph represents the inverse relation-
ship (who didn't date whom). The complement of an adjacency _matrix_ is given by
{~⍵}, and of an adjacency _vector_ by {(⊂⍳⍴⍵)~¨⍵}.

We investigate only the _vector_ representation from here onwards.

The functions in this workspace deal only with graph structure. There is no pro-
vision  for vertices or edges to carry data other than that required to maintain
the  graph.  In  real  applications,  such  "labelling" of vertices and edges is
required.  This  can  easily  be  achieved  by keeping a separate vector of such
values (URLs, names, distances-between-stations, ···), parallel with the graph.

An  index  origin of 1 is assumed in the examples that follow. An origin 1 graph
may be converted to origin 0, just by subtracting 1.

There  are  many useful and interesting questions that we can ask of, and trans-
formations that we can apply to, a graph. The functions in this workspace are:

Transformation/Question                                     Function
-----------------------                                     --------
Insert/remove a vertex.                                     →insnode← →remnode←

Insert/remove an edge.                                      →inslink← →remlink←

Rearrangement of vertices in graph vector:                  →gperm←

What is the shortest path from vertex A to vertex B?        →path←

Produce  a  "spanning tree" of the shortest path from the   →span←
    starting  vertex  to every other vertex in the graph.
    The  simple  function →stpath← can be used to recover   →stpath←
    shortest  vertex-to-vertex  paths  directly  from the
    spanning  tree.  Note that there may be any number of
    shortest paths between any two vertices.

The  path  and spanning functions are based on a breadth-   →search←
    first  search  of  the graph. A stripped-down version
    of  this  procedure  returns a vector of the vertices
    encountered  by  radiating  outwards  from a starting
    vertex. See →bfs←.

Examples:

    ⊢a←(2 3)(3)(2 4)(1 5)(3)            ⍝ simple origin-1 graph "a" (above).
┌───┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
└───┴─┴───┴───┴─┘

    a inslink 5 1                       ⍝ ··· with new link 5→1
┌───┬─┬───┬───┬───┐
│2 3│3│2 4│1 5│3 1│
└───┴─┴───┴───┴───┘

⍝ As many of the functions take a graph as _left_ argument and a "modifier" on
⍝ the _right_, the "fold left" operator →foldl← is useful:

    a inslink foldl (5 1) (3 5)         ⍝ graph "a" with new links: 5→1, 3→5.
┌───┬─┬─────┬───┬───┐
│2 3│3│2 4 5│1 5│3 1│
└───┴─┴─────┴───┴───┘

    a remlink foldl (1 3) (2 3)         ⍝ graph "a" without links: 1→3, 2→3.
┌─┬┬───┬───┬─┐
│2││2 4│1 5│3│
└─┴┴───┴───┴─┘

    a gperm 2 1 3 4 5                   ⍝ "a" with first two nodes reversed
┌─┬───┬───┬───┬─┐
│3│1 3│1 4│2 5│3│
└─┴───┴───┴───┴─┘

    a gperm ⌽⍳⍴a                        ⍝ "a" with nodes reversed
┌─┬───┬───┬─┬───┐
│3│5 1│4 2│3│4 3│
└─┴───┴───┴─┴───┘

⍝ We  can borrow some lines from the →kt← Knight's Tour function, to generate
⍝ a graph (k) of the knight's moves on an ⍵-sized chessboard.

    kt_graph←{                      ⍝ Graph of knight's moves on ⍵-board.
        kdef←,0 1∘.⌽1 ¯1∘.,2 ¯2     ⍝ vector of relative knight's moves.
        net←(⊂,⍳⍵)∩¨↓(⍳⍵)∘.+kdef    ⍝ absolute moves from each square.
        ⎕IO+,⍵∘⊥¨¨net-⎕IO           ⍝ adjacency vector.
    }

    k←kt_graph 8 8                  ⍝ graph of knight's moves on an 8×8 board.
┌─────┬────────┬──────────┬───────────┬───────────┬───────────┬────────┬─────┬───────┬──────────┬───────────────┬───────────────┬───────────────┬───────────────┬──────────┬───────┬──────────┬───────────────┬────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬───────────────┬──────────┬───────────┬────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬───────────┬─────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬───────────┬─────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬────────┬───────────┬─────────────────┬─────────────────┬─────────────────┬─────────────────┬───────────┬────────┬─────┬────────┬───────────┬───────────┬───────────┬───────────┬────────┬─────┐
│11 18│12 17 19│9 13 18 20│10 14 19 21│11 15 20 22│12 16 21 23│13 22 24│14 23│3 19 26│4 20 25 27│1 5 17 21 26 28│2 6 18 22 27 29│3 7 19 23 28 30│4 8 20 24 29 31│5 21 30 32│6 22 31│2 11 27 34│1 3 12 28 33 35│2 4 9 13 25 29 34 36│3 5 10 14 26 30 35 37│4 6 11 15 27 31 36 38│5 7 12 16 28 32 37 39│6 8 13 29 38 40│7 14 30 39│10 19 35 42│9 11 20 36 41 43│10 12 17 21 33 37 42 44│11 13 18 22 34 38 43 45│12 14 19 23 35 39 44 46│13 15 20 24 36 40 45 47│14 16 21 37 46 48│15 22 38 47│18 27 43 50│17 19 28 44 49 51│18 20 25 29 41 45 50 52│19 21 26 30 42 46 51 53│20 22 27 31 43 47 52 54│21 23 28 32 44 48 53 55│22 24 29 45 54 56│23 30 46 55│26 35 51 58│25 27 36 52 57 59│26 28 33 37 49 53 58 60│27 29 34 38 50 54 59 61│28 30 35 39 51 55 60 62│29 31 36 40 52 56 61 63│30 32 37 53 62 64│31 38 54 63│34 43 59│33 35 44 60│34 36 41 45 57 61│35 37 42 46 58 62│36 38 43 47 59 63│37 39 44 48 60 64│38 40 45 61│39 46 62│42 51│41 43 52│42 44 49 53│43 45 50 54│44 46 51 55│45 47 52 56│46 48 53│47 54│
└─────┴────────┴──────────┴───────────┴───────────┴───────────┴────────┴─────┴───────┴──────────┴───────────────┴───────────────┴───────────────┴───────────────┴──────────┴───────┴──────────┴───────────────┴────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴───────────────┴──────────┴───────────┴────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴───────────┴─────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴───────────┴─────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴────────┴───────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┴───────────┴────────┴─────┴────────┴───────────┴───────────┴───────────┴───────────┴────────┴─────┘

    ⍴¨k(↑,/k)                       ⍝ number of vertices and edges.
 64  336

    k path 1 2                      ⍝ Knight's path from square 1 to 2.
1 11 17 2

⍝ We  can  keep a vector of data associated with each vertex separate from, but
⍝ parallel with, the graph. In this case we might like a vector of board posit-
⍝ ion notations: A1 A2 ··· B1 B2 ··· H8. This vector may exist independently as
⍝ a workspace variable, or could be bound with a "translation" function.

    show←(,⍉8 8↑⎕A∘.,1↓⎕D)∘{⍺[⍵]}   ⍝ show board positions.

    show k path 1 9                 ⍝ a shortest path from A1 to A2.
 A1  C2  B4  A2

    show k path 1 64                ⍝   ··  ··  ··  ··  to opposite corner.
 A1  C2  E1  G2  F4  G6  H8

    show k path 1 10                ⍝   ··  ··  ··  ··  to adjacent diagonal
 A1  C2  E1  D3  B2

    a span 1                        ⍝ spanning tree for graph "a" from vertex 1.
¯1 1 1 3 4

    (a span 1)stpath 2              ⍝ shortest path from 1 to 2 using span tree.
1 2

    (a span 1)∘stpath¨⍳⍴a           ⍝ shortest path from 1 to each vertex.
┌─┬───┬───┬─────┬───────┐
│1│1 2│1 3│1 3 4│1 3 4 5│
└─┴───┴───┴─────┴───────┘
                                    ⍝ shortest path between
    ↑{(a span ⍵)∘stpath¨⍳⍴a}¨⍳⍴a    ⍝ each pair of vertices.
┌───────┬─────┬─────┬─────┬───────┐
│1      │1 2  │1 3  │1 3 4│1 3 4 5│
├───────┼─────┼─────┼─────┼───────┤
│2 3 4 1│2    │2 3  │2 3 4│2 3 4 5│
├───────┼─────┼─────┼─────┼───────┤
│3 4 1  │3 2  │3    │3 4  │3 4 5  │
├───────┼─────┼─────┼─────┼───────┤
│4 1    │4 1 2│4 5 3│4    │4 5    │
├───────┼─────┼─────┼─────┼───────┤
│5 3 4 1│5 3 2│5 3  │5 3 4│5      │
└───────┴─────┴─────┴─────┴───────┘

    k span 1                        ⍝ knight's spanning tree from vertex 1.
¯1 17 18 21 11 21 22 14 26 20 1 18 28 20 5 22 11 1 2 5 11 5 6 30 35 11 17 11 12 15 21 15 18 17 18 21 20 21 22 30 26 27 26 27 28 31 30 31 34 33 34 35 36 37 38 39 42 41 42 43 44 45 46 47

    k span 10                       ⍝ spanning tree from vertex 10.
11 19 20 10 20 21 24 14 19 ¯1 21 27 19 4 21 31 27 3 4 10 4 5 8 14 10 20 10 13 14 20 14 15 27 19 20 19 20 21 24 30 26 25 26 27 30 29 30 31 34 35 34 35 36 37 38 39 42 41 42 43 44 45 46 47

⍝ We can write a format operator to display the spanning tree:

    mtree←{                         ⍝ Matrix format of spanning tree.
        vfmt←⍺⍺                     ⍝ vertex format function.
        tree←⍵                      ⍝ spanning tree.
        ↑''{                        ⍝ mix to char matrix.
            this←⊂⍺,⊃vfmt ⍵         ⍝ indented, formatted vertex.
            next←(tree=⍵)/⍳⍴tree    ⍝ child vertices of current vertex ⍵.
            next≡⍬:this             ⍝ childless: finished.
            dent←⍺,'·   '           ⍝ increased indent.
            this,↑,/dent∘∇¨next     ⍝ formatted sub-trees.
        }tree⍳¯1                    ⍝ ... from starting vertex.
    }

⍝ Using the small graph "a" and {⍵⊃⎕a} as a vertex formatting function:

    a                       ⍝ graph "a".
┌───┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
└───┴─┴───┴───┴─┘

    {⍵⊃⎕a}mtree a span 3    ⍝ spanning tree from vertex 3.
C
·   B
·   D
·   ·   A
·   ·   E

⍝ The Word Ladder puzzle:

    wds←4⊃words                                 ⍝ vector of 4-letter words.

    wds[10?⍴wds]                                ⍝ random selection from 4-words.
 mack  minx  nest  gits  racy  clue  crib  lean  them  brow

    gph←{{⍵/⍳⍴⍵}¨↓⍵∘.{1=+/⍺≠⍵}⍵}wds             ⍝ graph of 1-letter changes.

    wds[gph path wds⍳'beer' 'wine']             ⍝ beer → wine
 beer  bear  bead  bend  bind  wind  wine

    wds[gph path wds⍳'wine' 'beer']             ⍝ wine → beer
 wine  dine  dint  dent  bent  beet  beer

    wds[gph path wds⍳'lead' 'gold']             ⍝ lead → gold
 lead  load  goad  gold

⍝ The following expression returns a graph of the "See also:" links
⍝ in this workspace:

    notes.({⍵∘{⍺{(1∊¨⍺⍷¨⊂⍵)/⍳⍴⍺}{(∨/'See also:'⍷⍵)⌿⍵}⎕FMT⍎⍵}¨⍵}⎕NL ¯2)

⍝ Cubes in ⍵-space
⍝ ----------------
⍝
⍝ An ⍵-cube is an undirected graph with 2*⍵ vertices and ⍵×2*⍵-1 edges.
⍝
⍝ We can make an ⍵-cube by joining the corresponding
⍝ vertices of a pair of (⍵-1)-cubes.
⍝                                                  .----------.
⍝                                                 /|\        /|\
⍝                                                / | \      / | \
⍝                              .----------.     .--+--.----.--+--.
⍝                             /|         /|     |\ | /|    |\ | /|
⍝                            / |        / |     | \'⌿-+----+-⍀'/ |
⍝       .   .----------.    .----------.  |     | /.⍀-+----+-⌿.\ |
⍝       |   |          |    |  |       |  |     |/ | \|    |/ | \|
⍝       |   |          |    |  '-------|--'     '--+--'----'--+--'
⍝       |   |          |    | /        | /       \ | /      \ | /
⍝       |   |          |    |/         |/         \|/        \|/
⍝   '   '   '----------'    '----------'           '----------'
⍝   ↑   ↑       ↑                   ↑                  ↑
⍝   │   │       │                   │                  │
⍝   │   │       │                   │                  └── 4-cube
⍝   │   │       │                   │                  (projected onto 2-space).
⍝   │   │       │                   │
⍝   │   │       │                   └── 3-cube (projected onto 2-space).
⍝   │   │       │
⍝   │   │       └── 2-cube (square)
⍝   │   │
⍝   │   └─ 1-cube (line)
⍝   │
⍝   └─ 0-cube (point)

⍝ This function returns an ⍵-cube graph:

    cube←{                      ⍝ ⍵-cube.
        ↓{                      ⍝ split simple matrix:
            0=⍵:1 0⍴0           ⍝ 0-cube: point.
            (2*⍵-1){            ⍝ number of vertices.
                (⍵⍪⍵+⍺),⍺⌽⍳2×⍺  ⍝ ⍵-cube from
            }∇ ⍵-1              ⍝   ⍵-1-cube.
        }⍵
    }

    cube 0              ⍝ point.
┌┐
││
└┘
    cube 1              ⍝ line.
┌─┬─┐
│2│1│
└─┴─┘

    cube 2              ⍝ square.
┌───┬───┬───┬───┐
│2 3│1 4│4 1│3 2│
└───┴───┴───┴───┘

    cube 3              ⍝ regular 3-cube.
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│2 3 5│1 4 6│4 1 7│3 2 8│6 7 1│5 8 2│8 5 3│7 6 4│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

    cube 4              ⍝ hypercube.
┌───────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬──────────┬─────────┬─────────┬──────────┬─────────┬──────────┬──────────┬──────────┐
│2 3 5 9│1 4 6 10│4 1 7 11│3 2 8 12│6 7 1 13│5 8 2 14│8 5 3 15│7 6 4 16│10 11 13 1│9 12 14 2│12 9 15 3│11 10 16 4│14 15 9 5│13 16 10 6│16 13 11 7│15 14 12 8│
└───────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴──────────┴─────────┴─────────┴──────────┴─────────┴──────────┴──────────┴──────────┘

    {(cube ⍵)path 1,2*⍵}10      ⍝ a path between opposite corners of a 10-cube.
1 513 769 897 961 993 1009 1017 1021 1023 1024

See also: wGraphs bfs scc
See also: inslink insnode remlink remnode gperm
See also: search path span stpath
See also: alists foldl
See also: stamps hampton konigsberg uksfr
See also: assign kt X

Back to: contents

Back to: Workspaces