Skip to content

Graph Module

graph

This module provides a Graph class and functionality for skeletonization using graphs.

Graph

This class is for representing graphs embedded in 3D. The class does not in itself come with many features: it contains methods for creating, accessing, and housekeeping. When vertices are used as parameters in the functions below, we usually use the parameter name n (for node). n is simply an index (i.e. an integer) that refers to a node (aka vertex).

Source code in pygel3d/graph.py 
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Graph:
    """ This class is for representing graphs embedded in 3D. The class does not in
    itself come with many features: it contains methods for creating, accessing, and
    housekeeping. When vertices are used as parameters in the functions below, we usually
    use the parameter name n (for node). n is simply an index (i.e. an integer) that
    refers to a node (aka vertex)."""
    def __init__(self,orig: Self|None=None):
        if orig == None:
            self.obj = lib_py_gel.Graph_new()
        else:
            self.obj = lib_py_gel.Graph_copy(orig.obj)
    def __del__(self):
        lib_py_gel.Graph_delete(self.obj)
    def clear(self):
        """ Clear the graph. """
        lib_py_gel.Graph_clear(self.obj)
    def cleanup(self):
        """ Cleanup reorders the graph nodes such that there is no
        gap in the index range. """
        lib_py_gel.Graph_cleanup(self.obj)
    def nodes(self) -> IntVector:
        """ Get all nodes as an iterable range """
        nodes = IntVector()
        lib_py_gel.Graph_nodes(self.obj, nodes.obj)
        return nodes
    def neighbors(self, n: int, mode: str = 'n') -> IntVector:
        """ Get the neighbors of node n. The final argument is either 'n' or 'e'. If it is 'n'
        the function returns all neighboring nodes, and if it is 'e' it returns incident edges."""
        nbors = IntVector()
        lib_py_gel.Graph_neighbors(self.obj, n, nbors.obj, ct.c_char(mode.encode('ascii')))
        return nbors
    def positions(self) -> ArrayLike:
        """ Get the vertex positions by reference. You can assign to the
        positions. """
        pos = ct.POINTER(ct.c_double)()
        n = lib_py_gel.Graph_positions(self.obj, ct.byref(pos))
        return np.ctypeslib.as_array(pos,(n,3))
    def average_edge_length(self) -> float:
        """ Returns the average edge length. """
        ael = lib_py_gel.Graph_average_edge_length(self.obj)
        return ael
    def add_node(self, p: ArrayLike) -> int:
        """ Adds node with position p to the graph and returns the
        index of the new node. """
        return lib_py_gel.Graph_add_node(self.obj, np.array(p))
    def remove_node(self, n: int):
        """ Removes the node n passed as argument. This does not change
        any indices of other nodes, but n is then invalid. """
        lib_py_gel.Graph_remove_node(self.obj, n)
    def node_in_use(self, n: int) -> bool:
        """ Checks if n is in_use. This function returns false both
        if n has been removed and if n is an index outside the range of
        indices that are used. """
        return lib_py_gel.Graph_node_in_use(self.obj, n)
    def connect_nodes(self, n0: int, n1: int) -> int:
        """ Creates a new edge connecting nodes n0 and n1. The index of
        the new edge is returned. """
        return lib_py_gel.Graph_connect_nodes(self.obj, n0, n1)
    def disconnect_nodes(self, n0: int, n1: int):
        """ Disconnect nodes n0 and n1"""
        lib_py_gel.Graph_disconnect_nodes(self.obj, n0, n1)
    def merge_nodes(self, n0: int, n1: int, avg_pos: bool):
        """ Merge nodes n0 and n1. avg_pos indicates if you want the position to be the average. """
        lib_py_gel.Graph_merge_nodes(self.obj, n0, n1, avg_pos)

clear 

clear()

Clear the graph.

Source code in pygel3d/graph.py 
28
29
30
def clear(self):
    """ Clear the graph. """
    lib_py_gel.Graph_clear(self.obj)

cleanup 

cleanup()

Cleanup reorders the graph nodes such that there is no gap in the index range.

Source code in pygel3d/graph.py 
31
32
33
34
def cleanup(self):
    """ Cleanup reorders the graph nodes such that there is no
    gap in the index range. """
    lib_py_gel.Graph_cleanup(self.obj)

nodes 

nodes() -> IntVector

