algo

Documentation

Overview

Package algo implements graph algorithms using the data structures from the 'ds' package. Any assertions regarding asymptotic behavior assume the worst-case scenario.

Index

• func DFS(g *ds.G, classify bool) (DFForest, EdgeTypes, error)
• func TSort(g *ds.G) ([]int, error)
• type BFNode
• type BFTree
  • func BFS(g *ds.G, src int) (BFTree, error)
• type CC
  • func CCDFS(g *ds.G) ([]CC, error)
  • func CCUnionFind(g *ds.G) ([]CC, error)
• type CCAlgo
• type DFForest
• type DFNode
• type EdgeTypes
• type MST
  • func MSTKruskal(g *ds.G) (MST, error)
  • func MSTPrim(g *ds.G) (MST, error)
• type MSTAlgo
• type SCC
  • func GSCC(g *ds.G) (*ds.G, []SCC, error)
  • func SCCKosaraju(g *ds.G) ([]SCC, error)
  • func SCCTarjan(g *ds.G) ([]SCC, error)
• type SCCAlgo

Functions

func DFS

func DFS(g *ds.G, classify bool) (DFForest, EdgeTypes, error)

DFS implements the Depth-First Search (DFS) algorithm.

Given a graph, DFS eventually explores every vertex, building a DF forest that holds DF trees. The search is conducted using a depth-first approach: given a vertex, one adjacent vertex and all of its descendants need to be fully explored before the next adjacent vertex (and all of its descendants) can be explored. After all of its adjacent vertices are explored, then a vertex can be marked as fully explored.

During its execution, DFS will record and assign both discovery and finish times to each vertex, which can later be used to infer ancestor/descendant relationships between vertices in the forest.

Certain implementations of DFS (like this one) can also classify edges (in addition to tree edges) according to the DF forest generated by the algorithm:

• Forward Edges: Connect an ancestor to a descendant in the same tree.
• Back Edges: Connect a descendant to an ancestor in the same tree.
• Cross Edges: Either connect vertices in different trees, or non ancestor/descendant vertices in the same tree.

Expectations:

• The graph is correctly built.

Complexity:

• Time: Θ(V + E)
• Space (without edge classification): Θ(V)
• Space (wit edge classification): Θ(V) + O(E)

func TSort

func TSort(g *ds.G) ([]int, error)

TSort implements an algorithm for Topological Sorting.

Given a directed graph, TSort eventually produces an ordering of the vertices in the original graph such that, for every edge (u,v) vertex u appears before vertex v in the final ordering.

This algorithm is a simplified version of a DFS, with the addition of a linked list that stores the ordering of the vertices, which is appended to - at the head - after each vertex is fully explored.

Expectations:

• The graph is correctly built.
• The graph is directed.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

Types

type BFNode

type BFNode struct {
	/*
		Distance is the length of the shortest path (edge count), from the source to this vertex.
		If the vertex is unreachable from the source, this value will be math.Inf(1).
	*/
	Distance float64

	/*
		Parent holds the vertex that discovered this vertex, with the edge (v.Parent, v) being called a tree edge.
		This is how the BF tree is encoded: by following the parent pointers from any reachable vertex back to
		the source, one can generate a shortest path from the source to the vertex.

		After a BFS, both the source and all unreachable vertices have a nil Parent.
	*/
	Parent int
	// contains filtered or unexported fields
}

A BFNode represents a node in a Breadth-First tree, holding the attributes produced by a BFS, for a particular vertex. At the end of the BFS, nodes with a distance < infinity are a part of a BF tree, rooted at the source vertex.

type BFTree

type BFTree []BFNode

A BFTree (Breadth-First Tree) is the result of a BFS, representing a tree (connected acyclic subgraph) rooted at the source, and containing every vertex that is reachable from the source. A BF tree encodes both the length of the shortest path between the source and each reachable vertex (Distance) and the path itself (Parent pointer).

Slightly different trees can be generated for the same graph and source, if the visiting order for either vertices or edges is changed, but the optimal distances are guaranteed to remain the same.

The gga graph implementation guarantees both vertex and edge traversal in insertion order, so repeated BFS calls always produce the same BF tree.

func BFS

func BFS(g *ds.G, src int) (BFTree, error)

BFS implements the Breadth-First Search (BFS) algorithm.

Given a graph and a source vertex, BFS explores all vertices that are reachable from the source, with the end result being a Breadth-First tree rooted at the source. The search explores all non-explored vertices at a certain distance d from the source before moving on to the vertices at distance d+1, working in "waves".

Expectations:

• The graph is correctly built.
• The source vertex exists.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

type CC

type CC []int

A CC holds the vertices in a connected component of an undirected graph.

func CCDFS

func CCDFS(g *ds.G) ([]CC, error)

CCDFS implements an algorithm for finding the connected components of an undirected graph by using a single DFS that returns each DF tree in the DF forest as a connected component.

The DFS approach is better suited for static graphs: when the sets of vertices and edges do not change over time. In this scenario, CCDFS has an asymptotically better time complexity (linear) than the disjoint-set implementation, CCUnionFind (superlinear).

However, if the graph is dynamic, CCUnionFind will do a better job over time, since CCDFS would need to be executed every time the graph changes - Θ(V + E) -, while CCUnionFind would only need to be executed once - O((V + E) α(V)), amortized -, and its disjoint-set data structure would need to be updated after every graph change, with each disjoint-set operation taking O(α(V)) amortized time.

Expectations:

• The graph is correctly built.
• The graph is undirected.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

func CCUnionFind

func CCUnionFind(g *ds.G) ([]CC, error)

CCUnionFind implements an algorithm for finding the connected components of an undirected graph by manipulating a disjoint-set data structure while traversing the input graph. One disjoint set is initially created for each vertex, and then for every edge that connects vertices in different disjoint sets, the sets are merged.

The "Union-Find" approach is better suited for dynamic graphs, where the sets of vertices and edges change over time, with the disjoint-set data structure being manipulated to update already calculated connected components - O(α(V)) amortized time per operation -, which makes it possible for the algorithm to be executed only once per graph.

For static graphs, however, CCUnionFind has an asymptotically worse time complexity than CCDFS: CCUnionFind is O((V + E) α(V)), amortized (superlinear), while CCDFS is Θ(V + E) (linear).

Expectations:

• The graph is correctly built.
• The graph is undirected.

Complexity:

• Time: O((V + E) α(V)), amortized
• Space: Θ(V)

type CCAlgo

type CCAlgo func(*ds.G) ([]CC, error)

CCAlgo describes the signature of an algorithm that can discover all connected components in an undirected graph. If such an algorithm is called on a directed graph, the ds.ErrUndefOp error is returned.

type DFForest

type DFForest []DFNode

A DFForest is one of the results of a DFS, representing a forest of DF trees (connected acyclic subgraphs), with each DF tree being composed of all (at the time) unvisited vertices that were reachable from the root of the DF tree, during the execution of the DFS.

Slightly different trees can be generated for the same graph, if the visiting order for either vertices or edges is changed.

The gga graph implementation guarantees both vertex and edge traversal in insertion order, so repeated DFS calls always produce the same DF forest.

type DFNode

type DFNode struct {
	// Discovery records when the vertex was marked as discovered.
	Discovery int

	// Finish records when the vertex was marked as fully explored.
	Finish int

	/*
		Parent holds the vertex that discovered this vertex, with the edge (v.Parent, v) being called a tree edge.
		This is how the DF tree that this vertex is a part of is encoded: by following the parent pointers from
		this vertex, one can get to the root of the DF tree.

		After a DFS, every root of a DF tree in the DF forest will have a nil Parent.
	*/
	Parent int
	// contains filtered or unexported fields
}

A DFNode node represents a node in a Depth-First tree in a Depth-First forest, holding the attributes produced by a DFS, for a particular vertex. At the end of the DFS, every vertex is part of one of the DF trees in the DF forest produced by the algorithm.

type EdgeTypes

type EdgeTypes struct {
	Forward []ds.GE
	Back    []ds.GE
	Cross   []ds.GE
}

EdgeTypes stores edges classified by a graph algorithm.

type MST

type MST []ds.GE

An MST holds the edges of a minimum spanning tree of an undirected graph with weighted edges.

func MSTKruskal

func MSTKruskal(g *ds.G) (MST, error)

MSTKruskal implements Kruskal's algorithm for finding a minimum spanning tree of an undirected graph with weighted edges.

This is a greedy algorithm that applies the greedy-choice property by first sorting all edges of the graph in order of non-decreasing edge weights, and then iterating over the sorted list of edges, always picking the edge of least weight (greedy choice, locally optimal) that connects previously unlinked components. A disjoint-set data structure is used to keep track of the components, and at the end of the algorithm, the list of edges returned forms an MST of the original graph (globally optimal solution).

Expectations:

• The graph is correctly built.
• The graph is undirected.

Complexity:

• Time: O(E log V)
• Space: Θ(V + E).

func MSTPrim

func MSTPrim(g *ds.G) (MST, error)

MSTPrim implements Prim's algorithm for finding a minimum spanning tree of an undirected graph with weighted edges. One extra restriction is that the graph needs to be connected: if not, the algorithm will not find the minimum spanning forest, and an error will be returned.

This is a greedy algorithm that can start from any source vertex (this particular implementation always starts from the first vertex added to the graph) and that expands the current MST subset one vertex at a time, after each iteration.

The greedy-choice property is used by maintaining a min-heap containing every vertex that has not been added to the MST subset, using the lowest known edge weight to reach that vertex from the MST subset as the heap key.

