ManimCommunity / ManimCommunity/manim
Unexpected ordering of nodes in partite graph
- 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:
## 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
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