Get all nodes as an iterable range

Source code in pygel3d/graph.py 
35
36
37
38
39
def nodes(self) -> IntVector:
    """ Get all nodes as an iterable range """
    nodes = IntVector()
    lib_py_gel.Graph_nodes(self.obj, nodes.obj)
    return nodes

neighbors 

neighbors(n: int, mode: str = 'n') -> IntVector

Get the neighbors of node n. The final argument is either 'n' or 'e'. If it is 'n' the function returns all neighboring nodes, and if it is 'e' it returns incident edges.

Source code in pygel3d/graph.py 
40
41
42
43
44
45
def neighbors(self, n: int, mode: str = 'n') -> IntVector:
    """ Get the neighbors of node n. The final argument is either 'n' or 'e'. If it is 'n'
    the function returns all neighboring nodes, and if it is 'e' it returns incident edges."""
    nbors = IntVector()
    lib_py_gel.Graph_neighbors(self.obj, n, nbors.obj, ct.c_char(mode.encode('ascii')))
    return nbors

positions 

positions() -> ArrayLike

Get the vertex positions by reference. You can assign to the positions.

Source code in pygel3d/graph.py 
46
47
48
49
50
51
def positions(self) -> ArrayLike:
    """ Get the vertex positions by reference. You can assign to the
    positions. """
    pos = ct.POINTER(ct.c_double)()
    n = lib_py_gel.Graph_positions(self.obj, ct.byref(pos))
    return np.ctypeslib.as_array(pos,(n,3))

average_edge_length 

average_edge_length() -> float

Returns the average edge length.

Source code in pygel3d/graph.py 
52
53
54
55
def average_edge_length(self) -> float:
    """ Returns the average edge length. """
    ael = lib_py_gel.Graph_average_edge_length(self.obj)
    return ael

add_node 

add_node(p: ArrayLike) -> int

Adds node with position p to the graph and returns the index of the new node.

Source code in pygel3d/graph.py 
56
57
58
59
def add_node(self, p: ArrayLike) -> int:
    """ Adds node with position p to the graph and returns the
    index of the new node. """
    return lib_py_gel.Graph_add_node(self.obj, np.array(p))

remove_node 

remove_node(n: int)

Removes the node n passed as argument. This does not change any indices of other nodes, but n is then invalid.

Source code in pygel3d/graph.py 
60
61
62
63
def remove_node(self, n: int):
    """ Removes the node n passed as argument. This does not change
    any indices of other nodes, but n is then invalid. """
    lib_py_gel.Graph_remove_node(self.obj, n)

node_in_use 

node_in_use(n: int) -> bool

Checks if n is in_use. This function returns false both if n has been removed and if n is an index outside the range of indices that are used.

Source code in pygel3d/graph.py 
64
65
66
67
68
def node_in_use(self, n: int) -> bool:
    """ Checks if n is in_use. This function returns false both
    if n has been removed and if n is an index outside the range of
    indices that are used. """
    return lib_py_gel.Graph_node_in_use(self.obj, n)

connect_nodes 

connect_nodes(n0: int, n1: int) -> int

Creates a new edge connecting nodes n0 and n1. The index of the new edge is returned.

Source code in pygel3d/graph.py 
69
70
71
72
def connect_nodes(self, n0: int, n1: int) -> int:
    """ Creates a new edge connecting nodes n0 and n1. The index of
    the new edge is returned. """
    return lib_py_gel.Graph_connect_nodes(self.obj, n0, n1)

disconnect_nodes 

disconnect_nodes(n0: int, n1: int)

Disconnect nodes n0 and n1

Source code in pygel3d/graph.py 
73
74
75
def disconnect_nodes(self, n0: int, n1: int):
    """ Disconnect nodes n0 and n1"""
    lib_py_gel.Graph_disconnect_nodes(self.obj, n0, n1)

merge_nodes 

merge_nodes(n0: int, n1: int, avg_pos: bool)

Merge nodes n0 and n1. avg_pos indicates if you want the position to be the average.

Source code in pygel3d/graph.py 
76
77
78
def merge_nodes(self, n0: int, n1: int, avg_pos: bool):
    """ Merge nodes n0 and n1. avg_pos indicates if you want the position to be the average. """
    lib_py_gel.Graph_merge_nodes(self.obj, n0, n1, avg_pos)

