Creating even valence graph / traversing all edges of a graph

Grasshopper
#4

ah yes! I was assuming a closed mesh.

#5

do you have any other constraints on the geometry? or you only care about the topology?

#6

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?

thanks again!

#7

Do you mean something like a Hamiltonian path? Either way, perhaps implementing a graph library, such as networkx, might be a way forward here.

1 Like
#8

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.

#9

@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:

I need help with creating a Python script for the Chinese Postman Problem
#10

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.

1 Like
#11

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
#12

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?

#13

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

Screen%20Shot%20150
Screen Shot 150.JPG1609×721 664 KB

Screen%20Shot%20151
Screen Shot 151.JPG1734×680 508 KB

Screen%20Shot%20152
Screen Shot 152.JPG1734×680 467 KB

#14

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

#15

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.

#16

Hierholzer’s algorithm then?

#17

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

1 Like
Joining 'Neighboring' Meshes / Connected Graphs to Meshes
#18

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

#19

Cough… see above… cough:

1 Like
#20

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?

#21

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
Network of curves to single curve
#22

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

#23

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!