graph: github.com/yourbasic/graph/build Index | Examples | Files

package build

import "github.com/yourbasic/graph/build"

Package build offers a tool for building virtual graphs.

Virtual graphs

In a virtual graph no vertices or edges are stored in memory, they are instead computed as needed. New virtual graphs are constructed by composing and filtering a set of standard graphs, or by writing functions that describe the edges of a graph. Multigraphs and graphs with self-loops are not suppported.

Non-virtual graphs can be imported, and used as building blocks, by the Specific function. Virtual graphs don't need to be “exported‬”; they implement the Iterator interface and hence can be used directly by any algorithm in the graph package.

Performance tips

When possible, try to use predefined building blocks rather than filter functions. In particular, note that graphs built by the Generic function must visit all potenential neighbors during iteration.

If space is readily available, you may use the Specific function to turn on caching for any component. This gives constant time performance for all basic operations on that component.

Tutorial

The Euclid and Maxflow examples show how to build graphs from standard components using composition and filtering. They also demonstrate how to apply a cost function to a virtual graph.

Find a shortest path going back and forth between two sets of points in the plane.

Code:

type Point struct{ x, y int }

// Euclidean distance.
Euclid := func(p, q Point) float64 {
    xd := p.x - q.x
    yd := p.y - q.y
    return math.Sqrt(float64(xd*xd + yd*yd))
}

// 0     3
// 1     4
// 2     5
points := []Point{
    {0, 0}, {0, 1}, {0, 2},
    {4, 0}, {4, 1}, {4, 2},
}

// Build a complete bipartite graph, connecting the three
// left-hand points to the three points on the right,
// and then apply a cost function to the edges of the graph.
g := build.Kmn(3, 3).AddCostFunc(func(v, w int) int64 {
    // Distance to three decimal places.
    return int64(1000 * Euclid(points[v], points[w]))
})

// Find a shortest path from 0 to 2.
path, dist := graph.ShortestPath(g, 0, 2)
fmt.Println("path:", path, "length:", float64(dist)/1000)

Output:

path: [0 4 2] length: 8.246

Find a maximum flow in a virtual grid graph.

Code:

// Build an undirected n×n grid with a silly edge cost.
n := 10
grid := build.Grid(n, n).AddCostFunc(func(v, w int) int64 {
    return int64((v + w) * (w - v))
})

// Keep only the forward-pointing edges.
grid = grid.Keep(func(v, w int) bool { return v < w })

// Join the top row, 0..n-1, of the grid to a source S.
// The vertex in S will get index n*n in the new graph.
// The new edges should point from S to the grid.
// Give the new edges maximum capacity.
S := build.Empty(1)
grid_S := grid.Join(S, build.EdgeSet{
    From: build.Range(0, n),
    To:   build.Vertex(n * n),
    Keep: func(v, w int) bool { return v > w },
    Cost: build.Cost(graph.Max),
})

// Join the bottom row, n*(n-1)..n*n-1, of the grid to a sink T.
// The vertex in T will get index n*n+1 in the new graph.
// The new edges should point from the grid to T.
// Give the new edges maximum capacity.
T := build.Empty(1)
grid_S_T := grid_S.Join(T, build.EdgeSet{
    From: build.Range(n*(n-1), n*n),
    To:   build.Vertex(n*n + 1),
    Keep: func(v, w int) bool { return v < w },
    Cost: build.Cost(graph.Max),
})

// Find the maximum flow from S to T.
flow, _ := graph.MaxFlow(grid_S_T, n*n, n*n+1)
fmt.Println(flow)

Output:

1900

Index

Examples

Package Files

build.go cartesian.go circulant.go connect.go cycle.go edgeset.go grid.go hyper.go intersect.go join.go kmn.go match.go subgraph.go tensor.go tree.go union.go vertexset.go

type CostFunc Uses

type CostFunc func(v, w int) int64

CostFunc is a function that computes the cost of an edge from v to w. The nil value represents a cost function that always returns 0.

func Cost Uses

func Cost(n int64) CostFunc

Cost returns a CostFunc that always returns n.

type EdgeSet Uses

type EdgeSet struct {
    From, To VertexSet
    Keep     FilterFunc
    Cost     CostFunc
}

EdgeSet describes a set of edges; an edge (v, w), v ≠ w, belongs to the set if Keep(v, w) is true and (v, w) belongs to either From × To or To × From. The zero value of an edge set is the universe, the set containing all edges.

func AllEdges Uses

func AllEdges() EdgeSet

AllEdges returns the universe, the set containing all edges. The edge cost is zero.

func Edge Uses

func Edge(v, w int) EdgeSet

Edge returns a set consisting of a single edge {v, w}, v ≠ w, of zero cost.

func NoEdges Uses

func NoEdges() EdgeSet

NoEdges returns a set that includes no edges.

