Implement pseudo-diameter computation #1223

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:

  1. 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).
  2. 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.
  3. Convert this program into an igraph function, complete with error checking, documentation, unit tests.
1 Like

Yes, I will start by trying to implement the algorithm in a generic manner.

Thank you.

Hi @iosonofabio,

I would really appreciate your help with this project too.

Thanks,
Kay

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 :wink:

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.