See every step gograph takes.
Pick an algorithm and a graph, then step through each decision it makes. Every run, result and timing on this site comes from the gograph Go library running on this server.
Read the code, or add gograph to a module with go get github.com/hmdsefi/gograph.
Traversal
Visit every vertex you can reach, in a defined order.
- Breadth-first: Visits vertices level by level from a start vertex.
traverse.NewBreadthFirstIterator - Depth-first: Follows one path as deep as it can, then continues from the most recently found vertex.
traverse.NewDepthFirstIterator - Closest-first: Visits vertices in order of their distance from a start vertex, nearest first.
traverse.NewClosestFirstIterator - Random walk: Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.
traverse.NewRandomWalkIterator
Ordering
Put the vertices of a graph without cycles in an order that respects every edge.
- Topological sort: Puts the vertices of a graph without cycles in an order where every edge points forward, taking vertices in the order they become ready.
gograph.TopologySort - Stable topological sort: Puts the vertices of a graph without cycles in an order where every edge points forward, taking the ready vertex that comes first alphabetically.
gograph.StableTopologySort
Shortest paths
Find the shortest distances on weighted maps, including maps with negative weights.
- Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
path.Dijkstra - Bellman-Ford: Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.
path.BellmanFord - Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.
path.FloydWarshall
Dependencies
Find what a vertex depends on, what depends on it, and what a change affects.
- Descendants: Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.
dag.Descendants - Ancestors: Finds every vertex that can reach a vertex, such as all the courses one course needs first.
dag.Ancestors - Affected: Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.
dag.Affected - Transitive reduction: Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.
path.TransitiveReduction
Connectivity
Find groups of vertices that can all reach each other.
- Tarjan: Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.
connectivity.Tarjan - Kosaraju: Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
connectivity.Kosaraju - Gabow: Finds the strongly connected components of a directed graph with one depth-first search and two stacks, without the lowlink values of Tarjan's algorithm.
connectivity.Gabow
Partitioning
Split a graph into cliques, communities or cuts.
- Maximal cliques: Finds every group of vertices that are all adjacent to each other and can't take one more vertex.
partition.MaximalCliques - Girvan-Newman: Splits an undirected graph into k communities by removing, one at a time, the edge that the most shortest paths cross.
partition.GirvanNewman - Randomized k-cut: Splits an undirected graph into k groups by merging the ends of random edges until k groups are left, and cuts the edges between them.
partition.RandomizedKCut