graph

package
v1.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 2, 2025 License: MIT Imports: 5 Imported by: 0

README

Graph Package

This package provides comprehensive graph data structure implementations and algorithms in Go. All implementations are thread-safe and support concurrent operations.

Features

Core Graph Structure
  • Weighted graph implementation supporting both directed and undirected graphs
  • Thread-safe operations with RWMutex
  • Adjacency list representation
  • Basic operations:
    • Add edge
    • Get neighbors
    • Get vertex count
    • Check if directed
Graph Traversal
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Support for custom traversal orders
Shortest Path Algorithms
  • Dijkstra's Algorithm:
    • Single-source shortest paths
    • Priority queue optimization
    • Distance and path reconstruction
  • Bellman-Ford Algorithm:
    • Negative weight support
    • Negative cycle detection
    • Path reconstruction
    • Reachability checking
  • Floyd-Warshall Algorithm:
    • All-pairs shortest paths
    • Path reconstruction
Minimum Spanning Trees
  • Kruskal's Algorithm:
    • Union-Find data structure
    • Edge sorting optimization
  • Prim's Algorithm:
    • Priority queue implementation
    • Efficient edge selection
Graph Analysis
  • Tarjan's Strongly Connected Components:
    • Component identification
    • Component size analysis
    • Connectivity checking
  • Articulation Points:
    • Cut vertex detection
    • Bridge identification
  • Euler Path:
    • Path existence checking
    • Path construction
  • Hamiltonian Path:
    • Path existence checking
    • Path construction

Usage Examples

Basic Graph Operations
// Create a new graph
graph := NewGraph(5, false) // 5 vertices, undirected

// Add edges
graph.AddEdge(0, 1, 4)  // edge from 0 to 1 with weight 4
graph.AddEdge(1, 2, 3)
graph.AddEdge(2, 3, 2)

// Get neighbors
neighbors := graph.GetNeighbors(1)

// Graph traversal
bfsOrder := graph.BFS(0)
dfsOrder := graph.DFS(0)
Shortest Path Algorithms
// Dijkstra's Algorithm
distances := graph.Dijkstra(0)

// Bellman-Ford Algorithm
bf := NewBellmanFord(graph, 0)
if bf.ComputeShortestPaths() {
    distance := bf.GetDistance(3)
    path := bf.GetPath(3)
}

// Floyd-Warshall Algorithm
fw := NewFloydWarshall(graph)
fw.ComputeAllPairs()
distance := fw.GetDistance(0, 3)
Minimum Spanning Tree
// Kruskal's Algorithm
mstEdges := graph.Kruskal()

// Prim's Algorithm
mstEdges = graph.Prim(0)
Graph Analysis
// Strongly Connected Components
tarjan := NewTarjanSCC(graph)
components := tarjan.FindComponents()
isStronglyConnected := tarjan.IsStronglyConnected()

// Articulation Points
ap := NewArticulationPoints(graph)
cutVertices := ap.FindArticulationPoints()
bridges := ap.FindBridges()

// Euler Path
euler := NewEulerPath(graph)
if euler.HasEulerPath() {
    path := euler.FindEulerPath()
}

Implementation Details

Time Complexities
Basic Operations
  • Add Edge: O(1)
  • Get Neighbors: O(1)
  • BFS/DFS: O(V + E)
Shortest Path Algorithms
  • Dijkstra: O((V + E) log V)
  • Bellman-Ford: O(VE)
  • Floyd-Warshall: O(V³)
Minimum Spanning Tree
  • Kruskal: O(E log E)
  • Prim: O((V + E) log V)
Graph Analysis
  • Tarjan's SCC: O(V + E)
  • Articulation Points: O(V + E)
  • Euler Path: O(E)
  • Hamiltonian Path: O(2^N * N^2)

Where:

  • V is the number of vertices
  • E is the number of edges
  • N is the size of the graph
Thread Safety
  • All operations are protected with RWMutex
  • Read operations use RLock
  • Write operations use Lock
  • Proper lock/unlock handling with defer

Testing

Each component comes with comprehensive test coverage. Run tests using:

go test ./...

Contributing

Contributions are welcome! Please ensure that any new features or modifications come with:

  • Proper documentation
  • Thread safety considerations
  • Comprehensive test cases
  • Example usage
  • Time complexity analysis

License

This package is distributed under the MIT license. See the LICENSE file for more details.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type AdjMatrix 

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

AdjMatrix represents a graph using adjacency matrix

func NewAdjMatrix 

func NewAdjMatrix(vertices int, directed bool) *AdjMatrix

NewAdjMatrix creates a new graph with adjacency matrix representation

func (*AdjMatrix) AddEdge 

