Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Graph traversal with Networkx (Python)

I'm playing a bit with Networkx to manage a graph of dependencies. Let's say I have this Graph which each letter represent a server

>>> G = nx.Graph()
>>> G.add_edge("A","B")
>>> G.add_edge("A","H")
>>> G.add_edge("H","C")
>>> G.add_edge("B","C")
>>> G.add_edge("B","D")

           A
         /   \
       H       B
     /        /  \
   C         C     D 

So here we can see that before starting A we need to start H and B and to start H we need to start C and then to start B wee need to start C and D

By fiddling a bit with Networkx I found that I can get that by doing a dfs traversal

print nx.dfs_successors(G,"A")
{A:[H,B], H:[C], B:[D] }

But I have a problem with that method. As you can see when there is two same letter in the tree, Networkx only chose to put one of them in the final structure (which is correct) But I need to have the complete structure How can I force Networkx to add in the structure B:[D,C] ??

I want to precise that by doing

>>> nx.dfs_successors(G,"B")
{'B': ['C', 'D']}

So everything is "Internally" correct, it's just the dfs_successors that displays it not in the way I wish.

Thank you

like image 768
Johny19 Avatar asked Jan 10 '13 13:01

Johny19


People also ask

Can NetworkX handle large graphs?

For NetworkX, a graph with more than 100K nodes may be too large. I'll demonstrate that it can handle a network with 187K nodes in this post, but the centrality calculations were prolonged. Luckily, there are some other packages available to help us with even larger graphs.

What type of graph is provided to NetworkX?

Multigraphs. NetworkX provides classes for graphs which allow multiple edges between any pair of nodes. The MultiGraph and MultiDiGraph classes allow you to add the same edge twice, possibly with different edge data. This can be powerful for some applications, but many algorithms are not well defined on such graphs.


2 Answers

Taking your code, your graph doesn't come out as you'd expect. If you do:

import pylab as p
import networkx as nx

G = nx.Graph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

nx.draw(G)
p.show()

you will see your graph as: Graph

This is due to the logic of G.add_edge("A", "B"):

  1. If G has no node of id "A", add it.
  2. If G has no node of id "B", add it.
  3. Connect "A" to "B" with a new edge.

Thus, you only create five nodes, not six as in your picture.

Edit Networkx can take any hashable as value for a node, and in the graph it uses str(node) to label each circle. So we can simply define our own Node class (which you maybe want to call Server?) and give it the desired behavior.

import pylab as p
import networkx as nx


class Node(object):
    nodes = []

    def __init__(self, label):
        self._label = label

    def __str__(self):
        return self._label

nodes = [Node(l) for l in ["A","B","C","C","D","H"]]
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)]

G = nx.Graph()
for i,j in edges:
    G.add_edge(nodes[i], nodes[j])

nx.draw(G)
p.show()

gives us New graph and so what you wanted.

like image 117
Thorsten Kranz Avatar answered Oct 19 '22 23:10

Thorsten Kranz


I think what you are looking for is a topological sort http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

This only works if you have a DAG (directed acyclic graph). If so you can draw the tree you want too - like this:

import uuid
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

order =  nx.topological_sort(G)
print "topological sort"
print order

# build tree
start = order[0]
nodes = [order[0]] # start with first node in topological order
labels = {}
print "edges"
tree = nx.Graph()
while nodes:
    source = nodes.pop()
    labels[source] = source
    for target in G.neighbors(source):
        if target in tree:
            t = uuid.uuid1() # new unique id
        else:
            t = target
        labels[t] = target
        tree.add_edge(source,t)
        print source,target,source,t
        nodes.append(target)

nx.draw(tree,labels=labels)
plt.show()

The drawing uses a label mapping to map the ids of the node to the original labels.

enter image description here

like image 21
Aric Avatar answered Oct 19 '22 22:10

Aric