graph

Documentation

Index

• func VertexID(v Vertex) interface{}
• func VertexName(v Vertex) string
• type DFSFunc
• type Graph
  • func (g *Graph) Add(v Vertex) Vertex
  • func (g *Graph) AddEdge(v1, v2 Vertex)
  • func (g *Graph) AddEdgeWeighted(v1, v2 Vertex, weight int)
  • func (g *Graph) AddOverwrite(v Vertex) Vertex
  • func (g *Graph) Copy() *Graph
  • func (g *Graph) Cycles() [][]Vertex
  • func (g *Graph) DFS(start Vertex, cb DFSFunc) error
  • func (g *Graph) Dijkstra(src Vertex) (distTo map[interface{}]int, edgeTo map[interface{}]Vertex)
  • func (g *Graph) EdgeToPath(target Vertex, edgeTo map[interface{}]Vertex) []Vertex
  • func (g *Graph) InEdges(v Vertex) []Vertex
  • func (g *Graph) KahnSort() TopoOrder
  • func (g *Graph) OutEdges(v Vertex) []Vertex
  • func (g *Graph) Remove(v Vertex) Vertex
  • func (g *Graph) RemoveEdge(v1, v2 Vertex)
  • func (g *Graph) Reverse() *Graph
  • func (g *Graph) String() string
  • func (g *Graph) StronglyConnected() [][]Vertex
  • func (g *Graph) TopoShortestPath(L TopoOrder) (distTo map[interface{}]int, edgeTo map[interface{}]Vertex)
  • func (g *Graph) Vertex(id interface{}) Vertex
  • func (g *Graph) Vertices() []Vertex
• type TopoOrder
  • func (t TopoOrder) At(v Vertex) TopoOrder
  • func (t TopoOrder) Until(v Vertex) TopoOrder
• type Vertex
• type VertexHashable

Functions

func VertexID

func VertexID(v Vertex) interface{}

VertexID returns the unique ID for a vertex.

func VertexName

func VertexName(v Vertex) string

VertexName returns the name of a vertex.

Types

type DFSFunc

type DFSFunc func(Vertex, func() error) error

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph represents a graph structure.

Unless otherwise documented, it is unsafe to call any method on Graph concurrently.

func (*Graph) Add

func (g *Graph) Add(v Vertex) Vertex

Add adds a vertex to the graph. If a vertex with the same identity exists this will overwrite that vertex.

func (*Graph) AddEdge

func (g *Graph) AddEdge(v1, v2 Vertex)

AddEdge adds a directed edge to the graph from v1 to v2. Both v1 and v2 must already be in the Graph via Add or this will do nothing.

func (*Graph) AddEdgeWeighted

func (g *Graph) AddEdgeWeighted(v1, v2 Vertex, weight int)

AddEdgeWeighted adds a weighted edge. This is the same as AddEdge but with the specified weight. This will overwrite any existing edges.

func (*Graph) AddOverwrite

func (g *Graph) AddOverwrite(v Vertex) Vertex

AddOverwrite is the same as Add, except that even if the vertex already exists with the same hashcode, the pointed to value is replaced with the given v. This allows two Vertex values with the same hashcode but different values to be replaced.

func (*Graph) Copy

func (g *Graph) Copy() *Graph

Copy copies the graph. In the copy, any added or removed edges do not affect the original graph. The vertices themselves are not deep copied.

func (*Graph) Cycles

func (g *Graph) Cycles() [][]Vertex

Cycles returns all the detected cycles. This may not be fully exhaustive since we use Tarjan's algoritm for strongly connected components to detect cycles and this isn't guaranteed to find all cycles.

func (*Graph) DFS

func (g *Graph) DFS(start Vertex, cb DFSFunc) error

func (*Graph) Dijkstra

func (g *Graph) Dijkstra(src Vertex) (distTo map[interface{}]int, edgeTo map[interface{}]Vertex)

Dijkstra implements Dijkstra's algorithm for finding single source shortest paths in an edge-weighted graph with non-negative edge weights. The graph may have cycles.

func (*Graph) EdgeToPath

func (g *Graph) EdgeToPath(target Vertex, edgeTo map[interface{}]Vertex) []Vertex

EdgeToPath turns an "edge to" mapping into a vertex slice of the path from some target.

func (*Graph) InEdges

func (g *Graph) InEdges(v Vertex) []Vertex

func (*Graph) KahnSort

func (g *Graph) KahnSort() TopoOrder

KahnSort will return the topological sort of the graph using Kahn's algorithm. The graph must not have any cycles or this will panic.

func (*Graph) OutEdges

func (g *Graph) OutEdges(v Vertex) []Vertex

func (*Graph) Remove

func (g *Graph) Remove(v Vertex) Vertex

Remove removes the given vertex from the graph.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(v1, v2 Vertex)

func (*Graph) Reverse

func (g *Graph) Reverse() *Graph

Reverse reverses the graph but _does not make a copy_. Any changes to this graph will impact the original Graph. You must call Copy on the result if you want to have a copy.

func (*Graph) String

func (g *Graph) String() string

String outputs some human-friendly output for the graph structure.

func (*Graph) StronglyConnected

func (g *Graph) StronglyConnected() [][]Vertex

StronglyConnected returns the list of strongly connected components within the Graph g.

func (*Graph) TopoShortestPath

func (g *Graph) TopoShortestPath(L TopoOrder) (distTo map[interface{}]int, edgeTo map[interface{}]Vertex)

TopoShortestPath returns the shortest path information given the topological sort of the graph L. L can be retrieved using any topological sort algorithm such as KahnSort.

The return value are two maps with the distance to and edge to information, respectively. distTo maps the total distance from source to the given vertex. edgeTo maps the previous edge to get to a vertex from source.

func (*Graph) Vertex

func (g *Graph) Vertex(id interface{}) Vertex

Vertex returns the vertex by id. This can be done to get the node that is actually in the graph. This will return nil if the given vertex is not in the graph any longer.

func (*Graph) Vertices

func (g *Graph) Vertices() []Vertex

Vertices returns the list of all the vertices in this graph.

type TopoOrder

type TopoOrder []Vertex

TopoOrder is a topological ordering.

func (TopoOrder) At

func (t TopoOrder) At(v Vertex) TopoOrder

At returns a new TopoOrder that starts at the given vertex. This returns a slice into the ordering so it is not safe to modify.

func (TopoOrder) Until

func (t TopoOrder) Until(v Vertex) TopoOrder

Until returns a new TopoOrder that ends at (and includes) the given vertex. This returns a slice into the ordering so it is not safe to modify.

type Vertex

type Vertex interface{}

Vertex can be anything.

type VertexHashable

type VertexHashable interface {
	Hashcode() interface{}
}

VertexHashable is an optional interface that can be implemented to specify an alternate hash code for a Vertex. If this isnt implemented, Go interface equality is used.