from_mesh 

from_mesh(m: Manifold) -> Graph

Creates a graph from a mesh. The argument, m, is the input mesh, and the function returns a graph with the same vertices and edges as m.

Source code in pygel3d/graph.py 
81
82
83
84
85
86
87
def from_mesh(m: Manifold) -> Graph:
    """ Creates a graph from a mesh. The argument, m, is the input mesh,
    and the function returns a graph with the same vertices and edges
    as m."""
    g = Graph()
    lib_py_gel.graph_from_mesh(m.obj, g.obj)
    return g

load 

load(fn: str) -> Graph | None

Load a graph from a file. The argument, fn, is the filename which is in a special format similar to Wavefront obj. The loaded graph is returned by the function - or None if loading failed.

Source code in pygel3d/graph.py 
89
90
91
92
93
94
95
96
97
def load(fn: str) -> Graph | None:
    """ Load a graph from a file. The argument, fn, is the filename which
    is in a special format similar to Wavefront obj. The loaded graph is
    returned by the function - or None if loading failed. """
    s = ct.c_char_p(fn.encode('utf-8'))
    g = Graph()
    if lib_py_gel.graph_load(g.obj, s):
        return g
    return None

save 

save(fn: str, g: Graph) -> bool

Save graph to a file. The first argument, fn, is the file name, and g is the graph. This function returns True if saving happened and False otherwise.

Source code in pygel3d/graph.py 
 99
100
101
102
103
104
def save(fn: str, g: Graph) -> bool:
    """ Save graph to a file. The first argument, fn, is the file name,
    and g is the graph. This function returns True if saving happened and
    False otherwise. """
    s = ct.c_char_p(fn.encode('utf-8'))
    return lib_py_gel.graph_save(g.obj, s)

to_mesh_cyl 

to_mesh_cyl(g: Graph, fudge: float = 0.0) -> Manifold

Convert a graph to a cylindrical mesh.

This is a compatibility wrapper. Prefer hmesh.graph_to_cylinders.

Source code in pygel3d/graph.py 
106
107
108
109
110
111
112
def to_mesh_cyl(g: Graph, fudge: float = 0.0) -> Manifold:
    """ Convert a graph to a cylindrical mesh.

    This is a compatibility wrapper. Prefer ``hmesh.graph_to_cylinders``.
    """
    from pygel3d.hmesh import graph_to_cylinders
    return graph_to_cylinders(g, fudge)

to_mesh_iso 

to_mesh_iso(g: Graph, fudge: float = 0.0, res: int = 256) -> Manifold

Convert a graph to an isosurface mesh.

This is a compatibility wrapper. Prefer hmesh.graph_to_isosurface.

Source code in pygel3d/graph.py 
114
115
116
117
118
119
120
def to_mesh_iso(g: Graph, fudge: float = 0.0, res: int = 256) -> Manifold:
    """ Convert a graph to an isosurface mesh.

    This is a compatibility wrapper. Prefer ``hmesh.graph_to_isosurface``.
    """
    from pygel3d.hmesh import graph_to_isosurface
    return graph_to_isosurface(g, fudge, res)

smooth 

smooth(g: Graph, num_iter: int = 1, alpha: float = 1.0)

Simple Laplacian smoothing of a graph. The first argument is the Graph, g, iter is the number of iterations, and alpha is the weight. If the weight is high, each iteration causes a lot of smoothing, and a high number of iterations ensures that the effect of smoothing diffuses throughout the graph, i.e. that the effect is more global than local.

Source code in pygel3d/graph.py 
123
124
125
126
127
128
129
def smooth(g: Graph, num_iter: int = 1, alpha: float = 1.0):
    """ Simple Laplacian smoothing of a graph. The first argument is the Graph, g, iter
    is the number of iterations, and alpha is the weight. If the weight is high,
    each iteration causes a lot of smoothing, and a high number of iterations
    ensures that the effect of smoothing diffuses throughout the graph, i.e. that the
    effect is more global than local. """
    lib_py_gel.graph_smooth(g.obj, num_iter, alpha)

edge_contract 

edge_contract(g: Graph, dist_thresh: float) -> int

