README
¶
Gosl. gm. Graph theory structures and algorithms
More information is available in the documentation of this package.
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:
var G Graph
G.Init(
// edge: 0 1 2 3
[][]int{{0, 1}, {0, 3}, {1, 2}, {2, 3}},
[]float64{5, 10, 3, 1}, // edge/weights
nil, nil, // optional: vertices and vertex/weights
)
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 ShortestPaths 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 ShortestPaths 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]
// initialise graph
var g graph.Graph
g.Init(
// edge: 0 1 2 3
[][]int{{0, 1}, {0, 3}, {1, 2}, {2, 3}},
// weights:
[]float64{5, 10, 3, 1},
// vertices (coordinates, for drawings):
[][]float64{
{0, 1}, // x,y vertex 0
{0, 0}, // x,y vertex 1
{1, 0}, // x,y vertex 2
{1, 1}, // x,y vertex 3
},
// weights:
nil,
)
// compute paths
g.ShortestPaths("FW")
// print shortest path from 0 to 2
io.Pf("dist from = %v\n", g.Path(0, 2))
// print shortest path from 0 to 3
io.Pf("dist from = %v\n", g.Path(0, 3))
// print distance matrix
io.Pf("dist =\n%v", g.StrDistMatrix())
// constants for plot
radius, width, gap := 0.05, 1e-8, 0.05
// plot
plt.Reset(true, &plt.A{WidthPt: 250, Dpi: 150, Prop: 1.0})
err := g.Draw(nil, nil, radius, width, gap, nil, nil, nil, nil)
if err != nil {
io.Pf("%v", err)
return
}
plt.Equal()
plt.AxisOff()
plt.Save("/tmp/gosl/graph", "shortestpath01")
Source code: ../examples/graph_shortestpaths01.go
Example: Sioux Falls
// load graph data from FLOW file
g := graph.ReadGraphTable("../graph/data/SiouxFalls.flow", false)
// compute paths
g.ShortestPaths("FW")
// print shortest path from 0 to 20
io.Pf("dist from = %v\n", g.Path(0, 20))
io.Pf("must be: [0, 2, 11, 12, 23, 20]\n")
// data for drawing: ids of vertices along columns in plot grid
columns := [][]int{
{0, 2, 11, 12},
{3, 10, 13, 22, 23},
{4, 8, 9, 14, 21, 20},
{1, 5, 7, 15, 16, 18, 19},
{6, 17},
}
// data for drawing: y-coordinats of vertices in plot
Y := [][]float64{
{7, 6, 4, 0}, // col0
{6, 4, 2, 1, 0}, // col1
{6, 5, 4, 2, 1, 0}, // col2
{7, 6, 5, 4, 3, 2, 0}, // col3
{5, 4}, // col4
}
// data for drawing: set vertices in graph structure
scalex := 1.8
scaley := 1.3
nv := 24
g.Verts = make([][]float64, nv)
for j, col := range columns {
x := float64(j) * scalex
for i, vid := range col {
g.Verts[vid] = []float64{x, Y[j][i] * scaley}
}
}
// data for drawing: set vertex labels
vlabels := make(map[int]string)
for i := 0; i < nv; i++ {
vlabels[i] = io.Sf("%d", i)
}
// data for drawing: set edge labels
ne := 76
elabels := make(map[int]string)
for i := 0; i < ne; i++ {
elabels[i] = io.Sf("%d", i)
}
// plot
plt.Reset(true, &plt.A{WidthPt: 500, Dpi: 150, Prop: 1.1})
err := g.Draw(vlabels, elabels, 0, 0, 0, nil, nil, nil, nil)
if err != nil {
io.Pf("%v", err)
return
}
plt.Equal()
plt.AxisOff()
plt.Save("/tmp/gosl/graph", "graph_siouxfalls01")
Source code: ../examples/graph_siouxfalls01.go
Munkres (Hungarian algorithm): the assignment problem
The Munkres method, also known as the Hungarian algorithm, aims to solve the assignment problem; i.e. problems such as the following example:
Minimise the cost of operation when assigning three employees (Fry, Leela, Bender) to three tasks,
where (the minimum cost is highlighted):
$ | Clean Sweep Wash
-------|--------------------
Fry | [2] 3 3
Leela | 3 [2] 3
Bender | 3 3 [2]
minimum cost = 6
The code is based on Bob Pilgrim' work.
The method runs in O(n²), in the worst case; therefore is not efficient for large matrices.
The Munkres structure implements the solver.
Examples
Solution of Euler's problem # 345 using the Hungarian algorithm.
// problem matrix
C := [][]float64{
{7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583},
{627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913},
{447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743},
{217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350},
{960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350},
{870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803},
{973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326},
{322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973},
{445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848},
{414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198},
{184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390},
{821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574},
{34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699},
{815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107},
{813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805},
}
// solver seeks to minimise cost, thus, multiply coefficients by -1
for i := 0; i < len(C); i++ {
for j := 0; j < len(C[i]); j++ {
C[i][j] *= -1
}
}
// initialise solver
var mnk graph.Munkres
mnk.Init(len(C), len(C[0]))
mnk.SetCostMatrix(C)
// solve rpoblem
mnk.Run()
// results
io.Pf("links = %v\n", mnk.Links)
io.Pf("cost = %v (optimal 13938)\n", -mnk.Cost)
Output:
links = [9 10 7 4 3 0 13 2 14 11 6 5 12 8 1]
cost = 13938 (optimal 13938)
Source code: ../examples/graph_munkres01.go
Documentation
¶
Overview ¶
Package graph implements solvers based on Graph theory
Index ¶
- func BuildIndicatorMatrix(nv int, pth []int) (x [][]int)
- func CheckIndicatorMatrix(source, target int, x [][]int, verbose bool) (errPath, errLoop int)
- func CheckIndicatorMatrixRowMaj(source, target, nv int, xmat []int) (errPath, errLoop int)
- func MetisPartition(npart, nvert int, xadj, adjncy []int32, recursive bool) (objval int32, parts []int32)
- func PrintIndicatorMatrix(x [][]int) (l string)
- type Graph
- func (o *Graph) CalcDist()
- func (o *Graph) GetAdjacency() (xadj, adjncy []int32)
- func (o *Graph) GetEdge(i, j int) (k int)
- func (o *Graph) HashEdgeKey(i, j int) (edge int)
- func (o *Graph) Init(edges [][]int, weightsE []float64, verts [][]float64, weightsV []float64)
- func (o *Graph) Nverts() int
- func (o *Graph) Path(s, t int) (p []int)
- func (o *Graph) ShortestPaths(method string)
- func (o *Graph) StrDistMatrix() (l string)
- type MaskType
- type Munkres
- type Plotter
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildIndicatorMatrix ¶
BuildIndicatorMatrix builds indicator matrix
func CheckIndicatorMatrix ¶
CheckIndicatorMatrix checks indicator matirx
func CheckIndicatorMatrixRowMaj ¶
CheckIndicatorMatrixRowMaj checks indicator matrix in row-major format
func MetisPartition ¶
func MetisPartition(npart, nvert int, xadj, adjncy []int32, recursive bool) (objval int32, parts []int32)
MetisPartition performs graph partitioning using METIS
func PrintIndicatorMatrix ¶
PrintIndicatorMatrix prints indicator matrix
Types ¶
type Graph ¶
type Graph struct {
// input
Edges [][]int // [nedges][2] edges (connectivity)
WeightsE []float64 // [nedges] weights of edges. can be <nil>
Verts [][]float64 // [nverts][ndim] vertices. can be <nil>
WeightsV []float64 // [nverts] weights of vertices. can be <nil>
// auxiliary
Key2edge map[int]int // maps (i,j) vertex to edge index
Dist [][]float64 // [nverts][nverts] distances
Next [][]int // [nverts][nverts] next tree connection. -1 means no connection
}
Graph defines a graph structure
func ReadGraphTable ¶
ReadGraphTable reads data and allocate graph
func (*Graph) CalcDist ¶
func (o *Graph) CalcDist()
CalcDist computes distances beetween all vertices and initialises 'Next' matrix
func (*Graph) GetAdjacency ¶
GetAdjacency returns adjacency list as a compressed storage format for METIS
func (*Graph) GetEdge ¶
GetEdge performs a lookup on Key2edge map and returs id of edge for given nodes ides
func (*Graph) HashEdgeKey ¶
HashEdgeKey creates a unique hash key identifying an edge
func (*Graph) Init ¶
Init initialises graph
Input: edges -- [nedges][2] edges (connectivity) weightsE -- [nedges] weights of edges. can be <nil> verts -- [nverts][ndim] vertices. can be <nil> weightsV -- [nverts] weights of vertices. can be <nil>
func (*Graph) Path ¶
Path returns the path from source (s) to destination (t)
Note: ShortestPaths method must be called first
func (*Graph) ShortestPaths ¶
ShortestPaths computes the shortest paths in a graph defined as follows
[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
Input:
method -- FW: Floyd-Warshall method
func (*Graph) StrDistMatrix ¶
StrDistMatrix returns a string representation of Dist matrix
type Munkres ¶
type Munkres struct {
// main
C [][]float64 // [nrow][ncol] cost matrix
Cori [][]float64 // [nrow][ncol] original cost matrix
Links []int // [nrow] will contain links/assignments after Run(), where j := o.Links[i] means that i is assigned to j. -1 means no assignment/link
Cost float64 // total cost after Run() and links are established
// auxiliary
M [][]MaskType // [nrow][ncol] mask matrix. If Mij==1, then Cij is a starred zero. If Mij==2, then Cij is a primed zero
// contains filtered or unexported fields
}
Munkres (Hungarian algorithm) method to solve the assignment problem
based on code by Bob Pilgrim from http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
Note: this method runs in O(n²), in the worst case; therefore is not efficient for large matrix
Example:
$ | Clean Sweep Wash
-------|--------------------
Fry | [2] 3 3
Leela | 3 [2] 3
Bender | 3 3 [2]
minimum cost = 6
Note: cost will be minimised
func (*Munkres) Run ¶
func (o *Munkres) Run()
Run runs the iterative algorithm
Output:
o.Links -- will contain assignments, where len(assignments) == nrow and
j := o.Links[i] means that i is assigned to j
-1 means no assignment/link
o.Cost -- will have the total cost by following links
func (*Munkres) SetCostMatrix ¶
SetCostMatrix sets cost matrix by copying from C to internal o.C
Note: costs must be positive
func (*Munkres) StrCostMatrix ¶
StrCostMatrix returns a representation of cost matrix with masks and covers
type Plotter ¶
type Plotter struct {
G *Graph // the graph
Parts []int32 // [nverts] partitions
VertsLabels map[int]string // [nverts] labels of vertices. may be nil
EdgesLabels map[int]string // [nedges] labels of edges. may be nil
FcParts []string // [nverts] face colors of circles indicating partitions. may be nil
Radius float64 // radius of circles. can be 0
Width float64 // distance between two edges. can be 0
Gap float64 // gap between text and edges; e.g. width/2. can be 0
ArgsVertsTxt *plt.A // arguments for vertex ids. may be nil
ArgsEdgesTxt *plt.A // arguments for edge ids. may be nil
ArgsVerts *plt.A // arguments for vertices. may be nil
ArgsEdges *plt.A // arguments for edges. may be nil
}
Plotter draws graphs
Source Files