Skip to main content
$$ % Define your custom commands here \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\E}{\mathbb{E}} \newcommand{\P}{\mathbb{P}} \newcommand{\S}{\mathbb{S}} \newcommand{\R}{\mathbb{R}} \newcommand{\S}{\mathbb{S}} \newcommand{\norm}[2]{\|{#1}\|_{{}_{#2}}} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\pdd}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\vectornorm}[1]{\left|\left|#1\right|\right|} \newcommand{\abs}[1]{\left|{#1}\right|} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\bm}[1]{\boldsymbol{#1}} \newcommand{\nicefrac}[2]{{}^{#1}\!/_{\!#2}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\dd}{\operatorname{d}\!} $$

4. The contact graph

catalog/graph.py builds edges between templates: transfer-adjacent (same body pair, and the features are adjacent on both bodies, so one contact can slide into the other) and shared-feature (the two templates use a common feature). It should also carry the exclusion table. This step counts the edges and looks at what is actually stored.

python walkthrough/04_graph.py
The script, 04_graph.py (download) 
"""Step 4: the contact graph (catalog-level edges).

ContactGraph builds two edge types over templates: transfer-adjacent (same
body pair, features adjacent on both bodies) and shared-feature (the two
templates share a feature). Count them, and look at what the edge list
actually stores.
"""
from collections import Counter

from cmg.catalog.graph import ContactGraph, EdgeTypes

from _common import STEP_YAML, load_spec, template_names

graph = ContactGraph.from_yaml(str(STEP_YAML))
catalog = graph.catalog
names = template_names(load_spec(), catalog)

print("Edges by type:", dict(Counter(EdgeTypes(t).name for _, _, t in graph.edges)))
print("First three stored edges:", graph.edges[:3])
print("Has an excluded-edge list:", hasattr(graph, "edges_excluded"))

# Recompute with catalog positions so the edges can be read.
index = {id(t): i for i, t in enumerate(catalog)}
first = names.index("B:zn-L:boundary")
print(f"\nNeighbours of {names[first]} (template {first}):")
for t1, t2 in ((a, b) for a in catalog for b in catalog if a is not b):
    if index[id(t1)] != first:
        continue
    kinds = []
    if catalog.transfer_adjacent(t1, t2):
        kinds.append("transfer-adjacent")
    if set(t1.key()) & set(t2.key()):
        kinds.append("shared-feature")
    if kinds:
        print(f"  {names[index[id(t2)]]:18s} {', '.join(kinds)}")

Output

Edges not provided for ContactGraph. Building edges using the default rules
Edges by type: {'SHARED_FEATURE': 192, 'TRANSFER_ADJACENT': 96}
First three stored edges: [(None, None, <EdgeTypes.SHARED_FEATURE: 1>), (None, None, <EdgeTypes.TRANSFER_ADJACENT: 0>), (None, None, <EdgeTypes.SHARED_FEATURE: 1>)]
Has an excluded-edge list: False

Neighbours of B:zn-L:boundary (template 11):
  M:boundary-B:zn    shared-feature
  B:xp-L:boundary    transfer-adjacent, shared-feature
  B:xn-L:boundary    transfer-adjacent, shared-feature
  B:yp-L:boundary    transfer-adjacent, shared-feature
  B:yn-L:boundary    transfer-adjacent, shared-feature
  B:zp-L:boundary    shared-feature
  B:zn-S:boundary    shared-feature
  B:zn-P:boundary    shared-feature

What to notice

  • Every stored edge is (None, None, type). Edges are recorded by template_id, which Catalog.from_spec never sets (step 2). The edge list cannot be mapped back to templates. The script works around this by recomputing the edges with catalog positions.
  • The exclusion table is dropped. ContactGraph.from_spec passes edges_excluded, but __init__ never stores it.
  • Nothing downstream uses the graph. Cand (step 6) and Search (step 8) work from the catalog alone, so no exclusion is enforced anywhere today.
  • Adjacency follows the box’s faces. B:zn-L is transfer-adjacent to the four side faces on the floor, not to B:zp-L: opposite faces share no edge.
  • Shared-feature edges here include shared environment features. B:zn-L and B:xp-L share only the floor’s boundary, yet they are linked.
  • Each edge appears twice, once in each direction.

Both defects (unset IDs, dropped exclusions) are on the list of code issues for Angelo in the discussion compendium.

Code to read

  • src/cmg/catalog/graph.py: ContactGraph.__init__ and __create_default_edges.
  • src/cmg/catalog/templates.py, Catalog.transfer_adjacent, and src/cmg/geometry/features.py, the adjacent method of BoxFaceFeature and BoxVertexFeature.

Exercises

4.1 Account for the 96 transfer-adjacent edges.

Within one body pair, the other body’s feature is a single boundary, which is adjacent to itself, so two templates are transfer-adjacent exactly when their box faces are adjacent. Each face is adjacent to the four faces on other axes, giving 6 × 4 = 24 ordered pairs per body pair. With four body pairs that makes 4 × 24 = 96.

4.2 Account for the 192 shared-feature edges. How many would there be if only shared object features counted, as the docstring’s name (shared-object-feature) suggests?

Take a template (box face f, other feature b). It shares f with the three other templates that use f (one per other body pair), and b with the five other templates of its own pair. That gives 8 neighbors per template and 24 × 8 = 192 ordered edges. Counting only the shared box face leaves 3 per template, 24 × 3 = 72.

4.3 Fix the missing template IDs so that the stored edges name templates, and check that the test suite still passes.

In src/cmg/catalog/templates.py, Catalog.from_spec, re-create the templates with their positions just before the ExecutionWorld line:

        templates = [
            Template.create(t.feature1, t.feature2, template_id=i)
            for i, t in enumerate(templates)
        ]
        exec_world = ExecutionWorld(spec.execution)

Then python walkthrough/04_graph.py prints

First three stored edges: [(0, 1, <EdgeTypes.SHARED_FEATURE: 1>), (0, 2, <EdgeTypes.TRANSFER_ADJACENT: 0>), (0, 2, <EdgeTypes.SHARED_FEATURE: 1>)]

and PYTHONPATH=tests python -m pytest -q tests still reports 6 passed. Templates 0 and 1 (the disk on xp and on xn) share the disk’s boundary but are not transfer-adjacent, because opposite faces share no edge. Undo the change with git checkout src/cmg/catalog/templates.py when you are done.

← 3. Formations · Next: 5. The hold LP →