dalicious.algorithm.graph

This module contains graph algorithms.

Members

connectedComponents size_t[][] connectedComponents(size_t n): Calculate connected components of the graph defined by hasEdge.
dagSingleSourceShortestPaths auto dagSingleSourceShortestPaths(size_t start, size_t n): Calculate all shortest paths in DAG starting at start. The functions hasEdge and weight define the graphs structure and weights, respectively. Nodes are represented as size_t integers. The graph must be directed and acyclic (DAG).
hopcroftKarp count_t hopcroftKarp(nodes_u_it U, nodes_v_it V, adjacency_t adjacency)
count_t hopcroftKarp(nodes_u_it U, nodes_v_it V, adjacency_t adjacency, node_t[node_t] pairU, node_t[node_t] pairV): Takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint.
topologicalSort auto topologicalSort(size_t n): Sort nodes of a DAG topologically. The graph structure is defined by hasEdge and n. Nodes are represented as size_t integers. The graph must be directed and acyclic (DAG).

HopcroftKarpImpl struct HopcroftKarpImpl(node_t, nodes_u_it, nodes_v_it, adjacency_t, count_t = size_t): Undocumented in source.
SingleSourceShortestPathsSolution struct SingleSourceShortestPathsSolution(weight_t)