At the start of each iteration, the vertex v with the smallest key is extracted from the heap and added to the MST subset (greedy choice, locally optimal). Then the adjacency list of v is examined, and every vertex u that is still in the heap and whose edge (v, u) has a weight that is smaller than the key of u is updated in the heap, which is then fixed to keep its heap property.

After the heap is emptied, the algorithm is guaranteed to have computed an MST of the original graph (globally optimal solution), but only if the graph is connected.

Expectations:

• The graph is correctly built.
• The graph is undirected.

Complexity:

• Time: O(E log V)
• Space: Θ(V).

type MSTAlgo

type MSTAlgo func(*ds.G) (MST, error)

MSTAlgo describes the signature of an algorithm that can build a minimum spanning tree of an undirected graph with weighted edges. If such an algorithm is called on a directed graph, then ds.ErrUndefOp error is returned.

type SCC

type SCC []int

An SCC holds the vertices in a strongly connected component of a directed graph.

func GSCC

func GSCC(g *ds.G) (*ds.G, []SCC, error)

GSCC implements an algorithm for building a condensation graph GSCC from a directed graph.

A condensation graph is the result of contracting each strongly connected component (SCC) of the original graph to a vertex in the GSCC. Each edge (u, v) in the GSCC exists because there exists at least one edge (x, y) in the original graph such that x is in the SCC u and y is in the SCC v. One important property of the condensation graph GSCC is that it is guaranteed to be a DAG (Directed Acyclic Graph).

Tarjan's SCC algorithm is used to calculate the SCCs because of its side-effect of returning the SCCs in reverse topological order of the GSCC, which means that if the SCC list is traversed in reverse we will never examine an edge connecting the current SCC to an SCC that was examined earlier. In theory, the space required to keep track of possible adjacencies between SCCs is reduced by one after each SCC that is examined, which would not change the worst-case space complexity of this step, O(V), but might end up yielding better constant factors in the end.

Expectations:

• The graph is correctly built.
• The graph is directed.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

func SCCKosaraju

func SCCKosaraju(g *ds.G) ([]SCC, error)

SCCKosaraju implements Kosaraju's algorithm for finding the strongly connected components of a directed graph. A strongly connected component of a graph being a subgraph where every vertex is reachable from every other vertex. Such a subgraph is maximal: no other vertex or edge from the graph can be added to the subgraph without breaking its property of being strongly connected.

Given a directed graph, SCCKosaraju will obtain an ordering of the vertices, in decreasing order of finish time in a DFS. This is implemented as a call to TSort (Topological Sort), even if the final sorting might not be an actual topological sorting (undefined for cyclic graphs), it will still return an ordering of vertices in decreasing order of finish time in a DFS.

A transpose of the original graph is then calculated (same graph with the direction of every edge reversed), and a second DFS is executed on it (TSort being a DFS itself). The second DFS uses the ordering obtained from the Topological Sort to calculate the DF forest of the transpose (the main loop of the DFS will visit the vertices in that order), and each DF tree in the forest will correspond to an SCC of the transpose. Since a graph and its transpose share the same SCCs, after the second DFS, the algorithm will have found the SCCs of the original graph.

Expectations:

• The graph is correctly built.
• The graph is directed.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

func SCCTarjan

func SCCTarjan(g *ds.G) ([]SCC, error)

SCCTarjan implements Tarjan's algorithm for finding the strongly connected components of a directed graph. A strongly connected component of a graph being a subgraph where every vertex is reachable from every other vertex. Such a subgraph is maximal: no other vertex or edge from the graph can be added to the subgraph without breaking its property of being strongly connected.

Given a directed graph, SCCTarjan will keep an auxiliary stack where it pushes vertices as soon as they are first visited during a modified DFS. The vertices are not necessarily popped from the stack after being fully explored, though, with the following invariant always holding:

A vertex remains on the stack after being explored IFF there exists a path from
the vertex to some other vertex earlier on the stack: meaning that a vertex is
only removed from the stack after alls of its connected paths have been traversed.

If after exploring a vertex and all of its descendants, the vertex still has no path to earlier vertices on the stack, then every vertex on the stack is popped until the current vertex is reached (it is included): this set of vertices is an SCC rooted at the vertex.

An important property of Tarjan's algorithm is that the SCCs are discovered in reverse topological order of the condensation graph of the input, which is a DAG obtained by contracting every vertex in a SCC into a single vertex.

Expectations:

• The graph is correctly built.
• The graph is directed.

Complexity:

• Time: Θ(V + E)
• Space: Θ(V)

type SCCAlgo

type SCCAlgo func(*ds.G) ([]SCC, error)

SCCAlgo describes the signature of an algorithm that can discover all strongly connected components in a directed graph. If such an algorithm is called on an undirected graph, the ds.ErrUndefOp error is returned.