I am creating a graph using networkx and using pyvis to visualise. Is there any way to set the length of the edge correspond to distance between nodes?
I find that pyvis allows setting up the edge width and label. But I need distance based length.
Asked
Active
Viewed 542 times
1 Answers
0
There isn't a layout in networkx (nor in igraph nor in graph-tool) that allows you to enforce edge lengths for an arbitrary graph. There are two approximations that may work:
You can use the inverse of the edge length to compute an edge weight and then supply that to the spring layout. This may force nodes with short edges between them to be closer together in the final layout but won't have a reliable effect on long edges (as repulsion forces often dominate the placement of nodes that are connected through edges with low weights).
If your graph is directed and acyclic, you can use the Sugiyama (a.k.a. dot layout), as suggested by @imxitiz and set a minimum edge length. If your graph is not a DAG and/or you don't want to use a tree layout, then you this approach does not work you.
I am the author and maintainer of netgraph, which is a python library built on matplotlib for graph visualisations. I have been working on writing a node layout routine for defined edge lengths. Below is the alpha version, which is very slow and only usable for graphs with less than 50 nodes or so.
However, there are some obvious places for improvements in the code, I just haven't got around to them yet. First and foremost, the minimisation uses finite differences. However, as the cost function is just the inverse of a distance norm, computing the derivative (and then providing a callable jac) should not be too complicated. Once I have addressed the performance issues, the geometric node layout will become part of the netgraph library.
#!/usr/bin/env python
"""
Create a node layout with fixed edge lengths but unknown node positions.
"""
import numpy as np
from scipy.optimize import minimize, NonlinearConstraint
from scipy.spatial.distance import pdist, squareform
from netgraph._node_layout import _rescale_to_frame
def get_geometric_node_layout(edges, edge_length, node_size=0., power=0.2, maximum_iterations=200, origin=(0, 0), scale=(1, 1)):
"""Node layout for defined edge lengths but unknown node positions.
Node positions are determined through non-linear optimisation: the
total distance between nodes is maximised subject to the constraint
imposed by the edge lengths, which are used as upper bounds.
If provided, node sizes are used to set lower bounds.
Parameters
----------
edges : list
The edges of the graph, with each edge being represented by a (source node ID, target node ID) tuple.
edge_lengths : dict
Mapping of edges to their lengths.
node_size : scalar or dict, default 0.
Size (radius) of nodes.
Providing the correct node size minimises the overlap of nodes in the graph,
which can otherwise occur if there are many nodes, or if the nodes differ considerably in size.
power : float, default 0.2.
The cost being minimised is the inverse of the sum of distances.
The power parameter is the exponent applied to each distance before summation.
Large values result in positions that are stretched along one axis.
Small values decrease the influence of long distances on the cost
and promote a more compact layout.
maximum_iterations : int
Maximum number of iterations of the minimisation.
origin : tuple, default (0, 0)
The (float x, float y) coordinates corresponding to the lower left hand corner of the bounding box specifying the extent of the canvas.
scale : tuple, default (1, 1)
The (float x, float y) dimensions representing the width and height of the bounding box specifying the extent of the canvas.
Returns
-------
node_positions : dict
Dictionary mapping each node ID to (float x, float y) tuple, the node position.
"""
# ensure that graph is bi-directional
edges = edges + [(target, source) for (source, target) in edges] # forces copy
edges = list(set(edges))
# upper bound: pairwise distance matrix with unknown distances set to the maximum possible distance given the canvas dimensions
lengths = []
for (source, target) in edges:
if (source, target) in edge_length:
lengths.append(edge_length[(source, target)])
else:
lengths.append(edge_length[(target, source)])
sources, targets = zip(*edges)
nodes = sources + targets
unique_nodes = set(nodes)
indices = range(len(unique_nodes))
node_to_idx = dict(zip(unique_nodes, indices))
source_indices = [node_to_idx[source] for source in sources]
target_indices = [node_to_idx[target] for target in targets]
total_nodes = len(unique_nodes)
max_distance = np.sqrt(scale[0]**2 + scale[1]**2)
distance_matrix = np.full((total_nodes, total_nodes), max_distance)
distance_matrix[source_indices, target_indices] = lengths
distance_matrix[np.diag_indices(total_nodes)] = 0
upper_bounds = squareform(distance_matrix)
# lower bound: sum of node sizes
if isinstance(node_size, (int, float)):
sizes = node_size * np.ones((total_nodes))
elif isinstance(node_size, dict):
sizes = np.array([node_size[node] if node in node_size else 0. for node in unique_nodes])
sum_of_node_sizes = sizes[np.newaxis, :] + sizes[:, np.newaxis]
sum_of_node_sizes -= np.diag(np.diag(sum_of_node_sizes)) # squareform requires zeros on diagonal
lower_bounds = squareform(sum_of_node_sizes)
def cost_function(positions):
return 1. / np.sum((pdist(positions.reshape((-1, 2))))**power)
def constraint_function(x):
x = np.reshape(x, (-1, 2))
return pdist(x)
initial_positions = _initialise_geometric_node_layout(edges)
nonlinear_constraint = NonlinearConstraint(constraint_function, lb=lower_bounds, ub=upper_bounds, jac='2-point')
result = minimize(cost_function, initial_positions.flatten(), method='SLSQP',
jac="2-point", constraints=[nonlinear_constraint], options=dict(maxiter=maximum_iterations))
if not result.success:
print("Warning: could not compute valid node positions for the given edge lengths.")
print(f"scipy.optimize.minimize: {result.message}.")
node_positions_as_array = result.x.reshape((-1, 2))
node_positions_as_array = _rescale_to_frame(node_positions_as_array, np.array(origin), np.array(scale))
node_positions = dict(zip(unique_nodes, node_positions_as_array))
return node_positions
# # slow
# def _initialise_geometric_node_layout(edges):
# sources, targets = zip(*edges)
# total_nodes = len(set(sources + targets))
# return np.random.rand(total_nodes, 2)
# faster
def _initialise_geometric_node_layout(edges):
from netgraph import get_fruchterman_reingold_layout
node_positions = get_fruchterman_reingold_layout(edges)
return np.array(list(node_positions.values()))
if __name__ == '__main__':
import matplotlib.pyplot as plt
import networkx as nx
from netgraph import Graph # pip install netgraph
fig, (ax1, ax2) = plt.subplots(1, 2)
g = nx.random_geometric_graph(50, 0.3, seed=2)
node_positions = nx.get_node_attributes(g, 'pos')
plot_instance = Graph(g,
node_layout=node_positions,
node_size=1, # netgraph rescales node sizes by 0.01
node_edge_width=0.1,
edge_width=0.1,
ax=ax1,
)
ax1.axis([0, 1, 0, 1])
ax1.set_title('Original node positions')
def get_euclidean_distance(p1, p2):
return np.sqrt(np.sum((np.array(p1)-np.array(p2))**2))
edge_length = dict()
for (source, target) in g.edges:
edge_length[(source, target)] = get_euclidean_distance(node_positions[source], node_positions[target])
new_node_positions = get_geometric_node_layout(list(g.edges), edge_length, node_size=0.01)
Graph(g,
node_layout=new_node_positions,
node_size=1,
node_edge_width=0.1,
edge_width=0.1,
ax=ax2,
)
ax2.axis([0, 1, 0, 1])
ax2.set_title('Reconstructed node positions')
plt.show()
Paul Brodersen
- 11,221
- 21
- 38