graph

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.

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.