this is a unity package I have been developing to have a robust graph theory toolset across my projects. It is currently in its first open source alpha version 0.0.2. The current features of the package are classes for representing directed / undirected graphs - and the special cases of trees and rooted trees. Classes for representing the components of a graph such as edges and nodes. Static classes for solving Tarjan's Strongly Connected Component on directed graphs, and for preforming Khan's Topological Sort or finding shortest paths on Directed Acyclic Graphs (called DAG's going forward). And lastly a D-ary heap data structure to test a use case of the rooted tree class.
Documentation for the package is a work in progress however it will be my primary development on this project focus over the next two weeks.
Before I go in depth into the current state of the project and my plans for it going forward, I want to state what the goals of this project is and what use cases it is designed for.
As stated above - this project is intended to be used as a graph theory toolset for game development in Unity. Its focus is on being robust and extendable so that it can be as broadly useful as possible. As such, it prioritizes robustness of systems rather than raw efficiency in its features (for example creating an entire class for edges rather than implicitly in the nodes class as a list of connected nodes). It is not intended to be a highly specialized and efficient implementation of these algorithms, but rather "efficient enough" for use on the scale of game systems - say, sparse graphs with ~10^3 nodes (I'll note that for the moment this bound is one I arrived at heuristically not rigorously).
The ultimate goals of this project is a library with the underlying logic for grid system (hex or euclidean), pathfinding, tree systems, AI state machines, or any other game system that can be represented as a set of things with some set of connections between them.
The changes identified as necessary in the code review conducted over the past two weeks have nearly all been implemented. The only change still left to do is to implement the restrictions on replacing edges in rooted trees (it should not be possible to replace an edge with one that would add a new root. This is to say that the source of the new edge must be in the connected component of the source of the old edge post-removal, and the same of the sink). The reason this has yet to be implemented is that the AbstractEdge.SwapNodes method depends on the TryReplaceEdge method to complete its work, but at intermediary stages of swapping two nodes on a graph some of the edge replacements may not be legal replacements (replacing one edge may an additional root that would latter be removed be replacing a different edge). The most reasonable solution for this would be to decouple these two methods, however this may be somewhat involved as TryReplaceEdge is an already fairly complicated method that would need to be recreated within the AbstractEdge.SwapNodes method. Beyond that however the majority of the features I want to implement in the data structure of graphs themselves have been implemented at this time. There is still more work that needs to be done implementing the algorithms I would like to be able to run on these graphs (namely Dijkstra and A* since writing Dijkstra has been implented however A* has still not been), the basic structure of the graph is ready to be used in other projects that do not need particular algorithms to be implemented (such as for representations of a map seen in many rouge-like games like slay the spire or FTL).
While full documentation for the use of this library has yet to be created, the code reviews written in the previous two weeks provide a robust breakdown of the purpose of the various fields and methods found in the project. This will be acceptable documentation for now while the library is still heavily in development.