# Efficient representation of twists

## Recommended Posts

I'm looking for a good data structure and set of twist addition/removal operations.

In a simulation I'm working on I need to represent twists in some cables.

There are an arbitrary but small number of cables, perhaps up to roughly 20 or 30. The bases of the cables are in a fixed order and will not move in space, but the tops of cables move around in 3D, potentially twisting with each other.

Importantly, these are logical twists, and are NOT supposed to be physically accurate. I don't care about positions of the twists or distances along the cables, nor do I care if one twist slides up or down the the cable. Even though these examples show them twisted in space that is for communication only. On screen all the twists will end up meeting at a single point, but they need to untwist the right number of times.

I need a data structure that can efficiently handle adding and removing twists between the cables.

I imagine I could store them in either order, but since they're accessible by index I could place them in a consistent order, like lowest is always first.

The "simple twists" image could be created by adding a clockwise twist to black/green, and adding an anticlockwise twist to blue and red. I could untwist by adding an anticlockwise twist to black/green, and by adding a clockwise twist to blue/red.

In the "multiple twists" image, I can add multiple twists to a pair if they're the same direction.  If I added a clockwise turn it should remove the twist.

I should be able to cross multiple lines.  In the "simple twists" image, I should be able to have the green cable loop up and over the other cables, and as it moved in 3D passing the crossover points it would add a clockwise green/black, a clockwise green/red, and a clockwise green/blue to the collection of twists.

I would prefer to always consider it an addition.  Add a clockwise or add an anticlockwise, add both and the two should cancel out.  As the cables move in 3D I can test if they would cross each other, and in that case add an appropriate twist.

I will need a query to see how many twists any particular cable is involved in.

I will also need a query to detect all the cables in involved. The "no twists" would return four collections of one cable, the "simple twists" would return two collections each with two cables, the "multiple twists" would return three collections with one and two and one cables, and the "arbitrary twists" would return one collection with four cables.

I think that's it. I'm not looking for a full implementation, just an idea to get this sorted out.

I've come up with some thoughts on my own that will work, but they all feel overly complex. I feel like there should be simple, elegant solution to this structure but I'm struggling to see it because I've been too close to the problem for too long.

Edited by frob
Formatting and clarity.

##### Share on other sites

As the cables move in 3D I can test if they would cross each other, and in that case add an appropriate twist.

This only makes sense to me if you're counting a "cross" as if projected in 2D somehow? Otherwise cables are either always twisting or never twisting if they aren't perfectly parallel.

I will need a query to see how many twists any particular cable is involved in.

Since I don't really have a good idea of what your insertion/removal/etc operations will be, the simplest thing I can think of is a vector of tuples: (cable1, cable2) where cable1 goes over cable2 (clockwise twist). (cable2, cable1) would be cable1 going under cable2 (anticlockwise).

It doesn't really make sense to me that you would be able to insert a twist in the middle of the vector, so you'll probably be push_backing everything. Might as well stick with a vector then.

I wouldn't bother trying to keep the isolated twists separate until they merge. "Merge" operations can be a hassle. Just keep everything in one vector.

Counting them would just be a linear pass that just tallies them all up (linear time for the loop, constant time for each increment operation assuming you can use constant-lookup for each cable into a map or array).

I will also need a query to detect all the cables in involved. The "no twists" would return four collections of one cable, the "simple twists" would return two collections each with two cables, the "multiple twists" would return three collections with one and two and one cables, and the "arbitrary twists" would return one collection with four cables.

This sounds similar to: https://en.wikipedia.org/wiki/Strongly_connected_component

There are some good linear time algorithms for that listed on the wiki page.

... Although, I guess your twists are more like an undirected graph. In which case you'll want a https://en.wikipedia.org/wiki/Disjoint-set_data_structure based algorithm, and treat cables as disjoint sets that you merge whenever they twist.

Found another thing that I hadn't seen before that might be applicable here:

https://en.wikipedia.org/wiki/Dynamic_connectivity Edited by Nypyren

##### Share on other sites

You're talking about braid groups right? Doesn't the standard presentation basically do what you want? For n cables:

https://en.wikipedia.org/wiki/Braid_group

