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.BFSWithDepth
  • Depth-first: Follows one path as deep as it can, then backs up to the last vertex with a neighbor left to try, and sorts every edge it meets into four kinds. traverse.DFSEvents
  • Closest-first: Visits vertices in order of their distance from a start vertex, nearest first. traverse.ClosestFirst
  • 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. traverse.Topological
  • 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
  • Dynamic topological sort: Keeps a topological order while edges are added one at a time, and moves only the vertices between the two ends of an edge that points backward. Graph.AddEdge

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.DijkstraPaths
  • A*: Finds the quickest route from one vertex to another, looking first where a guess of the time left says the goal is, so it settles far fewer vertices than Dijkstra. path.AStar
  • Bidirectional search: Finds the quickest route from one vertex to another by searching forward from the start and backward from the goal at once, until the two searches meet. path.Bidirectional
  • k shortest paths: Finds the k quickest routes from one vertex to another that don't repeat a vertex, quickest first, the way a navigation app offers a few routes. path.KShortest
  • Beam search: Looks for a route from one vertex to another while keeping only the few best partial paths at each step, so its memory and time stay bounded, at the cost of sometimes missing the best route. path.Beam
  • 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.BellmanFordPaths
  • 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
  • Diff: Compares two graphs and returns the vertices, edges, weights and edge labels that differ, matching vertices by label. gograph.Diff

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
  • Find a cycle: Returns the vertices of one cycle in order: the first one a depth-first search closes with an edge back to its search path. connectivity.FindCycle
  • Bridges and articulation points: Finds the edges and the vertices whose loss splits an undirected graph into more pieces, its single points of failure, from one depth-first search. gograph.UndirectedCuts

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 a 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