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
  • Topological levels: Splits a graph without cycles into levels, so that every edge goes to a later level and each level can run at the same time. dag.Levels
  • Ready-set tracker: Hands out the tasks of a graph without cycles as soon as every task they depend on is done, so a slow task holds up only the tasks that wait for it. dag.NewTracker

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
  • Multi-source Dijkstra: Finds the nearest of several sources for every vertex, and the distance from it, in one search. path.DijkstraMultiSource
  • k-center: Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it. path.KCenter
  • 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
  • Critical path: Finds the longest chain of tasks that wait on each other, which sets how long the whole run takes however many tasks run in parallel. dag.CriticalPath

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
  • Condensation: Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled. connectivity.Condense
  • Connected components: Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece. gograph.ConnectedComponents
  • Cycle detection: Says whether a graph has a cycle, a way to follow its edges from a vertex back to the same vertex, and stops at the first one it finds. gograph.HasCycle

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