Documentation ¶
Overview ¶
Package graph demonstrates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal
Index ¶
- Variables
- func ArticulationPoint(graph *Graph) []bool
- func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int)
- func DepthFirstSearch(start, end int, nodes []int, edges [][]bool) ([]int, bool)
- func DepthFirstSearchHelper(start, end int, nodes []int, edges [][]bool, showroute bool) ([]int, bool)
- func GetIdx(target int, nodes []int) int
- func LowestCommonAncestor(tree *Tree)
- func NotExist(target int, slice []int) bool
- func Topological(N int, constraints [][]int) []int
- type DisjointSetUnion
- type DisjointSetUnionElement
- type Edge
- type Graph
- type ITree
- type Item
- type Tree
- type TreeEdge
- type Vertex
- type WeightedGraph
Constants ¶
This section is empty.
Variables ¶
var Inf = math.Inf(1)
Defining maximum value. If two vertices share this value, it means they are not connected
Functions ¶
func ArticulationPoint ¶
ArticulationPoint is a function to identify articulation points in a graph. The function takes the graph as an argument and returns a boolean slice which indicates whether a vertex is an articulation point or not. Worst Case Time Complexity: O(|V| + |E|) Auxiliary Space: O(|V|) reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point
func BreadthFirstSearch ¶
BreadthFirstSearch is an algorithm for traversing and searching graph data structures. It starts at an arbitrary node of a graph, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Worst-case performance O(|V|+|E|)=O(b^{d})}O(|V|+|E|)=O(b^{d}) Worst-case space complexity O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) reference: https://en.wikipedia.org/wiki/Breadth-first_search
func DepthFirstSearch ¶
func DepthFirstSearchHelper ¶
func LowestCommonAncestor ¶
func LowestCommonAncestor(tree *Tree)
For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. Let's call `jump[j][u]` is the `2^j`-th ancestor above the node `u` with `u` in range `[0, numbersVertex)`, `j` in range `[0,MAXLOG)`. These information allow us to jump from any node to any ancestor above it in `O(MAXLOG)` time.
func Topological ¶
Assumes that graph given is valid and possible to get a topo ordering. constraints are array of []int{a, b}, representing an edge going from a to b
Types ¶
type DisjointSetUnion ¶
type DisjointSetUnion []DisjointSetUnionElement
DisjointSetUnion is a data structure that treats its elements as separate sets and provides fast operations for set creation, merging sets, and finding the parent of the given element of a set.
func NewDSU ¶
func NewDSU(n int) *DisjointSetUnion
NewDSU will return an initialised DSU using the value of n which will be treated as the number of elements out of which the DSU is being made
func (DisjointSetUnion) FindSetRepresentative ¶
func (dsu DisjointSetUnion) FindSetRepresentative(node Vertex) Vertex
FindSetRepresentative will return the parent element of the set the given node belongs to. Since every single element in the path from node to parent has the same parent, we store the parent value for each element in the path. This reduces consequent function calls and helps in going from O(n) to O(log n). This is known as path compression technique.
func (DisjointSetUnion) MakeSet ¶
func (dsu DisjointSetUnion) MakeSet(node Vertex)
MakeSet will create a set in the DSU for the given node
func (DisjointSetUnion) UnionSets ¶
func (dsu DisjointSetUnion) UnionSets(firstNode Vertex, secondNode Vertex)
unionSets will merge two given sets. The naive implementation of this always combines the secondNode's tree with the firstNode's tree. This can lead to creation of trees of length O(n) so we optimize by attaching the node with smaller rank to the node with bigger rank. Rank represents the upper bound depth of the tree.
type DisjointSetUnionElement ¶
DisjointSetUnionElement describes what an element of DSU looks like
type Graph ¶
type Graph struct { Directed bool // Differentiate directed/undirected graphs // contains filtered or unexported fields }
Graph provides a structure to store the graph. It is safe to use its empty object.
func (*Graph) AddVertex ¶
AddVertex will add a new vertex in the graph. If the vertex already exists it will do nothing.
func (*Graph) AddWeightedEdge ¶
AddWeightedEdge will add a new weighted edge between the provided vertices in the graph
func (*Graph) BellmanFord ¶
type WeightedGraph ¶
type WeightedGraph [][]float64
WeightedGraph defining matrix to use 2d array easier
func FloydWarshall ¶
func FloydWarshall(graph WeightedGraph) WeightedGraph
FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm