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

Package build offers a tool for building 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.

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.

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

- type CostFunc
- type EdgeSet
- func AllEdges() EdgeSet
- func Edge(v, w int) EdgeSet
- func NoEdges() EdgeSet
- func (e EdgeSet) Contains(v, w int) bool
- type FilterFunc
- type VertexSet
- func Range(a, b int) VertexSet
- func Vertex(v int) VertexSet
- func (s1 VertexSet) And(s2 VertexSet) VertexSet
- func (s1 VertexSet) AndNot(s2 VertexSet) VertexSet
- func (s VertexSet) Contains(v int) bool
- func (s1 VertexSet) Or(s2 VertexSet) VertexSet
- type Virtual
- func Circulant(n int, s ...int) *Virtual
- func Cycle(n int) *Virtual
- func Empty(n int) *Virtual
- func Generic(n int, edge FilterFunc) *Virtual
- func Grid(m, n int) *Virtual
- func Hyper(n int) *Virtual
- func Kmn(m, n int) *Virtual
- func Kn(n int) *Virtual
- func Specific(g graph.Iterator) *Virtual
- func Tree(k, n int) *Virtual
- func (g *Virtual) Add(e EdgeSet) *Virtual
- func (g *Virtual) AddCost(c int64) *Virtual
- func (g *Virtual) AddCostFunc(c CostFunc) *Virtual
- func (g1 *Virtual) Cartesian(g2 *Virtual) *Virtual
- func (g *Virtual) Complement() *Virtual
- func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual
- func (g *Virtual) Cost(v, w int) int64
- func (g *Virtual) Degree(v int) int
- func (g *Virtual) Delete(e EdgeSet) *Virtual
- func (g *Virtual) Edge(v, w int) bool
- func (g1 *Virtual) Intersect(g2 *Virtual) *Virtual
- func (g1 *Virtual) Join(g2 *Virtual, bridge EdgeSet) *Virtual
- func (g *Virtual) Keep(edge FilterFunc) *Virtual
- func (g1 *Virtual) Match(g2 *Virtual, bridge EdgeSet) *Virtual
- func (g *Virtual) Order() int
- func (g *Virtual) String() string
- func (g *Virtual) Subgraph(s VertexSet) *Virtual
- func (g1 *Virtual) Tensor(g2 *Virtual) *Virtual
- func (g1 *Virtual) Union(g2 *Virtual) *Virtual
- func (g *Virtual) Visit(v int, do func(w int, c int64) bool) bool
- func (g *Virtual) VisitFrom(v int, a int, do func(w int, c int64) bool) bool

- Generic
- Virtual.Cartesian
- Virtual.Connect (Barbell)
- Virtual.Intersect
- Virtual.Join (Wheel)
- Virtual.Keep
- Virtual.Match (Cube)
- Virtual.Match (Petersen)
- Virtual.Tensor
- package (Euclid)
- package (Maxflow)

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

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.

Cost returns a CostFunc that always returns n.

❖

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.

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

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

NoEdges returns a set that includes no edges.

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

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

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

Vertex returns a set containing the single vertex v.

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

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

Contains tells if v is a member of the set.

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

❖

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

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.

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

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

❖

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]

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

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.

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.

Kn returns a complete simple graph with n vertices.

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.

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.

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.

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

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

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

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.

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]

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

Degree returns the number of outward directed edges from v.

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

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

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}]

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 (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}]

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}]

Order returns the number of vertices in the graph.

String returns a string representation of the graph.

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

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}]

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.

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.

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. This is an inactive package (no imports and no commits in at least two years).