graph

package
v1.0.0 Latest Latest
Warning

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

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

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 finds 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 Returns true if no negative cycle is reachable from the source

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.