Deciding that two chains are one

A kinematic chain arrives as a list of pins: link 0 to link 1, link 1 to link 2, and so on. The numbers are arbitrary. Nobody chose them for a reason, and a different draughtsman writing the same mechanism down would have produced a different list.

So the question are these two chains the same is not a comparison of lists. It is the question of whether some relabelling of one list produces the other, and for a ten-link chain there are 3,628,800 relabellings to consider.

That is the cost per pair. The census asks it far more often than once. Building the ten-link census means deciding, for each of the 3,000 candidate graphs the search reaches, whether it has been seen before — and comparing every new candidate against every stored one would be 26,335 pairwise questions on the final list alone.

Neither cost is payable, and the spectral shortcut that used to make it payable has counterexamples. What is needed is something better than an invariant.

A labelling rather than a number #

The way out is to stop computing a number from the graph and start computing a labelling of it.

Pick a rule that assigns each link a number, using only what the graph says about that link and never the label it arrived with. Apply it to both chains. If the rule is deterministic and reads only the graph, then two isomorphic chains get the same labelling — up to whichever links the rule genuinely cannot distinguish — and their adjacency strings under that labelling match exactly.

That string is the canonical form. Two chains are the same chain precisely when their canonical forms are identical, and the comparison is a string equality rather than a search. There are no counterexamples by construction — unlike the spectral fingerprint of the previous rung — and the whole content of the claim is in the rule reading only the graph.

Refinement does most of the work #

The rule has two halves, and the first is cheap.

Colour every link by how many pins it carries. Then repeatedly recolour it with its own colour together with the multiset of its neighbours’ colours, until a pass changes nothing.

Two links that end in different colours cannot possibly be carried to one another by any relabelling: their colours are statements about their own neighbourhoods, then about their neighbourhoods’ neighbourhoods, and a relabelling preserves all of it. So refinement never merges links that ought to be separate, and everything it does separate is separated correctly.

On the chains in this field it does most of the job. A chain whose links carry different numbers of pins is often pinned down by that alone; adding one round of neighbours’ colours usually finishes it. Stephenson’s chain refines to three classes in two passes, and those three classes are exactly its three orbits.

What refinement cannot do is separate links that are genuinely alike to every local measurement. Watt’s chain has four binary links that refinement colours identically, and it is right to: no local test distinguishes them, because a symmetry of the whole chain carries any one of them to any other.

But refinement also stops on chains where the links are not interchangeable, and that is the case the second half exists for.

Backtracking on what is left #

When refinement stops with a class of more than one link, the rule picks one link out of that class, gives it a colour of its own, and refines again — which usually cascades and splits everything.

The catch is that the rule does not know which link to pick. So it tries each of them, follows each choice to the end, and keeps whichever produces the lexicographically largest adjacency string. That choice is arbitrary and it does not matter which arbitrary rule is used; what matters is that it is the same rule every time, so that two isomorphic chains explore corresponding branches and arrive at the same string.

The cost is the number of branches, and on chains this size refinement leaves very few. It is worth being honest that this is not a general result: individualisation-and-refinement is exponential in the worst case, and the worst cases are highly regular graphs — which is exactly what makes the ten-vertex chains here comfortable, since a chain with a triangle in it is not a chain at all and the graphs are sparse and irregular.

This is a tool and not a subject. The routine is written to the size of the problem and not to the state of the art; what is claimed here is a census of mechanisms, never anything about isomorphism testing in general, which is algorithms-data-structures.com’s ground.

What falls out for free: the symmetries #

The same search, run without the maximising, produces something the census needs anyway.

An automorphism is a relabelling of a chain that leaves it unchanged — every pin still between the same two links. Finding them all is the same backtracking with a different acceptance test: extend a partial map only to a link of the same degree whose adjacencies to the already-mapped links agree exactly, and record every complete map.

That matters because a chain is not a mechanism until a link is held still, and two links give the same mechanism exactly when an automorphism carries one to the other. So the number of genuinely different mechanisms a chain gives is the number of orbits — and that is where the classical counts come from. Two six-link chains, five orbits, five six-bars. Sixteen eight-link chains, seventy-one orbits, seventy-one eight-link mechanisms.

It is a nice economy that the expensive machinery a census needs for deduplication turns out to be the machinery it needs for counting driven mechanisms. Neither was built for the other.

Why the string is compared and not the matrix #

A small point of practice, because it is where an implementation of this usually goes wrong.

The canonical form here is the upper-triangle bit string of the adjacency matrix under the canonical labelling, read row by row — for a ten-link chain, forty-five characters. It is not the matrix, not the edge list, and not a hash of either.

The string form matters for three reasons. It is comparable with a single equality, so a census can store it as a map key and deduplicate in constant time rather than by pairwise testing. It is orderable, which is what lets the backtracking maximise over branches: “lexicographically largest” needs a total order, and a matrix has none. And it is exact — no floating point anywhere, so two chains either are the same or are not, with no tolerance to choose and nothing to be near.

That last property is unusual on this site and worth marking. Almost every other field’s central quantity is a real number arrived at by a solve, with a tolerance that is a check rather than a stopping rule and a decision somewhere about where a spectrum stops being signal — which is what the count that does not move is about. Here there is no such decision. The census is a set of strings, and a chain is in it or is not.

What it costs to be sure #

It is worth putting a number on the whole apparatus, because the argument for it is partly economic.

Building the ten-link census means: enumerating eleven degree sequences; walking a pruned search that reaches 3,000 complete labelled graphs; canonicalising each of them; deduplicating into 1,878 distinct graphs; running a subset scan over each to reject the 1,648 that hide a structure; and computing the automorphism group of each of the 230 survivors to count its mechanisms. That is about half a second.

