Hello everyone,
My name is Gulshan Kumar, and I am a Computer Science & Engineering undergraduate at IIT Bombay. I am excited to contribute to igraph in GSoC 2025!.
I have a strong background in C/C++ programming and computational geometry. My past projects involve implementing graph algorithms and reinforcement learning, which I believe will be beneficial for my contribution to igraph.
For GSoC, I am particularly interested in porting spatial network functions from IGraph/M to igraph’s C core, implementing Delaunay triangulation and k-D trees, and exposing these features in Python (I may learn R if needed).
I am currently exploring computational geometry concepts and igraph’s internal C implementation to prepare for this project.
Thank You
Welcome to the igraph community @Gulshan_Kumar.
This is indeed a good start. Please see point 1 in what I wrote in another thread:
To clarify, the primary goal would be to implement the computation of the proximity graphs, which is already done in IGraph/M. Please see here: IGraph/M Documentation These rely on Delaunay triangulations and nearest neighbour search algorithms (such as k-D trees), but ideally we won’t implement these from scratch. Instead, we should try to find existing libraries that are not too heavyweight and whose licenses are reasonably compatible with igraph. If we are forced to use a library with a divergent license, this may need to be an optional (togglable) feature.
Do you have access to and some experience with Mathematica / the Wolfram Language? This is not strictly required, but would make it easier to read the existing implementation.
Hi @szhorvat , I have now got an idea of Igraph Core C and Igraph/M after some contribution on github. I have also learnt some basic R and familarized with reading Mathematica Code. I have also read some of the theory and found it interesting.
I have seen some of the implementaion in Igraph/M like Delaunay triangulation and Beta skeleton graphs.
Now I want to make a proposal for the project: Spatial network analysis capabilities for igraph.
Please suggest what should I write for a good proposal?
The main goal for this project is to port the β-skeleton implementation from IGraph/M to the igraph C library. You can see the available functions here:
The implementations are not complicated, but they rely on two tools that are not present in igraph: (1) Delaunay triangulations in both 2D and 3D (higher-dimensional generalizations may be implemented) IGraph/M uses Mathematica’s built-in features for this (2) a nearest neighbour library, e.g. something based on k-D trees. IGraph/M uses nanoflann for this.
We need to find such libraries whose license is reasonably compatible with igraph, and which are also performant. These can be set up as optional dependencies. The triangle and TetGen libraries are good, but I believe the license won’t work. Finding suitable libraries is also part of the task.
Hello @szhorvat,
Regarding the libraries we might use for spatial data structures and Delaunay triangulation in igraph:
I believe we could also consider using nanoflann in igraph, although this would require writing the related portions in C++, since nanoflann is a C++ only library.
For Delaunay triangulation, I have explored several library options:
One compatible, permissively licensed library is delaunator-cpp. It is under the MIT license and works well for 2D point sets, but unfortunately does not support 3D triangulations.
Yes, I’ve verified that their licenses (non-permissive/GPL-style) are indeed incompatible with igraph’s licensing model.
I found two alternatives under a BSD license that could be of interest:
- Voro++: A C++ library for Voronoi tessellations and power diagrams. While it does not directly offer Delaunay triangulations, it could potentially be adapted or used alongside other tools.
- Stellar: A tetrahedral mesh improvement program developed at UC Berkeley. It is written in pure ANSI C, and is distributed under the BSD license. It offers robust tools for 3D Delaunay triangulations and mesh quality improvement. I believe this library may serve our needs well for 3D spatial structures. Please let me know your thoughts.
Hi @szhorvat ,
I’ve shared my initial draft of the project proposal via Google Drive (you should have received a notification — please let me know if not). I’d really appreciate any feedback you might have on how I can improve it, especially regarding areas that may need more clarity or detail.
Looking forward to hearing your thoughts!
Hi, my name is Arnór, I am working on a masters in computer science and I am interested in spatial networks.
I want to contribute to igraph for google summer of code 2025, specifically Beta skeletons and delaunay triangulations, but also potentially other spatial graphs if there is time and the need arises. I know that they are implemented in the mathematica interface but I don’t care much for mathematica, so having it available for other IGraph interfaces would be a great help.
I have experience with C and python development and am willing to learn R for porting to that interface.