"fixed_nodes" argument of get_fruchterman_reingold_layout function isn't handled properly for multi-component graphs

[robaki]

python version: 3.8.10
netgraph version: 4.1.0

I'm trying to use the get_fruchterman_reingold_layout function to get node positions for plotting. When used on edges/nodes from a small graph, it fails, raising ValueError: Some given node positions are not within the data range specified by origin and scale! and showing different scale values than the ones that were actually provided.

Below is a minimal example: using the smaller list of edges results in error, while the second, bigger one, is fine.

#! /usr/bin/env python3

import netgraph

import warnings
warnings.filterwarnings("ignore")

nodes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69]

# not enough edges
edges = [(0, 5), (0, 8), (0, 21), (0, 27), (1, 6),]

# enough edges
#edges = [(0, 5), (0, 8), (0, 21), (0, 27), (1, 6), (1, 7), (1, 10), (1, 11), (1, 16), (1, 27), (2, 3), (2, 8), (2, 9), (2, 14), ]

selected_node = 0

plot_x, plot_y = 1.7786, 1

pos = netgraph.get_fruchterman_reingold_layout(
    edges=edges,
    nodes=nodes,
    origin=(0,0),
    scale=(plot_x,plot_y),
    node_size=0,
    node_positions={selected_node:(plot_x/2,plot_y/2)},
    fixed_nodes=[selected_node],
)

print(pos)

[robaki]

OK, the problem isn't the size of the network, it is in the handling of multiple components: each has it's own bbox, and the specified positions may or may not fall inside of them:

def get_layout_for_multiple_components(edges, components, layout_function,

    bboxes = _get_component_bboxes(components, origin, scale)

    node_positions = dict()
    for ii, (component, bbox) in enumerate(zip(components, bboxes)):
        if len(component) > 1:
            subgraph = _get_subgraph(edges, component)
            component_node_positions = layout_function(subgraph, origin=bbox[:2], scale=bbox[2:], *args, **kwargs)
            node_positions.update(component_node_positions)
        else:
            # component is a single node, which we can simply place at the centre of the bounding box
            node_positions[component.pop()] = (bbox[0] + 0.5 * bbox[2], bbox[1] + 0.5 * bbox[3])

    return node_positions

I don't know how to work around that problem in an easy way, and not sure if my use-case is even within the intended scope of the library: I want to keep one of the nodes fixed in the center of the plot and let the other arrange themselves. I think I'll write my own algorithm for that

[paulbrodersen]

Hi, thanks for raising the issue and sorry about the late reply -- I was on holiday.

OK, the problem isn't the size of the network, it is in the handling of multiple components: each has it's own bbox, and the specified positions may or may not fall inside of them.

That is a very good point. I hadn't considered that conflict. Off the top of my head, I also can't think of a clean solution. To handle fixed nodes in conjunction with multiple components one would have to first draw the components containing the fixed nodes and then pass the remaining white space to a rectangle packing algorithm. However, I don't know of any implementation that handles non-rectangular "packing areas".

I don't know how to work around that problem in an easy way, and not sure if my use-case is even within the intended scope of the library.

Well, at the very least, netgraph should raise an exception, or at least a warning.

I want to keep one of the nodes fixed in the center of the plot and let the other arrange themselves.

The FR algorithm with fixed nodes works pretty well for that. A shell layout can also look good. Assuming that the other components in your ego-graph are unconnected nodes, then you can simply arrange them on a circle around the connected part of the graph.

import numpy as np

def get_positions_for_unconnected_nodes(unconnected_nodes, other_node_positions):
    """
    Determine a good position of unconnected nodes.
    Currently, we place these nodes on the periphery, which we define as the area
    just outside the circle covering all positions in `other_node_positions`.

    Arguments:
    ----------
    unconnected_nodes : list
        The nodes for which we need to find positions.

    other_node_positions : dict node ID : (float, float)
        The positions of all other nodes.

    Returns:
    --------
    node_positions : dict node ID : (float, float)
        The positions of the unconnected nodes.

    """

    xy = np.array(list(other_node_positions.values()))
    centroid = np.mean(xy, axis=0)
    delta = xy - centroid[np.newaxis, :]
    distance = np.sqrt(np.sum(delta**2, axis=1))
    radius = np.max(distance)

    node_positions = dict()
    for node in unconnected_nodes:
        node_positions[node] = _get_random_point_on_a_circle(centroid, radius*1.1)

    return node_positions


def _get_random_point_on_a_circle(origin, radius):
    random_angle = 2 * np.pi * np.random.random()
    return _get_point_on_a_circle(origin, radius, angle)


def _get_point_on_a_circle(origin, radius, angle):
    x0, y0 = origin
    x = x0 + radius * np.cos(angle)
    y = y0 + radius * np.sin(angle)
    return np.array([x, y])

Otherwise, I would connect each unconnected component to my node of interest using an edge with low weight, and then use FR to determine the node positions.

[robaki]

Hi, thanks for the answer

Otherwise, I would connect each unconnected component to my node of interest using an edge with low weight, and then use FR to determine the node positions.

this sounds like a good solution for me!

[paulbrodersen]

I haven't fixed the underlying issue but at least the problem is documented in the docstring and the error message indicates the potential issue (when it does indeed occur), so hopefully no other user is sent on an extended bug hunt.

[Thylowz]

I was personnally also confronted to this issue and defaulted to networkx non-interactive graphs in this case. It happens sometime when some of my nodes are not connected (which is a degraded case in my case so this issue is not that problematic).