Graphs as Dendrograms


I am struggling with this problem for weeks and I am almost to give up.
Let’s say I have a given number of polylines, in this case 166. In random order.

And I want to order them so they have path-like logic. I choose starting polyline, in this case southernmost one and start ordering them. Similar to this…

The best and cheapest way that almost completed the task, was this one:
sort mid-points by Y-values, pick the 1st for starting point,
plug it into P-Input of Sequantially-Sort-Points by neoarchaic (,
and plug all mid-points into S-Input. This is the result…

165-indexed point/polyline is problematic, as let’s say 10% of all. It is almost good-enough.
I am aware that script is choosing the closest point until the list is exhausted, so 164-point had to choose 165 since no one else has left.

The best solution I can think of is to solve TravellingSalesman path through all mid-points, draw the polyline and sort mid-points on it, then sort plylines accordingly. I have tried converting this to line-network and applied native shortest walk component, but it only allows 2 points per path.

I know this is complex problem, at least for me, since I do NOT know scripting.

Do you have any suggestions?

Or if it this TSP approach is super-heavy/impossible is there a way to move this 165 indexed point to index 1, then shift all list after index 1 by one. Find next wrong index move it to correct one and so on. It is not problem if I do it manually, since there are 10-15 points to move. It is not necessary to have it perfectly ordered, as long as I don’t have neighboring indices with large number difference.

Thank you in advance. (84.7 KB)

That’s rather easy via code (using a classic recursion on your poly List) but as you said you are not familiar with that option, meaning that you want something that you could manage and maybe use it for other cases as well.

So … If nobody provides a component based solution (and/or using some sort of add-on [I’m not at all familiar with what is available out there]) I could post a C# that does that very fast.

Searching through this great forum, reading posts i have learned and improved myself a lot.
And it seems that i have reached the level that i have to learn coding. And i will do it for sure. Especially when i see tons of elegant solutions that you and few alike have provided via C# here.

Until i learn coding or untill someone else/you helps me, i am stuck on this one.
What to say, i have to wait anyhow. Question is how much :slight_smile:

Whatever you decide, i am thankfull for all of your posts.

You are very kind.

But the good news are that after waiting, say, 1 day max for some “normal” good Samaritan … you’ll receive the salvation (or the torture) in some “simple” version that could being used as a starting point for your future walk to hell.

In the mean time I do hope that you are familiar with DataTrees, paths and other mysterious things because the solution (a classic hierarcy of nodes in fact) it would be via a DataTree where each child dimension would designate a child node . TextDots would indicate what is where (and why).

A simpler solution is to create a connectivity tree … but let’s do it the hard way, he he.

BTW: This is “similar” (and rather very close) to what you need. But … is Paradise or Hell depending on … er … hmm … you know what (but no pain == no gain). In fact this is what I had in mind for adding a line here and there and doing the thing of yours.

That said … the slightly(?) naive logic used (these freaky long paths that tell you all what you want to know) … is rather out of question if you have to make a ccx dendrogram out of a zillion polylines. Notice that I don’t care to measure Elapsed time (no need: is rather real-time).

DO NOT use your stuff on that thing because is using a root collection of curves (the “river”) whilst in your case the root should be some “start” polyline according to some rule, say, the left/bottom one in your graph etc etc (very easy to find the index of that, mind). (138.6 KB)

You can play a bit using as root poly the “river” (red) and as many branches you dare to add. Info panel counts the derivant dendrogram branches from that root curve. We must change ASAP that locomotive long paths thingy, mind.

1st Note: Updated collection of curves with omitted tiny one…everything was broke in 2 islands, now it is not… (37.6 KB)

2nd Note: Wow man, what a script!! Incredible.
Followed your instruction…picked the root polyline…
Still that neighbouring polyline is causing some issue…

Having 2 indices: 1 & 164. In 'Facts&Figures" 2 branches were found. 2nd starting at index 163. Tried baking and joining at that index, but still not solved. What do you think might be the case here?

Through the network, indices are splitting well at intersections, with strong logic behind… Love it!!

Still sometimes there are some high jumps like here…

What do you think? Might be that i need a longer root polyline spreading all the way from SouthWest to NorthEast? That would not be desirable since i want to keep some kind of 1 index/street, but is it the main constraint here?

Er … hmm … that thing is written for “similar” but not exactly the same purposes meaning that bananas MAY be in the menu for a vast variety of reasons (in fact bananas are always in the menu due to a user input different from what the idiot (who wrote the code) had in mind … that’s the bad aspect of coding, he he).

Let’s make a break: Imagine a graph that is NOT the ideal node to node thingy: meaning that segments (polylines) MAY not start/end at the graph nodes. What to do? How can we make a proper dendrogram and then do this, this (and that?).

See Phase1 in the attached and compare input and result (is just a WIP : I’m thinking for a major change in the whole concept having a zillion polylines in mind). (137.8 KB)

In the mean time: what if your graph has islands? (so what? we can detect them using the connectivity tree). what if has bananas? (we can do a banana split) what if we run out of cigars? ( that’s critical > adios amigos > no coding possible).

More soon … but see this wind report (I hear The Voice: there’s a mini gale around > quit the stupid thing ASAP and do the proper thing [i.e. a windsurf wave session]).

1 Like

Well, if Poseidon and Aeolus aim your board and wings to Montenegrin shores, dont worry, food & shelter will be provided. :slight_smile:

Perhaps Opt-2 strategy could resolve some of the issues?:

// Rolf

My dear Watson: using JUST a VV Graph conn tree (I do hope correct) you can detect any islands present (just do a recursive search on the indices and if no more found around: that’s an island, go for the next).

Moral: sail size 4.5 time (Ave, Imperator, morituri te salutant).

After a proper wind session I’m more after Jack Daniels matters you know.

Back to business:

  1. Automation for locating the root is out (automation is lobotomy) : use the “crosshairs” and pick any root curve you like. If you don’t > no honey + no party.
  2. The second C# does a recursive reorder of the connectivity tree using the index of the root curve resulting in fact a hierarchy.
  3. The dimension on each branch reflects the hierarchy depth and the indices are the indices of the nodeTonode computed curves from the first C#. This means that we can handle any N of polys and any depth (adios locomotive size paths). That said if your polys are nodeTonode on the first place … no harm done (the out List is the in List).
  4. Text dots are used for identifying things (by index). Notify if you need some other format.
  5. No island detection is included (I’m not sure if I can post a similar thing: is classified as internal) … so for the moment take care for a graph without islands.
  6. No tests are included for the ccx events and/or cycle (cirquits) stuff and/or the min poly length allowed etc etc (if your graph is bananas > a banana split would be the result). (146.0 KB)

BTW: That man said to me that your thread title is wrong: the correct one should be Graphs as Dendrograms.

BTW: V1B is 2+ times faster. Recycle the pathetic V1A ASAP. Notify is you want a flag to by-pass the nodeToNode phase/check (VERY risky) resulting 10 milliseconds max Elapsed time (in total) … almost for any reasonable N of polylines. (149.4 KB)

Here we are: take the challenge and win 10 cans of genuine DaMorgada sardines in pure mineral oil (15W/50).

Changed the thread title :slight_smile:

I am not ignoring your solutions, still testing them…
It seems that i have very chaotical inputs and unfortunatelly cannot affect them…they are simply facts from surveyors.

Well it seems that a special build is required: BananasGraphs_Dendrograms_V666. Here’s what I have done about that insofar:

The ugly news are that the next w/e is F1 time (forza Lewis) and MotoGP as well (forza Vale).


  1. Radical change in the whole approach: Elapsed time goes from 100 milliseconds to 2-3 (or maybe 5) for about 600 test Polylines (how this happened? it’s a mystery).

  2. Study the image: the newly added GetBananasDoNodeToNodePolylines function detects gaps in bananas Polylines and does good Polylines. Plus informs you where the change occured (Poly index) and displays Circles related with the fix: a mutual close gap acc a used defined search value (how this happened? it’s a mystery).

  1. The only issue is that the whole thingy works only for collections that look like a banana AND Polylines are yellow (how this happened? it’s a mystery).

Moral: hope dies last