Simplifies a graph by contracting edges. The first argument, g, is the graph, and only edges shorter than dist_thresh are contracted. When an edge is contracted the merged vertices are moved to the average of their former positions. Thus, the ordering in which contractions are carried out matters. Hence, edges are contracted in the order of increasing length and edges are only considered if neither end point is the result of a contraction, but the process is then repeated until no more contractions are possible. Returns total number of contractions.

Source code in pygel3d/graph.py 
131
132
133
134
135
136
137
138
139
def edge_contract(g: Graph, dist_thresh: float) -> int:
    """ Simplifies a graph by contracting edges. The first argument, g, is the graph,
    and only edges shorter than dist_thresh are contracted. When an edge is contracted
    the merged vertices are moved to the average of their former positions. Thus,
    the ordering in which contractions are carried out matters. Hence, edges are
    contracted in the order of increasing length and edges are only considered if
    neither end point is the result of a contraction, but the process is then repeated
    until no more contractions are possible. Returns total number of contractions. """
    return lib_py_gel.graph_edge_contract(g.obj, dist_thresh)

prune 

prune(g: Graph)

Prune leaves of a graph. The graph, g, is passed as the argument. This function removes leaf nodes (valency 1) whose only neighbour has valency > 2. In practice such isolated leaves are frequently spurious if the graph is a skeleton. Does not return a value.

Source code in pygel3d/graph.py 
141
142
143
144
145
146
def prune(g: Graph):
    """ Prune leaves of a graph. The graph, g, is passed as the argument. This function
        removes leaf nodes (valency 1) whose only neighbour has valency > 2. In practice
        such isolated leaves are frequently spurious if the graph is a skeleton. Does not
        return a value. """
    lib_py_gel.graph_prune(g.obj)

saturate 

saturate(g: Graph, hops: int = 2, dist_frac: float = 1.001, rad: float = 1e+300)

Saturate the graph with edges. This is not a complete saturation. Edges are introduced between a vertex and other vertices that are reachable in hops steps, i.e. hops-order neighbors. dist_frac and rad are parameters used to govern the precise behaviour. Two nodes are only connected if their distance is less than rad and if their distance is less than dist_frac times the length of the path along existing edges in the graph. If dist_frac is at approximately 1 and rad is enormous, these two parameters make no difference.

Source code in pygel3d/graph.py 
148
149
150
151
152
153
154
155
156
def saturate(g: Graph, hops: int = 2, dist_frac: float = 1.001, rad: float = 1e300):
    """ Saturate the graph with edges. This is not a complete saturation. Edges are
    introduced between a vertex and other vertices that are reachable in hops steps, i.e.
    hops-order neighbors. dist_frac and rad are parameters used to govern the precise
    behaviour. Two nodes are only connected if their distance is less than rad and if
    their distance is less than dist_frac times the length of the path along existing
    edges in the graph. If dist_frac is at approximately 1 and rad is enormous, these
    two parameters make no difference. """
    lib_py_gel.graph_saturate(g.obj, hops, dist_frac, rad)

LS_skeleton 

LS_skeleton(g: Graph, sampling: bool = True) -> Graph

Skeletonize a graph using the local separators approach. The first argument, g, is the graph, and, sampling indicates whether we try to use all vertices (False) as starting points for finding separators or just a sampling (True). The function returns a new graph which is the skeleton of the input graph.

Source code in pygel3d/graph.py 
158
159
160
161
162
163
164
165
166
def LS_skeleton(g: Graph, sampling: bool = True) -> Graph:
    """ Skeletonize a graph using the local separators approach. The first argument,
        g, is the graph, and, sampling indicates whether we try to use all vertices
        (False) as starting points for finding separators or just a sampling (True).
        The function returns a new graph which is the skeleton of the input graph. """
    skel = Graph()
    mapping = IntVector()
    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
    return skel

LS_skeleton_and_map 

LS_skeleton_and_map(g: Graph, sampling: bool = True) -> tuple[Graph, IntVector]

Skeletonize a graph using the local separators approach. The first argument, g, is the graph, and, sampling indicates whether we try to use all vertices (False) as starting points for finding separators or just a sampling (True). The function returns a tuple containing a new graph which is the skeleton of the input graph and a map from the graph nodes to the skeletal nodes.

