60 lines
2.0 KiB
Markdown
60 lines
2.0 KiB
Markdown
|
|
# 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)
|
|
|