func (g *AdjMatrix) AddEdge(v1, v2, weight int)

AddEdge adds an edge between vertices v1 and v2 with given weight

func (*AdjMatrix) FloydWarshall 

func (g *AdjMatrix) FloydWarshall() [][]int

FloydWarshall finds shortest paths between all pairs of vertices

func (*AdjMatrix) GetNeighbors 

func (g *AdjMatrix) GetNeighbors(vertex int) []int

GetNeighbors returns all neighbors of a vertex

func (*AdjMatrix) GetVertices 

func (g *AdjMatrix) GetVertices() int

GetVertices returns the number of vertices

func (*AdjMatrix) GetWeight 

func (g *AdjMatrix) GetWeight(v1, v2 int) int

GetWeight returns the weight of the edge between v1 and v2

func (*AdjMatrix) IsDirected 

func (g *AdjMatrix) IsDirected() bool

IsDirected returns whether the graph is directed

type ArticulationPoints 

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

ArticulationPoints implements algorithms for finding articulation points and bridges

func NewArticulationPoints 

func NewArticulationPoints(g *Graph) *ArticulationPoints

NewArticulationPoints creates a new ArticulationPoints instance

func (*ArticulationPoints) FindArticulationPoints 

func (ap *ArticulationPoints) FindArticulationPoints() []int

FindArticulationPoints finds all articulation points in the graph

func (*ArticulationPoints) FindBridges 

func (ap *ArticulationPoints) FindBridges() []Edge

FindBridges returns all bridges in the graph

func (*ArticulationPoints) GetArticulationPointCount 

func (ap *ArticulationPoints) GetArticulationPointCount() int

GetArticulationPointCount returns the number of articulation points

func (*ArticulationPoints) GetBridgeCount 

func (ap *ArticulationPoints) GetBridgeCount() int

GetBridgeCount returns the number of bridges

func (*ArticulationPoints) IsArticulationPoint 

func (ap *ArticulationPoints) IsArticulationPoint(v int) bool

IsArticulationPoint checks if a vertex is an articulation point

func (*ArticulationPoints) IsBridge 

func (ap *ArticulationPoints) IsBridge(from, to int) bool

IsBridge checks if an edge is a bridge

type BellmanFord 

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

BellmanFord implements the Bellman-Ford algorithm for single-source shortest paths

func NewBellmanFord 

func NewBellmanFord(g *Graph, source int) *BellmanFord

NewBellmanFord creates a new Bellman-Ford instance

func (*BellmanFord) ComputeShortestPaths 

func (bf *BellmanFord) ComputeShortestPaths() bool

ComputeShortestPaths computes single-source shortest paths

func (*BellmanFord) GetAllDistances 

func (bf *BellmanFord) GetAllDistances() []float64

GetAllDistances returns all computed distances

func (*BellmanFord) GetDistance 

func (bf *BellmanFord) GetDistance(to int) float64

GetDistance returns the shortest distance to a vertex

func (*BellmanFord) GetPath 

func (bf *BellmanFord) GetPath(to int) []int

GetPath returns the shortest path to a vertex

func (*BellmanFord) GetPredecessors 

func (bf *BellmanFord) GetPredecessors() []int

GetPredecessors returns the predecessor array

func (*BellmanFord) IsReachable 

func (bf *BellmanFord) IsReachable(to int) bool

IsReachable checks if a vertex is reachable from the source

type Edge 

type Edge struct {
	From   int
	To     int
	Weight int
}

Edge represents a weighted edge in the graph

type EulerPath 

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

EulerPath implements algorithms for finding Euler paths and circuits

func NewEulerPath 

func NewEulerPath(g *Graph) *EulerPath

NewEulerPath creates a new EulerPath instance

func (*EulerPath) FindEulerCircuit 

func (ep *EulerPath) FindEulerCircuit() []int

FindEulerCircuit finds an Euler circuit in the graph if it exists

func (*EulerPath) FindEulerPath 

func (ep *EulerPath) FindEulerPath() []int

FindEulerPath finds an Euler path in the graph if it exists

func (*EulerPath) HasEulerCircuit 

func (ep *EulerPath) HasEulerCircuit() bool

HasEulerCircuit checks if the graph has an Euler circuit

func (*EulerPath) HasEulerPath 

func (ep *EulerPath) HasEulerPath() bool

HasEulerPath checks if the graph has an Euler path

type FloydWarshall 

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

FloydWarshall implements the Floyd-Warshall algorithm for all-pairs shortest paths

func NewFloydWarshall 

func NewFloydWarshall(g *Graph) *FloydWarshall

NewFloydWarshall creates a new Floyd-Warshall instance

func (*FloydWarshall) ComputeShortestPaths 

