CODEWITHSUNDEEP
pythonjsontreeflasknetworkx
Bernard
Bernard

Reputation: 11

networkx: generate JSON tree with weights

This is probably easy to solve for a bit more experienced programmer, but I really can't find the solution yet.

I have a networkx DiGraph (in Python w/flask) which contains tuples as nodes, and edges with weights.

I would like to extract a tree of all paths from start-node to end-node, with their weights. This is basically all_simple_paths(), but with weights, and export them in JSON as a tree, with one root (the start-node), and all (simple) paths till the end-node.

Solutions (among other) I looked at:

Any hints on how to do this would be highly appreciated. :)

Upvotes: 1

Views: 944

Answers (1)

daedalus
daedalus

Reputation: 10923

The question needs some specificity, but here is an effort at constructing some dummy data with tuples for nodes, extracting an arbitrary path, and dumping to a JSON format.

Set up some Dummy Data

from random import seed, random, shuffle
seed(11405)

u = [('a','b','c'), ('d','e','f'), ('g','h','i'), 
     ('j','k','l'), ('m','n','o'), ('p','q','r'), 
     ('s','t','u'), ('v','w','x'), ('y','z','a')]
shuffle(u)
v = [('a','b','c'), ('d','e','f'), ('g','h','i'), 
     ('j','k','l'), ('m','n','o'), ('p','q','r'), 
     ('s','t','u'), ('v','w','x'), ('y','z','a')]
shuffle(v)
edges = [ (s,t, {'weight': random()}) for s,t in zip(u,v) if s != t]

Create the Graph

import networkx as nx
from networkx.readwrite import json_graph

G = nx.DiGraph()
G.add_edges_from(edges)

# Extract a Path between Two Arbitrary Nodes
u = ('m', 'n', 'o')
v = ('a', 'b', 'c')
paths = list(nx.all_simple_paths(G, u,v))
path = paths[0]

# Extract the Subgraph of G using the Selected Nodes
H = G.subgraph(path)

# Output to JSON in Node-Link Format
print json_graph.node_link_data(H)

Result

See also the docs for other JSON export formats.

{'directed': True, 
 'graph': [], 
 'nodes': [{'id': ('g', 'h', 'i')}, 
           {'id': ('p', 'q', 'r')}, 
           {'id': ('a', 'b', 'c')}, 
           {'id': ('m', 'n', 'o')}, 
           {'id': ('v', 'w', 'x')}], 
 'links': [{'source': 0, 'target': 1, 'weight': 0.5156976823289995}, 
           {'source': 1, 'target': 4, 'weight': 0.7392883299553644}, 
           {'source': 3, 'target': 0, 'weight': 0.2109456825712841}, 
           {'source': 4, 'target': 2, 'weight': 0.8368736026881095}], 
 'multigraph': False}

Upvotes: 2

Related Questions