Creating even valence graph / traversing all edges of a graph

timothytai · March 13, 2018, 8:55pm

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.

DanielPiker · March 13, 2018, 9:06pm

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

timothytai · March 13, 2018, 9:21pm

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

DanielPiker · March 13, 2018, 9:54pm

ah yes! I was assuming a closed mesh.

DanielPiker · March 13, 2018, 9:59pm

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

timothytai · March 13, 2018, 10:05pm

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!

AndersDeleuran · March 13, 2018, 10:33pm

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

timothytai · March 13, 2018, 10:35pm

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.

timothytai · March 14, 2018, 1:52am

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

AndersDeleuran · March 14, 2018, 9:30am

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.

DanielPiker · March 14, 2018, 9:42am

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

timothytai · March 14, 2018, 4:10pm

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?

PeterFotiadis · March 14, 2018, 4:47pm

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

timothytai · March 14, 2018, 5:20pm

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

timothytai · March 14, 2018, 5:28pm

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.

PeterFotiadis · March 14, 2018, 6:05pm

Hierholzer’s algorithm then?

AndersDeleuran · March 14, 2018, 6:11pm

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

github.com

AndersDeleuran/MeshAnalysis/blob/master/src/MeshPaths.py

""" 
Calculate shortest paths on a mesh. Uses the NetworkX 1.5 Python module:
Download here:
http://networkx.lanl.gov/download/networkx/
Read about shortest path algorithms here:
http://networkx.lanl.gov/archive/networkx-1.5/reference/algorithms.shortest_paths.html
-
Name: MeshPaths
Updated: 141031
Author: Anders Holden Deleuran (CITA/KADK)
Copyright: Creative Commons - Attribution 4.0 International
GitHub: www.github.com/AndersDeleuran/MeshAnalysis
Contact: adel@kadk.dk

    Args:
        Mesh: The mesh to calculate paths on.
        Destinations: List of lines representing path source (line start) and path target (line end).
        GraphType: Make the mesh graph nodes from either its vertices or its faces
        PathMode: The algorithm to use when calculating the shortest path (refer to NetworkX documentation).
        WeightMode: The graph edge weight. Can be either metric length or the same weight for all edges (1).

This file has been truncated. show original

AndersDeleuran · March 14, 2018, 6:15pm

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

AndersDeleuran · March 14, 2018, 6:17pm

Cough… see above… cough:

timothytai · March 14, 2018, 6:20pm

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?