func (EdgeSet) Contains Uses

func (e EdgeSet) Contains(v, w int) bool

Contains tells if the set contains the edge {v, w}.

type FilterFunc Uses

type FilterFunc func(v, w int) bool

FilterFunc is a function that tells if there is a directed edge from v to w. The nil value represents an edge function that always returns true.

type VertexSet Uses

type VertexSet struct {
    // contains filtered or unexported fields
}

VertexSet represents a set of vertices in a graph. The zero value of a VertexSet is the universe; the set containing all vertices.

func Range Uses

func Range(a, b int) VertexSet

Range returns a set containing all vertices v, a ≤ v < b.

func Vertex Uses

func Vertex(v int) VertexSet

Vertex returns a set containing the single vertex v.

func (VertexSet) And Uses

func (s1 VertexSet) And(s2 VertexSet) VertexSet

And returns the set of all vertices belonging to both s1 and s2.

func (VertexSet) AndNot Uses

func (s1 VertexSet) AndNot(s2 VertexSet) VertexSet

AndNot returns the set of all vertices belonging to s1 but not to s2.

func (VertexSet) Contains Uses

func (s VertexSet) Contains(v int) bool

Contains tells if v is a member of the set.

func (VertexSet) Or Uses

func (s1 VertexSet) Or(s2 VertexSet) VertexSet

Or returns the set of all vertices belonging to either s1 or s2.

type Virtual Uses

type Virtual struct {
    // contains filtered or unexported fields
}

Virtual represents a virtual graph. In a virtual graph no vertices or edges are stored in memory, they are instead computed as needed. New virtual graphs are constructed by composing and filtering a set of standard graphs, or by writing functions that describe the edges of a graph.

func Circulant Uses

func Circulant(n int, s ...int) *Virtual

Circulant returns a virtual circulant graph with n vertices in which vertex i is adjacent to vertex (i + j) mod n and vertex (i - j) mod n for each j in the list s.

func Cycle Uses

func Cycle(n int) *Virtual

Cycle returns a virtual cycle graph with n vertices and the edges {0, 1}, {1, 2}, {2, 3},... , {n-1, 0}.

func Empty Uses

func Empty(n int) *Virtual

Empty returns a virtual graph with n vertices and no edges.

func Generic Uses

func Generic(n int, edge FilterFunc) *Virtual

Generic returns a virtual graph with n vertices; its edge set consists of all edges (v, w), v ≠ w, for which edge(v, w) returns true.

Build a directed graph containing all edges (v, w) for which v is odd and w even.

Code:

// Define a graph by a function.
g := build.Generic(10, func(v, w int) bool {
    // Include all edges with v odd and w even.
    return v%2 == 1 && w%2 == 0
})

// In a topological ordering of this graph,
// odd numbered vertices must come before even.
order, acyclic := graph.TopSort(g)
fmt.Println("Acyclic:", acyclic)
fmt.Println(order)

Output:

Acyclic: true
[1 3 5 7 9 0 2 4 6 8]

func Grid Uses

func Grid(m, n int) *Virtual

Grid returns a virtual graph whose vertices correspond to integer points in the plane: y-coordinates being in the range 0..m-1, and x-coordinates in the range 0..n-1. Two vertices of a grid are adjacent whenever the corresponding points are at distance 1.

Point (x, y) gets index nx + y, and index i corresponds to the point (i/n, i%n).

func Hyper Uses

func Hyper(n int) *Virtual

Hyper returns a virtual hypercube graph with 2ⁿ vertices. Two vertices of a hypercube are adjacent when their binary representations differ in a single digit.

func Kmn Uses

func Kmn(m, n int) *Virtual

Kmn returns a virtual complete bipartite graph with m+n vertices. The vertices are divided into two subsets U = [0..m) and V = [m..m+n), and the edge set consists of all edges {u, v}, where u ∊ U and v ∊ V.

func Kn Uses

func Kn(n int) *Virtual

Kn returns a complete simple graph with n vertices.

func Specific Uses

func Specific(g graph.Iterator) *Virtual

Specific returns a cached copy of g with constant time performance for all basic operations. It uses space proportional to the size of the graph.

This function does not accept multigraphs and graphs with self-loops.

func Tree Uses

func Tree(k, n int) *Virtual

Tree returns a full k-ary tree with n levels and (kⁿ-1)/(k-1) vertices. The parent of vertex v is (v-1)/k, and its children are kv + 1, kv + 2,… , kv + k.

func (*Virtual) Add Uses

func (g *Virtual) Add(e EdgeSet) *Virtual

Add returns a graph containing all edges in g plus all edges in e. Any edges belonging to both g and e will retain their cost from g.

func (*Virtual) AddCost Uses

func (g *Virtual) AddCost(c int64) *Virtual

AddCost returns a copy of g with a new cost assigned to all edges.

