Contributing your first function to igraph
We regularly receive feature requests and know many graph scientists that would like to contribute a new algorithm or function to igraph. Thanks for contributing, don't be shy with those PRs!
This page will guide you through a typical journey of adding a function to igraph.
We are friendly and responsive, so why don't you reach out on our forum and propose your idea!
We don't want to police new contributors: just trying to help so you can focus your precious brain power on the algorithm instead of the intricacies of the library.
Once your idea has been discussed a little and it is clear that the function is missing, it's time to open a draft pull request. Here's how that goes:
- Make a GitHub account if you don't have one
- Fork the igraph/igraph repo and clone the fork onto your computer.
- Pull in the igraph/develop branch to base your own work onto:
git remote add igraph https://github.com/igraph/igraph.git
git fetch igraph
git checkout -b develop
git merge igraph/develop- Create a branch with the name of your function, e.g.
git checkout -b simple_algo- Push your branch to your online fork and open the draft pull request:
git push --set-upstream origin simple_algoand then refresh the webpage of your repo and at the top you'll find a green button: Start pull request. Click on it and make sure you open:
- a draft PR
- against the igraph/develop branch
At that point, we know you've started working on it. Because it's a draft, we also know you're not done with it yet.
Each one of us codes in a different style, but typically you would start by deciding the name (which must start with igraph_) and arguments of your function, i.e. the function signature.
The include folder contains header .h files with all public function declarations. Each file describes a specific topic within the vast realm of graphs. If you find a header file that is related to your function, open it and add the declaration in a place that looks reasonable, e.g.:
DECLDIR int igraph_simple_algo(const igraph_t *graph, const igraph_integer_t initial_node, igraph_vector_long_t *res);Notice:
-
DECLDIRcomes before anything else - many functions return an
intwith an error code. In fact, if your function can fail in any way, it must return anintwith an igraph error code, and you need to use output arguments for the "real" result of the function. - input arguments that do not change are passed as
const. Atomic C values such asints are passed by value so there is no need to declare themconstexplicitly. - the result of the function is passed as a pointer after the
constarguments, and are often the last argument
It is common to push a commit (or several) during this process to discuss the function signature. Feel free to ping us on the forum when you are done or if you are unsure what signature is best!
Implementation .c files are in the src folder. Each file refers to a different topic, however there tend to be more .c files than equivalent .h header files.
If your function fits into an existing .c file, add it at the bottom. If your function is a whole new kind of fish, just make a new .c file in src.
If you are starting a new .c file, at the top of the file you must include igraph's license message:
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2020- The igraph development team
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/as well as the includes you believe you need, e.g.:
#include "igraph_structural.h"
#include "igraph_error.h"
#include "igraph_adjlist.h"Note: at this stage no exact list is expected, just wing it.
Your function signature is known at this stage, so you can start a skeleton implementation:
int igraph_simple_algo(const igraph_t *graph, igraph_integer_t initial_node, igraph_vector_long_t *res) {
/* this is a simple algorithm that computes the number of nodes and edges in the graph */
/* If everything went well, return no error */
return IGRAPH_SUCCESS;
}It is a good idea at this point to commit into the PR to signal you are ready for the actual implementation.
If your function is simple enough, you can just code the algorithm down, e.g.:
int igraph_simple_algo(const igraph_t *graph, igraph_integer_t initial_node, igraph_vector_long_t *res) {
/* this is a simple algorithm that computes the number of nodes and edges in the graph */
long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges = igraph_ecount(graph);
IGRAPH_CHECK(igraph_vector_long_resize(res, 2));
res[0] = no_of_nodes;
res[1] = no_of_edges;
/* If everything went well, return no error */
return IGRAPH_SUCCESS;
}The code need not be perfect at this stage, but please check out our tips for writing igraph code.
If your code is not very simple, you might want to separate chunks of code into auxiliary functions. In igraph, an aux function that is too specific to become a public - or API - function will not appear in the header files, but only in the .c file after (??) the function it supports.
Auxiliary non-public functions have names starting with igraph_i_ where the _i_ stands for internal, i.e. not for public use. This function should also be declared static to ensure it is not visible to other compilation units (unless you need it from another file of course). For instance we could outsource the edge calculation to a - rather silly, admittedly - aux function:
static int igraph_i_simple_algo_count_edges(const igraph_t *graph, long int *n);
int igraph_simple_algo(const igraph_t *graph, igraph_integer_t initial_node, igraph_vector_long_t *res) {
/* this is a simple algorithm that computes the number of nodes and edges in the graph */
long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges;
IGRAPH_CHECK(igraph_i_simple_algo_count_edges(graph, &no_of_edges));
IGRAPH_CHECK(igraph_vector_long_init(res, 2));
res[0] = no_of_nodes;
res[1] = no_of_edges;
/* If everything went well, return no error */
return IGRAPH_SUCCESS;
}
static int igraph_i_simple_algo_count_edges(const igraph_t *graph, long int *n) {
*n = igraph_ecount(graph);
return IGRAPH_SUCCESS;
}If your auxiliary function can fail and it returns an igraph error code, you also need to wrap it in IGRAPH_CHECK, which takes care of inspecting the returned error code and bailing out early if needed.
Committing regularly during the fleshing out is common. It gives you savepoints and can elicit useful feedback from the igraph team. Don't worry too much about bad code for now: the PR is in draft state, so we won't criticize for silliness or inaccuracies!
Public functions are documented before the function definition in the .c file using a special syntax which is described in our documentation guidelines. For instance:
/**
* \function igraph_simple_algo
* Number of nodes and edges
*
* This function finds the number of nodes and edges in the graph.
*
* \param graph The input graph.
* \param res Pointer to an uninitialized vector where the results will be stored.
* \return Error code.
*
* Time complexity: O(1), the information is stored in the graph
* object already.
*/
int igraph_simple_algo(const igraph_t *graph, igraph_integer_t initial_node, igraph_vector_long_t *res) {Auxiliary functions don't need this level of polished docs, however a block comment before their definition, outlining what the function does, is useful and recommended.
Commit to the draft PR once documentation is in place.
Good tests are essential! In igraph:
- tests sit in the
examples/testsfolder - tests are organized for the test suite via
.atfiles in thetestsfolder
First, let's add a file called igraph_simple_algo.c into examples/tests:
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2020- The igraph development team
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include <igraph.h>
#include "test_utilities.inc"
int main() {
igraph_t graph;
igraph_vector_long_t result;
/* Set default seed to get reproducible results */
igraph_rng_seed(igraph_rng_default(), 0);
/* Simple unweighted graph */
igraph_small(&graph, 10, IGRAPH_UNDIRECTED,
0, 1, 0, 2);
if (igraph_simple_algo(graph, &result)) {
printf("igraph_simple_algo() failed unexpectedly.\n");
return 1;
}
printf("N of nodes: %d, n of edges: %d.\n", result[0], result[1]);
igraph_vector_destroy(&result);
igraph_destroy(&graph);
VERIFY_FINALLY_STACK();
return 0;
}Then, we create a file igraph_simple_algo.out in the same folder that contains the expected result:
N of nodes: 10, n of edges: 2.(pay attention to the line end!).
Finally, we look through the .at files in tests and identify one that seems related and add a test block:
AT_SETUP([Simple algorithm (igraph_simple_algo): ])
AT_KEYWORDS([igraph_simple_algo])
AT_COMPILE_CHECK([tests/igraph_simple_algo.c], [tests/igraph_simple_algo.out])
AT_CLEANUP
If none of the .at files seems relevant, create a new one, but pay attention to the top part of the file. Feel free to ask the igraph team in the PR chat about this!
Commit once the tests are in place.
The implementation above is correct conceptually, but contains several bugs, e.g. memory leaks. We have a checklist for new functions which you should go over to verify that your function is memory safe and in line with the general coding style of igraph:
int igraph_simple_algo(const igraph_t *graph, const igraph_integer_t initial_node, igraph_vector_long_t *res) {
/* this is a simple algorithm that computes the number of nodes and edges in the graph */
long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges;
IGRAPH_CHECK(igraph_i_simple_algo_count_edges(graph, &no_of_edges));
IGRAPH_CHECK(igraph_vector_long_init(res, 2));
res[0] = no_of_nodes;
res[1] = no_of_edges;
/* If everything went well, return no error */
return IGRAPH_SUCCESS;
}
int igraph_i_simple_algo_count_edges(const igraph_t *graph, long int *n) {
*n = igraph_ecount(graph);
return IGRAPH_SUCCESS;
}Among other things, we need to add the function name to interfaces/functions.def to ensure the function will be visible in the R language interface.
This concludes this simple journey about adding a function to igraph.
For details or if you have suggestions on how to improve this guide, contact us on the igraph forum!