───────────────
Weighted Graphs
───────────────
A  weighted  graph has a traversal cost associated with each edge. An example of
an application might be in modelling a transportation system such as a road net-
work.  An  edge  of  the graph would correspond to a stretch of road between two
intersections,  and  its  weight with the length of the section or expected time
taken to drive along it. Choosing an optimal path through such a network amounts
to finding a set of graph edges connecting the start and end points, which has a
minimal total cost.

The  following  diagram  represents a simple example, whose weights are shown to
the right of, or below, the direction arrow for each edge.

  Weighted Graph "aa".
    ┌─────A←────┐
    │     │1    │   5 vertices: A B C D E
    ↓1    ↓3    │
    B←───→C────→D   8 edges:    A→B  A→C  B→C  C→B  C→D  D→A  D→E  E→C
     4   1↑1   1│   weights:     1    3    1    4    1    1    1    1
          │     ↓1
          └─────E   Notice that there is an edge C→B, as well as B→C.

The  graph  is  implemented as a 2-row  matrix, whose first row is an unweighted
graph and whose second row is a vector of weights for each edge.

Functions →wpath← and →wspan← do the same job as →path← and →span← respectively,
and →wcost← returns the cost for each edge of a path through the graph.

Mike Day suggests a class of problem in which we navigate between adjacent cells
of  a  matrix  and where there is a cost of visiting each cell. There may be re-
strictions  on  which  directions  we can take (for example: only rightwards and
downwards).

Mike  provides  a  function  to  convert from such a matrix to a weighted graph,
suitable for wpath, wspan, etc:

    mattographa←{⎕ML←0
        i←{⍵⍴⍳×/⍵}⍴⍵
        max←1+⌈/,i
        ⍺←1 1 1 1           ⍝ if up left right down
        addlink←{
            1 1↓¯1 ¯1↓⍺{
                ⍺=0:⍵
                ⍺=1:¯1⊖⍵
                ⍺=2:¯1⌽⍵
                ⍺=3:1⌽⍵
                ⍺=4:1⊖⍵
            }⍵
        }
        op←⍺/⍳4
        w←max,max,⍨max⍪max⍪⍨i
        links←,{⍵/⍨⍵<max}¨↓[⎕IO]↑op addlink¨⊂w
        costs←links{⍺⊃¨⊂⍵}¨⊂,⍵
        links←(⊂⊂¨,i)⍳¨⊂¨¨links
        ↑links costs
    }

    cell_costs          ⍝ cost of visiting each cell.
131 673 234 103  18
201  96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524  37 331

    1 25 wpath⍨ 0 0 1 1 mattographa cell_costs      ⍝ minimal path: down, right.
1 6 7 8 13 14 19 24 25

    1 25 wpath⍨ 1 1 1 1 mattographa cell_costs      ⍝ minimal path: any dirn.
1 6 7 8 3 4 5 10 15 14 19 24 25

    costs←{⍵ wcost ⍵ wpath ⍺}                       ⍝ cost function.

    1 25 costs 0 0 1 1 mattographa cell_costs       ⍝ cost of each link in path.
201 96 342 746 422 121 37 331

Note that the cost of _entering_ the first cell is missing from the cost vector.

This nested version of mattographa is smaller but runs a lot slower than Mike's:

    m2g←{⎕ML←0                          ⍝ Graph from weightings matrix.
        ⍺←1 1 1 1                       ⍝ up left right down.
        dirns←⍺/(¯1 0)(0 ¯1)(0 1)(1 0)  ⍝ directions.
        xvecs←dirns∘+∘⊂¨⍳⍴⍵             ⍝ index vectors per link.
        links←,{⍵⍳¨⍵∩¨xvecs}⊂,⍳⍴⍵       ⍝ unweighted graph.
        costs←,links{⍺⊃¨⊂⍵}¨⊂,⍵         ⍝ costs per link.
        ↑links costs                    ⍝ weighted graph.
    }

Examples:

      aa←↑((2 3)3(2 4)(1 5)3) ((1 3)1(4 1)(1 1)1)

      aa                            ⍝ simple weighted graph "aa".
┌───┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
├───┼─┼───┼───┼─┤
│1 3│1│4 1│1 1│1│
└───┴─┴───┴───┴─┘

      show←{↑{⍺,'→',⍵}/⎕a[⍵]}       ⍝ translate path vertices to: A B C ···

      show aa wpath 3 2             ⍝ lowest cost path C→B.
C→D→A→B

      show aa[1;] path 3 2          ⍝ compare: best path C→B _ignoring_ weights.
C→B

      aa wspan 5                    ⍝ spanning tree for aa from vertex 3.
4 1 5 3 ¯1

      disp(aa wspan 5)∘stpath¨⍳5    ⍝ paths to each vertex from spanning tree 5.
┌→──────┬─────────┬───┬─────┬─┐
│5 3 4 1│5 3 4 1 2│5 3│5 3 4│5│
└~─────→┴~───────→┴~─→┴~───→┴→┘

      aa wcost 1 3 4 5 3 2 3 2      ⍝ cost of path through graph "aa".
3 1 1 1 4 1 4

See also: Graphs wpath wspan wcost wmst stpath
See also: path span

Back to: contents

Back to: Workspaces