Hey,
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.
Thank you.
Hi @kay-23,
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
- compile
- install
- 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.
Cheers,
Fabio
Hey @iosonofabio,
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:
Thanks,
Kay
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.