1

I'm working with AI and one of my algorithms needs to work adding and removing edges. I can do it with igraph, but my problem is: It's too slow.

If I work with two dictionaries, I can run my code in 0.2s. But with igraph, I take more than 5s. And I don't know how to improve the code performance.

The code below is a part of algorithm. This remove all edges between two lists of vertex. Anyone knows how to do this with better performance?

for vertexI in self.vertexSI:
    for vertexJ in self.vertexSJ:
        try:
            nOfLoops += 1
            edgeID = self.g.get_eid(vertexI.index, vertexJ.index)
            self.g.delete_edges(edgeID)
        except Exception as e:
            nOfErrors += 1

Thanks.

Luiz Felipe F M Costa
  • 102
  • 1
  • 12

1 Answers1

3

igraph's data structures are optimized for fast queries but not-so-fast updates. There are several data structures within an igraph graph that have to be updated / reindexed whenever you add a vertex, delete a vertex, add an edge or delete an edge. In many cases, deleting a single edge is almost as costly as deleting many of them in one single pass.

For instance, if I understood correctly, your goal above is to delete all edges that fall between two vertex groups (self.vertexSI and self.vertexSJ). You could do it like you did above, but this will be very slow since you are deleting edges one-by-one. You could speed it up already by collecting the IDs of the edges to delete first into a list, and then call self.g.delete_edges() with that list at the end. But there is an even simpler one-liner (assuming that your graph is undirected):

self.g.es.select(_between=(self.vertexSI, self.vertexSJ)).delete()
Tamás
  • 47,239
  • 12
  • 105
  • 124
  • Hi, Tamás. As you say, add/update the igraph graph is too slow, even using code line above. My solution was do all modification using just dictonaries and than recreate an new igraph object. That is perfect for me by now. Now I can do everything I want with simples structures and I can debug and using community detection functions from igraph. Thanks a lot for your answer and this awesome library! – Luiz Felipe F M Costa Feb 06 '17 at 05:14