Source code in pygel3d/graph.py 
168
169
170
171
172
173
174
175
176
177
def LS_skeleton_and_map(g: Graph, sampling: bool = True) -> tuple[Graph, IntVector]:
    """ Skeletonize a graph using the local separators approach. The first argument,
        g, is the graph, and, sampling indicates whether we try to use all vertices
        (False) as starting points for finding separators or just a sampling (True).
        The function returns a tuple containing a new graph which is the skeleton of
        the input graph and a map from the graph nodes to the skeletal nodes. """
    skel = Graph()
    mapping = IntVector()
    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
    return skel, mapping

MSLS_skeleton 

MSLS_skeleton(g: Graph, grow_thresh: int = 64) -> Graph

Skeletonize a graph using the multi-scale local separators approach. The first argument, g, is the graph. grow_thresh controls how far a separator is allowed to grow (larger is coarser and faster). The function returns a new graph which is the skeleton of the input graph.

Source code in pygel3d/graph.py 
179
180
181
182
183
184
185
186
187
def MSLS_skeleton(g: Graph, grow_thresh: int = 64) -> Graph:
    """ Skeletonize a graph using the multi-scale local separators approach. The first
        argument, g, is the graph. grow_thresh controls how far a separator is allowed
        to grow (larger is coarser and faster). The function returns a new graph which
        is the skeleton of the input graph. """
    skel = Graph()
    mapping = IntVector()
    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
    return skel

MSLS_skeleton_and_map 

MSLS_skeleton_and_map(g: Graph, grow_thresh: int = 64) -> tuple[Graph, IntVector]

Skeletonize a graph using the multi-scale local separators approach. The first argument, g, is the graph. grow_thresh controls how far a separator is allowed to grow (larger is coarser and faster). The function returns a tuple containing a new graph which is the skeleton of the input graph and a map from the graph nodes to the skeletal nodes.

Source code in pygel3d/graph.py 
189
190
191
192
193
194
195
196
197
198
def MSLS_skeleton_and_map(g: Graph, grow_thresh: int = 64) -> tuple[Graph, IntVector]:
    """ Skeletonize a graph using the multi-scale local separators approach. The first
        argument, g, is the graph. grow_thresh controls how far a separator is allowed
        to grow (larger is coarser and faster). The function returns a tuple containing
        a new graph which is the skeleton of the input graph and a map from the graph
        nodes to the skeletal nodes. """
    skel = Graph()
    mapping = IntVector()
    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
    return skel, mapping

front_skeleton_and_map 

front_skeleton_and_map(g: Graph, colors: ArrayLike, intervals: int = 100) -> tuple[Graph, IntVector]

Skeletonize a graph using the front separators approach. The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence of floating point values - one for each node. We can have as many columns as needed for the front separator computation. We can think of this as a coloring of the nodes, hence the name. In practice, a coloring might just be the x-coordinate of the nodes or some other function that indicates something about the structure of the graph. The function returns a tuple containing a new graph which is the skeleton of the input graph and a map from the graph nodes to the skeletal nodes.

