Euler-cycle / path that doesn't cross itself

Hey,

I am new to gh, and I am looking for an Euler path on a mesh that doesn’t cross itself as in this example:

so far I have managed to find an eulerian path on mesh, but I am not sure how to define that it will not cross itself.

Thank you very much, I appreciate your help!
test surface.gh (56.1 KB)

Your def is using lot’s of add-ons (I don’t work with any other than K2). One of them is called Euler Cycle (so it should - in theory - provide a solution).

Anyway … Euler/Hamiltonial paths in graphs are one of the most challenging tasks known to man (if we want a solution in less than a week). If the EulerCycle thingy doesn’t work AND you can’t code (level required : expert) I would suggest to go after some other task. See Ham cycles using Meshes as Graphs.



And one in a rnd prox Graph:

That said 99% of the Internet solutions posted are out of question (N factorial : why bother talking?)

1 Like

thank you very much for your answer,
it indeed provides an Euler path for a given mesh (after making sure that all the mesh nod degrees are even, and if not pairing based on distance, find the shortest way between the 2 vertices for each pair and double the edges, according to the chinese postman problem - Chinese postman problem - Wikipedia)
In this sense, it works perfectly.

however, I do look for a specific one: an Euler path that doesn’t cross itself.

I am willing to put my time on because it is important to me, but I am looking for a clue on how to start
thanks again!

FWIW, the source code for the networkx method I implemented is open source. Might help if you intend on writing your own implementation:

https://networkx.org/documentation/stable/_modules/networkx/algorithms/euler.html#eulerian_circuit

1 Like

Well … thst’s kinda saying that a Harley Davidson is a motorcycle. I mean a Ham path/cycle algo should work (if there’s a solution anyway) on ANY valid Graph. So your thing is … er … hmm … some other thing.

That said your C# for the prox pairs … well … that’s another quite hard task: imagine trying to find the “best” prox pairs. In order to get the gist of what the issue is do a graph that displays the distances … and attempt to make it “as even as possible”.

.
Kinda a Steiner Graph pairs problem.

Anyway … you don’t need “best” prox pairs for a Ham cycle so don’t bother with that one.

How to start? Get a Graph, do the VV Connectivity, find possible islands (general case) using SOLELY the VV (and some Recursion) and “reorder” the VV using obviously 2 dim paths. Any “isolated” VV means a classic Adjacency Matrix: the only thing that a Ham cycle solution needs (assuming that the cost is not an issue for you).

How to end? In order to be pragmatic you should avoid any N factorial algo: this means advanced heuristics, so to speak.

Tip: what about a TSP thing? Or a PMST? (both are far easier to deal with).


PS: 1 to 10 what is your C# Level?

well, I am actually interested in a path that travels through all the edges once - the Euler path (and not through all the nods- Hamiltonian path), and specifically a path that doesn’t cross itself.
unfortunately, the Hamiltonian cycle/path are not relevant to my problem at the moment.
your definitions look fantastic though! maybe for a next project :slight_smile:

Get any Graph > do the VV/AdjMatrix thing > then do that:

PS: Replace Dictionary (very slow) with … anything else in fact.

There doesn’t appear to be much precedent, but this paper might be relevant assuming planar graphs:

1 Like

Indeed (most notably when an E path can visit Vertices more than once). It could be a good thing if we had some insight: what is the goal? Some AEC thing? (a freaky truss “spine” for instance). Some routing optimization? Some Academic thing?

Plan Z:

EH_Graphs_chapter5-part2.pdf (315.4 KB)

This is rather a very simple paper to follow. Also is very easy to write a Method that tells if an Edge is a Bridge (*). So given a Mesh, the Mesh TopoV, TopoE connectivity Methods available in R SDK (thus the related VV, VE, EV Trees AND the Bridges) … blah ,blah. Plus during the search a “cross” check Method based on neighbor indices intersections maybe could cut the mustard.

(*) Like:

And in case that you think that the right most result is wrong:

1 Like

Hello
I don’t follow where you are now, but for

If you have a graph that is self intersecting, you can use it in order to suppress self intersection.
The idea is quite simple at each self intersection flip the direction of the curve . I have done this tool for curve in my Nautilus Plugin (not online at the moment, but could be send).
If you have that


You could get that

3 Likes

Thank you all very much for the time and help!