Skip to content

Mask hierarchy: transitive reduction before cycle detection hides dense cycles #197

Closed

Description

@guijacquemet

_relations in src/morphobricks_preprocessing/mask_scan.py marks a parent link direct=False whenever a two-edge path exists (transitive reduction), which assumes an acyclic graph. Cycle detection (hierarchy_cycles) runs only afterwards, on the direct edges.

For a dense or chorded cycle (for example every pair among A, B, C is inside the other), every edge has an alternate two-step path, so every edge becomes direct=False. MaskReport.hierarchy then has no edges, no mask_hierarchy_cycle warning is emitted, and the masks silently appear as separate roots.

Reproduced on current main through _relations with a complete directed 3-cycle and with a 3-cycle plus a chord: no edge is direct.

Fix: find strongly connected components on the full nested-relation graph before choosing direct edges; edges inside a component stay direct (so the cycle is reported), and the transitive reduction runs only between components. Acyclic hierarchies keep exactly the same direct edges.

Release blocker (external review, batch 16, claim P7).

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions