{"gographVersion":"v0.8.2","categories":[{"id":"traversal","name":"Traversal","summary":"Visit every vertex you can reach, in a defined order."},{"id":"ordering","name":"Ordering","summary":"Put the vertices of a graph without cycles in an order that respects every edge."},{"id":"shortest-paths","name":"Shortest paths","summary":"Find the shortest distances on weighted maps, including maps with negative weights."},{"id":"dependencies","name":"Dependencies","summary":"Find what a vertex depends on, what depends on it, and what a change affects."},{"id":"connectivity","name":"Connectivity","summary":"Find groups of vertices that can all reach each other."},{"id":"partitioning","name":"Partitioning","summary":"Split a graph into cliques, communities or cuts."}],"algorithms":[{"id":"bfs","name":"Breadth-first","fullName":"Breadth-first search","category":"traversal","summary":"Visits vertices level by level from a start vertex.","complexity":"O(V+E)","function":"traverse.NewBreadthFirstIterator","templates":[{"id":"home-network","name":"Home network","vertices":6,"edges":6},{"id":"office-network","name":"Office network","vertices":13,"edges":16},{"id":"maze","name":"Maze","vertices":30,"edges":31},{"id":"karate-club","name":"Karate club","vertices":34,"edges":78},{"id":"campus-network","name":"Campus network","vertices":100,"edges":114}]},{"id":"dfs","name":"Depth-first","fullName":"Depth-first search","category":"traversal","summary":"Follows one path as deep as it can, then continues from the most recently found vertex.","complexity":"O(V+E)","function":"traverse.NewDepthFirstIterator","templates":[{"id":"home-network","name":"Home network","vertices":6,"edges":6},{"id":"office-network","name":"Office network","vertices":13,"edges":16},{"id":"maze","name":"Maze","vertices":30,"edges":31},{"id":"karate-club","name":"Karate club","vertices":34,"edges":78},{"id":"campus-network","name":"Campus network","vertices":100,"edges":114}]},{"id":"closest-first","name":"Closest-first","fullName":"Closest-first traversal","category":"traversal","summary":"Visits vertices in order of their distance from a start vertex, nearest first.","complexity":"O(E log V)","function":"traverse.NewClosestFirstIterator","templates":[{"id":"school-run","name":"School run","vertices":6,"edges":13},{"id":"delivery-area","name":"Delivery area","vertices":8,"edges":12},{"id":"downtown-grid","name":"Downtown grid","vertices":20,"edges":60},{"id":"one-way-city","name":"One-way city","vertices":45,"edges":88},{"id":"metro-region","name":"Metro region","vertices":100,"edges":346}]},{"id":"random-walk","name":"Random walk","fullName":"Random walk","category":"traversal","summary":"Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.","complexity":"O(steps × degree)","function":"traverse.NewRandomWalkIterator","templates":[{"id":"service-calls","name":"Microservice calls","vertices":9,"edges":15},{"id":"import-cycles","name":"Import cycles","vertices":18,"edges":30},{"id":"linked-pages","name":"Linked web pages","vertices":40,"edges":114},{"id":"web-crawl","name":"Web crawl","vertices":100,"edges":274}]},{"id":"topological-sort","name":"Topological sort","fullName":"Topological sort","category":"ordering","summary":"Puts the vertices of a graph without cycles in an order where every edge points forward, taking vertices in the order they become ready.","complexity":"O(V+E)","function":"gograph.TopologySort","note":"traverse.NewTopologicalIterator returns the same order one vertex at a time, because it calls gograph.TopologySort.","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"stable-topological-sort","name":"Stable topological sort","fullName":"Stable topological sort","category":"ordering","summary":"Puts the vertices of a graph without cycles in an order where every edge points forward, taking the ready vertex that comes first alphabetically.","complexity":"O((V+E) log V)","function":"gograph.StableTopologySort","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"dijkstra","name":"Dijkstra","fullName":"Dijkstra's algorithm","category":"shortest-paths","summary":"Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.","complexity":"O((V+E) log V)","function":"path.Dijkstra","templates":[{"id":"new-york","name":"New York streets","vertices":295,"edges":669,"place":"New York"},{"id":"london","name":"London streets","vertices":274,"edges":598,"place":"London"},{"id":"san-francisco","name":"San Francisco streets","vertices":248,"edges":548,"place":"San Francisco"},{"id":"rasht","name":"Rasht streets","vertices":298,"edges":568,"place":"Rasht"},{"id":"school-run","name":"School run","vertices":6,"edges":13},{"id":"delivery-area","name":"Delivery area","vertices":8,"edges":12},{"id":"downtown-grid","name":"Downtown grid","vertices":20,"edges":60},{"id":"one-way-city","name":"One-way city","vertices":45,"edges":88},{"id":"metro-region","name":"Metro region","vertices":100,"edges":346}]},{"id":"bellman-ford","name":"Bellman-Ford","fullName":"Bellman-Ford algorithm","category":"shortest-paths","summary":"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.","complexity":"O(V·E)","function":"path.BellmanFord","templates":[{"id":"school-run","name":"School run","vertices":6,"edges":13},{"id":"fx-majors","name":"Major currencies","vertices":6,"edges":20},{"id":"delivery-area","name":"Delivery area","vertices":8,"edges":12},{"id":"fx-arbitrage","name":"Arbitrage loop","vertices":8,"edges":24},{"id":"one-way-city","name":"One-way city","vertices":45,"edges":88}]},{"id":"floyd-warshall","name":"Floyd-Warshall","fullName":"Floyd-Warshall algorithm","category":"shortest-paths","summary":"Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.","complexity":"O(V³)","function":"path.FloydWarshall","templates":[{"id":"fx-majors","name":"Major currencies","vertices":6,"edges":20},{"id":"delivery-area","name":"Delivery area","vertices":8,"edges":12},{"id":"downtown-grid","name":"Downtown grid","vertices":20,"edges":60},{"id":"one-way-city","name":"One-way city","vertices":45,"edges":88}]},{"id":"descendants","name":"Descendants","fullName":"DAG descendants","category":"dependencies","summary":"Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.","complexity":"O(V+E)","function":"dag.Descendants","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"ancestors","name":"Ancestors","fullName":"DAG ancestors","category":"dependencies","summary":"Finds every vertex that can reach a vertex, such as all the courses one course needs first.","complexity":"O(V+E)","function":"dag.Ancestors","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"affected","name":"Affected","fullName":"DAG affected vertices","category":"dependencies","summary":"Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.","complexity":"O(V+E)","function":"dag.Affected","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"transitive-reduction","name":"Transitive reduction","fullName":"Transitive reduction","category":"dependencies","summary":"Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.","complexity":"O(V(V+E))","function":"path.TransitiveReduction","templates":[{"id":"build-pipeline","name":"Build pipeline","vertices":7,"edges":9},{"id":"course-prereqs","name":"Course prerequisites","vertices":14,"edges":18},{"id":"spreadsheet","name":"Spreadsheet formulas","vertices":25,"edges":41},{"id":"go-mod-graph","name":"Go module graph","vertices":62,"edges":116},{"id":"monorepo-build","name":"Monorepo build","vertices":100,"edges":266}]},{"id":"tarjan","name":"Tarjan","fullName":"Tarjan's SCC algorithm","category":"connectivity","summary":"Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.","complexity":"O(V+E)","function":"connectivity.Tarjan","templates":[{"id":"service-calls","name":"Microservice calls","vertices":9,"edges":15},{"id":"import-cycles","name":"Import cycles","vertices":18,"edges":30},{"id":"linked-pages","name":"Linked web pages","vertices":40,"edges":114},{"id":"web-crawl","name":"Web crawl","vertices":100,"edges":274}]},{"id":"kosaraju","name":"Kosaraju","fullName":"Kosaraju's SCC algorithm","category":"connectivity","summary":"Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.","complexity":"O(V+E)","function":"connectivity.Kosaraju","templates":[{"id":"service-calls","name":"Microservice calls","vertices":9,"edges":15},{"id":"import-cycles","name":"Import cycles","vertices":18,"edges":30},{"id":"linked-pages","name":"Linked web pages","vertices":40,"edges":114},{"id":"web-crawl","name":"Web crawl","vertices":100,"edges":274}]},{"id":"gabow","name":"Gabow","fullName":"Gabow's SCC algorithm","category":"connectivity","summary":"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.","complexity":"O(V+E)","function":"connectivity.Gabow","templates":[{"id":"service-calls","name":"Microservice calls","vertices":9,"edges":15},{"id":"import-cycles","name":"Import cycles","vertices":18,"edges":30},{"id":"linked-pages","name":"Linked web pages","vertices":40,"edges":114},{"id":"web-crawl","name":"Web crawl","vertices":100,"edges":274}]},{"id":"maximal-cliques","name":"Maximal cliques","fullName":"Bron-Kerbosch maximal cliques","category":"partitioning","summary":"Finds every group of vertices that are all adjacent to each other and can't take one more vertex.","complexity":"O(3^(V/3))","function":"partition.MaximalCliques","templates":[{"id":"friend-groups","name":"Friend groups","vertices":12,"edges":21},{"id":"office-network","name":"Office network","vertices":13,"edges":16},{"id":"karate-club","name":"Karate club","vertices":34,"edges":78},{"id":"campus-network","name":"Campus network","vertices":100,"edges":114}]},{"id":"girvan-newman","name":"Girvan-Newman","fullName":"Girvan-Newman algorithm","category":"partitioning","summary":"Splits an undirected graph into k communities by removing, one at a time, the edge that the most shortest paths cross.","complexity":"O(E·V·(V+E))","function":"partition.GirvanNewman","note":"gograph keeps each undirected edge once per direction and gives each direction half of the edge's betweenness, so the scores shown are half the usual values.","templates":[{"id":"friend-groups","name":"Friend groups","vertices":12,"edges":21},{"id":"office-network","name":"Office network","vertices":13,"edges":16},{"id":"karate-club","name":"Karate club","vertices":34,"edges":78},{"id":"campus-network","name":"Campus network","vertices":100,"edges":114}]},{"id":"randomized-k-cut","name":"Randomized k-cut","fullName":"Karger's randomized k-cut","category":"partitioning","summary":"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.","complexity":"O(V·E)","function":"partition.RandomizedKCut","note":"gograph picks the edges to contract at random, so the cut can change each time the server restarts.","templates":[{"id":"friend-groups","name":"Friend groups","vertices":12,"edges":21},{"id":"office-network","name":"Office network","vertices":13,"edges":16},{"id":"maze","name":"Maze","vertices":30,"edges":31},{"id":"karate-club","name":"Karate club","vertices":34,"edges":78}]}]}