graph

Documentation

Overview

Package graph provides a flexible graph implementation and related primitives.

Index

• Variables
• type Edge
  • func (e *Edge) String() string
• type EdgeFilterFunc
• type EdgeVisitorFunc
• type FindPathFunc
• type FindPathsFunc
• type Graph
  • func New() *Graph
  • func NewUndirected() *Graph
  • func (g *Graph) AddEdge(from Key, to Key) bool
  • func (g *Graph) AddEdgeCost(from Key, to Key, cost int) bool
  • func (g *Graph) AddVertex(value interface{}) Key
  • func (g *Graph) DeleteEdge(from Key, to Key)
  • func (g *Graph) DeleteVertex(key Key)
  • func (g *Graph) FilterEdges(filter EdgeFilterFunc) *Graph
  • func (g *Graph) FilterVertices(filter VertexFilterFunc) *Graph
  • func (g *Graph) FindPath(algo FindPathFunc, from Key, to Key) Path
  • func (g *Graph) FindPaths(algo FindPathsFunc, from Key, to Key) Paths
  • func (g *Graph) Get(key Key) (Vertex, bool)
  • func (g *Graph) Order() int
  • func (g *Graph) String() string
  • func (g *Graph) VisitEdges(key Key, fn EdgeVisitorFunc)
  • func (g *Graph) VisitVertices(key Key, fn VertexVisitorFunc)
• type Key
  • func (k Key) String() string
• type Path
  • func Dijkstra(g *Graph, from Key, to Key) Path
• type Paths
• type Vertex
  • func (v *Vertex) Key() Key
  • func (v *Vertex) String() string
  • func (v *Vertex) Value() interface{}
• type VertexFilterFunc
• type VertexVisitorFunc

Variables

var (
	// Any TODOC
	Any = Key{/* contains filtered or unexported fields */}
	// Root is a default key for specifying graph iteration and/or filtering.
	Root = Key{/* contains filtered or unexported fields */}
)

Types

type Edge

type Edge struct {
	Start Vertex
	End   Vertex
	Cost  int
}

Edge is a connection between two incident vertices in a graph. An edge is always directed, but for undirected graphs, can be assumed to be invertable with the same cost.

func (*Edge) String

func (e *Edge) String() string

String returns a string representation of e.

type EdgeFilterFunc

type EdgeFilterFunc = func(Edge) bool

EdgeFilterFunc is used by Graph as a predicate function to filter its edges.

type EdgeVisitorFunc

type EdgeVisitorFunc = func(Edge) bool

EdgeVisitorFunc is used by Graph to yield visited edges to callers.

type FindPathFunc

type FindPathFunc = func(graph *Graph, from Key, to Key) Path

FindPathFunc is used by Graph do perform pluggable pathing/costing for a single path.

type FindPathsFunc

type FindPathsFunc = func(graph *Graph, from Key, to Key) Paths

FindPathsFunc is used by Graph to perform pluggable pathing/costing for multiple paths.

type Graph

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

A Graph is a basic data structure defined as a set of vertices and a set of edges. Graphs may be either directed or undirected.

func New

func New() *Graph

New constructs a new directed graph.

func NewUndirected

func NewUndirected() *Graph

NewUndirected constructs a new undirected graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(from Key, to Key) bool

AddEdge adds a new directed edge to the graph, spanning the vertices from and to. If the graph is undirected, a second edge is added implicitly in the reverse direction. Edges added with AddEdge have an implicit cost of 1.

func (*Graph) AddEdgeCost

func (g *Graph) AddEdgeCost(from Key, to Key, cost int) bool

AddEdgeCost behaves identically to AddEdge except using the provided cost.

func (*Graph) AddVertex

func (g *Graph) AddVertex(value interface{}) Key

AddVertex adds a new vertex containing value to the graph and returns its corresponding Key for subsequent lookup.

func (*Graph) DeleteEdge

func (g *Graph) DeleteEdge(from Key, to Key)

DeleteEdge deletes the edge spanning vertices from and to, if such an edge exists. If the graph is undirected, the reverse edge will also be deleted.

func (*Graph) DeleteVertex

func (g *Graph) DeleteVertex(key Key)

DeleteVertex deletes the vertex represented by key, if it exists.

Importantly, deleting a vertex will also delete adjacent edges, potentially fragmenting the underlying graph or isolating vertices.

func (*Graph) FilterEdges

func (g *Graph) FilterEdges(filter EdgeFilterFunc) *Graph

FilterEdges returns a copy of g, filtering the edges of g based on the provided predicate filter: for a given edge e, if filter(e) returns true, e remains part of g; if filter(e) returns false, however, e is removed from g.

A critical difference between FilterVertices and FilterEdges is that the former will prune edges (there is no such thing as non-incident/adjacent edges) whereas the latter will remove only edges (potentially introducing disjoint/multi-part sub-graphs or vertex isolation).

func (*Graph) FilterVertices

func (g *Graph) FilterVertices(filter VertexFilterFunc) *Graph

FilterVertices returns a copy of g, filtering the vertices of g based on the provided predicate filter: for a given vertex v, if filter(v) returns true, v remains part of g; if filter(v) returns false, however, v - as well as any edges referencing v - are removed from g.

It is possible for filters to create disjoint (multi-part) sub-graphs, or to introduce vertex isolation.

func (*Graph) FindPath

func (g *Graph) FindPath(algo FindPathFunc, from Key, to Key) Path

FindPath uses algo to find a path spanning vertices from and to.

func (*Graph) FindPaths

func (g *Graph) FindPaths(algo FindPathsFunc, from Key, to Key) Paths

FindPaths uses algo to find paths spanning vertices from and to. The number and order of paths is determined by algo.

func (*Graph) Get

func (g *Graph) Get(key Key) (Vertex, bool)

Get gets the Vertex represented by key, if it exists.

func (*Graph) Order

func (g *Graph) Order() int

Order returns the order of the graph (the number of vertices).

func (*Graph) String

func (g *Graph) String() string

String provides a string representation of the graph.

func (*Graph) VisitEdges

func (g *Graph) VisitEdges(key Key, fn EdgeVisitorFunc)

VisitEdges uses fn to visit each edge, starting at the vertex key.

func (*Graph) VisitVertices

func (g *Graph) VisitVertices(key Key, fn VertexVisitorFunc)

VisitVertices uses fn to visit each vertex, starting at the vertex key.

type Key

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

Key is a thin identifier for graph vertices.

func (Key) String

func (k Key) String() string

type Path

type Path struct {
	Cost     int
	Vertices []Key
}

A Path is a costed sequence of vertices, where cost is equal to the sum of edge costs used to construct the path.

func Dijkstra

func Dijkstra(g *Graph, from Key, to Key) Path

Dijkstra evaluates paths in g spanning from and to and returns the cheapest path possible within the graph.

type Paths

type Paths = []Path

Paths is an ordered collection of paths.

type Vertex

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

Vertex is a point node in a graph.

func (*Vertex) Key

func (v *Vertex) Key() Key

Key provides the key for v.

func (*Vertex) String

func (v *Vertex) String() string

String returns a string representation of v.

func (*Vertex) Value

func (v *Vertex) Value() interface{}

Value returns the value held in v.

type VertexFilterFunc

type VertexFilterFunc = func(Vertex) bool

VertexFilterFunc is used by Graph as a predicate function to filter its vertices.

type VertexVisitorFunc

type VertexVisitorFunc = func(Vertex) bool

VertexVisitorFunc is used by Graph to yield visited vertices to callers.