Graph theory structures and algorithms

This package implements algorithms for handling graphs and solving problems such as shortest path finding. It also implements an algorithm to solve the assignment problem.

Graph representation

In graph, directed graphs are mainly defined by edges. A weight can be assigned to each edge as well. For example, the graph below:

          [10]
     0 ––––––––→ 3      numbers in parentheses
     |    (1)    ↑      indicate edge ids
  [5]|(0)        |
     |        (3)|[1]
     ↓    (2)    |      numbers in brackets
     1 ––––––––→ 2      indicate weights
          [3]

is defined with the following code:

module main

import vsl.graph

edges := [[0, 1], [0, 3], [1, 2], [2, 3]]
weights_e := [5.0, 10.0, 3.0, 1.0]
verts := [][]f64{}
weights_v := []f64{}
g := graph.Graph.new(edges, weights_e, verts, weights_v)
// print distance matrix
print(g.str_dist_matrix())

Vertex coordinates can be specified as well. Furthermore, weights can be assigned to vertices. These are useful when computing distances, for example.

Floyd-Warshall algorithm to compute shortest paths

The shortest_paths method of Graph computes the shortest paths using the Floyd-Warshall algorithm. For example, the graph above has the following distances matrix:

       [10]
    0 ––––––→ 3            numbers in brackets
    |         ↑            indicate weights
[5] |         | [1]
    ↓         |
    1 ––––––→ 2
        [3]                ∞ means that there are no
                           connections from i to j
graph:  j= 0  1  2  3
           -----------  i=
           0  5  ∞ 10 |  0  ⇒  w(0→1)=5, w(0→3)=10
           ∞  0  3  ∞ |  1  ⇒  w(1→2)=3
           ∞  ∞  0  1 |  2  ⇒  w(2→3)=1
           ∞  ∞  ∞  0 |  3

After running the shortest_paths command, paths from source (s) to destination (t) can be extracted with the path method.

Example: Small graph

         [10]
    0 ––––––––→ 3      numbers in parentheses
    |    (1)    ↑      indicate edge ids
 [5]|(0)        |
    |        (3)|[1]
    ↓    (2)    |      numbers in brackets
    1 ––––––––→ 2      indicate weights
         [3]

module main

import vsl.graph

// initialise graph
edges := [[0, 1], [0, 3], [1, 2], [2, 3]]
weights_e := [5.0, 10.0, 3.0, 1.0]
verts := [][]f64{}
weights_v := []f64{}
g := graph.Graph.new(edges, weights_e, verts, weights_v)
// compute paths
g.shortest_paths(.fw)
// print shortest path from 0 to 2
print(g.path(0, 2))
// print shortest path from 0 to 3
print(g.path(0, 3))
// print distance matrix
print(g.str_dist_matrix())