# 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.

- [x] model (bi-)directional graphs
    - [x] representation: `(v, adj(e))` (adjacency list approach)
    - [ ] representation: `(v, adj(e), w(e))` (weighted edges)
    - [x] macro: `graph! { ... }` (from adjacency list)
- [x] pathfinding
    - [x] breadth-first search
    - [x] depth-first search
    - [ ] bidirectional search
    - [ ] a* search
    - [x] dijkstra's algorithm (bidirectionally?)
- [ ] general concepts
    - [x] hamilton paths and cycles
    - [x] 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)