GTRS - graph theory in rust

implementations of graph-theoretical algorithms and utilities in rust.

capabilities

NOTE: this library isn't complete at this point. only checked off points are implemented.

• model (bi-)directional graphs
  • representation: (v, adj(e)) (adjacency list approach)
  • representation: (v, adj(e), w(e)) (weighted edges)
  • macro: graph! { ... } (from adjacency list)
• pathfinding
  • breadth-first search
  • depth-first search
  • bidirectional search
  • a* search
  • dijkstra's algorithm (bidirectionally?)
• general concepts
  • hamilton paths and cycles
  • euler paths and cycles (hierholzer's algorithm)
  • chromatic number (graph coloring), DSATUR, edge coloring
  • connectivity, strongly connected components
    • kosaraju's algorithm
    • tarjan's algorithm
  • cliques
  • vertex degree, degeneracy
  • (sub-)graph isomorphism
• matchings
  • hopcroft-karp algorithm (bipartite matching)
  • blossom algorithm
  • hungarian algorithm
• minimum spanning trees
  • prim's algorithm
  • kruskal's algorithm
  • borůvka's algorithm
• flow-graphs (max-flow/min-cut)
  • ford-fulkerson algorithm (edmonds-karp)
  • dinic's algorithm
  • push relabel algorithm (preflow-push)
• all pairs shortest paths
  • floyd-warshall algorithm
  • bellman-ford algorithm
  • johnson's algorithm (sparse graphs)
• k shortest paths
  • yen's algorithm

todo

• make vertex identities separate from vertex data
• if useful, add (V, inc(E)) representation (incidence matrix)
• improve allocation size heuristic for queue, visited set, etc in search algos
• improve iterator implementation (allow for &vert in &g)
• improve dijkstra (BinaryHeap::retain might be slow)
• improve dijkstra (make bidirectional)