graph

Build a plain graph and visit all of its edges.

package main

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

func main() {
	// Build a graph with four vertices and four undirected edges.
	// (Each of these edges are, in fact, represented by two directed
	// edges pointing in opposite directions.)
	g := graph.New(4)
	g.AddBoth(0, 1) //  0 -- 1
	g.AddBoth(0, 2) //  |    |
	g.AddBoth(2, 3) //  2 -- 3
	g.AddBoth(1, 3)

	// The vertices of all graphs in this package are numbered 0..n-1.
	// The edge iterator is a method called Visit; it calls a function
	// for each neighbor of a given vertex. Together with the Order
	// method — which returns the number of vertices in a graph — it
	// constitutes an Iterator. All algorithms in this package operate
	// on any graph implementing this interface.

	// Visit all edges of a graph.
	for v := 0; v < g.Order(); v++ {
		g.Visit(v, func(w int, c int64) (skip bool) {
			// Visiting edge (v, w) of cost c.
			return
		})
	}

	// The immutable data structure created by Sort has an Iterator
	// that returns neighbors in increasing order.

	// Visit the edges in order.
	for v := 0; v < g.Order(); v++ {
		graph.Sort(g).Visit(v, func(w int, c int64) (skip bool) {
			// Visiting edge (v, w) of cost c.
			return
		})
	}

	// The return value of an iterator function is used to break
	// out of the iteration. Visit, in turn, returns a boolean
	// indicating if it was aborted.

	// Skip the iteration at the first edge (v, w) with w equal to 3.
	for v := 0; v < g.Order(); v++ {
		aborted := graph.Sort(g).Visit(v, func(w int, c int64) (skip bool) {
			fmt.Println(v, w)
			if w == 3 {
				skip = true // Aborts the call to Visit.
			}
			return
		})
		if aborted {
			break
		}
	}
}

Output:

0 1
0 2
1 0
1 3

Show how to use this package by implementing a complete depth-first search.

package main

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

const (
	White = iota
	Gray
	Black
)

// The package doesn't support vertex labeling. However,
// since vertices are always numbered 0..n-1, it's easy
// to add this type of data on the side. This implementation
// of depth-first search uses separate slices to keep track of
// vertex colors, predecessors and discovery times.
type DFSData struct {
	Time     int
	Color    []int
	Prev     []int
	Discover []int
	Finish   []int
}

func DFS(g graph.Iterator) DFSData {
	n := g.Order() // Order returns the number of vertices.
	d := DFSData{
		Time:     0,
		Color:    make([]int, n),
		Prev:     make([]int, n),
		Discover: make([]int, n),
		Finish:   make([]int, n),
	}
	for v := 0; v < n; v++ {
		d.Color[v] = White
		d.Prev[v] = -1
	}
	for v := 0; v < n; v++ {
		if d.Color[v] == White {
			d.dfsVisit(g, v)
		}
	}
	return d
}

func (d *DFSData) dfsVisit(g graph.Iterator, v int) {
	d.Color[v] = Gray
	d.Time++
	d.Discover[v] = d.Time
	// Visit calls a function for each neighbor w of v,
	// with c equal to the cost of the edge (v, w).
	// The iteration is aborted if the function returns true.
	g.Visit(v, func(w int, c int64) (skip bool) {
		if d.Color[w] == White {
			d.Prev[w] = v
			d.dfsVisit(g, w)
		}
		return
	})
	d.Color[v] = Black
	d.Time++
	d.Finish[v] = d.Time
}

// Show how to use this package by implementing a complete depth-first search.
func main() {
	// Build a small directed graph:
	//
	//   0 ---> 1 <--> 2     3
	//
	g := graph.New(4)
	g.Add(0, 1)
	g.AddBoth(1, 2)

	fmt.Println(g)
	fmt.Println(DFS(g))
}

Output:

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