func (*Virtual) AddCostFunc Uses

func (g *Virtual) AddCostFunc(c CostFunc) *Virtual

AddCostFunc returns a copy of g with a new cost function assigned.

func (*Virtual) Cartesian Uses

func (g1 *Virtual) Cartesian(g2 *Virtual) *Virtual

Cartesian returns the cartesian product of g1 and g2: a graph whose vertices correspond to ordered pairs (v1, v2), where v1 and v2 are vertices in g1 and g2, respectively. The vertices (v1, v2) and (w1, w2) are connected by an edge if v1 = w1 and {v2, w2} ∊ g2 or v2 = w2 and {v1, w1} ∊ g1.

In the new graph, vertex (v1, v2) gets index n⋅v1 + v2, where n = g2.Order(), and index i corresponds to the vertice (i/n, i%n).

Build a cube graph by multiplying a single edge with itself.

Code:

edge := build.Grid(1, 2)
square := edge.Cartesian(edge)
cube := square.Cartesian(edge)

fmt.Println(edge)
fmt.Println(square)
fmt.Println(cube)

fmt.Println(graph.Equal(edge, build.Hyper(1)))
fmt.Println(graph.Equal(square, build.Hyper(2)))
fmt.Println(graph.Equal(cube, build.Hyper(3)))

Output:

2 [{0 1}]
4 [{0 1} {0 2} {1 3} {2 3}]
8 [{0 1} {0 2} {0 4} {1 3} {1 5} {2 3} {2 6} {3 7} {4 5} {4 6} {5 7} {6 7}]
true
true
true

func (*Virtual) Complement Uses

func (g *Virtual) Complement() *Virtual

Complement returns the complement graph of g. This graph has the same vertices as g, but its edge set consists of the edges not present in g. The edges of the complement graph will have zero cost.

func (*Virtual) Connect Uses

func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual

Connect connects g1 and g2 by making v1 in g1 a common vertex with 0 in g2. The vertices in g2 are renumbered: 0 becomes v1 in the new graph; and w, with w > 0, becomes w + g1.Order() - 1.

Build a weighted barbell graph.

Code:

// The n-barbell graph consists of two non-overlapping n-vertex cliques
// together with a single edge that has an endpoint in each clique.
n := 2
bar := build.Grid(1, 2).AddCost(20)
redPlate := build.Kn(n).AddCost(25)

// Connect one plate to each end of the bar.
barbell := bar.Connect(0, redPlate).Connect(1, redPlate)
fmt.Println(barbell)

Output:

4 [{0 1}:20 {0 2}:25 {1 3}:25]

func (*Virtual) Cost Uses

func (g *Virtual) Cost(v, w int) int64

Cost returns the cost of an edge from v to w, or 0 if no such edge exists.

func (*Virtual) Degree Uses

func (g *Virtual) Degree(v int) int

Degree returns the number of outward directed edges from v.

func (*Virtual) Delete Uses

func (g *Virtual) Delete(e EdgeSet) *Virtual

Delete returns a graph containing all edges in g except those also found in e.

func (*Virtual) Edge Uses

func (g *Virtual) Edge(v, w int) bool

Edge tells if there is an edge from v to w.

func (*Virtual) Intersect Uses

func (g1 *Virtual) Intersect(g2 *Virtual) *Virtual

Intersect returns the graph intersection g1 ∩ g2, which consists of the intersection of the two vertex sets and the intersection of the two edge sets of g1 and g2. The edges of the new graph will have zero cost.

Compute the difference of two graphs.

Code:

// The complete graph with four vertices.
Kn4 := build.Kn(4)
fmt.Println(Kn4)

// The circle graph with four vertices.
Cn4 := build.Cycle(4)
fmt.Println(Cn4)

// Remove all edges belonging to Cn4 from Kn4.
Kn4DiffCn4 := Kn4.Intersect(Cn4.Complement())
fmt.Println(Kn4DiffCn4)

Output:

4 [{0 1} {0 2} {0 3} {1 2} {1 3} {2 3}]
4 [{0 1} {0 3} {1 2} {2 3}]
4 [{0 2} {1 3}]

func (*Virtual) Join Uses

func (g1 *Virtual) Join(g2 *Virtual, bridge EdgeSet) *Virtual

Join joins g1 to g2 by adding edges from vertices in g1 to vertices in g2. Only the edges in the bridge are added. The vertices of g2 are renumbered before the operation: vertex v ∊ g2 becomes v + g1.Order() in the new graph.

Build a wheel graph.

Code:

// A wheel graph is a graph formed by joining a single vertex
// to all vertices of a cycle.
n := 32
hub := build.Empty(1)
rim := build.Cycle(n)
wheel := hub.Join(rim, build.AllEdges())
fmt.Println("Number of spokes:", wheel.Degree(0))

Output:

