groph

README

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

Documentation

Overview

Package groph is a pure Go library for graph data and algorithms.

It provides an abstract graph model through some interfaces described below, a set of different implementations for those graph models—there is no one-size-fits-all implementation—and graph algorithms provided in sub packages.

Vertices are always represented by an integer value of type VIdx ranging from 0 to n-1 for graphs with n vertices. Mapping different vertex types to the VIdx values for groph is currently left to the user. Edges are associated with values called “weights” which is a useful feature for most graph algorithms. A simple, unweighted graph can be considered to have weights of type bool that represent whether an edged is in the graph.

The graph interfaces

The graph interfaces are grouped by some specific aspects:

- Graph implementations can be read-only and read-write.

- Graph implementations are for directed or undirected graphs.

- Values associated with edges can be general, i.e. of type interface{}, or have some specific type.

The most basic is the RGraph interface that allows read-only access to directed and undirected graphs with no specific edge type. The WGraph interface extends RGraph with methods to change edges in the graph.

The variants of RGraph and WGraph for undirected graphs are RUndirected and WUndirected. Any specific graph that does not implement RUndirected is considered to be a directed graph. One can use the Directed() function to just distinguish directed and undirected at runtime. To also downcast to undirected graphs use standard Go features.

More specific interfaces are derived from these interfaces and adhere to the following naming convention. The first letter is either 'R' or 'W' to indicate read-only respectively read-write graphs. The second letter is either 'G' or 'U' to distinguish general graph interfaces from undirected interfaces. Finally comes an indicator for the edge weights, e.g. “i32” for int32 or “f32” for float32 or “bool” for just bool.

Index

• func Degree(g RGraph, v VIdx) (res int)
• func Directed(g RGraph) bool
• func EachAdjacent(g RGraph, this VIdx, onOther VisitVertex) (stopped bool)
• func EachEdge(g RGraph, onEdge VisitEdge) (stopped bool)
• func EachIncoming(g RGraph, to VIdx, onSource VisitVertex) (stopped bool)
• func EachOutgoing(g RGraph, from VIdx, onDest VisitVertex) (stopped bool)
• func InDegree(g RGraph, v VIdx) (res int)
• func IsNaN32(x float32) bool
• func NaN32() float32
• func OutDegree(g RGraph, v VIdx) (res int)
• func Reset(g WGraph)
• func Set(g WGraph, w interface{}, edges ...Edge)
• func Size(g RGraph) (res int)
• type Edge
• type EdgeLister
• type InLister
• type LeavesLister
• type OutLister
• type RGbool
• type RGf32
• type RGi32
• type RGraph
• type RUbool
• type RUf32
• type RUi32
• type RUndirected
• type RootsLister
• type Tree
  • func (t Tree) EachEdge(onEdge VisitEdge) (stop bool)
  • func (t Tree) EachOutgoing(from VIdx, onDest VisitVertex) (stop bool)
  • func (t Tree) EachRoot(onRoot VisitVertex) (stop bool)
  • func (t Tree) Edge(u, v VIdx) bool
  • func (t Tree) Order() int
  • func (t Tree) OutDegree(v VIdx) int
  • func (t Tree) Root() (res VIdx)
  • func (t Tree) RootCount() int
  • func (t Tree) Size() int
  • func (t Tree) Weight(u, v VIdx) interface{}
• type VIdx
• type VisitEdge
• type VisitVertex
• type WGbool
• type WGf32
• type WGi32
• type WGraph
• type WUbool
• type WUf32
• type WUi32
• type WUndirected

Functions

func Degree

func Degree(g RGraph, v VIdx) (res int)

func Directed

func Directed(g RGraph) bool

Directed returns true, iff g is a directed graph and false otherwise.

func EachAdjacent

func EachAdjacent(g RGraph, this VIdx, onOther VisitVertex) (stopped bool)

EachAdjacent calls onOther on each vertex o where at least one of the edges (this,o) and (o,this) is in graph g.

func EachEdge

func EachEdge(g RGraph, onEdge VisitEdge) (stopped bool)

EachEdge call onEdge for every edge in graph g.

func EachIncoming

func EachIncoming(g RGraph, to VIdx, onSource VisitVertex) (stopped bool)

EachIncoming calls onSource on each vertex s where the edge (s,to) is in graph g.

func EachOutgoing

func EachOutgoing(g RGraph, from VIdx, onDest VisitVertex) (stopped bool)