func (fw *FloydWarshall) ComputeShortestPaths()

ComputeShortestPaths computes all-pairs shortest paths

func (*FloydWarshall) GetAllPairsDistances 

func (fw *FloydWarshall) GetAllPairsDistances() [][]float64

GetAllPairsDistances returns the distance matrix

func (*FloydWarshall) GetAllPairsNextHops 

func (fw *FloydWarshall) GetAllPairsNextHops() [][]int

GetAllPairsNextHops returns the next hop matrix

func (*FloydWarshall) GetDistance 

func (fw *FloydWarshall) GetDistance(from, to int) float64

GetDistance returns the shortest distance between two vertices

func (*FloydWarshall) GetPath 

func (fw *FloydWarshall) GetPath(from, to int) []int

GetPath returns the shortest path between two vertices

func (*FloydWarshall) HasNegativeCycle 

func (fw *FloydWarshall) HasNegativeCycle() bool

HasNegativeCycle checks if the graph contains a negative cycle

type Graph 

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

Graph represents a graph data structure

func NewGraph 

func NewGraph(vertices int, directed bool) *Graph

NewGraph creates a new graph with n vertices

func (*Graph) AddEdge 

func (g *Graph) AddEdge(v1, v2, weight int)

AddEdge adds an edge between vertices v1 and v2 with given weight

func (*Graph) BFS 

func (g *Graph) BFS(start int) []int

BFS performs Breadth First Search starting from vertex v

func (*Graph) DFS 

func (g *Graph) DFS(start int) []int

DFS performs Depth First Search starting from vertex v

func (*Graph) Dijkstra 

func (g *Graph) Dijkstra(source int) map[int]int

Dijkstra finds shortest paths from source vertex to all other vertices

func (*Graph) GetNeighbors 

func (g *Graph) GetNeighbors(vertex int) []int

GetNeighbors returns all neighbors of a vertex

func (*Graph) GetVertices 

func (g *Graph) GetVertices() int

GetVertices returns the number of vertices

func (*Graph) IsDirected 

func (g *Graph) IsDirected() bool

IsDirected returns whether the graph is directed

func (*Graph) Kruskal 

func (g *Graph) Kruskal() []Edge

Kruskal finds Minimum Spanning Tree using Kruskal's algorithm

func (*Graph) Prim 

func (g *Graph) Prim(start int) []Edge

Prim finds Minimum Spanning Tree using Prim's algorithm

type HamiltonianPath 

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

HamiltonianPath implements algorithms for finding Hamiltonian paths and circuits

func NewHamiltonianPath 

func NewHamiltonianPath(g *Graph) *HamiltonianPath

NewHamiltonianPath creates a new HamiltonianPath instance

func (*HamiltonianPath) FindHamiltonianCircuit 

func (hp *HamiltonianPath) FindHamiltonianCircuit() []int

FindHamiltonianCircuit finds a Hamiltonian circuit in the graph if it exists

func (*HamiltonianPath) FindHamiltonianPath 

func (hp *HamiltonianPath) FindHamiltonianPath() []int

FindHamiltonianPath finds a Hamiltonian path in the graph if it exists

func (*HamiltonianPath) GetPath 

func (hp *HamiltonianPath) GetPath() []int

GetPath returns the last found path

func (*HamiltonianPath) HasHamiltonianCircuit 

func (hp *HamiltonianPath) HasHamiltonianCircuit() bool

HasHamiltonianCircuit checks if the graph has a Hamiltonian circuit

func (*HamiltonianPath) HasHamiltonianPath 

func (hp *HamiltonianPath) HasHamiltonianPath() bool

HasHamiltonianPath checks if the graph has a Hamiltonian path

func (*HamiltonianPath) IsHamiltonianCircuit 

func (hp *HamiltonianPath) IsHamiltonianCircuit(circuit []int) bool

IsHamiltonianCircuit checks if a given circuit is a valid Hamiltonian circuit

func (*HamiltonianPath) IsHamiltonianPath 

func (hp *HamiltonianPath) IsHamiltonianPath(path []int) bool

IsHamiltonianPath checks if a given path is a valid Hamiltonian path

type Item 

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

Priority Queue implementation for Dijkstra and Prim

type KruskalMST 

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

KruskalMST implements Kruskal's algorithm for finding Minimum Spanning Tree

func NewKruskalMST 

func NewKruskalMST(g *Graph) *KruskalMST

NewKruskalMST creates a new Kruskal's MST instance

func (*KruskalMST) FindMST 

func (k *KruskalMST) FindMST() bool

FindMST finds the Minimum Spanning Tree

func (*KruskalMST) GetMSTCost 

