groph

import "git.fractalqb.de/fractalqb/groph"

---

A pure Go library of graphs and their algorithms. More info at godoc.org.

Catchy Examples… hopefully

On can create the Graphviz .dot file for a directed graph:

with this lines of code:

func writePlain(wr io.Writer) {
	g := groph.NewAdjMxDbool(9, nil)
	type E = groph.Edge
	groph.Set(g, true, E{0, 1}, E{1, 3}, E{3, 2}, E{2, 0}, E{4, 3},
		E{4, 5}, E{5, 6}, E{6, 4}, E{7, 4}, E{8, 7})
	graphviz.Writer{}.Write(wr, g, "")
}

If you want it more fancy and show the embedded MST in the graph…

use Dijkstra's algorithm and configure the Graphviz writer to highlight it:

func writeFancy(wr io.Writer) {
	g := groph.NewAdjMxDbool(9, nil)
	type E = groph.Edge
	groph.Set(g, true, E{0, 1}, E{1, 3}, E{3, 2}, E{2, 0}, E{4, 3},
		E{4, 5}, E{5, 6}, E{6, 4}, E{7, 4}, E{8, 7})

	// Compute distances and minimal spanning tree starting at vertex 8
	dists, mst := (&shortestpath.DijkstraBool{}).On(g, 8, nil, []groph.VIdx{})

	// Tell Graphviz writer how to set the correct node and edge attributes
	dot := graphviz.Writer{
		GraphAtts: graphviz.AttMap(graphviz.Attributes{"rankdir": "LR"}),
		NodeAtts:  graphviz.AttMap(graphviz.Attributes{"shape": "box"}),
		PerNodeAtts: func(g groph.RGraph, v groph.VIdx) graphviz.Attributes {
			atts := graphviz.Attributes{"label": fmt.Sprintf("%c / %d", 'a'+v, v)}
			if v == mst.Root() {
				atts["shape"] = "circle"
			} else if groph.Degree(mst, v) == 1 {
				atts["shape"] = "doublecircle"
			}
			return atts
		},
		PerEdgeAtts: func(g groph.RGraph, u, v groph.VIdx) (atts graphviz.Attributes) {
			if mst.Edge(v, u) {
				atts = graphviz.Attributes{
					"label": fmt.Sprint(dists[v]),
					"color": "blue"}
			} else {
				atts = graphviz.Attributes{
					"label": graphviz.NoLabel,
					"color": "gray"}
			}
			return atts
		},
	}

	// Write the dot file
	dot.Write(wr, g, "")
}

Graph Implementations

The following table shows the supported graph implementations along with their relative access performance, i.e. read & write. Access performance is the factor relative to the fastest implementation – the one with 1 in the t/* column. Each implementation can be accessed through their WGraph interface (t/gen) or through their specifically typed interface (t/typed).

Implementation	Weight Type	Dir/Undir	t/typed	t/gen
Adjacency matrix	bool (bitmap)	D	1.51	3.68
Adjacency matrix	bool	D	1	2.01
Adjacency matrix	int32	D, U	1.08	8.18
Adjacency matrix	float32	D, U	1.12	8.35
Slice of Maps	interface{}	D, U	–	26.07
Slice of Maps	int32	D, U	15.92	25.22
Slice of Maps	float32	D, U	15.90	25.90

Note: Performance losses for generic access are mainly due to the type cast to a specific type after calling g.Weight(). Because this is probably relevant for real applications, this remains part of the benchmarks.

Algorithms

Algorithm	Problem	Weight Types
Depth First	Traversal (tvr)	interface{}
Floyd Warshall	Shortest path (sp)	int32, float32
Dijkstra	Shortest path (sp), Minimal spannig Tree	int32, float32
Kruskal	Minimal spannig Tree (msp)	int32, float32
TSP greedy	Travelling Salesman (tsp)	float32
2-Opt	Travelling Salesman (tsp)	float32

Performance compared to other Libraries

Comparison benchmarks can be found in the separate project groph-cmpbench.

Access Performance

Access performance is measured by writing and reading graph edges of a graph with a fixed number of vertices. While this does not tell anything about the quality of the provided algorithms theses operations are frequently called in inner loops of most algorithms. I.e. access performance will make a factor of algorithm's performance.

Other graph implementations are run against the groph top-speed graph. Use the numbers from groph's internal benchmark to estimate other comparisons.

Feedback on the benchmark project is very welcome to improve the validity of the comparison!

Library	Test	t-Factor
groph	access directed int32	1
yourbasic graph	directed int64	44
goraph	directed float64	737
thcyron graphs	directed float64	1145

t-Factor: smaller is better