EachOutgoing calls onDest on each vertex d where the edge (from,d) is in graph g.

func InDegree

func InDegree(g RGraph, v VIdx) (res int)

InDegree returns the number of incoming edges of vertex v in graph g. Note that for undirected graphs each edge is also considered to be an incoming edge.

func IsNaN32

func IsNaN32(x float32) bool

IsNaN32 test is x is NaN (no a number). See also NaN32.

func NaN32

func NaN32() float32

NaN32 is used by adjacency matrices with edge weight type 'float32' to mark edges that do not exist.

See AdjMxDf32 and AdjMxUf32

func OutDegree

func OutDegree(g RGraph, v VIdx) (res int)

OutDegree returns the number of outgoing edges of vertex v in graph g. Note that for undirected graphs each edge is also considered to be an outgoing edge.

func Reset

func Reset(g WGraph)

Reset clears a WGraph while keeping the original order. This is the same as calling g.Reset(g.Order()).

func Set

func Set(g WGraph, w interface{}, edges ...Edge)

Set sets the weight of all passed edges to w.

func Size

func Size(g RGraph) (res int)

Size returns the number of edges in the graph g.

Types

type Edge

type Edge struct {
	U, V VIdx
}

Edge represents a graphs edge between vertices U and V. For directed graphs its the edge from U to V.

type EdgeLister

type EdgeLister interface {
	EachEdge(onEdge VisitEdge) (stop bool)
	Size() int
}

InLister is implemented by graph implementations that can easily iterate over all edges of the graph.

See also Size and traverse.EachEdge function.

type InLister

type InLister interface {
	EachIncoming(to VIdx, onSource VisitVertex) (stopped bool)
	InDegree(v VIdx) int
}

InLister is implemented by graph implementations that can easily iterate over all incoming edges of one node.

See also InDegree and traverse.EachIncoming function.

type LeavesLister

type LeavesLister interface {
	EachLeaf(onEdge VisitVertex) (stop bool)
	LeafCount() int
}

type OutLister

type OutLister interface {
	EachOutgoing(from VIdx, onDest VisitVertex) (stopped bool)
	OutDegree(v VIdx) int
}

OutLister is implemented by graph implementations that can easily iterate over all outgoing edges of one node.

See also OutDegree and traverse.EachOutgoing function.

type RGbool

type RGbool interface {
	RGraph
	// Edge returns true, iff the edge (u,v) is in the graph.
	Edge(u, v VIdx) bool
}

RGbool represents a RGraph with boolean edge weights.

type RGf32

type RGf32 interface {
	RGraph
	// Edge returns Nan32() when the edge (u,v) is not in the graph. Otherwise
	// it returns the weight of the edge.
	Edge(u, v VIdx) (weight float32)
}

An RGf32 is a RGraph with type safe access to the edge weight of type float32. Besides type safety this avoids boxing/unboxing of the Weight method for performance reasons.

type RGi32

type RGi32 interface {
	RGraph
	// Edge returns ok == true, iff the edge (u,v) is in the graph. Then it will
	// also return the weight of the edge. Otherwise the value of weight is
	// unspecified.
	Edge(u, v VIdx) (weight int32, ok bool)
}

An RGi32 is a RGraph with type safe access to the edge weight of type int32. Besides type safety this avoids boxing/unboxing of the Weight method for performance reasons.

type RGraph

type RGraph interface {
	// Order return the numer of vertices in the graph.
	Order() int
	// Returns the weight of the edge that connects the vertex with index
	// u with the vertex with index v. If there is no such edge it returns nil.
	Weight(u, v VIdx) interface{}
}

RGraph represents graph that allows read only access to the egde weights.

For graphs that can change be modified see WGraph. For undirected graphs see also RUndirected.

type RUbool

type RUbool interface {
	RGbool
	EdgeU(u, v VIdx) bool
}

RUbool represents a RUndirected with boolean edge weights.

type RUf32

type RUf32 interface {
	RGf32
	EdgeU(u, v VIdx) (weight float32)
}

type RUi32

type RUi32 interface {
	RGi32
	EdgeU(u, v VIdx) (weight int32, ok bool)
}

type RUndirected

type RUndirected interface {
	RGraph
	// Weight must only be called when u ≥ v.  Otherwise WeightU's
	// behaviour is unspecified, it even might crash.  In many
	// implementations this can be way more efficient than the
	// general case, see method Weight().
	WeightU(u, v VIdx) interface{}
}

