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

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

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

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())

fn Graph.new(edges [][]int, weights_e []f64, verts [][]f64, weights_v []f64) &Graph

Graph.new initialises graph edges -- [nedges][2] edges (connectivity) weights_e -- [nedges] weights of edges verts -- [nverts][ndim] vertices weights_v -- [nverts] weights of vertices

enum ShortestPaths {
	fw // FW: Floyd-Warshall method
}

struct Graph {
pub:
	// input
	edges     [][]int // [nedges][2] edges (connectivity)
	weights_e []f64   // [nedges] weights of edges
	verts     [][]f64 // [nverts][ndim] vertices
	weights_v []f64   // [nverts] weights of vertices
	// auxiliary
	shares   map[int][]int // [nverts] edges sharing a vertex
	key2edge map[int]int   // maps (i,j) vertex to edge index
	dist     [][]f64       // [nverts][nverts] distances
	next     [][]int       // [nverts][nverts] next tree connection. -1 means no connection
}

Graph defines a graph structure

fn (g &Graph) nverts() int

nverts returns the number of vertices

fn (g &Graph) get_edge(i int, j int) !int

get_edge performs a lookup on key2edge map and returs id of edge for given nodes ides

fn (g &Graph) shortest_paths(method ShortestPaths) Graph

fn (g &Graph) path(s int, t int) []int

path returns the path from source (s) to destination (t)

Note: shortest_paths method must be called first

fn (g &Graph) calc_dist() Graph

calc_dist computes distances beetween all vertices and initialises 'next' matrix

fn (g &Graph) str_dist_matrix() string

str_dist_matrix returns a string representation of dist matrix

fn (g &Graph) get_adj() ([]int, []int)

get_adj returns adjacency list as a compressed storage format for METIS