Skip to content

task_graph__node_link__mst_weight

Program Contract

Program: sum(weights(minimum_spanning_tree(graph))); scene=node_link; scope=mst_weight

Candidate set: the visible graph, tree, network, route, matrix, table, node, edge, label, weight, path, and option elements inside the mst_weight objective scope. Operands: visible scene state and prompt-bound operands named by weights, minimum_spanning_tree, graph, node_link, mst_weight. Operation: evaluate sum over the candidate set using the visible graph structure, labels, weights, directions, reachability, paths, connectivity, or option-selection constraints encoded in the program expression; generation enforces a unique final answer. Output binding: answer uses the integer schema; the sum of the weights on the unique minimum spanning tree,. Annotation witnesses: annotation uses the segment_set schema; the segment_set of endpoint-node-center segments for all MST edges. Query ids: single.

Reasoning Operations

Families: ranking, aggregation, topology

1) Identity

  1. Domain: graph
  2. Scene: optimization
  3. Scene id: weighted_node_link
  4. Task id: task_graph__node_link__mst_weight
  5. Objective: return the total weight of the graph's unique minimum spanning tree.

2) Scene + task contract

  1. Branch metadata: query_id
  2. query_id: single
  3. Supported scene_variant values: circular, shell, spring, grid_jitter, layered, component_clustered, path_spine, radial_tree
  4. answer_gt.type: integer
  5. annotation_gt.type: segment_set
  6. Scene contract:
  7. one single-panel labeled connected weighted graph per image,
  8. undirected graph only,
  9. no self-loops,
  10. no multi-edges,
  11. visible node labels use uppercase letters by default (A..J),
  12. node count is sampled from 4..7,
  13. generation always includes at least one non-tree edge so the scene never collapses to a bare tree.
  14. Query contract:
  15. the prompt defines a spanning tree as connecting every node without cycles and asks for the smallest total edge weight,
  16. answer is the sum of the weights on the unique minimum spanning tree,
    • annotation is the unordered set of MST edges, represented as endpoint-node-center pixel segments [[x0, y0], [x1, y1]], with each endpoint as an [x, y] pixel point.
  17. Weight policy:
  18. edge weights are distinct integers from 1..9,
  19. generation samples 1..2 non-tree edges,
  20. the heaviest sampled weights are assigned to non-tree edges so the intended spanning tree is the unique MST by construction,
  21. the finalized weighted graph is rechecked with networkx.minimum_spanning_tree(...) before exposing answer or annotation.
  22. Topology variation:
  23. topology_profile values are balanced, low_degree, and hub_heavy,
  24. topology profile affects both the spanning-tree shape and which non-tree edges are added,
  25. graph semantics always come from adjacency + weights, never from layout position.
  26. Layout variation:
  27. scene_variant records the realized graph layout,
  28. requested layout variants are all reusable node-link layouts: circular|shell|spring|grid_jitter|layered|component_clustered|path_spine|radial_tree,
  29. the renderer may fall back to a cleaner node-link layout when a sampled layout is too cramped for readable node or edge-label separation.
  30. Visual variation:
  31. one whole-image named node color is sampled from the shared Trace named-color palette,
  32. one whole-image node glyph style is sampled from circle|rounded_square|hexagon,
  33. one whole-image label format is sampled as letters by default; numeric labels remain renderer-supported but are not part of this task's default generation distribution,
  34. one whole-image layout transform is sampled from identity|rotate_90|rotate_180|rotate_270|mirror_left_right|mirror_up_down,
  35. edge weights are rendered as small boxed integers near each edge,
  36. these style axes are non-semantic for this task and are recorded in trace metadata.

3) Prompt contract

  1. Bundle: graph_node_link_optimization_v1
  2. scene_key: single_graph_optimization
  3. task_key: minimum_spanning_tree_weight_query
  4. Required slots:
  5. scene: object_description
  6. task: question_text
  7. answer output: json_output_contract_answer_only, answer_hint, json_example_answer_only
  8. answer+annotation mode: json_output_contract, annotation_hint, answer_hint, json_example
  9. Modes: answer_only, answer_and_annotation
  10. Answer JSON shape: {"answer":12}
  11. Answer+annotation JSON shape: {"annotation":[[[180,220],[310,180]],[[310,180],[430,260]],[[430,260],[520,340]]],"answer":12}
  12. Prompt-facing annotation uses segment_set; each edge is one endpoint-node-center segment [[x0, y0], [x1, y1]], with each endpoint as an [x, y] pixel point.

4) Annotation + trace contract

  1. Prompt-facing annotation is the segment_set of endpoint-node-center segments for all MST edges.
  2. Each annotation item is an undirected segment; endpoint order is unordered semantically for reward matching, and the corresponding endpoint labels remain in witness_symbolic.
  3. scene_ir.entities stores one node entity per rendered node plus one edge entity per rendered edge with:
  4. endpoint labels,
  5. rendered segment,
  6. integer edge weight,
  7. weight-label bbox,
  8. MST-membership flag.
  9. scene_ir.relations stores:
  10. graph directionality,
  11. full edge-weight list,
  12. MST edge list,
  13. adjacency map,
  14. degree map.
  15. projected_annotation includes:
  16. segment_set
  17. segment_map
  18. execution_trace records:
  19. query_id (the concrete public query branch)
  20. scene_variant
  21. node_count
  22. extra_edge_count
  23. edge-weight range
  24. total MST weight
  25. MST edges
  26. weighted edge list
  27. topology profile
  28. requested and realized layout variants

5) Visual policy

  1. Background and post-image noise use the merged graph-domain visual defaults from src/trace_tasks/resources/configs/domains/graph/base.yaml.
  2. Current weighted graph scenes use a single rounded light panel on a light solid background.
  3. Node labels are rendered inside the nodes; edge weights are rendered in small boxed labels near edge midpoints.
  4. Layout and styling may vary for readability and diversity, but the prompt never refers to node position, node color, or node shape as the semantic source of truth.
  5. Weight labels stay semantic for this task, so trace metadata and rendered labels come from the same canonical edge-weight map.

6) Determinism + constraints

  1. Deterministic sampling/rendering from instance_seed.
  2. Answers and annotation come from the same finalized weighted graph.
  3. Unique-answer policy: generation enforces a unique MST by construction and rejects any graph whose final weighted edges do not preserve that unique witness.
  4. Reject/resample conditions:
  5. infeasible node-count / extra-edge-count / weight-range combination,
  6. failure to realize a connected weighted graph with at least one non-tree edge,
  7. failure to preserve the intended unique MST after weight assignment,
  8. unreadable layout that cannot keep nodes sufficiently separated.
  9. No semantic auto-relaxation: failures do not weaken the connectivity, weight, or unique-MST contract.

7) Complexity + tests

  1. Complexity definition/components: topology_reasoning, visual_scan, ambiguity, clutter
  2. Determinism/build tests: tests/test_graph_optimization_minimum_spanning_tree_weight_contracts.py
  3. Behavior/trace/prompt tests: tests/test_graph_optimization_minimum_spanning_tree_weight_tasks.py
  4. Prompt bundle/config tests: tests/test_prompt_system.py, tests/test_scene_config.py