Number of spokes: 32

func (*Virtual) Keep Uses

func (g *Virtual) Keep(edge FilterFunc) *Virtual

Keep returns a graph containing all edges (v, w) of g for which edge(v, w) is true.

Filter a graph with a function.

Code:

// The complete graph with four vertices.
Kn4 := build.Kn(4)
fmt.Println(Kn4)

// Remove all edges incident with vertex 0.
Kn4MinusZero := Kn4.Keep(func(v, w int) bool { return v != 0 && w != 0 })
fmt.Println(Kn4MinusZero)

Output:

4 [{0 1} {0 2} {0 3} {1 2} {1 3} {2 3}]
4 [{1 2} {1 3} {2 3}]

func (*Virtual) Match Uses

func (g1 *Virtual) Match(g2 *Virtual, bridge EdgeSet) *Virtual

Match connects g1 to g2 by matching vertices in g1 with vertices in g2. Only vertices belonging to the bridge are included, and the vertices are matched in numerical order. The vertices of g2 are renumbered before the matching: vertex v ∊ g2 becomes v + g1.Order() in the new graph.

Build a cube graph.

Code:

// Build a cube graph.
square := build.Grid(2, 2)
cube := square.Match(square, build.AllEdges())
fmt.Println(cube)
fmt.Println(graph.Equal(cube, build.Hyper(3)))

Output:

8 [{0 1} {0 2} {0 4} {1 3} {1 5} {2 3} {2 6} {3 7} {4 5} {4 6} {5 7} {6 7}]
true

Build a Petersen graph.

Code:

// The Petersen graph is most commonly drawn as a pentagon
// with a pentagram inside, with five spokes.
pentagon := build.Cycle(5)
pentagram := pentagon.Complement()
petersen := pentagon.Match(pentagram, build.AllEdges())
fmt.Println(petersen)

Output:

10 [{0 1} {0 4} {0 5} {1 2} {1 6} {2 3} {2 7} {3 4} {3 8} {4 9} {5 7} {5 8} {6 8} {6 9} {7 9}]

func (*Virtual) Order Uses

func (g *Virtual) Order() int

Order returns the number of vertices in the graph.

func (*Virtual) String Uses

func (g *Virtual) String() string

String returns a string representation of the graph.

func (*Virtual) Subgraph Uses

func (g *Virtual) Subgraph(s VertexSet) *Virtual

Subgraph returns a subgraph of g that consists of the vertices in s and all edges whose endpoints are in s.

func (*Virtual) Tensor Uses

func (g1 *Virtual) Tensor(g2 *Virtual) *Virtual

Tensor returns the tensor product of g1 and g2: a graph whose vertices correspond to ordered pairs (v1, v2), where v1 and v2 are vertices in g1 and g2, respectively. The vertices (v1, v2) and (w1, w2) are connected by an edge whenever both of the edges {v1, w1} and {v2, w2} exist in the original graphs.

In the new graph, vertex (v1, v2) gets index n⋅v1 + v2, where n = g2.Order(), and index i corresponds to the vertice (i/n, i%n).

Build a crown graph by multiplying Kₙ with K₂.

Code:

// The tensor product G × K₂ is a bipartite graph called the bipartite double cover of G.
// A crown graph on 2n vertices is an undirected graph with two sets of vertices Uᵢ and Vⱼ
// and with an edge from Uᵢ to Vⱼ whenever i ≠ j.
// It can be computed as the bipartite double cover of Kn.
k4 := build.Kn(4)
crown8 := k4.Tensor(build.Kn(2))
fmt.Println(crown8)

Output:

8 [{0 3} {0 5} {0 7} {1 2} {1 4} {1 6} {2 5} {2 7} {3 4} {3 6} {4 7} {5 6}]

func (*Virtual) Union Uses

func (g1 *Virtual) Union(g2 *Virtual) *Virtual

Union returns the graph union g1 ∪ g2, which consists of the union of the two vertex sets and the union of the two edge sets of g1 and g2. The edges of the new graph will have zero cost.

func (*Virtual) Visit Uses

func (g *Virtual) Visit(v int, do func(w int, c int64) bool) bool

Visit calls the do function for each neighbor w of v, with c equal to the cost of the edge from v to w. The neighbors are visited in increasing numerical order. If do returns true, Visit returns immediately, skipping any remaining neighbors, and returns true.

func (*Virtual) VisitFrom Uses

func (g *Virtual) VisitFrom(v int, a int, do func(w int, c int64) bool) bool

VisitFrom calls the do function starting from the first neighbor w for which w ≥ a, with c equal to the cost of the edge from v to w. The neighbors are then visited in increasing numerical order. If do returns true, VisitFrom returns immediately, skipping any remaining neighbors, and returns true.

Package build imports 3 packages (graph). Updated 2018-05-29. Refresh now. Tools for package owners.