In [1]:
# CREATE HIERARCHICAL SPATIAL TEMPORAL GRAPH
In [35]:
import networkx as nx
import numpy as np
import logging as log
import itertools
import random
import math
import pprint as pp
import matplotlib.pyplot as plt
log.basicConfig(level=log.DEBUG, format='%(asctime)s %(levelname)s: %(message)s')
In [11]:
def generate_forest_balanced_trees(r, h, n):
graphs = []
roots = []
num_nodes = num_nodes_balanced_tree(r, h)
starting_num = 0
for i in range(0, n):
#log.debug("building tree with starting root: %s", starting_num)
g = nx.balanced_tree(r, h)
g = nx.convert_node_labels_to_integers(g, first_label=starting_num)
#log.debug("nodes: %s", pp.pformat(g.nodes()))
graphs.append(g)
roots.append(starting_num)
starting_num += num_nodes
trees = nx.union_all(graphs)
return (trees, roots)
def num_nodes_balanced_tree(r,h):
"""
Returns the number of nodes in a balanced tree, with branching factor R and height H.
"""
total = 0
for i in range(0,h+1):
total += r ** i
#log.debug("total: %s", total)
return total
In [89]:
def generate_linked_roots_forest(graph, roots, frac = 0.3):
"""
Given a forest of trees, and the list of root vertices, link
a specified fraction of the roots with edges to produce a
single connected graph from the disparate trees in the forest.
Returns the input graph, after edge addition. Warning - need to
check whether the result is connected. With low fractions, it
may not be connected.
"""
new_graph = graph.copy()
edge_pairs = []
# take combinations of the root nodes, filtering out self-combos
nodes = []
nodes.append(roots)
nodes.append(roots)
for tup in itertools.product(*nodes):
if tup[0] == tup[1]:
continue
edge_pairs.append(tup)
num_links = int(math.ceil(len(edge_pairs) * frac))
log.debug("number of edges to create between random roots: %s", num_links)
random_pairs = random.sample(edge_pairs, num_links)
# now create the edges between the chosen pairs of roots
for pair in random_pairs:
new_graph.add_edge(pair[0], pair[1])
return new_graph
In [22]:
%matplotlib inline
In [74]:
g = generate_forest_balanced_trees(2,2,6)
gr = g[0]
roots = g[1]
In [33]:
def draw_tree(graph):
pos=nx.graphviz_layout(graph,prog='dot')
nx.draw(graph,pos,with_labels=True,arrows=False)
plt.show()
In [75]:
draw_tree(gr)
In [90]:
for i in range(0, 10):
gr2 = None
gr2 = generate_linked_roots_forest(gr,roots,frac=0.3)
print nx.is_connected(gr2)
print roots
In [87]:
draw_tree(gr2)
In [91]:
num_centroids = len(roots)
In [92]:
# choose random spatial locations for the roots, and then lay out the children
# randomly around the root centroids
In [94]:
x_max = 100
y_max = 100
In [96]:
centroids = []
for i in xrange(0,num_centroids):
x = int(random.uniform(0, x_max))
y = int(random.uniform(0, y_max))
centroids.append((x,y))
print centroids
In [97]:
# assign the centroid coordinates to the roots
for root in roots:
label = "a-" + str(x) + "-" + str(y)
gr2.node[root]['xcoord'] = x
gr2.node[root]['ycoord'] = y
gr2.node[root]['label'] = label
gr2.node[root]['level'] = 'root'
In [101]:
for t in nx.generate_gml(gr2):
print t
In [ ]: