CODEWITHSUNDEEP
pythonigraph
Luiz Felipe F M Costa
Luiz Felipe F M Costa

Reputation: 100

Faster way to delete edge by vertex index [igraph Python]

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.

Upvotes: 1

Views: 1237

Answers (1)

Tamás
Tamás

Reputation: 48051

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()

Upvotes: 3

Related Questions