This is a really cool project and the doc comments are great too! Why the need for the simorgh branch though?

[jackoconnordev]

Preamble

Hi @maminrayej, reading through this project has been an education in modularity and abstraction. I particularly liked separating abstract graphs and graph storage implementations into separate modules. I've been reading up on software design principles and this is another concrete example I now have in my head of the dependency-inversion principle being good (high-level/low-level modules should be separated by an interface) alongside ORMs like Sequelize. I can also see how traits play nicely with good design principles.

I'm hoping to do a basic rust version of PGMpy someday. Graph algorithms are essential for this and your crate is easily the most digestible example of implementing graphs in Rust I've seen so far, so thank you!

An actual question

Looking through the simorgh branch I see the storage module is gone and is replaced with:

/// New storage trait
pub trait Storage {
    type Node: Id<Id = NodeId>;
    type Edge: Id<Id = EdgeId>;
    type Dir: Direction;
    type Map: IdMap;

    fn idmap(&self) -> Self::Map;
}

Do you think you could elaborate/document somewhere on what it is you didn't like about the module structure from the main branch and why storage not having its own dedicated module is preferable to you?

Also this could be a silly question but is there just one storage implementation based on idmap now or is it still possible to have different implementations of graph storage like an adjacency list or adjacency matrix?

[maminrayej]

Thank you for your kind words @jackoconnordev :)

Do you think you could elaborate/document somewhere on what it is you didn't like about the module structure from the main branch and why storage not having its own dedicated module is preferable to you?

storage module in not implemented in the simorgh branch yet. I was bored with implementing storage again, so I decided to implement the algo module first.

Also this could be a silly question but is there just one storage implementation based on idmap now or is it still possible to have different implementations of graph storage like an adjacency list or adjacency matrix?

Yes it's still possible to implement your own storage solution. Each storage can have it's own implementation of the IdMap trait. For example let's say you have an adjacency matrix with non-stable node ids (you reorder columns/rows after node deletion). Your IdMap implementation could be a simple identity function since you can use indices of the matrix as node ids. But, in a adjacency map you don't have the same luxury so you have to actually map node ids to continuous integers using a hash map for example. So basically each storage can choose the best way to map node ids.

Below is my rant about the current design and goal

What I have in mind in terms of abstraction is something likes this now:

.------------.
| Algorithms |
'------------'
       ^
       |
.-----------------.
| Provide  | Prop |
'-----------------'
       ^
       |
.--------------.
|     View     |
'--------------'
       ^
       |
.--------------.
|    Graph     |
'--------------'
       ^
       |
.------------.
|   Storage  |
'------------'

You have the low level storage implementations like adjacency matrix, list, map, and so on. On top of them, you can create graphs like a simple graph, DAG, and so on. On top of a graph, you can create a view. A view is basically how you perceive the structure of the underlying graph. For example, you can view a directed graph as undirected or vice versa. You can filter some nodes and edges that you don't want to see temporarily, for example the result returned from a shortest path algorithm is a view of the input graph that only exposes the shortest path and hides other nodes and edges. A view itself implements the provide layer so you can again run algorithms on it like DFS for example. The provide layer is the glue that connects the implementation to the algorithms. I'm not still quite sure about Prop. Its basic idea is algorithms like flow analysis that require an edge to have a capacity and flow. So algorithms can declare that they expect some properties from the nodes and edges of a graph to be able to run. You can imagine that a view can add props to a barebone graph. So basically All these constructs come together and (should) play nicely in order for the storage to reach a certain algorithm.

To be honest, simorgh is pretty close to what I've had in mind about what prepona should look like. It misses some algorithms like VF2 that are a little bit painful to implement, but it has the basics. I wish I had the time to work on it the many hours that I'd really liked. But at this point in my life I have very few hours to myself to be able to work on my projects.

Again, thanks for your heartwarming comment.

[jackoconnordev]

Thanks so much for your detailed answer @maminrayej! I really appreciate it and definitely feel like I've learned something today 😁