path

func BellmanFord ¶ added in v0.4.1

func BellmanFord[T comparable](g gograph.Graph[T], start T) (map[T]float64, error)

BellmanFord finds the shortest path from a source vertex to all other vertices in a weighted graph, even in the presence of negative weight edges, as long as there are no negative weight cycle.

The graph must have the Weighted option or ErrNotWeighted is returned. Unreachable vertices have distance math.Inf(1). Only negative cycles reachable from the source, and the overflow described below, produce ErrNegativeWeightCycle.

Steps:

	1.Initialization: Start by setting the distance of the source vertex to itself
    as 0, and the distance of all other vertices to infinity.

	2. Relaxation: Iterate through all edges in the graph |V| - 1 times, where |V|
	is the number of vertices. In each iteration, attempt to improve the shortest
	path estimates for all vertices. This is done by relaxing each edge: if the distance
	to the destination vertex through the current edge is shorter than the current
	estimate, update the estimate with the shorter distance.

	3.Detection of Negative Cycles: After the |V| - 1 iterations, perform an additional
	iteration. If during this iteration, any of the distances are further reduced, it
	indicates the presence of a negative weight cycle in the graph. This is because if a
	vertex's distance can still be improved after |V| - 1 iterations, it means there's a
	negative weight cycle that can be traversed indefinitely to reduce the distance further.

	4.Output: If there is no negative weight cycle, the algorithm outputs the shortest path
	distances from the source vertex to all other vertices. If there is a negative weight
	cycle, the algorithm typically returns an indication of this fact.

An edge with a NaN weight is skipped, as if it weren't in the graph. A path through a +Inf weight is as long as no path. A path through a -Inf weight has a distance of -Inf, and a cycle through a -Inf weight is a negative cycle. Finite weights that add up below the float64 range give a distance of -Inf, which returns ErrNegativeWeightCycle.

The time complexity of the Bellman-Ford algorithm is O(V*E), where V is the number of vertices and E is the number of edges. The passes stop after one that changes no distance, so when every shortest path has at most k edges, they take O(k*E) time. With -Inf weights, finding the cycles through them and the vertices they lead to takes O(V+E) more time. It uses O(V+E) space.

If the start vertex isn't in the graph, it returns gograph.ErrVertexDoesNotExist.

package main

import (
	"errors"
	"fmt"
	"math"

	"github.com/hmdsefi/gograph"
	"github.com/hmdsefi/gograph/path"
)

func main() {
	g := gograph.New[string](gograph.Directed(), gograph.Weighted())
	g.AddVertexByLabel("A")
	b := g.AddVertexByLabel("B")
	c := g.AddVertexByLabel("C")
	_, _ = g.AddEdge(b, c, gograph.WithEdgeWeight(-1))
	_, _ = g.AddEdge(c, b, gograph.WithEdgeWeight(-1))
	dist, err := path.BellmanFord(g, "A")
	fmt.Println(err == nil, math.IsInf(dist["B"], 1))
	_, err = path.FloydWarshall(g)
	fmt.Println(errors.Is(err, path.ErrNegativeWeightCycle))
}

Output:
true true
true

func Dijkstra ¶

func Dijkstra[T comparable](g gograph.Graph[T], start T) map[T]float64

Dijkstra is a standard implementation of Dijkstra's Algorithm that uses a min heap as a priority queue to find the shortest path between start vertex and all other vertices in the specified graph.

The time complexity of the standard Dijkstra's algorithm with a min heap is O((E+V)logV).

It returns the shortest distances from the starting vertex to all other vertices in the graph. A vertex that isn't reachable has the distance math.MaxFloat64. Edge weights are used whether or not the graph has the Weighted option. An edge with a NaN weight is skipped, and a path through a +Inf weight is as long as no path.

Edge weights must be non-negative, and this is not checked: a negative weight can give a wrong distance without an error. For directed graphs created with gograph.Weighted(), use BellmanFord to handle negative weights. DijkstraMultiSource, which also takes a single source, returns ErrNegativeWeight instead.

