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
Index ¶
- type CostFunc
- type EdgeSet
- type FilterFunc
- type 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
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CostFunc ¶
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.
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.
type FilterFunc ¶
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.
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 ¶
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 ¶
Cycle returns a virtual cycle graph with n vertices and the edges {0, 1}, {1, 2}, {2, 3},... , {n-1, 0}.
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 ¶
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 ¶
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 ¶
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 Specific ¶
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 ¶
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 ¶
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) AddCostFunc ¶
AddCostFunc returns a copy of g with a new cost function assigned.
func (*Virtual) Cartesian ¶
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 ¶
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 ¶
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
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) Delete ¶
Delete returns a graph containing all edges in g except those also found in e.
func (*Virtual) Intersect ¶
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 ¶
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 ¶
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) Subgraph ¶
Subgraph returns a subgraph of g that consists of the vertices in s and all edges whose endpoints are in s.
func (*Virtual) Tensor ¶
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 ¶
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 ¶
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 ¶
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.
Source Files