So I would like to start working on the algorithm for implementing pseudo-diameter computation.
For context, this is a followup on the discussion at https://github.com/igraph/igraph/issues/1336
Please do confirm with @iosonofabio that he would be happy to help you with this project as well, before getting started. He might suggest another one. As I said, I won’t be around during the upcoming few weeks.
Tentatively, I would suggest the following work plan:
- Understand the math. Do you know what is the graph diameter? The pseudodiameter is a way to approximate the diameter. Understand why the pseudodiameter calculation can be much faster. The key: shortest path algorithms (BFS or Dijkstra) compute shortest path lengths from one chosen vertex to all other vertices. A complete diameter calculation must run this computation for each vertex (O(V) steps) while the pseudodiameter calculation must only run it a few times (generally O(1) steps).
- Translate the algorithm on Wikipedia to a standalone program that uses igraph. All the building blocks are available in igraph. Ask questions if needed. You may prototype it with one of the high-level interfaces before starting to do it in C.
- Convert this program into an igraph function, complete with error checking, documentation, unit tests.
Yes, I will start by trying to implement the algorithm in a generic manner.
I would really appreciate your help with this project too.
Welcome to the forum. In happy to provide some advice in the form of broad design suggestions and explanation of some igraph tricks. I won’t give detailed advice step by step because I’m already busy with my own students
If you are up for a challenge - well you found one.
Like @szhorvat mentioned, recommended approach:
- clone igraph
- write a small C program that uses it
- compile and run it
- fork the repo
- learn git and pull requests
- start a new branch off “develop”
- push some commits that define any new API
- start a PR against igraph/develop
At that point we can look a little at the progress.
Thank you so much. I’m working through the list.
I was trying to compile a small program using igraph but was unable to do so. I checked the documentation, but the problem persists. The compiler is not able to find the header file “igraph.h”.
Could you perhaps point me to what I might be doing wrong?
This is the error I’m getting:
Before getting started, you need to compile and install igraph. The instructions are here: https://igraph.org/c/#startc It looks like you simply cloned the git repo, but did not compile/install the library.