microsoft / microsoft/automatic-graph-layout

LayerConstraints are not enforced when Subgraph is present

Open
#228 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C#
Stars
1.5k
Forks
319
Avg merge
38m
Merged PRs (30d)
1

Description

I think I've found an issue with Graph.LayerConstraints.AddUpDownConstraint / Graph.LayerConstraints.AddLeftRightConstraint.
In a simple graph, the feature works fine but, when using subgraphs, constraints are no longer enforced.

I figured out the Dictionary<Node, int> nodeIdToIndex fields in VerticalConstraintsForSugiyama / HorizontalConstraintsForSugiyama might be related to this issue.
When using subgraphs, some Layout.Node duplication occur and the Node keys in the dictionary never match.
As a consequence, int NodeIndex(Node node) always returns -1.

For example, the following graph has no layout constraints:
image

If I add a layout constraint where all nodes must be ordered from top to bottom in lexical order, I should get the following graph:
image

The latest image was generated using a hack where I changed Dictionary<Node, int> nodeIdToIndex into Dictionary<string, int> nodeIdToIndex and using node.ToString() as keys.
Without this hack, I get the same graph as the one with no constraint.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by inspecting VerticalConstraintsForSugiyama and HorizontalConstraintsForSugiyama, especially their nodeIdToIndex dictionaries and NodeIndex(Node node). Reproduce the reported top-to-bottom lexical constraint on a graph containing subgraphs, then verify that constraints are enforced without changing the keys to strings or relying on the linked hack.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
computer-graphics
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.