graph

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 Edge
  • func KruskalMST(n int, edges []Edge) ([]Edge, int)
• type Graph
  • func New(v int) *Graph
  • func (g *Graph) AddEdge(one, two int)
  • func (g *Graph) AddVertex(v int)
  • func (g *Graph) AddWeightedEdge(one, two, weight int)
  • func (g *Graph) BellmanFord(start, end int) (isReachable bool, distance int, err error)
  • func (g *Graph) Dijkstra(start, end int) (int, bool)
  • func (g *Graph) FindAllCycles() []Graph
  • func (g *Graph) HasCycle() bool
• type ITree
• type Item
  • func (a Item) Idx() int
  • func (a Item) More(b any) bool
• type Tree
  • func NewTree(numbersVertex, root int, edges []TreeEdge) (tree *Tree)
  • func (tree *Tree) GetDad(u int) int
  • func (tree *Tree) GetDepth(u int) int
  • func (tree *Tree) GetLCA(u, v int) int
• type TreeEdge
• type UnionFind
  • func NewUnionFind(s int) UnionFind
  • func (u UnionFind) Find(q int) int
  • func (u UnionFind) Union(a, b int) UnionFind
• type Vertex
• type WeightedGraph
  • func FloydWarshall(graph WeightedGraph) WeightedGraph

Variables

var Inf = math.Inf(1)

Defining maximum value. If two vertices share this value, it means they are not connected

Functions

func ArticulationPoint

func ArticulationPoint(graph *Graph) []bool

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

func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int)

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 DepthFirstSearch(start, end int, nodes []int, edges [][]bool) ([]int, bool)

func DepthFirstSearchHelper

func DepthFirstSearchHelper(start, end int, nodes []int, edges [][]bool, showroute bool) ([]int, bool)

func GetIdx

func GetIdx(target int, nodes []int) int

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 NotExist

func NotExist(target int, slice []int) bool

func Topological

func Topological(N int, constraints [][]int) []int

Topological assumes that graph given is valid and that its possible to get a topological ordering. constraints are array of []int{a, b}, representing an edge going from a to b

Types

type Edge

type Edge struct {
	Start  Vertex
	End    Vertex
	Weight int
}

func KruskalMST

func KruskalMST(n int, edges []Edge) ([]Edge, int)

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 New

func New(v int) *Graph

Constructor functions for graphs (undirected by default)

func (*Graph) AddEdge

func (g *Graph) AddEdge(one, two int)

AddEdge will add a new edge between the provided vertices in the graph

func (*Graph) AddVertex

func (g *Graph) AddVertex(v int)

AddVertex will add a new vertex in the graph. If the vertex already exists it will do nothing.

func (*Graph) AddWeightedEdge

func (g *Graph) AddWeightedEdge(one, two, weight int)

AddWeightedEdge will add a new weighted edge between the provided vertices in the graph

func (*Graph) BellmanFord

func (g *Graph) BellmanFord(start, end int) (isReachable bool, distance int, err error)

func (*Graph) Dijkstra

func (g *Graph) Dijkstra(start, end int) (int, bool)

func (*Graph) FindAllCycles

func (g *Graph) FindAllCycles() []Graph

this function can do HasCycle() job but it is slower

func (*Graph) HasCycle

func (g *Graph) HasCycle() bool

type ITree

type ITree interface {
	GetDepth(int) int
	GetDad(int) int
	GetLCA(int, int) int
	// contains filtered or unexported methods
}

type Item

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

func (Item) Idx

func (a Item) Idx() int

func (Item) More

func (a Item) More(b any) bool

type Tree

type Tree struct {
	MAXLOG int
	// contains filtered or unexported fields
}

func NewTree

func NewTree(numbersVertex, root int, edges []TreeEdge) (tree *Tree)

func (*Tree) GetDad

func (tree *Tree) GetDad(u int) int

func (*Tree) GetDepth

func (tree *Tree) GetDepth(u int) int

func (*Tree) GetLCA

func (tree *Tree) GetLCA(u, v int) int

type TreeEdge

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

type UnionFind

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

Defining the union-find data structure

func NewUnionFind

func NewUnionFind(s int) UnionFind

Initialise a new union find data structure with s nodes

func (UnionFind) Find

func (u UnionFind) Find(q int) int

to find the root of the set to which the given element belongs, the Find function serves the purpose

func (UnionFind) Union

func (u UnionFind) Union(a, b int) UnionFind

to merge two sets to which the given elements belong, the Union function serves the purpose

type Vertex

type Vertex int

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