NetworkX: tous les arbres Spanning et leur poids total associé

Question

Étant donné un simple réseau de réseau non orienté comme ceci:

import networkx as nx 
from pylab import * 
import matplotlib.pyplot as plt 
%pylab inline 

ncols=3 
N=3 
G=nx.grid_2d_graph(N,N) 
labels = dict(((i,j), i + (N-1-j) * N) for i, j in G.nodes()) 
nx.relabel_nodes(G,labels,False) 
inds=labels.keys() 
vals=labels.values() 
inds=[(N-j-1,N-i-1) for i,j in inds] 
pos2=dict(zip(vals,inds)) 
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10) 
plt.axis('off') 
plt.title('grid') 
plt.show() 

Et étant donné que chaque bord a un poids correspondant à sa longueur:

#Weights 
from math import sqrt 

weights = dict() 
for source, target in G.edges(): 
    x1, y1 = pos2[source] 
    x2, y2 = pos2[target] 
    weights[(source, target)] = round((math.sqrt((x2-x1)**2 + (y2-y1)**2)),3) 

for e in G.edges(): 
    G[e[0]][e[1]] = weights[e] #Assigning weights to G.edges() 

Comment pourrait-il être possible de calculer tous les arbres couvrant dans la grille, et leur poids total associé?

NB: ceci est un cas trivial où tous les poids = 1.

Answer 1

Cela a pris beaucoup plus de temps que prévu, mais le code suivant trouve tous les arbres couvrant pour le cas général. Obtenir le poids total associé devrait être trivial, car vous avez accès à l'edgelist de chaque arbre. Ne l'utilisez pas sur de très gros arbres - même l'exemple du jouet donne 192 arbres qui s'étendent.

import numpy as np 
import matplotlib.pyplot as plt 
import networkx as nx 

def _expand(G, explored_nodes, explored_edges): 
    """ 
    Expand existing solution by a process akin to BFS. 

    Arguments: 
    ---------- 
    G: networkx.Graph() instance 
     full graph 

    explored_nodes: set of ints 
     nodes visited 

    explored_edges: set of 2-tuples 
     edges visited 

    Returns: 
    -------- 
    solutions: list, where each entry in turns contains two sets corresponding to explored_nodes and explored_edges 
     all possible expansions of explored_nodes and explored_edges 

    """ 
    frontier_nodes = list() 
    frontier_edges = list() 
    for v in explored_nodes: 
     for u in nx.neighbors(G,v): 
      if not (u in explored_nodes): 
       frontier_nodes.append(u) 
       frontier_edges.append([(u,v), (v,u)]) 

    return zip([explored_nodes | frozenset([v]) for v in frontier_nodes], [explored_edges | frozenset(e) for e in frontier_edges]) 

def find_all_spanning_trees(G, root=0): 
    """ 
    Find all spanning trees of a Graph. 

    Arguments: 
    ---------- 
    G: networkx.Graph() instance 
     full graph 

    Returns: 
    ST: list of networkx.Graph() instances 
     list of all spanning trees 

    """ 

    # initialise solution 
    explored_nodes = frozenset([root]) 
    explored_edges = frozenset([]) 
    solutions = [(explored_nodes, explored_edges)] 
    # we need to expand solutions number_of_nodes-1 times 
    for ii in range(G.number_of_nodes()-1): 
     # get all new solutions 
     solutions = [_expand(G, nodes, edges) for (nodes, edges) in solutions] 
     # flatten nested structure and get unique expansions 
     solutions = set([item for sublist in solutions for item in sublist]) 

    return [nx.from_edgelist(edges) for (nodes, edges) in solutions] 


if __name__ == "__main__": 

    N = 3 
    G = nx.grid_2d_graph(N,N) 
    labels = dict(((i,j), i + (N-1-j) * N) for i, j in G.nodes()) 
    nx.relabel_nodes(G,labels,False) 
    inds=labels.keys() 
    vals=labels.values() 
    inds=[(N-j-1,N-i-1) for i,j in inds] 
    pos2=dict(zip(vals,inds)) 

    fig, ax = plt.subplots(1,1) 
    nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10,ax=ax) 
    plt.axis('off') 
    plt.title('grid') 

    ST = find_all_spanning_trees(G) 
    print len(ST) 

    for g in ST: 
     fig, ax = plt.subplots(1,1) 
     nx.draw_networkx(g, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10,ax=ax) 
     plt.axis('off') 
     plt.title('grid') 
     plt.show()