graph

package module
v0.0.0-...-e28f6b4 Latest Latest
Warning

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

 Go to latest Published: Feb 13, 2020 License: MIT Imports: 3 Imported by: 0

README

graph

This repository provides go implementation of some algorithms on graphs

Install

go get -u github.com/batiazinga/graph

Documentation

Overview

Package graph provides some algorithms on graphs.

Visit:

  • breadth-first visit
  • depth-first visit

Shortest distance:

  • Dijkstra
  • A* (TODO)
  • Bellman-Ford (TODO)
  • Johnson all pairs (TODO)

Minimum Spanning Tree:

  • Kruskal (TODO)
  • Prim (TODO)

Cycles and Circuits:

  • Euler cycle (TODO)

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func BreadthFirstSearch 

func BreadthFirstSearch(g Forward, vis BfsVisitor, source, target string)

BreadthFirstSearch visits a graph starting from the source vertex. It visits closer vertices first and stops when the target is discovered.

The slice returned by calls to NextVertices is never modified. So there is no risk of accidentally modifying g.

At some event points the visitor is called. An appropriate visitor can then compute distances and shortest paths.

Methods TreeEdge(v, target) and DiscoverVertex(target) are called before the search stops. If the target is not reachable from the source, it is equivalent to BreadthFisrtVisit.

func BreadthFirstVisit 

func BreadthFirstVisit(g Forward, vis BfsVisitor, source string)

BreadthFirstVisit visits a graph starting from the source vertex and visiting closer vertices first.

The slice returned by calls to NextVertices is never modified. So there is no risk of accidentally modifying g.

At some event points the visitor is called. An appropriate visitor can then compute distances and shortest paths.

Example 
package main

import (
	"fmt"

	"github.com/batiazinga/graph"
	"github.com/batiazinga/graph/visitor"
)

// digraph is a directed graph implementing the Forward interface.
type digraph map[string][]string

func (g digraph) NextVertices(v string) []string { return g[v] }

// bfsVisitorDistance computes the distance between the source and any reachable vertex.
// The distance between two adjacent vertices is one.
//
// Beware that distance from source vertex to non-reachable vertices is zero with this visitor.
type bfsVisitorDistance struct {
	visitor.BfsNoOp // bfsVisitorDistance implement BfsVisitor

	// map storing the distance between the source and other vertices
	// it should initially be empty
	distance map[string]int
}

func (vis *bfsVisitorDistance) TreeEdge(from, to string) {
	vis.distance[to] = vis.distance[from] + 1
}

func main() {
	// create the following digraph
	// A -> B -> D
	//   \-> C -- \-> E
	g := digraph{
		"A": []string{"B", "C"},
		"B": []string{"D"},
		"C": []string{"E"},
		"D": []string{"E"},
	}

	// create a distance visitor
	vis := &bfsVisitorDistance{
		BfsNoOp:  visitor.BfsNoOp{},
		distance: make(map[string]int),
	}

	// Run the breadth-first visit
	graph.BreadthFirstVisit(g, vis, "A")

	// read results
	fmt.Println("A", vis.distance["A"])
	fmt.Println("B", vis.distance["B"])
	fmt.Println("C", vis.distance["C"])
	fmt.Println("D", vis.distance["D"])
	fmt.Println("E", vis.distance["E"])

}

Output:

A 0
B 1
C 1
D 2
E 2

func DepthFirstVisit 

func DepthFirstVisit(g VertexListForward, vis DfsVisitor)

DepthFirstVisit is similar to DepthFirstVisitFrom but it visits the whole graph. It needs a graph whose vertices can be listed.

The slices returned by calls to NextVertices and Vertices are never modified. So there is no risk of accidentally modifying g.

Example 
package main

import (
	"fmt"
	"sort"

	"github.com/batiazinga/graph"
	"github.com/batiazinga/graph/visitor"
)

// vertexListDAG is a directed graph implementing the VertexListForward interface.
type vertexListDAG map[string][]string

func (g vertexListDAG) NextVertices(v string) []string {
	// deterministic order to make the visit deterministic
	return g[v]
}

func (g vertexListDAG) Vertices() []string {
	vertices := make([]string, 0, len(g))
	for v := range g {
		vertices = append(vertices, v)
	}
	// sort to make order deterministic
	// the visit can then be deterministic
	sort.Strings(vertices)
	return vertices
}

// toposortVisitor computes a topological ordering of a graph.
// It is a DfsVisitor
type toposortVisitor struct {
	visitor.DfsNoOp // toposortVisitor implement BfsVisitor

	// reverse topological order
	order []string
}

func (vis *toposortVisitor) FinishVertex(v string) {
	vis.order = append(vis.order, v)
}

func main() {
	g := vertexListDAG{
		"A": []string{"B", "C"},
		"B": []string{"D", "E"},
		"C": []string{"E"},
		"D": []string{"E"},
		"E": nil,
		"F": []string{"B"},
	}

	// create a distance visitor
	vis := &toposortVisitor{
		DfsNoOp: visitor.DfsNoOp{},
	}

	// Run the breadth-first visit
	graph.DepthFirstVisit(g, vis)

	// read results
	for _, v := range vis.order {
		fmt.Println(v)
	}

}

Output:

E
D
B
C
A
F

func DepthFirstVisitFrom 

func DepthFirstVisitFrom(g Forward, vis DfsVisitor, source string)

DepthFirstVisitFrom performs a depth-first-search from the source vertex. When possible, it chooses a vertex adjacent to the current vertex to visit next. Otherwise it backtracks to the last vertex with unvisited adjacent vertices.

The slice returned by calls to NextVertices is never modified. So there is no risk of accidentally modifying g.

At some event points the visitor is called.

func Dijkstra 

func Dijkstra(g WeightForward, vis DijkstraVisitor, source string)

Dijkstra visits the graph in Dijkstra order, i.e. closest vertices first. It stops when all vertices reachable from the source have been visited.

Shortest paths and distances can be computed thanks to an appropriate visitor.

It works for both undirected and directed graphs with non-negative distances and is non destructive.

The slice returned by calls to NextVertices is never modified. So there is no risk of accidentally modifying g.

If all weights are equal to one, use breadth-first-search with the appropriate visitor instead.

func DijkstraTo 

func DijkstraTo(g WeightForward, vis DijkstraVisitor, source, target string)

DijkstraTo is similar to Dijkstra except that it stops when the target vertex has been reached. If the target vertex is not-reachable from the source, it behaves exactly as Dijkstra.

Example 
package main

import (
	"fmt"
	"sort"

	"github.com/batiazinga/graph"
	"github.com/batiazinga/graph/visitor"
)

// distanceGraph is an undirected graph implementing the WeightForward interface.
type distanceGraph struct {
	next     map[string][]string
	distance map[string]float64
}

func (g distanceGraph) NextVertices(v string) []string { return g.next[v] }
func (g distanceGraph) Weight(v, w string) float64 {
	sorted := []string{v, w}
	sort.Strings(sorted)
	return g.distance[sorted[0]+"-"+sorted[1]]
}

// dijkstraVisitorPath computes the path between the source and a target vertex.
type dijkstraVisitorPath struct {
	visitor.DijkstraNoOp // dijkstraVisitorPath implement DijkstraVisitor

	// information to build a path:
	// predecessor map and target
	pred map[string]string
}

func (vis *dijkstraVisitorPath) EdgeRelaxed(from, to string) {
	vis.pred[to] = from
}

func (vis *dijkstraVisitorPath) path(source, target string) (p []string) {
	// init search
	v := target
	pred, found := vis.pred[v]
	if !found {
		return // did not reach target
	}
	p = append(p, v)

	// loop as long as v is in the map (source is not in the map)
	for found {
		v = pred
		pred, found = vis.pred[v]
		p = append(p, v)
	}

	// reverse path
	last := len(p) - 1
	for i := 0; i < len(p)/2; i++ {
		p[i], p[last-i] = p[last-i], p[i]
	}

	return
}

func main() {
	// create the following graph
	// A -0.1- B -0.2- D -0.1-
	//   \---0.6--- C ---0.3-- \-> E
	g := distanceGraph{
		// make it undirected!
		next: map[string][]string{
			"A": []string{"B", "C"},
			"B": []string{"A", "D"},
			"C": []string{"A", "E"},
			"D": []string{"B", "E"},
			"E": []string{"C", "D"},
		},
		distance: map[string]float64{
			"A-B": 0.1,
			"B-D": 0.2,
			"D-E": 0.1,
			"A-C": 0.6,
			"C-E": 0.3,
		},
	}

	// create a path visitor
	vis := &dijkstraVisitorPath{
		DijkstraNoOp: visitor.DijkstraNoOp{},
		pred:         make(map[string]string),
	}

	// run the dikstra visit
	graph.DijkstraTo(g, vis, "A", "E")

	// read results
	path := vis.path("A", "E")
	var distance float64
	for i := 0; i < len(path)-1; i++ {
		distance += g.Weight(path[i], path[i+1])
	}
	fmt.Printf("Distance from A to E is 0.4: %v\n", distance > 0.39 && distance < 0.41)
	fmt.Printf("Path from A to E is %v", path)

}

Output:

Distance from A to E is 0.4: true
Path from A to E is [A B D E]

Types

type BfsVisitor 

type BfsVisitor interface {
	// DiscoverVertex is called when a new vertex is found.
	DiscoverVertex(v string)

	// ExamineVertex is called when a vertex is dequeued.
	ExamineVertex(v string)

	// ExamineEdge is called when navigating through the edge.
	ExamineEdge(from, to string)

	// TreeEdge is called when navigating to a new vertex.
	// This edge is then an edge of the minimum spanning tree
	// (where the distance between two neighbour vertices is one).
	TreeEdge(from, to string)

	// NonTreeEdge is called when navigating to an already discovered vertex.
	NonTreeEdge(from, to string)

	// GrayTarget is called when the vertex we are navigating to has already been discovered
	// but has not been examined yet.
	GrayTarget(from, to string)

	// BlackTarget is called when the vertex we are navigating to has already been examined.
	BlackTarget(from, to string)

	// FinishVertex is called when a vertex has been examined.
	FinishVertex(v string)
}

BfsVisitor is the visitor to be passed to BreadthFirstVisit graph traversal function.

type DfsVisitor 

type DfsVisitor interface {
	// InitializeVertex is called for each vertex before the visit starts.
	// It is called only for DepthFirstVisit.
	InitializeVertex(v string)

	// DiscoverVertex is called when a new vertex if found.
	DiscoverVertex(v string)

	// ExamineEdge is called when navigating through the edge.
	ExamineEdge(from, to string)

	// TreeEdge is called when navigating to a new vertex.
	// This edge is then an edge of the search tree.
	TreeEdge(from, to string)

	// BackEdge is called when a visited but unfinished vertex is found.
	// On an undirected graph this is called for each tree edge.
	BackEdge(from, to string)

	// ForwardCrossEdge is called when a finished vertex is found.
	// This is never called on an undirected graph.
	ForwardCrossEdge(from, to string)

	// FinishVertex is called when all out edges have been added to the search tree
	// and all corresponding adjacent vertices are finished.
	FinishVertex(v string)
}

DfsVisitor is the visitor to be passed to DepthFirstVisit graph traversal function.

type DijkstraVisitor 

type DijkstraVisitor interface {
	// DiscoverVertex is called when a new vertex is found.
	DiscoverVertex(v string)

	// ExamineVertex is called when a vertex is dequeued.
	ExamineVertex(v string)

	// ExamineEdge is called when navigating through the edge.
	ExamineEdge(from, to string)

	// EdgeRelaced is called when a shorter path to vertex 'to' is found
	// or if it was just discovered.
	EdgeRelaxed(from, to string)

	// EdgeNotRelaxed is called when a longer path to vertex 'to' is found.
	EdgeNotRelaxed(from, to string)

	// FinishVertex is called when a vertex has been examined.
	FinishVertex(v string)
}

DijkstraVisitor is the visitor to be passed to Dijkstra functions.

type Forward 

type Forward interface {
	// NextVertices returns the list of vertices reachable when leaving the vertex v.
	NextVertices(v string) []string
}

Forward is the interface allowing to navigate forward in a graph. The graph can be directed or undirected.

type VertexListForward 

type VertexListForward interface {
	Forward

	// Vertices returns the list of vertices of the graph.
	Vertices() []string
}

VertexListForward is a Forward graph whose vertices can be listed.

type WeightForward 

type WeightForward interface {
	Forward

	// Weight return the weight of the edge.
	Weight(from, to string) float64
}

WeightForward is a Forward graph with float64 weights on its edges.

Source Files

View all Source files

Directories

Path Synopsis
Package visitor provides visitors to use with graph algorithms.
 Package visitor provides visitors to use with graph algorithms.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.