func (k *KruskalMST) GetMSTCost() float64

GetMSTCost returns the total cost of the MST

func (*KruskalMST) GetMSTEdges 

func (k *KruskalMST) GetMSTEdges() []Edge

GetMSTEdges returns the edges in the MST

func (*KruskalMST) GetNumComponents 

func (k *KruskalMST) GetNumComponents() int

GetNumComponents returns the number of connected components

func (*KruskalMST) IsConnected 

func (k *KruskalMST) IsConnected(x, y int) bool

IsConnected checks if two vertices are connected in the MST

type PrimMST 

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

PrimMST implements Prim's algorithm for finding Minimum Spanning Tree

func NewPrimMST 

func NewPrimMST(g *Graph) *PrimMST

NewPrimMST creates a new Prim's MST instance

func (*PrimMST) FindMST 

func (p *PrimMST) FindMST() bool

FindMST finds the Minimum Spanning Tree

func (*PrimMST) GetMSTCost 

func (p *PrimMST) GetMSTCost() float64

GetMSTCost returns the total cost of the MST

func (*PrimMST) GetMSTEdges 

func (p *PrimMST) GetMSTEdges() []Edge

GetMSTEdges returns the edges in the MST

func (*PrimMST) GetParent 

func (p *PrimMST) GetParent(v int) int

GetParent returns the parent of a vertex in the MST

func (*PrimMST) IsInMST 

func (p *PrimMST) IsInMST(v int) bool

IsInMST checks if a vertex is in the MST

type PriorityQueue 

type PriorityQueue []*Item

func (PriorityQueue) Len 

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less 

func (pq PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(x interface{})

func (PriorityQueue) Swap 

func (pq PriorityQueue) Swap(i, j int)

type StronglyConnectedComponents 

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

StronglyConnectedComponents implements Kosaraju's algorithm for finding SCCs

func NewSCC 

func NewSCC(g *Graph) *StronglyConnectedComponents

NewSCC creates a new SCC instance

func (*StronglyConnectedComponents) FindComponents 

func (scc *StronglyConnectedComponents) FindComponents() [][]int

FindComponents finds all strongly connected components

func (*StronglyConnectedComponents) GetComponentCount 

func (scc *StronglyConnectedComponents) GetComponentCount() int

GetComponentCount returns the number of strongly connected components

func (*StronglyConnectedComponents) GetComponents 

func (scc *StronglyConnectedComponents) GetComponents() [][]int

GetComponents returns all found components

type TarjanSCC 

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

TarjanSCC implements Tarjan's algorithm for finding Strongly Connected Components

func NewTarjanSCC 

func NewTarjanSCC(g *Graph) *TarjanSCC

NewTarjanSCC creates a new Tarjan's SCC instance

func (*TarjanSCC) FindComponents 

func (t *TarjanSCC) FindComponents() [][]int

FindComponents finds all strongly connected components

func (*TarjanSCC) GetComponentCount 

func (t *TarjanSCC) GetComponentCount() int

GetComponentCount returns the number of strongly connected components

func (*TarjanSCC) GetComponents 

func (t *TarjanSCC) GetComponents() [][]int

GetComponents returns all found components

func (*TarjanSCC) GetLargestComponent 

func (t *TarjanSCC) GetLargestComponent() []int

GetLargestComponent returns the largest strongly connected component

func (*TarjanSCC) IsStronglyConnected 

func (t *TarjanSCC) IsStronglyConnected() bool

IsStronglyConnected checks if the graph is strongly connected

type TopologicalSort 

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

TopologicalSort performs topological sorting on a directed graph

func NewTopologicalSort 

func NewTopologicalSort(g *Graph) *TopologicalSort

NewTopologicalSort creates a new topological sort instance

func (*TopologicalSort) GetDependencyOrder 

func (ts *TopologicalSort) GetDependencyOrder() []int

GetDependencyOrder returns the dependency order of vertices For example, if v depends on u, then u will appear before v in the result

func (*TopologicalSort) HasCycle 

func (ts *TopologicalSort) HasCycle() bool

HasCycle returns true if the graph contains a cycle

func (*TopologicalSort) Sort 

func (ts *TopologicalSort) Sort() []int

Sort performs topological sorting and returns the sorted vertices Returns nil if the graph has a cycle

type UnionFind 

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

Union-Find implementation for Kruskal's algorithm

func NewUnionFind 

func NewUnionFind(size int) *UnionFind

func (*UnionFind) Connected 

func (uf *UnionFind) Connected(x, y int) bool

func (*UnionFind) Find 

func (uf *UnionFind) Find(x int) int

func (*UnionFind) Union 

func (uf *UnionFind) Union(x, y int)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.