Source code in pygel3d/graph.py 
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
def front_skeleton_and_map(g: Graph, colors: ArrayLike, intervals: int = 100) -> tuple[Graph, IntVector]:
    """ Skeletonize a graph using the front separators approach. The first argument,
        g, is the graph, and, colors is an nD array where each column contains a sequence
        of floating point values - one for each node. We can have as many columns as needed
        for the front separator computation. We can think of this as a coloring
        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
        of the nodes or some other function that indicates something about the structure of the
        graph. The function returns a tuple containing a new graph which is the
        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
    skel = Graph()
    mapping = IntVector()
    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
    lib_py_gel.graph_front_skeleton(g.obj, skel.obj, mapping.obj, N_col, colors_flat.ctypes.data_as(ct.POINTER(ct.c_double)), intervals)
    return skel, mapping

front_skeleton 

front_skeleton(g: Graph, colors: ArrayLike, intervals: int = 100) -> Graph

Skeletonize a graph using the front separators approach. The first argument, g, is the graph, and, colors is a nD array where each column contains a sequence of floating point values - one for each node. We can have as many columns as needed for the front separator computation. We can think of this as a coloring of the nodes, hence the name. In practice, a coloring might just be the x-coordinate of the nodes or some other function that indicates something about the structure of the graph. The function returns a new graph which is the skeleton of the input graph.

Source code in pygel3d/graph.py 
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
def front_skeleton(g: Graph, colors: ArrayLike, intervals: int = 100) -> Graph:
    """ Skeletonize a graph using the front separators approach. The first argument,
        g, is the graph, and, colors is a nD array where each column contains a sequence
        of floating point values - one for each node. We can have as many columns as needed
        for the front separator computation. We can think of this as a coloring
        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
        of the nodes or some other function that indicates something about the structure of the
        graph. The function returns a new graph which is the skeleton of the input
        graph. """
    skel = Graph()
    mapping = IntVector()
    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
    lib_py_gel.graph_front_skeleton(g.obj, skel.obj, mapping.obj, N_col, colors_flat.ctypes.data_as(ct.POINTER(ct.c_double)), intervals)
    return skel

combined_skeleton_and_map 

combined_skeleton_and_map(g: Graph, colors: ArrayLike, intervals: int = 100) -> tuple[Graph, IntVector]

Skeletonize a graph using both the front separators approach and the multi scale local separators. The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence of floating point values - one for each node. We can have as many columns as needed for the front separator computation. We can think of this as a coloring of the nodes, hence the name. In practice, a coloring might just be the x-coordinate of the nodes or some other function that indicates something about the structure of the graph. The function returns a tuple containing a new graph which is the skeleton of the input graph and a map from the graph nodes to the skeletal nodes.

Source code in pygel3d/graph.py 
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
def combined_skeleton_and_map(g: Graph, colors: ArrayLike, intervals: int = 100) -> tuple[Graph, IntVector]:
    """ Skeletonize a graph using both the front separators approach and the multi scale local separators.
        The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence
        of floating point values - one for each node. We can have as many columns as needed
        for the front separator computation. We can think of this as a coloring
        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
        of the nodes or some other function that indicates something about the structure of the
        graph. The function returns a tuple containing a new graph which is the
        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
    skel = Graph()
    mapping = IntVector()
    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
    lib_py_gel.graph_combined_skeleton(g.obj, skel.obj, mapping.obj, N_col, colors_flat.ctypes.data_as(ct.POINTER(ct.c_double)), intervals)
    return skel, mapping

combined_skeleton 

combined_skeleton(g: Graph, colors: ArrayLike, intervals: int = 100) -> Graph

Skeletonize a graph using both the front separators approach and the multi scale local separators. The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence of floating point values - one for each node. We can have as many columns as needed for the front separator computation. We can think of this as a coloring of the nodes, hence the name. In practice, a coloring might just be the x-coordinate of the nodes or some other function that indicates something about the structure of the graph. The function returns a new graph which is the skeleton of the input graph.

Source code in pygel3d/graph.py 
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
def combined_skeleton(g: Graph, colors: ArrayLike, intervals: int = 100) -> Graph:
    """ Skeletonize a graph using both the front separators approach and the multi scale local separators.
        The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence
        of floating point values - one for each node. We can have as many columns as needed
        for the front separator computation. We can think of this as a coloring
        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
        of the nodes or some other function that indicates something about the structure of the
        graph. The function returns a new graph which is the skeleton of the input
        graph. """
    skel = Graph()
    mapping = IntVector()
    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
    lib_py_gel.graph_combined_skeleton(g.obj, skel.obj, mapping.obj, N_col, colors_flat.ctypes.data_as(ct.POINTER(ct.c_double)), intervals)
    return skel

minimum_spanning_tree 

minimum_spanning_tree(g: Graph, root_node: int = 0) -> Graph

Compute the minimum spanning tree of g using Prim's algorithm. The second argument is the root node to start from. The spanning tree of the connected component containing the root node is returned.

Source code in pygel3d/graph.py 
265
266
267
268
269
270
271
def minimum_spanning_tree(g: Graph, root_node: int = 0) -> Graph:
    """ Compute the minimum spanning tree of g using Prim's algorithm.
    The second argument is the root node to start from. The spanning tree
    of the connected component containing the root node is returned. """
    mst = Graph()
    lib_py_gel.graph_minimum_spanning_tree(g.obj, mst.obj, root_node)
    return mst

close_chordless_cycles 

close_chordless_cycles(g: Graph, node: int = None, hops: int = 5, rad: float = None)

This function closes chordless cycles. A chordless cycle is a cycle in a graph such that two nodes that belong to the cycle are not connected unless they are adjacent in the cycle. The first argument is the graph, g, the second argument is the starting node. If none is provided, the procedure is executed for all nodes. hops indicates how far from the starting node we venture in the search for cycles. Finally, rad (if provided) indicates how far away the farthest node in the cycle is allowed to be.

Source code in pygel3d/graph.py 
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
def close_chordless_cycles(g: Graph, node: int = None, hops: int = 5, rad: float = None):
    """ This function closes chordless cycles. A chordless cycle is a 
    cycle in a graph such that two nodes that belong to the cycle are 
    not connected unless they are adjacent in the cycle. The first 
    argument is the graph, g, the second argument is the starting node. 
    If none is provided, the procedure is executed for all nodes. hops 
    indicates how far from the starting node we venture in the search 
    for cycles. Finally, rad (if provided) indicates how far away the 
    farthest node in the cycle is allowed to be."""
    if rad is None:
        rad = g.average_edge_length()
    if node is None:
        l = list(g.nodes())
        shuffle(l)
        for n in l:
            lib_py_gel.graph_close_chordless_cycles(g.obj, n, hops, rad)
    else:
        lib_py_gel.graph_close_chordless_cycles(g.obj, node, hops, rad)

The graph module provides a 3D spatial graph data structure for representing curve skeletons and other graph-based geometric structures.

Graph Class

The Graph class represents a spatial graph with 3D vertices connected by edges.

Creating Graphs

import pygel3d.graph as graph
import pygel3d.hmesh as hmesh

# Create empty graph
g = graph.Graph()

# Load from file
g = graph.load("skeleton.graph")

# Create from mesh
m = hmesh.load("model.obj")
g = graph.from_mesh(m)

Graph I/O

Loading and Saving

  • load(filename) - Load graph from file
  • save(filename, graph) - Save graph to file

Graph Information

Basic Queries

  • g.nodes() - Get all node IDs
  • len(g.nodes()) - Number of nodes
  • g.neighbors(node_id, mode) - Get neighbors of a node

Geometry

  • g.positions() - Get all node positions as flat array
  • average_edge_length(g) - Average edge length

Graph Construction

Adding Elements

  • g.add_node(position) - Add a node at position [x, y, z]
  • g.connect_nodes(n0, n1) - Connect two nodes with an edge

Removing Elements

  • g.remove_node(node_id) - Remove a node
  • g.disconnect_nodes(n0, n1) - Remove edge between nodes

Status

  • g.node_in_use(node_id) - Check if node exists

Graph Processing

Cleaning

  • g.cleanup() - Remove unused nodes
  • prune(g) - Remove degree-1 nodes

Smoothing

  • smooth(g, iterations, alpha) - Smooth node positions

Optimization

  • edge_contract(g, threshold) - Contract short edges
  • saturate(g, hops, dist_fraction, radius) - Add edges for connectivity

Mesh Conversion

  • from_mesh(mesh) - Extract graph from mesh
  • hmesh.graph_to_cylinders(g, fudge) - Convert graph to cylindrical mesh
  • hmesh.graph_to_isosurface(g, fudge) - Convert graph to an isosurface mesh

Example Usage

Graph Processing Pipeline

import pygel3d.graph as graph
import pygel3d.hmesh as hmesh

# Load mesh
m = hmesh.load("model.obj")

# Extract skeleton graph
g = graph.from_mesh(m)

# Process graph
graph.smooth(g, num_iter=10, alpha=0.5)
graph.prune(g)
graph.edge_contract(g, dist_thresh=0.1)

# Save graph
graph.save("skeleton.graph", g)

# Convert to mesh for visualization
result = hmesh.graph_to_cylinders(g, fudge=0.5)
hmesh.save("skeleton_mesh.obj", result)

Building a Custom Graph

import pygel3d.graph as graph

# Create graph
g = graph.Graph()

# Add nodes
n0 = g.add_node([0, 0, 0])
n1 = g.add_node([1, 0, 0])
n2 = g.add_node([0.5, 1, 0])
n3 = g.add_node([0.5, 0.5, 1])

# Connect nodes
g.connect_nodes(n0, n1)
g.connect_nodes(n1, n2)
g.connect_nodes(n2, n3)
g.connect_nodes(n3, n0)

# Query
print(f"Nodes: {len(g.nodes())}")
print(f"Neighbors of node 0: {list(g.neighbors(n0))}")