Version: v0.0.0-...-8ecfec1 Latest Latest Go to latest
Published: Jun 6, 2021 License: BSD-2-Clause

## Documentation ¶

### Overview ¶

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.

Example (Euclid)

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

```package main

import (
"fmt"
"github.com/yourbasic/graph"
"github.com/yourbasic/graph/build"
"math"
)

func main() {
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
```
Example (Maxflow)

Find a maximum flow in a virtual grid graph.

```package main

import (
"fmt"
"github.com/yourbasic/graph"
"github.com/yourbasic/graph/build"
)

func main() {
// 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
```

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type CostFunc ¶

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

`func Cost(n int64) CostFunc`

Cost returns a CostFunc that always returns n.

#### type EdgeSet ¶

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

`func AllEdges() EdgeSet`

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

#### func Edge ¶

`func Edge(v, w int) EdgeSet`

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

#### func NoEdges ¶

`func NoEdges() EdgeSet`

NoEdges returns a set that includes no edges.

#### func (EdgeSet) Contains ¶

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

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

#### type FilterFunc ¶

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

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

`func Range(a, b int) VertexSet`

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

#### func Vertex ¶

`func Vertex(v int) VertexSet`

Vertex returns a set containing the single vertex v.

#### func (VertexSet) And ¶

`func (s1 VertexSet) And(s2 VertexSet) VertexSet`

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

#### func (VertexSet) AndNot ¶

`func (s1 VertexSet) AndNot(s2 VertexSet) VertexSet`

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

#### func (VertexSet) Contains ¶

`func (s VertexSet) Contains(v int) bool`

Contains tells if v is a member of the set.

#### func (VertexSet) Or ¶

`func (s1 VertexSet) Or(s2 VertexSet) VertexSet`

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

#### type Virtual ¶

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

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

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

`func Empty(n int) *Virtual`

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

#### func Generic ¶

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

Example

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

```package main

import (
"fmt"
"github.com/yourbasic/graph"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

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

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

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

`func Kn(n int) *Virtual`

Kn returns a complete simple graph with n vertices.

#### func Specific ¶

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

`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 (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 (g *Virtual) AddCost(c int64) *Virtual`

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

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

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

#### func (*Virtual) Cartesian ¶

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

Example

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

```package main

import (
"fmt"
"github.com/yourbasic/graph"
"github.com/yourbasic/graph/build"
)

func main() {
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 ¶

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

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

Example (Barbell)

Build a weighted barbell graph.

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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

// 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 ¶

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

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

Degree returns the number of outward directed edges from v.

#### func (*Virtual) Delete ¶

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

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

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

#### func (*Virtual) Intersect ¶

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

Example

Compute the difference of two graphs.

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

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

Example (Wheel)

Build a wheel graph.

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

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

Example

Filter a graph with a function.

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

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

Example (Cube)

Build a cube graph.

```package main

import (
"fmt"
"github.com/yourbasic/graph"
"github.com/yourbasic/graph/build"
)

func main() {
// 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
```
Example (Petersen)

Build a Petersen graph.

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

`func (g *Virtual) Order() int`

Order returns the number of vertices in the graph.

#### func (*Virtual) String ¶

`func (g *Virtual) String() string`

String returns a string representation of the graph.

#### func (*Virtual) Subgraph ¶

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

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

Example

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

```package main

import (
"fmt"
"github.com/yourbasic/graph/build"
)

func main() {
// 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 ¶

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

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

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