CODEWITHSUNDEEP
pythongraphnetworkx
mcbetz
mcbetz

Reputation: 2379

How to check whether two nodes are connected?

I have a NetworkX graph with four nodes (a,b,c,d) which are partially connected. How can I check whether two nodes are adjacent? For example: How could I assert that a and d are not adjacent?

import networkx as nx
G=nx.Graph()
G.add_edge('a','b',weight=1)
G.add_edge('a','c',weight=1)
G.add_edge('c','d',weight=1)

I tried the following, but failed:

nx.is_connected(G) # I assume it checks whether edges are connected at all
nx.connected_components(G) # outputs an object that I can make no use of

Upvotes: 23

Views: 25974

Answers (3)

Aric
Aric

Reputation: 25289

This is the recommended way:

import networkx as nx
G=nx.Graph()
G.add_edge('a','b',weight=1)
G.add_edge('a','c',weight=1)
G.add_edge('c','d',weight=1)

print(G.has_edge('a','d'))  # False
print('d' in G['a']) # False, faster
print('d' not in G['a']) # True

Upvotes: 13

frhyme
frhyme

Reputation: 1036

I think you ask about "how to know two nodes are reachable each other" It can be solve by this code. 

networkx.algorithms.descendants(G, target_nodes)

it returns all reachable nodes from target_nodes in G.

Upvotes: 7

mdml
mdml

Reputation: 22882

One way to check whether two nodes are connected with NetworkX is to check whether a node u is a neighbor of another node v.

>>> def nodes_connected(u, v):
...     return u in G.neighbors(v)
... 
>>> nodes_connected("a", "d")
False
>>> nodes_connected("a", "c")
True

Note that networkx.is_connected checks whether every node in a graph G is reachable from every other node in G. This is equivalent to saying that there is one connected component in G (i.e. len(nx.connected_components(G)) == 1).

Upvotes: 21

Related Questions