Layout graphs with many disconnected components using python-igraph. - Adapted from https://stackoverflow.com/questions/53120739/lots-of-edges-on-a-graph-plot-in-python

layout.py

import igraph as ig
import numpy as np
from itertools import combinations

def layout_components(
    graph: ig.Graph,
    component_layout: str = "fr",
    arrange_boxes: str = "dense",
    pad_x: float = 1.0,
    pad_y: float = 1.0,
) -> np.ndarray:
    """
    Compute a graph layout by layouting all connected components individually. 

    Adapted from https://stackoverflow.com/questions/53120739/lots-of-edges-on-a-graph-plot-in-python

    Arguments:
    ----------
    graph
        The graph to plot.
    component_layout
        Layout function used to layout individual components.
        Can be anything that can be passed to :meth:`igraph.Graph.layout`
    arrange_boxes
        How to arrange the individual components. Can be "size" 
        to arange them by the component size or "dense" to pack them as densly
        as possible. 
    pad_x, pad_y
        Padding between subgraphs in the x and y dimension.

    Returns:
    --------
    pos 
        n_nodes x dim array containing the layout coordinates 

    """
    # assign the original vertex id, it will otherwise get lost by decomposition
    for i, v in enumerate(graph.vs):
        v["id"] = i
    components = np.array(graph.decompose(mode="weak"))
    component_sizes = np.array([component.vcount() for component in components])
    order = np.argsort(component_sizes)
    components = components[order]
    component_sizes = component_sizes[order]
    vertex_ids = [v["id"] for comp in components for v in comp.vs]
    vertex_sorter = np.argsort(vertex_ids)

    bbox_fun = _bbox_rpack if arrange_boxes == "dense" else _bbox_sorted
    bboxes = bbox_fun(component_sizes, pad_x, pad_y)

    component_layouts = [
        _layout_component(component, bbox, component_layout)
        for component, bbox in zip(components, bboxes)
    ]
    # get vertexes back into their original order
    coords = np.vstack(component_layouts)[vertex_sorter, :]
    return coords


def _bbox_rpack(component_sizes, pad_x=1.0, pad_y=1.0):
    """Compute bounding boxes for individual components
    by arranging them as densly as possible. 

    Depends on `rectangle-packer`. 
    """
    import rpack

    dimensions = [_get_bbox_dimensions(n, power=0.8) for n in component_sizes]
    # rpack only works on integers; sizes should be in descending order
    dimensions = [
        (int(width + pad_x), int(height + pad_y))
        for (width, height) in dimensions[::-1]
    ]
    origins = rpack.pack(dimensions)
    bboxes = [
        (x, y, width - pad_x, height - pad_y)
        for (x, y), (width, height) in zip(origins, dimensions)
    ]
    return bboxes[::-1]


def _bbox_sorted(component_sizes, pad_x=1.0, pad_y=1.0):
    """Compute bounding boxes for individual components
    by arranging them by component size"""
    bboxes = []
    x, y = (0, 0)
    current_n = 1
    for n in component_sizes:
        width, height = _get_bbox_dimensions(n, power=0.8)

        if not n == current_n:  # create a "new line"
            x = 0  # reset x
            y += height + pad_y  # shift y up
            current_n = n

        bbox = x, y, width, height
        bboxes.append(bbox)
        x += width + pad_x  # shift x down the line
    return bboxes


def _get_bbox_dimensions(n, power=0.5):
    # return (np.sqrt(n), np.sqrt(n))
    return (n ** power, n ** power)


def _layout_component(component, bbox, component_layout_func):
    """Compute layout for an individual component"""
    layout = component.layout(component_layout_func)
    rescaled_pos = _rescale_layout(np.array(layout.coords), bbox)
    return rescaled_pos


def _rescale_layout(coords, bbox):
    """Transpose the layout of a component into its bounding box"""
    min_x, min_y = np.min(coords, axis=0)
    max_x, max_y = np.max(coords, axis=0)

    if not min_x == max_x:
        delta_x = max_x - min_x
    else:  # graph probably only has a single node
        delta_x = 1.0

    if not min_y == max_y:
        delta_y = max_y - min_y
    else:  # graph probably only has a single node
        delta_y = 1.0

    new_min_x, new_min_y, new_delta_x, new_delta_y = bbox

    new_coords_x = (coords[:, 0] - min_x) / delta_x * new_delta_x + new_min_x
    new_coords_y = (coords[:, 1] - min_y) / delta_y * new_delta_y + new_min_y

    return np.vstack([new_coords_x, new_coords_y]).T


def test_layout_components():
    g = ig.Graph()

    # add 100 unconnected nodes
    g.add_vertices(100)

    # add 50 2-node components
    g.add_vertices(100)
    g.add_edges([(ii, ii + 1) for ii in range(100, 200, 2)])

    # add 33 3-node components
    g.add_vertices(100)
    for ii in range(200, 299, 3):
        g.add_edges([(ii, ii + 1), (ii, ii + 2), (ii + 1, ii + 2)])

    # add a couple of larger components
    n = 300
    for ii in np.random.randint(4, 30, size=10):
        g.add_vertices(ii)
        g.add_edges(combinations(range(n, n + ii), 2))
        n += ii

    layout = layout_components(g, arrange_boxes="dense", component_layout="fr")
    return ig.plot(g, layout=ig.Layout(coords=layout.tolist()), vertex_size=4)