Creating even valence graph / traversing all edges of a graph

I actually wrote some code for finding Eulerian paths for 3d printing not long ago - the general approach I used was to pair up and connect the odd valence nodes (there is always an even number of them in any graph), then use Hierholzer’s algorithm to find an Eulerian path.
You generally still have multiple choices at each step though, so it helps to have some geometric rules by which to decide in addition to the topological ones

3 Likes

Thanks a lot for the links! It seems like I have got it working so far - haven’t done extensive testing yet. Could you please show me what your routine is for turning a network of lines (which isn’t necessarily a mesh) in gh to a networkx graph?

Pardon me Timothy … but are you by accident after Graph routings like the ones (all nodes NOT connections) shown?

hi peter, no, i’m after the chinese postman problem, where i can traverse all edges with one single polyline, but thanks!

Thanks Daniel - I actually have implemented the Eulerian path myself a few months ago as well. I just wasn’t sure about the pairing of odd valence nodes for this question now, but will try to implement the algorithm for Chinese Postman Problem now. Would you mind exposing what you had in the topologizer component? It’d be great to see your routine in making a given line network into a graph in the grasshopper environment.

Hierholzer’s algorithm then?

See an old example here (it has two functions meshVertexGraph and meshFacesGraph for making networkx graphs for respectively vertices and faces):

1 Like

Ivy might also be relevant here, although I believe it mainly operates on face-graphs, but’ I’d have a look.

Cough… see above… cough:

1 Like

awesome - thanks so much!
when the graph has edges that cross each other, however, using the weaverbird mesh from lines returns a mesh that has overlapping faces; would this be a problem for using the mesh methods? or is it better to define a graph straight from a line network without the mesh?

if anyone is still interested in the problem:

i’ve managed to import networkx library (version 2.0.dev_20160927182259) into rhino6 and gh and implemented some of the codes to solve the route inspection problem from the very detailed tutorial from here:

thanks @DanielPiker @AndersDeleuran @PeterFotiadis

2 Likes

That’s terrific, can share how you managed to get this working (for future reference on the board)?

Of course! i actually responded to a post afterwards describing the process.
I placed the networkx folder into C:\Program Files\Rhino 6\Plug-ins\IronPython\Lib\site-packages\networkxrkx , typed in _EditPythonScript command in Rhino, went into Options (under Tools tab) and added the same path. Let me know if it works if you happen to try it out. Thanks again for the help!

Good job (wrong language).

Latest (and greatest) news: Postman escaped to Vietnam (LOL) and changed trade: now he does the Hanoi Tower stuff:

:roll_eyes:

hi @timothytai :slight_smile:
some years have passed, but I was wondering if you still have this file?

I am looking for a similar thing…
I have imported networkx library into rhino and gh, and this code into the pyhton component, but I am not sure what the args I should give.

(Like what should I connect to Destinations for example)

I was wondering if you still have it and could maybe share it so I can learn from what you have done?

would help me a lot!
Thank you very much!

You can find a recent implementation of my old script here:

2 Likes

Oh now I see that I was fully addlepated, I was actually looking for Hierholzer’s algorithm,
But thank you very much!

As far as I understand, Hierholzer’s algorithm is one of several methods for constructing Eulerian circuits. I’ve never done so myself, nor checked which algorithm it implements, but one might implement the networkx method for computing these. It appears to be available in the old 1.5 version compatible with IronPython 2.7:

Edit: Here’s a quick implementation @Moria_Schwarz:


230127_EulerianCircuit_NetworkX_00.gh (5.5 KB)

3 Likes

Thank you so much!

1 Like