ManimCommunity / ManimCommunity/manim

Unexpected ordering of nodes in partite graph

Open
#4,212 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
40.9k
Forks
3.1k
Avg merge
3d 12h
Merged PRs (30d)
25

Description

## Description of bug / unexpected behavior

I want to create a multi-partite graph not fully connected between the layers. It is created by subtracting a probability mass function from layer to layer and therefore, the nodes carry the type `tuple[int,int]` (layer number, display value). I expect the nodes in the layers / partitions to be either ascending or descending but this is not the case:

Image

## Expected behavior

I expect to be able to take influence on how the nodes are rendered by specifying the order in the `partitions` argument to `Graph()`. This is not the case.

## How to reproduce the issue

Code for reproducing the problem

```py
loss = [list(range(4)), list(range(5)), list(range(5))]

layers: list[list[tuple[int, int]]] = [[(0, start)]]

values = {start}
edges: list[tuple[tuple[int, int], tuple[int, int]]] = []
for i, layer_loss in enumerate(loss):
new_layer = []
new_values = set()
edges_layer = []
for d in layer_loss:
for v in values:
n = int(max(0, v - d))
if n not in new_values:
new_layer.append((i + 1, n))
new_values.add(n)
edges_layer.append(((i, v), (i + 1, n)))
edges += edges_layer
values = new_values
layers += [new_layer]

graph = Graph(
vertices,
edges,
layout="partite",
partitions=partitions,
)
```

## Additional comments

I found a solution that works around this behavior:
After digging into networkx, I found out that in `networkx.utils.misc.groups` the ordering is lost. To avoid calling this tool, one can pass a dictionary that maps the layer number to a sorted list of its nodes:

```py
for i, p in enumerate(partitions):
subset_key[i] = p

graph = Graph(
vertices,
edges,
# labels=True,
labels=labels,
layout="partite",
layout_config={"subset_key": subset_key}, # <----- This line suppress a shuffling of nodes
partitions=partitions,
)
```

I have the feeling, that this is closer to the expected behavior and should be considered to be added to `Graph._partite_layout`.

Contributor guide

Open the contributing guide

Research direction

Start by reading Graph._partite_layout and the reported ordering behavior around networkx.utils.misc.groups. Compare the partitions argument with the layout_config subset_key workaround, then verify that supplied partition ordering is preserved when rendering a partite graph.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
data-visualization
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.