# graph

package
v0.0.0-...-544ef16 Latest Latest

Go to latest
Published: Jun 14, 2022 License: MIT

## Documentation ¶

### Constants ¶

View Source
`const UnweightedCost = 0`

UnweightedCost represents the cost of an unweighted edge

### Variables ¶

View Source
`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 (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 (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 (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 (g *Graph) AddVertex(name string) *Vertex`

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

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

#### 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
// 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 (v *Vertex) AddEdge(to *Vertex, cost int)`

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

`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.