graphalgo

Documentation

Overview

Package graphalgo implements different algorithms for working with graph.Graph.

Index

• func FindArticulationPoints[T any](g *graph.Graph[T]) []int
• func FindCycle[T any](g *graph.Graph[T]) []int
• func FindShortestPath[T any](g *graph.Graph[T], start, end int) []int
• func TopologicalSort[T any](g *graph.Graph[T]) []int
• func Transpose[T any](g *graph.Graph[T]) *graph.Graph[T]
• type Edge
  • func FindBridges[T any](g *graph.Graph[T]) []Edge[T]
  • func KruskalMST[T constraints.Integer](g *graph.Graph[T]) []Edge[T]
• type LCA
  • func NewLCA[T any](g *graph.Graph[T]) LCA
  • func (a LCA) LCA(u, v int) int

Functions

func FindArticulationPoints

func FindArticulationPoints[T any](g *graph.Graph[T]) []int

FindArticulationPoints finds all articulation points in given graph.

func FindCycle

func FindCycle[T any](g *graph.Graph[T]) []int

FindCycle returns cycle if there is any otherwise empty slice returned.

func FindShortestPath

func FindShortestPath[T any](g *graph.Graph[T], start, end int) []int

FindShortestPath returns vertices that shortest path contains returns nil if start == end or if there are no path.

func TopologicalSort

func TopologicalSort[T any](g *graph.Graph[T]) []int

TopologicalSort returns vertices in topological order.

func Transpose

func Transpose[T any](g *graph.Graph[T]) *graph.Graph[T]

Transpose return graph that is transposes of given graph. Returns given graph if it is not directed.

Types

type Edge

type Edge[T any] struct {
	From, To int
	Value    T
}

Edge struct represents edge of graph.

func FindBridges

func FindBridges[T any](g *graph.Graph[T]) []Edge[T]

FindBridges returns all bridges of given graph.

func KruskalMST

func KruskalMST[T constraints.Integer](g *graph.Graph[T]) []Edge[T]

KruskalMST finds minimum spanning tree using Kruskal’s algorithm.

type LCA

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

func NewLCA

func NewLCA[T any](g *graph.Graph[T]) LCA

NewLCA returns new LCA struct for computing LCA of given vertexes.

func (LCA) LCA

func (a LCA) LCA(u, v int) int

LCA returns LCA of given vertexes.