G = <x1, ..., x(n-1) | xi+xj = xj+xi (|i - j| > 1 or i = j), xi+x(i+1)+xi = x(i+1)+xi+x(i+1) (0 < i < n-1)>

x2 means cable 2 goes under cable 3. x2 + x3 means cable 2 goes under cable 3 then cable 3 (which used to be cable 2) goes under cable 4. -x2 means cable 2 goes OVER cable 3. So x2 - x2 = 0. See below:

http://imgur.com/a/ix6YP

This numbering is different than yours, watch out for that. Below I encode your examples:

No twists:

0

Simple twist:

x1 - x3

= -x3 + x1

Multiple twist:

-x2 - x2 - x2

Arbitrary twists:

x1 + x2 - x3 + x2 + x1 + x3

= x1 + x2 - x3 + x2 + x3 + x1

Note: x2 - x3 + x2 != -x3 + x2 - x3.

Store the list of numbers (1, 2, -3, 2, 1, -3). It is exactly addition (in a group), when you see the same number and its inverse you just delete both. You can use the relations to rearrange and try to simplify the equation. E.g. ...

-x2 + x1 + x2 + x1 - x2 - x1

= -x2 + x2 + x1 + x2 - x2 - x1

= 0

See the other image in that imgur

To query how many twists a particular cable is involved in, you read the string from left to right, keeping track of which position the cable is in, and incrementing by 1 every time it is involved in a twist.

Or, since you always add twists at one end, do the computations to update the twists-per-cable counts every time you add a twist, and never recompute from the beginning.

To group the cables into components, where everything in a component is twisted together (transitively), read from left to right and keep track. Again, you can probably update this computation in real time if you prefer.

It's probably not very satisfying that you can get multiple representations for the same braid, even for the trivial braid, but that's fundamental to the problem. Maybe look into computations with the braid group?

Edited by EqualityAssignment

##### Share on other sites

This only makes sense to me if you're counting a "cross" as if projected in 2D somehow? Otherwise cables are either always twisting or never twisting if they aren't perfectly parallel.

They're able to move, like fish on the end of fishing lines, or kites on strings, or dogs on tied-off leashes.

They cross when -- as viewed from the base of the cable or the twist point -- they pass over a left/right boundary and then an up/down boundary, gaining either a clockwise twist or anticlockwise twist.

Since I don't really have a good idea of what your insertion/removal/etc operations will be, the simplest thing I can think of is a vector of tuples: (cable1, cable2) where cable1 goes over cable2 (clockwise twist). (cable2, cable1) would be cable1 going under cable2 (anticlockwise).

I suppose I should have offered up the solutions we've explored so far.

Initial "this can't be right" thought:

At first was a collection of twist tuples, {A, B, dir}.  When a twist is added, scan the collection for the {A, B} pair and if dir matches add another twist tuple, if dir is different remove the found tuple.  The problem is unbounded growth.

Computing the count of twists means scanning the collection of tuples and counting the matches in A or in B. Linear search based on the number of elements.

Computing the set of cables involved in each cluster of twists can be nasty but shouldn't be too bad in small numbers. Put a cable into the first collection and scan the table. Any cable that twists with it gets added to the collection and queued for scanning. Repeat until no new cables are added. Add the next non-added cable to the next collection and scan it for twists, adding as above. Repeat until all cables have been scanned. Gives N*M, each cable scans the each twist in the array once.

That potentially gets some horribly nasty growth as the number of twists grows, and soon we're no longer talking about nanoseconds for processing. As twists increase the problems rapidly grow. Design suggested adding a warning with a high number of twists like making cables start to blink and flash, and then calling it "broken" counting the game as a loss or something, but it wasn't satisfying.

After posting, someone (sadly not me, as I've been working on this too long) had an idea of a single element per pair with a count of accumulated twists, {A, B, sum}.  Adding a clockwise twist increases the sum, adding an anticlockwise twist decreases the sum. With 30 cables the worst case is 870 elements, which is tolerable.

That still leaves us with a linear scan to compute the number of twists but we can add abs(sum) for the total. It also leaves the N*M for collections of twisted cables. With 30 cables, that's 26100 tests to build the group of collections, and it could probably be cached and only marked as dirty if a twist is added and then recalculated when eventually requested, probably the next frame.  That's not horrible, but still feels too high to me.

##### Share on other sites

You're talking about braid groups right? Doesn't the standard presentation basically do what you want?

Looking it over, that's probably exactly the set of math behind it, although some of the actions inside the description don't feel like they match the problem, at least not intuitively.

I don't think that set of math makes the two queries any easier, though, I think they're still the same linear and N*M operations, unless there is something buried in braid group theory that makes them faster.

Edited by frob
Quoting text is hard when brain is fried. Probably time to be done for today.

##### Share on other sites

But clumping cables by twist shouldn't be on the order of #cables*#twists should it? Assign every cable a color, then for each twist, if the cables have different colors (red, blue), pick one (red), then for every cable if its color is red make it blue. Iterate until no more twists. Each time you replace a color like that, the number of colors falls by 1. When it hits 1, you know every cable is together and you early-out. At the end you arrange the cables into lists by color.

So you can never iterate all the cables more than (#cables - 1) times. Because for each twist, either the cables are the same color and you don't iterate all the cables, or they are different colors and that can only happen (#cables - 1) times.

That's #twists + #cables^2 + some #cables terms for set-up and tear-down right? If #twists is the problem that should be fine?

Edited by EqualityAssignment

##### Share on other sites

Doing some more math and tracking them from the same perspective I was considering before, it boils out be the same. Their operation of ?1?2?1 = ?2?1?2 gives me the pairwise result of  {A,B,1} {A,C,1} {B,C,1}, and a few of the other operations also boil down to the same results when taken pairwise, the only difference is referencing them based on their cable letter rather than the index at the time of twist.  Since the game objects in the world will be tracked by the cable their attached to, it seems that would be the more natural approach for this.

The Wikipedia articles suggest the most compact representation is the "Lawrence–Krammer representation", taking (n(n-1))/2 square matrices, for 30 with each a pair, that works out to be the same as the all-pairs collection, so at least we happened upon the tightest representation.

I'm still not seeing anything useful for improving the two key operations of twist count or the sets that are braided together. ... but looking at the dates of the papers on braid theory, most within the last 60 years, this stupid little problem could become a published math paper if someone was bothered enough to write it up. :-)

When it hits 1, you know every cable is together and you early-out.

Yes, there are several early-out possibilities. If a cable is already included you don't need to test anything against it. But for such a small number, the cost of making special-case loop hopping probably is about the same cost as the cache-friendly linear scan.  With a structure of { byte, byte, short } or even {byte byte byte} it suggests some SIMD operations could make short work of the 26100 worst case.

Edited by frob

##### Share on other sites

After several more hours of research, and discovering there really isn't much depth to the young field of braid theory, I realized this encoding may be entirely novel, at least as far as research papers go.

I think (but haven't done that type of proof since grad school decades ago) it provides a unique, guaranteed minimal-twist encoding, which looks both shorter and easier than the normalization encoding you mentioned and the literature I could find also mentions.  There is no extra work involved since the minimal form is naturally accumulated when spanning the range. The only real change is that instead of consider operations by row you instead consider them based on the ID of the two lines that twisted.

Anybody looking for some low-hanging fruit for their math degree?

##### Share on other sites

First, in your blog post, "Multiple twists: {0, 0, 0, -2, 0, 0}" should be "Multiple twists: {0, 0, 0, -3, 0, 0}" shouldn't it?

More importantly, I think your normal form isn't right. Let there be three cables, red, green, and blue. Then we have an a length three twist array: {green-red, blue-red, blue-green}. I can make two different braids that both have twist array {2, 0, 2}, but they are not the same. In particular, if you add the same sequence of extra twists to the end, one of them untwists all the way and the other gets twistier. I think that is gonna be a problem for you?

Images here:

http://imgur.com/a/IDcls

x1+x1+x2+x2 and x2+x2+x1+x1. If I understand your idea right, you would call them both {2,0,2}. If you add (-x2-x2-x1-x1) to the end, then only one of them becomes the trivial braid, both you would call both {0,0,0}. I think that will cause problems for you?

The normal form defined in that paper doesn't look too much like yours to me. As exhibited above, even the positive word component can't be reduced to {*, *, *} form. That's equivalent to assuming commutativity for twist-addition I think, and commutativity fails.

I agree that your twist-array is a braid-invariant, but not a complete one. If the braids are the same they have the same twist-array, but if the twist-arrays are the same that doesn't mean the braids are. You basically proved that in your blog post. The set of twist-arrays has group structure with elementwise addition. The mapping from braid to twist-array is a group homomorphism. You proved this yourself, by showing that the sum of the twist-arrays of two braids is the twist-array of their concatenation, and by showing that the relations xi+xj=xj+xi (if not adjacent) and xi+x(i+1)+xi=x(i+1)+xi+x(i+1) hold for the twist-arrays too.

In the paper they use a braid invariant called exp which just counts twists (-1 for one way, +1 for the other), the twist-array is a stronger version of that invariant that counts twists for each pair of cables individually.

The normal form they define in the paper expresses every braid as the concatenation of a power of one of the "Garside braids" and a "positive braid", in which every crossing goes in the same direction (CW or CCW). If I am reading the paper right, the Garside braids themselves are positive braids, and in the normal form, the Garside braid always has power <= 0. Basically if you have B = delta^k * T with B a braid, delta a Garside braid, and T a positive word, you can always do B = delta^k * delta^(-1) * delta * T = delta^(k-1) * T' with T' = delta * T a new (larger) positive word. So you can always make the power on delta smaller, but it is bounded above. (Sorry, I just switched from additive to multiplicative notation.)

(Finally, The Sage mathematics package can draw braids nicely ... so no more gimp for me :). It's a pain to install though so that doesn't help you.)

I guess this still doesn't help you solve your problem. Good discussion though, thanks for bringing this up.

Edited by EqualityAssignment

##### Share on other sites

Multiple twists: {0, 0, 0, -2, 0, 0}" should be "Multiple twists: {0, 0, 0, -3, 0, 0}

Good eyes. That's three full rotations in my crappy hand drawing. Updating.

x1+x1+x2+x2 and x2+x2+x1+x1. If I understand your idea right, you would call them both {2,0,2}. If you add (-x2-x2-x1-x1) to the end, then only one of them becomes the trivial braid, both you would call both {0,0,0}. I think that will cause problems for you? ... twist-array is a braid-invariant, but not a complete one ...  they use a braid invariant called exp which...

It's been many, many years since my last class on topology (and I wouldn't care to repeat it), but I understand your comment about being braid-invariant but not complete is rather important. That's the part I don't really have the time or patience for in this math.  My understanding of reading that is that the core question is about the end conditions, and if a specific line can be pulled out or not.
I think that's where the notation difference becomes important. Their notation is about the row of the twist without regard of the line they are on. My notation was about the twists between individual lines without regard to which row they are in.
If you're counting the rank of the twist, this one happens relative to rank 1, that one in rank 2, another in rank 7, then they are not commutative because each change also changes the lines that are involved.  A twist on x2 one time happens to change red and green. A twist on x2 another time happens to change black and red.  Later a twist in x7 could also involve red and green. It appears that ordering is only important because they are operating on the rank of the twist, not operating on the lines of the twist. There might be other reasons in their theory, but I don't see them.
If we are working with the lines instead of the rank then (I believe) they are completely commutative. A swap of the red and black lines is the same no matter what rank they happen to be in at the time. There might be something more in their branch of math that causes that to be not true in the general case.

The normal form they define in the paper expresses every braid as the concatenation of a power of one of the "Garside braids" and a "positive braid", in which every crossing goes in the same direction (CW or CCW).

That part was a little trickier for me in the papers.  You can change the notation in a pair by reversing the order.  {Green Black +1} is equivalent to {Black Green -1}. For reasons of convenience I'd prefer them in consistent ordering by cable (e.g. operator less()) , rather than consistent ordering by direction (e.g. always positive).
I don't think that part makes a difference. I dislike their normal form because it focuses on something that is irrelevant to me. Which leads to the core of my problem, which I think is now fully resolved.
In my specific problem, I'm trying to control a few things:

• Is the line involved in ANY twists? If no twists I can operate directly.
• If there are twists I need to establish a knot point. Doing that means I need to know ALL the lines involved in the twists. If I have a knot involving the tethering cables holding objects A, C, and F are involved in a twist, then I need the knot to slide to their central point between the lines, which will be the midpoint between the three.
• If an object can escape from the knot it needs to be able to do so immediately.

So in my specific problem we assume the lines can slip and slide freely because they are slippery and constantly being tugged. Ordering of the twists are irrelevant. Even if there are ten other line twists mixed among them, if a red line looped clockwise over the black line once, then there were a bunch of other twists involved that included the red line, then the red line eventually looped anticlockwise over the black line, no matter what other twists were involved with the red line, if that was the only involvement with the black line then the black line would be free of the braid.
If red was twisted with green, green with yellow, yellow with pink, and pink with black, it would still be linked to the braid, but if black could get a corresponding un-twist for each, it would be free and could leave.
An unexpected aspect that doesn't fit well with what I was reading is a simple physical problem.  Suppose I had three of them floating in a cluster, arbitrarily choosing A, C and F because I've mentioned those before, then another one (J) floats around them in a circle, it ends up adding a twist with each line individually as at passes.  Wrapping around causes a twist between AJ, CJ, and FJ. No matter what other twisting A, C, and F do, each one can perform an anti-twist with J and because they can slip freely, J becomes free.
I'm not absolutely sure physically if that works out exactly the same, and and that's where the question remains.  If A, C, and F have their own individual twists with J wrapped once around the bundle, would an anti-twist of AJ always free that pair? No matter the other twists, would CJ and FJ anti-twists free those pairs?  When I run it on paper myself I can always free the line, and that's why I think it works out. But I don't want to do the number crunching to prove it.

So as far as my problem set is concerned, I *THINK* it solves all the issues.  Physically it may be awkward to slip through an enormous pile of knot twists, but logically it seems that they could slide freely and the lines would escape the knot regardless of the topology of the other knots.

If that works out, I think it would be a useful alternate normal form, since it seems (I will readily admit to error) that the pairwise representation encodes the final twist state of all cables. If order doesn't matter -- and I don't think it does due to the examples they give of x1-x2-x1- being equivalent to x2-x1-x2-, then a strict weak ordering of pairs (like the < operator) would give a self-normalizing form. The papers discuss manual steps to find the shortest form in order to establish the normal form, but I don't think that is necessary. The papers also involve heavy math steps walking through the entire twist chain to see if a line becomes free of the braid, but I don't think that's necessary either with this encoding.
But as I wrote, it has been a long time since my math classes and there are probably more nuanced details that I am overlooking or not understanding.

##### Share on other sites

On the question of does it slip free, in my program the answer will need to be yes. In braid theory it needs to be no.

##### Share on other sites

I may have sent you on a wild goose chase with braid theory. Sorry about that :(. It sounds like you are saying that that bottom set of lines there--where blue/green twist in steps 3, 4, 7, and 8--that those strings will all slip free in your simulation, so that configuration is basically no tangle at all? If that's what's happening, then your algorithm seems correct to me.

I must be misunderstanding something. Actual, physical, strings in that configuration don't slip free: I just took three very thin wires and twisted them together like the green blue and red lines in that bottom plot, then I taped the ends down, and I found that I could not separate the wires without removing the tape.

Are the top ends basically free in your simulation, since they are connected to kites, not the ground? Like you can pull the kite through the knot to get it and its string free? I guess then every knot would slip free though ...

It's not important that I understand what you are doing though, only that it works for your purposes. So if you are convinced then don't worry about it, the fault is mine and no harm is done :).

Edited by EqualityAssignment

##### Share on other sites
So, wait... cables will *always* be able to untwist if they're all completely independent at at least one end. Otherwise how did they form that twist in the first place? Providing a force which is allowed to, the twists would naturally untwist in the reverse order they became twisted, and adjacent opposite twists would cancel each other out immediately. What I mean by "dependent" vs "independent" is:

When you mentioned kites, I thought about stunt kites. Stunt kites have two, four, and maybe more strings that let you control them.

If you turn a stunt kite, it can twist its cables, but the twists it can make are constrained - on a four line kite, you'd never be able to get the diagonally opposite lines to cross without first crossing one of their adjacent lines. And things like that. Those types of lines are "dependent" on each other.

Similarly, if you try to tangle two different kites' lines with each other, there are some types of twists which are no longer possible due to the constraints they have by being fixed to a specific kite. There are edge cases such as flying one kite between the other's lines first, or passing one of the control lines between one of the pilot's arms, but there is a definite set of constraints that exist based on how the ends are anchored (or not anchored) in relation to each other.

As far as twists "sliding", there are certain combinations of twists that prevent sliding. Think of the classic 3-line braid. You can't slide any of those twists before or after the twists that come before/after it. You have to undo them by starting at one of the ends. You can change the length of the lines *between* twists, but if that space has been reduced to its minimum (as in a tight braid or a braided rope), you can't slide them any further in that direction.

Because of this, I REALLY doubt the twist state can be represented as a constant-sized set of twist counts. It feels heavily order-dependent to me.

In braid group terms, the longer a classic 3-line braid gets, the pattern (?-1?2)+ is used; the + is Kleene plus. As far as I can tell there is no way to simplify any expression generated by this pattern into a shorter expression, so as more twists are made, the braid group expression either requires unbounded storage space just like the vector-of-tuples does, or a complex pattern recognizer to do things like add that Kleene plus (you may be able to use a simple compression algorithm like Sequitur on it). But the braid group expressions don't track the identity of which cable is in which position, either.

I feel like we're still missing critical information about what you need to do before we can come up with data structures and algorithms for it. Edited by Nypyren

##### Share on other sites

I find it hard to understand what you're aiming for, or what you're trying to solve. No idea if my suggestion will do any good, but perhaps it will push you into a better territory.

Instead of "twist", I'd use 'move in front'. One wire moves in front of (1 or more) of its (left or right) neighbours. All neighbours move 1 position in the other direction. Sequences of movements with the same wire can be merged trivially.

If you encode the movements on absolute index positions, tracking which twists are independent is simple, but finding the involved wires is a mess. If you attach the movements to a wire, it's simple to see how a wire changes position, but the final twisted result is difficult.

Perhaps you need to duplicate the latter, use absolute positions, but also tag which wire colours are involved.

Edit: Also, any movement that only involves a sub-set of the neighbours is independent as well, and can be swapped. Perhaps a normal form can be to push down and merge moves as much as possible.

Edited by Alberth

##### Share on other sites
I may have sent you on a wild goose chase with braid theory. Sorry about that .

Actually it helped me quite a lot.  I read everything I could find on the subject, quickly scanning for bits that were useful for me and discarding stuff I didn't want to wrap my brain around.

It taught me that we were on the right track (good to have affirmation). It taught me that there are ways to solve the problems that ARE physically correct, but they are beyond the scope of this simulation. It also taught me the approaches for the query are basically correct, and if we relax it to be physically incorrect it can still approximate to be close enough.

When you mentioned kites, I thought about stunt kites. Stunt kites have two, four, and maybe more strings

I fly those, which is a reason I mentioned it among the examples.  These kite lines use a synthetic line, a product called Spectra, which is lightweight, has amazing tensile strength, and is EXTREMELY slippery. Most twists can be resolved without difficulty, sliding right through each other.

Among the more difficult group maneuvers ("compound benefits") has six kites with four lines each go through nine combined twists, so 216 combined twists. Again, they naturally bunch up and slide into a central ball of line. They each flip in the middle (which can be difficult to slide through), then reverse the chain of twists.  I'm not skilled enough to even dare that type of maneuver, but I've done some smaller multi-kite stuff involving around 64 twists, it still slides easily with twists between lines sliding right over each other.

I got to fly three times this week, once with my dual lines, twice with my quads, in some fun groups.  It's a fun hobby.

No idea if my suggestion will do any good, but perhaps it will push you into a better territory.

Thanks.  I'm pretty sure I've got my issue resolved thanks to the bunch of braid math.

Now that I have the real braid math involved, I know solving it physically can't be done within my compute budget. However, the approximation solution has a known worst case -- now reduced to about 13,000 items in a linear search -- which is easily within budget.  The typical case is back down to something that can be solved in nanoseconds again, so the terrifying part of the problem is over.

##### Share on other sites
each twist is represented as

struct twist
{
float position;
twist * with;
}

tiwst * twists; //first element

now you have 1d platform with all ropes

you have to define first twist as postion with lowest value, another twist with position as bigger value than before, or use * next, * prev list

you cant define a tiwst without a twist.


Edited by WiredCat

##### Share on other sites

Wiredcat, I think you misread the entire conversation.

## Create an account

Register a new account