README
¶
gograph - Connectivity
Why Strong Connectivity Is Important?
The concept of strong connectivity in a graph is important for a variety of reasons. Here are some of the main reasons why strong connectivity is important:
- Robustness: A graph that is strongly connected is more robust and resilient than a graph that is not strongly connected. This is because in a strongly connected graph, every vertex can be reached from every other vertex, which means that even if some vertices or edges are removed, the graph remains connected.
- Communication: In many applications, such as network routing and communication networks, it is important to be able to communicate between any pair of vertices in the graph. A strongly connected graph ensures that there is a path between any two vertices, which makes communication between them possible.
- Analysis: Strong connectivity is often used as a tool for analyzing the structure of a graph. For example, identifying strongly connected components in a graph can reveal important patterns and relationships between vertices.
- Optimization: In some applications, it may be necessary to find the shortest path or the minimum spanning tree that connects all vertices in the graph. Strong connectivity can help to optimize such algorithms by reducing the search space and ensuring that all vertices are reachable.
- Design of algorithms: Strong connectivity is also an important concept in the design of algorithms for various graph problems. For example, many graph algorithms rely on identifying strongly connected components or paths in the graph to find optimal solutions.
- Network reliability: In network reliability analysis, strong connectivity is used to determine the probability that a network will remain connected in the event of failures or disruptions. This is important in designing robust networks for critical applications such as transportation, energy distribution, and telecommunications.
- Social network analysis: Strong connectivity is also important in social network analysis, where it is used to identify closely-knit groups or communities within a larger network. This can provide insights into social structures and relationships that are not immediately apparent from the graph topology.
- Testing and verification: Strong connectivity is an important concept in testing and verification of digital circuits, where it is used to ensure that all nodes in the circuit can be reached from all other nodes. This is important for ensuring correct functionality and avoiding problems such as deadlocks or race conditions.
- Transportation and logistics: Strong connectivity is also important in transportation and logistics, where it is used to optimize routing and scheduling of vehicles or goods. In a strongly connected graph, it is possible to find the shortest path or the minimum time required to transport goods between any two locations.
- Graph drawing and visualization: Strong connectivity is also an important consideration in graph drawing and visualization. Many graph layout algorithms aim to minimize edge crossings while maintaining strong connectivity, which can improve the readability and aesthetics of the graph.
Strong connectivity is a fundamental concept in graph theory that is used to describe the property of a directed graph where every vertex is reachable from every other vertex through a directed path. Strong connectivity has a wide range of practical applications, such as designing robust networks, optimizing transportation routes, analyzing social structures, and testing digital circuits.
Several algorithms, such as Tarjan's Algorithm, Kosaraju's Algorithm, Path-Based Strong Component Algorithm, and Gabow's Algorithm, are available to determine the strong connectivity of a graph, and the choice of algorithm depends on the specific characteristics of the graph and the requirements of the application.
Understanding strong connectivity and its implications is essential for anyone working with graphs or network data. Strongly connected graphs are more robust and resilient, enable communication between any pair of vertices, and provide insights into social structures and relationships. Additionally, strong connectivity is important in optimizing algorithms, network reliability, transportation and logistics, graph drawing, and verification of digital circuits.
Tarjan's Algorithm
Tarjan's algorithm is a popular algorithm in graph theory used to find strongly connected components in a directed graph. The algorithm is named after its inventor, Robert Tarjan. The algorithm is based on depth-first search (DFS) and is very efficient in both time and space complexity.
connectivity.Tarjan finding the strongly connected components of a set of microservice calls. Run it step by step on gograph.dev.
The main usage of the Tarjan algorithm is to find strongly connected components in a directed graph. Strongly connected components are used in many applications, such as finding the shortest path between two nodes in a graph, identifying the critical paths in a project schedule, and solving problems related to synchronization in computer science.
The time complexity of Tarjan's algorithm is O(V + E), where V is the number of vertices in the graph and E is the number of edges in the graph. The space complexity of the algorithm is O(V), where V is the number of vertices in the graph.
To use Tarjan algorithm, you can call the 'Tarjan[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]' function and path your graph to it:
import (
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[int](gograph.Directed())
v1 := g.AddVertexByLabel(1)
v2 := g.AddVertexByLabel(2)
v3 := g.AddVertexByLabel(3)
v4 := g.AddVertexByLabel(4)
v5 := g.AddVertexByLabel(5)
g.AddEdge(v1, v2)
g.AddEdge(v2, v3)
g.AddEdge(v3, v1)
g.AddEdge(v3, v4)
g.AddEdge(v4, v5)
g.AddEdge(v5, v4)
sccs := connectivity.Tarjan(g)
}
It returns a slice of strongly connected component.
Kosaraju's Algorithm
Kosaraju's algorithm is another popular algorithm in graph theory used to find strongly connected components in a directed graph. The algorithm is named after its inventor, S. Rao Kosaraju. The algorithm is also based on depth-first search (DFS), but it performs two DFS passes over the graph.
The main usage of Kosaraju's algorithm is to find strongly connected components in a directed graph. Strongly connected components are used in many applications, such as finding the shortest path between two nodes in a graph, identifying the critical paths in a project schedule, and solving problems related to synchronization in computer science.
The time complexity of Kosaraju's algorithm is O(V + E), where V is the number of vertices in the graph and E is the number of edges in the graph. The space complexity of the algorithm is O(V), where V is the number of vertices in the graph.
Run Kosaraju's algorithm step by step on gograph.dev.
To use Kosaraju algorithm, you can call the 'Kosaraju[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]' function and path your graph to it:
import (
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[int](gograph.Directed())
v1 := g.AddVertexByLabel(1)
v2 := g.AddVertexByLabel(2)
v3 := g.AddVertexByLabel(3)
v4 := g.AddVertexByLabel(4)
v5 := g.AddVertexByLabel(5)
g.AddEdge(v1, v2)
g.AddEdge(v2, v3)
g.AddEdge(v3, v1)
g.AddEdge(v3, v4)
g.AddEdge(v4, v5)
g.AddEdge(v5, v4)
sccs := connectivity.Kosaraju(g)
}
It returns a slice of strongly connected component.
Gabow's Algorithm
Gabow's algorithm is another algorithm used to find strongly connected components (SCCs) in a directed graph. It's the path-based algorithm published by Harold N. Gabow in 2000. Like Tarjan's algorithm it runs a single depth-first search (DFS), but instead of a low-link value per vertex it keeps a second stack with the vertices on the search path that can still be the root of a component.
The main usage of Gabow's algorithm is to find strongly connected components in a directed graph. It can be used in many applications, such as detecting cycles in a graph, solving problems related to synchronization, and analyzing network traffic.
The time complexity of Gabow's algorithm is O(V + E), where V is the number of vertices in the graph and E is the number of edges in the graph. The space complexity of the algorithm is O(V), where V is the number of vertices in the graph.
Run Gabow's algorithm step by step on gograph.dev.
To use Gabow algorithm, you can call the 'Gabow[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]' function and path your graph to it:
import (
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[int](gograph.Directed())
v1 := g.AddVertexByLabel(1)
v2 := g.AddVertexByLabel(2)
v3 := g.AddVertexByLabel(3)
v4 := g.AddVertexByLabel(4)
v5 := g.AddVertexByLabel(5)
g.AddEdge(v1, v2)
g.AddEdge(v2, v3)
g.AddEdge(v3, v1)
g.AddEdge(v3, v4)
g.AddEdge(v4, v5)
g.AddEdge(v5, v4)
sccs := connectivity.Gabow(g)
}
It returns a slice of strongly connected component.
Condensation
Functions that need a directed acyclic graph, such as gograph.TopologySort, refuse graphs with cycles.
The condensation of a graph replaces each strongly connected component with a single vertex, so it never
has a cycle. A component with more than one member is a group of vertices that depend on each other, for
example modules that have to be upgraded in one step.
Condense runs Tarjan's algorithm once, in O(V + E) time. The components are labeled 0 to n-1 in
topological order, and there is an edge between two components if an edge of the graph crosses between
them:
c, err := connectivity.Condense(g)
if err != nil {
return err
}
order, err := gograph.TopologySort(c.Graph) // never fails with ErrDAGHasCycle
if err != nil {
return err
}
for _, comp := range order {
members := c.Members[comp.Label()]
if len(members) > 1 {
// these vertices depend on each other and have to be handled together
}
}
c.ComponentOf maps each vertex label to its component. WithComponentWeight sets the weight of each
component, for example the sum of its members' weights, and WithCrossingWeight sets the weight of each
edge from the edges that cross between the two components.
Documentation
¶
Index ¶
- func ConnectedComponents[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
- func FindCycle[T comparable](g gograph.Graph[T]) ([]*gograph.Vertex[T], bool)
- func Gabow[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
- func HasCycle[T comparable](g gograph.Graph[T]) bool
- func Kosaraju[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
- func Tarjan[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
- type Condensation
- type CondenseOption
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ConnectedComponents ¶ added in v0.9.0
func ConnectedComponents[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
ConnectedComponents returns the connected components of g. For a directed graph, edge directions are ignored, so it returns the weakly connected components. The vertices in the result are the vertices stored in g, not copies, and an empty graph returns an empty slice.
The components are in the order of their first vertex in GetAllVertices. In an undirected graph, the vertices of a component are in breadth-first order from that vertex, following the order the edges were added. In a directed graph, they are in GetAllVertices order.
A graph from gograph.New takes O(V+E) time, up to the inverse Ackermann factor of union-find for directed graphs, and uses O(V) extra space. Any other Graph is read through GetAllVertices and EdgesOf. It panics if g is nil.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[string](gograph.Directed())
_, _ = g.AddEdge(gograph.NewVertex("api"), gograph.NewVertex("auth"))
_, _ = g.AddEdge(gograph.NewVertex("billing"), gograph.NewVertex("auth"))
_, _ = g.AddEdge(gograph.NewVertex("search"), gograph.NewVertex("index"))
// Edge directions are ignored, so billing joins api through auth.
for _, component := range connectivity.ConnectedComponents(g) {
var labels []string
for _, v := range component {
labels = append(labels, v.Label())
}
fmt.Println(labels)
}
}
Output: [api auth billing] [search index]
func FindCycle ¶ added in v0.10.0
FindCycle returns the vertices of one cycle of g in order, without repeating the first vertex at the end: [a b c] means a -> b -> c -> a. It returns nil and false when g has no cycle, so it reports a cycle exactly when HasCycle does.
A self-loop is a cycle of one vertex. In a directed graph, a cycle follows the edge directions. In an undirected graph, the two stored directions of an edge count as one edge, so any other cycle has at least three vertices.
The cycle is the first one that traverse.DFSEventsAll finds: the first back edge u -> v closes it, and it runs from v down the search path to u. That is one cycle of g, and a shorter one can exist.
A graph created with gograph.Acyclic returns false without a search. Any other graph takes O(V+E) time, and the search stops at the first back edge. It keeps O(V) state, plus the neighbors still to look at of each vertex on the search path, which is at most O(V+E). HasCycle gives the answer alone faster, since it skips the edge events. It panics if g is nil.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{{"api", "auth"}, {"auth", "db"}, {"db", "cache"}, {"cache", "auth"}} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
cycle, ok := connectivity.FindCycle(g)
if !ok {
fmt.Println("no cycle")
return
}
var path []string
for _, v := range cycle {
path = append(path, v.Label())
}
fmt.Println("import cycle:", strings.Join(path, " -> "), "->", path[0])
}
Output: import cycle: auth -> db -> cache -> auth
func Gabow ¶
func Gabow[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
Gabow runs Gabow's path-based algorithm, and returns a list of strongly connected components, where each component is represented as an array of pointers to vertex structs.
It keeps the search path in a slice instead of recursing, so the depth of the graph doesn't grow the goroutine stack.
The order of the components and of the vertices in them is stable: it only depends on the order of the vertices and edges in the graph, so a graph built the same way gives the same result on every run.
func HasCycle ¶ added in v0.9.0
func HasCycle[T comparable](g gograph.Graph[T]) bool
HasCycle reports whether g contains a cycle. Directed graphs are checked using their edge directions. In undirected graphs, the two stored directions of an edge are treated as one edge. A self-loop is a cycle.
A graph created with gograph.Acyclic returns false without a search. A graph from gograph.New takes O(V+E) time and O(V) extra space, and the search stops at the first cycle it finds. Any other graph is read through its methods. It panics if g is nil.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[int]()
_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(3))
fmt.Println(connectivity.HasCycle(g))
_, _ = g.AddEdge(g.GetVertexByID(3), g.GetVertexByID(1))
fmt.Println(connectivity.HasCycle(g))
}
Output: false true
func Kosaraju ¶
func Kosaraju[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
Kosaraju implements Kosaraju's Algorithm. It performs a depth-first search of the graph to create a stack of vertices, and then performs a second depth-first search on the transposed graph to identify the strongly connected components.
The function returns a slice of slices, where each slice represents a strongly connected component and contains the vertices that belong to that component. The vertices are the ones stored in g, not copies.
The order of the components and of the vertices in them is stable: it only depends on the order of the vertices and edges in the graph, so a graph built the same way gives the same result on every run.
func Tarjan ¶
func Tarjan[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
Tarjan is the entry point to the algorithm. It initializes the index, stack, and sccs variables and then loops through all the vertices in the graph. It returns a slice of vertices' slice, where each inner slice represents a strongly connected component of the graph.
The order of the components and of the vertices in them is stable: it only depends on the order of the vertices and edges in the graph, so a graph built the same way gives the same result on every run.
Types ¶
type Condensation ¶ added in v0.9.0
type Condensation[T comparable] struct { // Graph has one vertex per strongly connected component, labeled 0 to // n-1 so that every edge goes from a lower label to a higher one. It is // directed and has no cycles. Graph gograph.Graph[int] // Members has the vertices of each component, indexed by component // label, as the original graph's own vertex pointers. Members [][]*gograph.Vertex[T] // ComponentOf maps the label of each original vertex to the label of // its component. ComponentOf map[T]int }
Condensation is a graph with one vertex per strongly connected component of another graph. It never has a cycle, so the functions that need a DAG, such as gograph.TopologySort, work on it.
func Condense ¶ added in v0.9.0
func Condense[T comparable](g gograph.Graph[T], opts ...CondenseOption[T]) (*Condensation[T], error)
Condense replaces each strongly connected component of g with a single vertex. A component with more than one member is a group of vertices that depend on each other, for example modules that have to be upgraded in one step.
There is an edge from component a to component b if at least one edge of g goes from a member of a to a member of b. Edges inside a component, including self-loops, are dropped. Without options, Condensation.Graph is unweighted and its vertices have no weight.
The components are numbered in topological order, and the members of each component follow the order of GetAllVertices. The result is stable: a graph built the same way gives the same result on every run.
Condensation.Graph is created with gograph.Directed and not gograph.Acyclic, since an acyclic graph sorts itself on every AddEdge. It has no cycles all the same.
It runs Tarjan once and takes O(V + E) time. It returns gograph.ErrNotDirected for undirected graphs.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/connectivity"
)
func main() {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"api", "auth"},
{"auth", "users"},
{"users", "auth"},
{"users", "db"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
c, err := connectivity.Condense(g)
if err != nil {
fmt.Println(err)
return
}
// the condensation has no cycles, so it can be sorted
order, err := gograph.TopologySort(c.Graph)
if err != nil {
fmt.Println(err)
return
}
for _, comp := range order {
var members []string
for _, v := range c.Members[comp.Label()] {
members = append(members, v.Label())
}
fmt.Println(comp.Label(), members)
}
}
Output: 0 [api] 1 [auth users] 2 [db]
type CondenseOption ¶ added in v0.9.0
type CondenseOption[T comparable] func(*condenseOptions[T])
CondenseOption configures Condense.
func WithComponentWeight ¶ added in v0.9.0
func WithComponentWeight[T comparable](fn func(members []*gograph.Vertex[T]) float64) CondenseOption[T]
WithComponentWeight sets the weight of each component vertex, for example the sum of the weights of its members. fn gets the members in the same order as Condensation.Members.
func WithCrossingWeight ¶ added in v0.9.0
func WithCrossingWeight[T comparable](fn func(crossing []*gograph.Edge[T]) float64) CondenseOption[T]
WithCrossingWeight sets the weight of each edge between two components from the original edges that cross between them, for example their minimum or their sum. fn gets the crossing edges in the order of AllEdges. With this option, Condensation.Graph is weighted.
Source Files