CODEWITHSUNDEEP
pythongraphnetworkx
Jack Twain
Jack Twain

Reputation: 6382

List of edges that don't exist in a networkx graph?

I have a networkx graph. With G.edges() I can get a list of all the edges. But is there a way to get a list of all other non-existing edges? So if there are 3 nodes: a, b, c and we suppose a and b are connected only, then I would like to get a list of edges that don't exist, so like this: (a,c), (c,b). Is there an easy pythonic way to do this?

Upvotes: 6

Views: 4260

Answers (3)

Ezekiel Kruglick
Ezekiel Kruglick

Reputation: 4686

There is actually a new function in networkx 1.9 called non_edges just for this purpose:

import networkx as nx
G = nx.MultiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C')])
list(nx.non_edges(G))

Out[3]:
[('A', 'C')]

I've put non_edges into a list() command here to materialize the output, as nx.non_edges is a generator. Having a generator can be very helpful when handling large graphs.

Upvotes: 12

unutbu
unutbu

Reputation: 880767

Note that Ezekiel Kruglick shows a better way to do this, now that networkx has anon_edges (and also a non-neighbors) function.

You could iterate through all possible edges using itertools.combinations, and check if it is not an edge in G using G.has_edge:

import networkx as nx
import itertools as IT
G = nx.MultiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C')])

missing = [pair for pair in IT.combinations(G.nodes(), 2)
           if not G.has_edge(*pair)]
print(missing)

yields

[('A', 'C')]

Upvotes: 5

Aric
Aric

Reputation: 25319

@unutbu's answer is likely the most efficient way. You could also generate the complement graph and emit the edges.

In [1]: import networkx as nx                                                           

In [2]: G = nx.Graph([('A', 'B'), ('B', 'C')])                                          

In [3]: print(nx.complement(G).edges()) 
[('A', 'C')]

Upvotes: 1

Related Questions