I’ve tested a high variety of algorithms that calculates remaining edges in order to complete a graph for any given list of edges and number of vertices of complete graph n. They were written in numpy and other bunch of Python librories but it seems that none of them can’t outperform igraph.Graph.complementer method in case list of edges covers a complete graph near fully (size of edges is near n*(n-1)/2)
def ig_(n, edges: list):
#identifies a list of remaining edges:
g = ig.Graph()
g.add_vertices(range(n))
g.add_edges(edges)
c = g.complementer()
return sorted(e.tuple for e in c.es if e.source != e.target)
What an idea is hidden behind this igraph.Graph.complementer method that makes it so fast?
You can see the implementation of igraph_complementer here:
A bit of guidance to reading the code: igraph_neighbors(graph, &neis, i, ...) returns the neighbours of vertex i into the vector neisin sorted order. Then the following loop simply builds an edge list, connecting i to all vertices no in neis.
It’s quite trivial—just like the problem itself. I’m not sure why it would be faster than other implementations. Perhaps it’s just that you wrote yours in Python, while this is in C. I would expect that the performance of an implementation would heavily depend on the specific data structure used to represent the igraph. igraph currently uses an edge list that is sorted in a way that makes it very efficient to retrieve neighbours (or to convert to an ajdacency list).
