Skip to content

pred path arrow summary hides steps by collapsing consecutive same-name nodes #1086

Description

@isPANN

Background

The path rendering used by pred path (asymptotic Pareto front) collapses consecutive nodes with the same problem name, hiding genuine intermediate steps between two variants of the same problem.

problemreductions-cli/src/commands/graph.rs, path_arrow_summary:

let mut prev_name = "";
for step in &reduction_path.steps {
    if step.name != prev_name {                 // <-- skips same-name steps
        parts.push(fmt_node(graph, &step.name, &step.variant));
        prev_name = &step.name;
    }
}

Symptom (current #1080 branch)

pred path MinimumFeedbackVertexSet ILP prints:

--- Path 1 (2 steps) ---
MinimumFeedbackVertexSet/i32 → ILP/i32
  num_constraints = O(num_arcs + num_vertices)
  num_vars = O(num_vertices)

The header says 2 steps, but only one transition is shown. The actual chosen path is MinimumFeedbackVertexSet/i32 → ILP/i32 → ILP/bool (the second edge is the ILP<i32> → ILP<bool> binary-encoding cast). Because both intermediate/final nodes are named ILP, the summary collapses them: the cast step is invisible and the true endpoint (ILP/bool) is not shown.

This is misleading to users and actively obscured a real overhead bug during #1080 development (the hidden cast edge was the one carrying the defect fixed in commit 015b1c6e).

Objective

Render every reduction step of the chosen path, including variant-to-variant casts of the same problem name. Each node should show its full name+variant so that consecutive same-name / different-variant steps are distinguishable.

Verification

  1. pred path MinimumFeedbackVertexSet ILP: the number of transitions in the arrow chain equals the reported "N steps", and the ILP/i32 → ILP/bool cast (when on the chosen path) is visible, ending at the true final variant.
  2. Any path whose chain contains a same-name variant cast shows that cast explicitly.

Negative control: on the current code, pred path MinimumFeedbackVertexSet ILP shows one for a "2 steps" path and never displays ILP/bool — proving steps are being hidden.

Scope

Display-only (path_arrow_summary and any code that assumes it). No change to the search or growth composition. --json output already lists the full step chain and is unaffected.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    Status
    No status

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions