CODEWITHSUNDEEP
pythonpython-3.xigraph
flotzilla
flotzilla

Reputation: 1262

python-igraph: cannot decompose directed graph (neither STRONG nor WEAK)

Using python-igraph 0.7.1 (Python 3.4.8), I want to decompose a directed graph into all unconnected subgraphs. However, g.decompose(mode=WEAK) fails:

igraph._igraph.InternalError: Error at components.c:469: only 'IGRAPH_WEAK' is implemented, Invalid value

As the error message and google (e.g. click) tells me, STRONG decomposition is not implemented and thus expected to fail, however WEAK decomposition SHOULD work. Well, it doesn't for me!

Here's a minimal example:

from igraph import Graph, WEAK
g = Graph(directed=True)
g.add_vertices(4)
g.add_edges([(0, 1), (2, 3)])
g.decompose(mode=WEAK) # <= FAILS!

I've tried mode="weak", mode="WEAK", mode=WEAK, and mode=1, and always get the same error.

Is there maybe a workaround, i.e. a set of some other commands that lead to the same result? (Note that I'm not really familiar with graph theory, so I might miss something obvious in this regard.)

Upvotes: 1

Views: 737

Answers (1)

flotzilla
flotzilla

Reputation: 1262

Is there maybe a workaround, i.e. a set of some other commands that lead to the same result?

Indeed, I've found a workaround that seems to work:

from igraph import graph, WEAK
g = Graph(directed=True)
g.add_vertices(6)
g.vs["ts"] = [0, 1, 2, 3, 1, 2] # timesteps
g.add_edges([(0, 1), (1, 2), (2, 3), (4, 5)])

# sgs = g.decompose(mode=WEAK) # fails!
#< workaround
g.to_undirected() # we won't need 'g' anymore afterwards
sgs = g.decompose(mode=WEAK)
for sg in sgs:
    sg.to_directed(mutual=True)
    es_del = sg.es.select(lambda e: e.graph.vs[e.source]["ts"] > e.graph.vs[e.target]["ts"])
    sg.delete_edges(es_del)
#>

I convert the original directed graph to an unidirected graph, decompose it into subgraphs, convert all subgraphs back to directed graphs with edges in both directions, and remove all edges that point in the wrong direction. Of course if the original graph should be retained, we should make a copy of it first (or convert it back to a directed graph after decomposition).

Warning: Be aware that edge attributes seem to be lost when converting the directed graph to undirected! As far as I can see, they need to be restored manually (at least that's what I'm doing).

Upvotes: 1

Related Questions