RUndirected represents an undirected graph that allows read only access to the edge weights. For undirected graphs each edge (u,v) is considered outgiong as well as incoming for both, vertex u and vertext v.

type RootsLister

type RootsLister interface {
	EachRoot(onEdge VisitVertex) (stop bool)
	RootCount() int
}

type Tree

type Tree []VIdx

TODO verify beeing a tree

func (Tree) EachEdge

func (t Tree) EachEdge(onEdge VisitEdge) (stop bool)

func (Tree) EachOutgoing

func (t Tree) EachOutgoing(from VIdx, onDest VisitVertex) (stop bool)

func (Tree) EachRoot

func (t Tree) EachRoot(onRoot VisitVertex) (stop bool)

func (Tree) Edge

func (t Tree) Edge(u, v VIdx) bool

func (Tree) Order

func (t Tree) Order() int

func (Tree) OutDegree

func (t Tree) OutDegree(v VIdx) int

func (Tree) Root

func (t Tree) Root() (res VIdx)

func (Tree) RootCount

func (t Tree) RootCount() int

func (Tree) Size

func (t Tree) Size() int

func (Tree) Weight

func (t Tree) Weight(u, v VIdx) interface{}

type VIdx

type VIdx = int

VIdx is the type used to represent vertices in the graph implementations provided by the groph package.

type VisitEdge

type VisitEdge = func(u, v VIdx) (stop bool)

type VisitVertex

type VisitVertex = func(v VIdx) (stop bool)

type WGbool

type WGbool interface {
	WGraph
	// see RGbool
	Edge(u, v VIdx) bool
	// SetEdge removes the edge (u,v) from the graph when flag == bool.
	// Otherwise it adds the edge (u,v) to the graph.
	SetEdge(u, v VIdx, flag bool)
}

WGbool represents a WGraph with boolean edge weights.

type WGf32

type WGf32 interface {
	WGraph
	// see RGf32
	Edge(u, v VIdx) (weight float32)
	// SetEdge removes the edge (u,v) from the graph, iff weight is NaN32().
	// Othwerwise it sets the weight of the edge to weight.
	SetEdge(u, v VIdx, weight float32)
}

An WGf32 is to WGraph what RGf32 is to RGraph.

type WGi32

type WGi32 interface {
	WGraph
	// see RGi32
	Edge(u, v VIdx) (weight int32, ok bool)
	// SetEdge sets the weight of the edge (u,v). If the edge (u,v) was not in
	// the graph before, it is implicitly added.
	SetEdge(u, v VIdx, weight int32)
}

An WGi32 is to WGraph what RGi32 is to RGraph.

type WGraph

type WGraph interface {
	RGraph
	// Reset resizes the graph to order and reinitializes it. Implementations
	// are expected to reuse memory.
	Reset(order int)
	// SetWeight sets the edge weight for the edge starting at vertex u and
	// ending at vertex v. Passing w==nil removes the edge.
	SetWeight(u, v VIdx, w interface{})
}

WGraph represents graph that allows read and write access to the egde weights.

For undirected graphs see also WUndirected.

type WUbool

type WUbool interface {
	WGbool
	WeightU(u, v VIdx) interface{}
	SetWeightU(u, v VIdx, w interface{})
	EdgeU(u, v VIdx) bool
	SetEdgeU(u, v VIdx, flag bool)
}

type WUf32

type WUf32 interface {
	WGf32
	WeightU(u, v VIdx) interface{}
	SetWeightU(u, v VIdx, w interface{})
	EdgeU(u, v VIdx) (weight float32)
	SetEdgeU(u, v VIdx, weight float32)
}

type WUi32

type WUi32 interface {
	WGi32
	WeightU(u, v VIdx) interface{}
	SetWeightU(u, v VIdx, w interface{})
	EdgeU(u, v VIdx) (weight int32, ok bool)
	SetEdgeU(u, v VIdx, weight int32)
}

type WUndirected

type WUndirected interface {
	WGraph
	// See RUndirected.WeightU
	WeightU(u, v VIdx) interface{}
	// SetWeightU must only be called when u ≥ v.  Otherwise
	// SetWeightU's behaviour is unspecified, it even might crash.
	//
	// See also RUndirected.WeightU
	SetWeightU(u, v VIdx, w interface{})
}

WUndirected represents an undirected graph that allows read and write access to the egde weights.