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

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

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, "")
}

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

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.

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

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!

t-Factor: smaller is better