Creating even valence graph / traversing all edges of a graph

script
rhinocommon
grasshopper
mesh
unhandled

#1

Hi all,

Any advice on making the valence of a given mesh/graph always even, either by generating one or transforming an existing one?

Thanks a lot.


Networkx Module on GhPython
(Daniel Piker) #2

For a triangulated mesh you could put split each face like this:
image


#3

hi @DanielPiker thanks - maybe we’re misunderstanding each other, but aren’t all the naked vertices of this graph valence three?


(Daniel Piker) #4

ah yes! I was assuming a closed mesh.


(Daniel Piker) #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.


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


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


(Daniel Piker) #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


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


(Pfotiad0) #13

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


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


(Pfotiad0) #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):


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:


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