For comparison: the spectral shortcut this replaces would have taken a few milliseconds and would have returned 228 chains, with two of them silently absent and two others silently doubled. The saving is real and the error is permanent, which is roughly the worst exchange rate available.

The one place the cost does bite is the next row. Twelve links means 4,096 subsets to scan per graph, a search space larger by about the factor the last three steps were, and a canonical form on twelve vertices rather than ten. That is the subject of its own rung, and the honest answer there is that this routine does not reach it.

Why the drawings depend on it #

There is a second use, and it is the one that decides whether this field’s figures can be trusted at all.

A graph has no geometry. Where the discs go on a page is a choice, and an arbitrary choice would make two drawings of the same chain look like different chains — which is the single worst thing a figure in this field could do, because are these two the same is the field’s central question and a reader’s first instrument is their eye.

So the layout is defined as a function of the canonical form and of nothing else. Links start on a circle in canonical order, relax under a fixed number of spring-and-repulsion steps with a fixed schedule, and the result is rotated so its longest principal axis is horizontal and reflected so the first canonical link is on the left. No random seed, no hand-placement, no per-chain adjustment.

The consequence is checkable, and it is checked: a chain relabelled forty times at random produces forty different edge lists and one drawing. The assertion compares the closest pair of links in the picture and requires it to be unchanged to $10^{-9}$.

That is the same discipline the rest of the site applies to positions — nothing is drawn that was not solved — carried over to the one thing in this field with no solve behind it. It is worth stating as a rule because the alternative is so easy and so quietly wrong: hand-placing the discs of sixteen chains until each looks tidy produces sixteen good pictures and destroys the only comparison the reader can make.

The rule that makes the census finish #

The canonical form decides whether two graphs are the same. It does not, on its own, make a census affordable, and the reason is that a search generating labelled graphs produces every labelling of every chain.

At eight links the unpruned search reaches 8,494 complete graphs and returns 71. At ten links it does not finish at all.

What fixes it is one rule, and it is a weak relative of the canonical form. When two links carry the same number of pins, swapping them gives a relabelling of the same partial graph; if that swap would make the adjacency string lexicographically larger, the current labelling is not the largest in its class and can be abandoned. The largest one is generated by some other branch, so nothing is lost.

It is a partial test — adjacent swaps generate all the relabellings within a degree class but checking them one at a time does not decide maximality — which is why the full canonical form is still taken at the end. That combination is the ordinary shape of an enumeration: a cheap partial rule that removes almost everything during the search, and an exact rule that finishes the job on what survives.

A canonical form is a name, and names have to be versioned #

The canonical form is used above for deduplication and for drawing, and it has a third use that is worth stating because it is the one that outlives any particular run.

A canonical form is a name. It is a short string, it is computed from the chain and from nothing else, and two people who have never spoken produce the same string for the same chain. So a chain can be stored under it, looked up by it, and referred to in a table without anybody agreeing on a numbering first — which is exactly what a census needs if its rows are to be compared against a census somebody else built, or against the same census rebuilt a year later after the enumerator has been rewritten.

That is a genuinely useful property and it comes with a trap that is easy to walk into. The string is stable against relabelling and not against the rule. It is stable against relabelling by construction, which is the whole point and is what the scramble test checks. It is not stable against a change to the refinement rule, the tie-breaking order, or the direction the upper triangle is read in — change any of those and every chain in the census gets a different name, all of them still correct, none of them matching what was stored yesterday.

So a stored canonical form is only a name in the presence of the rule that produced it, and a census that records the strings without recording the rule has recorded something that will silently stop matching. The remedy is dull and complete: keep the rule’s identity beside the strings, and treat a mismatch as a question about which rule was used rather than as a discovery about chains.

The failure this prevents is a particular one and it is worse than a broken lookup. Two censuses with different rules produce two sets of strings with no overlap at all, so a comparison between them reports that every chain in one is absent from the other — which reads exactly like a genuine disagreement about what the census contains, and is a disagreement about spelling. The first thing to check when two enumerations disagree completely is therefore not the enumeration.

None of that argues against the string form, which is the right representation for all three uses. It argues for one line of metadata, and it is the same discipline the site applies to a figure’s own numbers: a value is only a value with the thing that produced it attached.

The thing that has to be got right #

One property carries the whole census and it is worth stating on its own: the rule must read the graph and never the labels.

Every failure mode here is a leak of the arrival order into the answer. A refinement that broke ties by link number would give two isomorphic chains different canonical forms. A backtracking search that tried the branches in the order the links happened to be listed, and stopped at the first complete labelling instead of maximising, would do the same. In both cases the census would silently over-count — the same chain stored twice under different strings — and there is no gate anywhere that would notice, because every graph in it would still be a perfectly good chain.

The check for it is the relabelling test above, and it is the only check that would catch it: take a chain, scramble its labels, and require the canonical form and the drawing to be unchanged. Comparing against published counts helps too — the census reproduces 1, 2, 16 and 230, and separately reproduces the number of unlabelled trees on up to ten vertices, which is a sequence from an entirely different subject — but agreement with a published number is weaker evidence than it looks. It confirms the total and says nothing about which objects are in it.

A related point about what the string can and cannot be compared against. Two canonical forms produced by the same rule are equal exactly when the chains are the same, so equality is a complete test and inequality is a complete test. What the strings do not support is anything in between: they cannot be ordered meaningfully, the distance between two of them says nothing about how similar the chains are, and a near-match is not a near-miss. That is worth knowing before anybody tries to index the census by string prefix or to cluster chains by how much of the string they share, both of which look reasonable and measure the labelling rule rather than the graphs.