package main

import (
	"fmt"
	"math"

	"github.com/hmdsefi/gograph"
	"github.com/hmdsefi/gograph/path"
)

func main() {
	g := gograph.New[string](gograph.Directed(), gograph.Weighted())
	g.AddVertexByLabel("A")
	g.AddVertexByLabel("B")
	fmt.Println(path.Dijkstra(g, "A")["B"] == math.MaxFloat64)
	fmt.Println(path.DijkstraSimple(g, "A")["B"] == math.MaxFloat64)
	dist, err := path.BellmanFord(g, "A")
	fmt.Println(err == nil, math.IsInf(dist["B"], 1))
	all, err := path.FloydWarshall(g)
	fmt.Println(err == nil, math.IsInf(all["A"]["B"], 1))
}

Output:
true
true
true true
true true

package main

import (
	"errors"
	"fmt"

	"github.com/hmdsefi/gograph"
	"github.com/hmdsefi/gograph/path"
)

func main() {
	g := gograph.New[string](gograph.Directed())
	a := g.AddVertexByLabel("A")
	b := g.AddVertexByLabel("B")
	_, _ = g.AddEdge(a, b, gograph.WithEdgeWeight(3))
	fmt.Println(path.Dijkstra(g, "A")["B"])
	_, err := path.BellmanFord(g, "A")
	fmt.Println(errors.Is(err, path.ErrNotWeighted))
}

Output:
3
true

func DijkstraSimple ¶

func DijkstraSimple[T comparable](g gograph.Graph[T], start T) map[T]float64

DijkstraSimple is a simple implementation of Dijkstra's algorithm. It's using a simple slice to keep track of unvisited vertices, and selected the vertex with the smallest tentative distance using linear search.

The time complexity of the simple Dijkstra's algorithm implementation is O(V^2).

It returns the shortest distances from the starting vertex to all other vertices in the graph. A vertex that isn't reachable has the distance math.MaxFloat64. Edge weights are used whether or not the graph has the Weighted option. An edge with a NaN weight is skipped, and a path through a +Inf weight is as long as no path.

Edge weights must be non-negative, and this is not checked: a negative weight can give a wrong distance without an error. For directed graphs created with gograph.Weighted(), use BellmanFord to handle negative weights. DijkstraMultiSource, which also takes a single source, returns ErrNegativeWeight instead.

func FloydWarshall ¶ added in v0.4.1

func FloydWarshall[T comparable](g gograph.Graph[T]) (map[T]map[T]float64, error)

FloydWarshall finds the shortest paths between all pairs of vertices in a weighted graph, even in the presence of negative weight edges (as long as there are no negative weight cycles). It was proposed by Robert Floyd and Stephen Warshall.

The graph must have the Weighted option or ErrNotWeighted is returned. Unreachable vertices have distance math.Inf(1).

Steps:

1. Initialization: Create a distance matrix D[][] where D[i][j] represents the shortest distance between vertex i and vertex j. Initialize this matrix with the weights of the edges between vertices if there is an edge, otherwise set the value to infinity. Also, set the diagonal elements D[i][i] to 0. A self-loop only changes D[i][i] if its weight is negative.

2. Shortest Path Calculation: Iterate through all vertices as intermediate vertices. For each pair of vertices (i, j), check if going through the current intermediate vertex k leads to a shorter path than the current known distance from i to j. If so, update the distance matrix D[i][j] to the new shorter distance D[i][k] + D[k][j].

3. Detection of Negative Cycles: After the iterations, if any diagonal element D[i][i] of the distance matrix is negative, it indicates the presence of a negative weight cycle in the graph.

4. Output: The resulting distance matrix D[][] will contain the shortest path distances between all pairs of vertices. If there is a negative weight cycle, it might not produce the correct shortest paths, but it can still detect the presence of such cycles.

