please find attached an example graph i was looking at. graph_1.gh (3.9 KB)

so the whole story is: i would like to traverse this graph with one single polyline ideally without repeating an edge.
one way to do so is to make all the vertices even valence, then i will be able to traverse it with an euler path.
hence the even valence question above.

i would say that if there is a way to keep the topology as much as possible that would be great, but perhaps some operations like edge flipping locally would be fine too…

alternatively, is there a way to ‘traverse as much as one can’ (without repeating an edge) either in terms of numbers of edges covered, or edge lengths covered?

hi @AndersDeleuran, i wouldn’t say it is necessarily related to the hamiltonian path although i have looked into it, since i don’t really care about only traversing each vertex once.

@DanielPiker@AndersDeleuran I think the second half of my question, where the graph doesn’t necessarily consist of all vertices with even valence, could be viewed as the Chinese Postman Problem. It does seem like having a library like networkx could help. Anders, might you have experience with it in GH?

However, It seems like many had problems trying to import the library into the python node.
And in addition, numpy and scipy are needed by networkx, and I believe the former two libraries only work in 32bit? Maybe relevant:

Indeed, I’ve used it quite extensively. There are known compatibility issues with IronPython and networkx (beyond version 1.5). Some discussions and GH install instructions/files can be found here.

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

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?

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.

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?

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:

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!