title: Python networkx : edge contraction
body: <p>I have a <a href="http://networkx.github.com" rel="nofollow">NetworkX</a> graph. I would like to know how to do <a href="http://en.wikipedia.org/wiki/Edge_contraction" rel="nofollow">edge contraction</a> between multiple nodes.</p>
  
  <p>For example, if I wanted to contract X, Y and Z:</p>
  
  <pre><code>         _ node A _
         _/    |     \_
  node X --- node Y --- node Z
  </code></pre>
  
  <p>Would become</p>
  
  <pre><code>           node A 
               |     
             node XYZ (or whatever X/Y/Z)
  </code></pre>
  
  <p>Graph creation is not the problem. It works. I want to reduce the graph by merging nodes that have the same "meanings": nodes that I call "end lvl" (node name length is equal to 7) and that are linked together.</p>
  
  <p>I have found the condensation function in NetworkX so I tried to use it:</p>
  
  <pre><code># edge contraction for same nodes
  # for each node, get the links to other nodes "end lvl"
  # if there is such a link, it means that these node are
  # the sames
  #
  # copy graph
  I = G
  for n,d in G.nodes(data=True):
      if n in I.nodes():
          if len(n) == 7:
              # list of nodes adjacent to n : filter only "end lvl" nodes
              neighbors = [ node for node in I.neighbors(n) if len(node) == 7 ]
              nodes_to_merges = neighbors.append(n)
              I = nx.condensation(I,scc=nodes_to_merges)
  </code></pre>
  
  <p>The thing I got when I convert to JSON is:</p>
  
  <pre><code>{"directed": true, "graph": [], "nodes": [{"id": 0}], "links": [], "multigraph": false}
  </code></pre>
  
  <p>There is a problem as you can see...</p>
  
  <p>Reference to functions are <a href="http://networkx.github.com/documentation/" rel="nofollow">here</a>.</p>