An edge with a NaN weight is skipped, as if it weren't in the graph. A path through a +Inf weight is as long as no path. A path through a -Inf weight has a distance of -Inf, and a cycle through a -Inf weight is a negative cycle. Finite weights that add up below the float64 range give a distance of -Inf, which returns ErrNegativeWeightCycle.

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph. Despite its cubic time complexity, it is often preferred over other algorithms like Bellman-Ford for dense graphs or when the graph has negative weight edges and no negative weight cycles, as it calculates shortest paths between all pairs of vertices in one go. With -Inf weights, each vertex that one of them leads to adds O(V^2) time, so the total stays O(V^3). It uses O(V^2) space.

func KCenter ¶ added in v0.9.0

func KCenter[T comparable](g gograph.Graph[T], k int, fixed ...T) ([]*gograph.Vertex[T], float64, error)

KCenter chooses k centers so that the vertex farthest from its nearest center is as close to one as it can make it. It returns the centers in the order it chose them, and the radius: the largest distance from a vertex to its nearest center.

fixed are centers that are already open, such as existing warehouses. They come first, in the order given, and count toward k. A fixed center listed twice counts once. Without fixed centers, the first center is the first vertex added to the graph.

Each next center is the vertex farthest from the centers chosen so far. Ties take the vertex added earlier, so the same graph gives the same centers on every run. On an undirected graph, the radius is at most twice the smallest radius any k centers that include the fixed ones can have. With zero or one fixed center, that is any k centers. On a directed graph the distances are not symmetric, and that factor of two does not hold.

A vertex no center reaches is infinitely far and is chosen next. If some vertex is still unreachable after k centers, the radius is +Inf. When k is at least the number of vertices, every vertex is a center, min(k, V) centers are returned, and the radius is 0. An empty graph returns nil centers and radius 0.

Distances follow the edges. The graph does not have to be weighted, and an edge without a weight counts as 0. An edge with a NaN weight is skipped, and a path through a +Inf weight is as long as no path. A negative weight returns ErrNegativeWeight. k below 1, or below the number of fixed centers, returns ErrInvalidK. A fixed center that is not in the graph returns gograph.ErrVertexDoesNotExist.

Time is O(k (V + E) log V) and extra space is O(V + E). The distances from one round are kept. Opening a center searches only the vertices it gets strictly closer to, which is safe because a path that is no closer at a vertex cannot be closer past it when every weight is at least 0.

g := gograph.New[string](gograph.Weighted())
depot := g.AddVertexByLabel("depot")
market := g.AddVertexByLabel("market")
school := g.AddVertexByLabel("school")
clinic := g.AddVertexByLabel("clinic")
station := g.AddVertexByLabel("station")
road := func(from, to *gograph.Vertex[string]) {
	_, _ = g.AddEdge(from, to, gograph.WithEdgeWeight(1))
}
road(depot, market)
road(market, school)
road(school, clinic)
road(clinic, station)

centers, radius, err := KCenter(g, 2)
if err != nil {
	panic(err)
}
fmt.Println("centers", centers[0].Label(), centers[1].Label())
fmt.Println("radius", radius)

Output:
centers depot station
radius 2

func TransitiveReduction ¶ added in v0.6.0

func TransitiveReduction[T comparable](g gograph.Graph[T]) (gograph.Graph[T], error)

TransitiveReduction computes the transitive reduction of a directed graph. The transitive reduction of a directed graph G is a graph G' with the same vertices such that there is a path from vertex u to vertex v in G' if and only if there is a path from u to v in G, and G' has as few edges as possible.

This implementation uses a depth-first search approach inspired by NetworkX library to efficiently compute the transitive reduction by identifying and removing edges that have alternate paths.

For directed acyclic graphs (DAGs), the transitive reduction can be computed efficiently without needing to build the full transitive closure matrix.

The result keeps the vertex weights, edge weights, and labels of the remaining edges, and is weighted if g is weighted. It is created with Acyclic when g is, so AddEdge on the result rejects edges that would create a cycle, matching the input.

It returns an error if the graph is not directed or if the graph contains cycles.