build

package
v1.0.6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 21, 2021 License: BSD-2-Clause Imports: 3 Imported by: 0

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

Examples

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 (*Virtual) Add

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

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

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

func (*Virtual) AddCostFunc

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

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL