graph

Documentation

Index

• Constants
• Variables
• func BFS(g *Graph, v *Vertex, f func(v *Vertex))
• func DFS(g *Graph, v *Vertex, f func(v *Vertex))
• func RecursiveDFS(g *Graph, v *Vertex, f func(v *Vertex))
• type Color
• type Edge
• type Graph
  • func DAG() *Graph
  • func Directed(disconnected bool) *Graph
  • func New() *Graph
  • func WithCycle() *Graph
  • func (g *Graph) AddEdge(fromName, toName string, cost int)
  • func (g *Graph) AddEdges(fromName string, toNames []string, costs []int)
  • func (g *Graph) AddUnweightedEdge(fromName, toName string)
  • func (g *Graph) AddVertex(name string) *Vertex
  • func (g *Graph) AddVertices(names []string)
  • func (g *Graph) ClassicDijkstra(start *Vertex)
  • func (g *Graph) FrontierDijkstra(start *Vertex)
  • func (g *Graph) Prim(root *Vertex)
  • func (g *Graph) ToString() string
  • func (g *Graph) Vertex(name string) *Vertex
  • func (g *Graph) VertexCount() int
• type PathVertices
  • func (v PathVertices) Len() int
  • func (v PathVertices) Less(i, j int) bool
  • func (v *PathVertices) Pop() interface{}
  • func (v *PathVertices) Push(x interface{})
  • func (v PathVertices) Swap(i, j int)
• type Vertex
  • func TopoSort(g *Graph) (vertices []*Vertex, acyclic bool)
  • func (v *Vertex) AddEdge(to *Vertex, cost int)
  • func (v *Vertex) AddUnweightedEdge(to *Vertex)
  • func (v *Vertex) ToString(sb *strings.Builder)

Constants

const UnweightedCost = 0

UnweightedCost represents the cost of an unweighted edge

Variables

var NamedVertices = []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"}

NamedVertices contains example named vertices

Functions

func BFS

func BFS(g *Graph, v *Vertex, f func(v *Vertex))

BFS implements a non-recursive breadth-first search on graph g, starting at vertex v, calling f(v) on each visited vertex. O(E + V)

func DFS

func DFS(g *Graph, v *Vertex, f func(v *Vertex))

DFS implements a non-recursive depth-first search on graph g, starting at vertex v, calling f(v) on each visited vertex. O(E + V)

func RecursiveDFS

func RecursiveDFS(g *Graph, v *Vertex, f func(v *Vertex))

RecursiveDFS implements a recursive depth-first search on graph g, starting at vertex v, calling f(v) on each visited vertex. O(E + V)

Types

type Color

type Color int

Color defines the state ("colour") of a given vertex, e.g. black, grey, white or simply visited, unvisited, depending on the use case.

const (
	Black Color = iota
	Gray
	White
	Red
	Blue
	Visited
	Unvisited
)

The vertex colours.

type Edge

type Edge struct {
	To   *Vertex
	Cost int
}

Edge represents a directed connection between a vertex to another To vertex, associated with Cost.

type Graph

type Graph struct {
	Vertices map[string]*Vertex
}

Graph represents a directed graph with weighted (cost) edges

func DAG

func DAG() *Graph

DAG returns a weighted (random costs) directed acyclic graph.

func Directed

func Directed(disconnected bool) *Graph

Directed returns a directed graph (with possible cycles)

func New

func New() *Graph

New creates and initialises a new empty graph.

func WithCycle

func WithCycle() *Graph

WithCycle returns a graph with a simple cycle

func (*Graph) AddEdge

func (g *Graph) AddEdge(fromName, toName string, cost int)

AddEdge adds an edge with cost, connecting named vertices fromName and toName. No edge is added if either vertex does not exist.

func (*Graph) AddEdges

func (g *Graph) AddEdges(fromName string, toNames []string, costs []int)

AddEdges adds multiple edge with costs, connecting named vertices fromName and toName. No edge is added if either vertex does not exist.

func (*Graph) AddUnweightedEdge

func (g *Graph) AddUnweightedEdge(fromName, toName string)

AddUnweightedEdge adds an unweighted edge (with cost=0), connecting named vertices fromName and toName. No edge is added if either vertex does not exist.

func (*Graph) AddVertex

func (g *Graph) AddVertex(name string) *Vertex

AddVertex creates and adds a named vertex, and returns it. Color is set to unvisited.

func (*Graph) AddVertices

func (g *Graph) AddVertices(names []string)

AddVertices creates and adds named vertices.

func (*Graph) ClassicDijkstra

func (g *Graph) ClassicDijkstra(start *Vertex)

ClassicDijkstra calculates all the shortest paths, starting from start vertex to any other connected vertex. Costs must all be non-negative.

The "classic" implementation is derived from an "Introduction to Algorithms" and builds the heap up front, with all graph vertices. That is, no "is element of" check is hence necessary (but that check can be easily implemented in O(1) time).

Assuming that the implementation of Golang heap is a binary heap the runtime is hence O((V + E)log V). With a Fibonacci heap which supports decreaseKey in amortised O(1) the total runtime would only be O(V log V + E).

func (*Graph) FrontierDijkstra

func (g *Graph) FrontierDijkstra(start *Vertex)

FrontierDijkstra calculates the shortest paths like the above ClassicDijkstra, except that the heap - the "frontier" of newly discovered vertices - is extended as we go. This requires an efficient "find" ("member of") implementation, but which is easily implemented in O(1) by setting the index flag from its initial notInHeap value ("not member of") to a valid index [0, V[ ("member of").

func (*Graph) Prim

func (g *Graph) Prim(root *Vertex)

Prim calculates the minimum spanning tree.

func (*Graph) ToString

func (g *Graph) ToString() string

ToString returns a textual represenation of this graph.

func (*Graph) Vertex

func (g *Graph) Vertex(name string) *Vertex

Vertex returns the named vertex. If not exist then nil is returned

func (*Graph) VertexCount

func (g *Graph) VertexCount() int

VertexCount returns the number of vertices in this graph

type PathVertices

type PathVertices []*Vertex

PathVertices represent (shortest) paths in the graph

func (PathVertices) Len

func (v PathVertices) Len() int

Len returns the count of all vertices.

func (PathVertices) Less

func (v PathVertices) Less(i, j int) bool

Less returns true if element with index i is less than element with index j, by comparing the vertex distances.

func (*PathVertices) Pop

func (v *PathVertices) Pop() interface{}

Pop removes and returns the last vertex

func (*PathVertices) Push

func (v *PathVertices) Push(x interface{})

Push appends x, which must be of type pointer to a vertex (*Vertex).

func (PathVertices) Swap

func (v PathVertices) Swap(i, j int)

Swap swaps element i and j.

type Vertex

type Vertex struct {
	Name      string
	Color     Color
	Adjacency []*Edge
	// contains filtered or unexported fields
}

Vertex represents a vertex in a graph

func TopoSort

func TopoSort(g *Graph) (vertices []*Vertex, acyclic bool)

TopoSort returns a topologically sorted order of the vertices in the graph. The boolean acyclic is true if no circle has been detected, otherwise sorted contains the vertices which form a closed circle (and acyclic is false). Running time: O(E + V)

func (*Vertex) AddEdge

func (v *Vertex) AddEdge(to *Vertex, cost int)

AddEdge adds an edge with cost to this vertex, connecting with the to vertex.

func (*Vertex) AddUnweightedEdge

func (v *Vertex) AddUnweightedEdge(to *Vertex)

AddUnweightedEdge adds an unweighted edge (with cost=0) to this vertex, connecting with the to vertex.

func (*Vertex) ToString

func (v *Vertex) ToString(sb *strings.Builder)

ToString adds a textual represenation of this vertex to sb.