pygel3d.graph

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

View Source

  1""" This module provides a Graph class and functionality for skeletonization using graphs. """
  2from __future__ import annotations
  3from typing import TYPE_CHECKING
  4
  5import ctypes as ct
  6import numpy as np
  7from random import shuffle
  8from pygel3d import lib_py_gel, IntVector
  9
 10class Graph:
 11    """ This class is for representing graphs embedded in 3D. The class does not in
 12    itself come with many features: it contains methods for creating, accessing, and
 13    housekeeping. When vertices are used as parameters in the functions below, we usually
 14    use the parameter name n (for node). n is simply an index (i.e. an integer) that
 15    refers to a node (aka vertex)."""
 16    def __init__(self,orig=None):
 17        if orig == None:
 18            self.obj = lib_py_gel.Graph_new()
 19        else:
 20            self.obj = lib_py_gel.Graph_copy(orig.obj)
 21    def __del__(self):
 22        lib_py_gel.Graph_delete(self.obj)
 23    def clear(self):
 24        """ Clear the graph. """
 25        lib_py_gel.Graph_clear(self.obj)
 26    def cleanup(self):
 27        """ Cleanup reorders the graph nodes such that there is no
 28        gap in the index range. """
 29        lib_py_gel.Graph_cleanup(self.obj)
 30    def nodes(self):
 31        """ Get all nodes as an iterable range """
 32        nodes = IntVector()
 33        lib_py_gel.Graph_nodes(self.obj, nodes.obj)
 34        return nodes
 35    def neighbors(self, n, mode='n'):
 36        """ Get the neighbors of node n. The final argument is either 'n' or 'e'. If it is 'n'
 37        the function returns all neighboring nodes, and if it is 'e' it returns incident edges."""
 38        nbors = IntVector()
 39        lib_py_gel.Graph_neighbors(self.obj, n, nbors.obj, ct.c_char(mode.encode('ascii')))
 40        return nbors
 41    def positions(self):
 42        """ Get the vertex positions by reference. You can assign to the
 43        positions. """
 44        pos = ct.POINTER(ct.c_double)()
 45        n = lib_py_gel.Graph_positions(self.obj, ct.byref(pos))
 46        return np.ctypeslib.as_array(pos,(n,3))
 47    def average_edge_length(self):
 48        """ Returns the average edge length. """
 49        ael = lib_py_gel.Graph_average_edge_length(self.obj)
 50        return ael
 51    def add_node(self, p):
 52        """ Adds node with position p to the graph and returns the
 53        index of the new node. """
 54        return lib_py_gel.Graph_add_node(self.obj, np.array(p))
 55    def remove_node(self, n):
 56        """ Removes the node n passed as argument. This does not change
 57        any indices of other nodes, but n is then invalid. """
 58        lib_py_gel.Graph_remove_node(self.obj, n)
 59    def node_in_use(self, n):
 60        """ Checks if n is in_use. This function returns false both
 61        if n has been removed and if n is an index outside the range of
 62        indices that are used. """
 63        return lib_py_gel.Graph_node_in_use(self.obj, n)
 64    def connect_nodes(self, n0, n1):
 65        """ Creates a new edge connecting nodes n0 and n1. The index of
 66        the new edge is returned. """
 67        return lib_py_gel.Graph_connect_nodes(self.obj, n0, n1)
 68    def disconnect_nodes(self, n0, n1):
 69        """ Disconect nodes n0 and n1"""
 70        lib_py_gel.Graph_disconnect_nodes(self.obj, n0, n1)
 71    def merge_nodes(self, n0, n1, avg_pos):
 72        """ Merge nodes n0 and n1. avg_pos indicates if you want the position to be the average. """
 73        lib_py_gel.Graph_merge_nodes(self.obj, n0, n1, avg_pos)
 74
 75
 76def from_mesh(m: Manifold):
 77    """ Creates a graph from a mesh. The argument, m, is the input mesh,
 78    and the function returns a graph with the same vertices and edges
 79    as m."""
 80    g = Graph()
 81    lib_py_gel.graph_from_mesh(m.obj, g.obj)
 82    return g
 83
 84def load(fn):
 85    """ Load a graph from a file. The argument, fn, is the filename which
 86    is in a special format similar to Wavefront obj. The loaded graph is
 87    returned by the function - or None if loading failed. """
 88    s = ct.c_char_p(fn.encode('utf-8'))
 89    g = Graph()
 90    if lib_py_gel.graph_load(g.obj, s):
 91        return g
 92    return None
 93
 94def save(fn, g: Graph):
 95    """ Save graph to a file. The first argument, fn, is the file name,
 96    and g is the graph. This function returns True if saving happened and
 97    False otherwise. """
 98    s = ct.c_char_p(fn.encode('utf-8'))
 99    return lib_py_gel.graph_save(g.obj, s)
100
101def to_mesh_cyl(g: Graph, fudge=0.0):
102    """ Creates a Manifold mesh from the graph. The first argument, g, is the
103    graph we want converted, and fudge is a constant that is used to increase the radius
104    of every node. This is useful if the radii are 0. """
105    m = Manifold()
106    lib_py_gel.graph_to_mesh_cyl(g.obj, m.obj, fudge)
107    return m
108
109def to_mesh_iso(g: Graph, fudge=0.0, res=256):
110    """ Creates a Manifold mesh from the graph. The first argument, g, is the
111    graph we want converted, and fudge is a constant that is used to increase the radius
112    of every node. This is useful if the radii are 0. """
113    m = Manifold()
114    lib_py_gel.graph_to_mesh_iso(g.obj, m.obj, fudge, res)
115    return m
116
117
118def smooth(g: Graph, iter=1, alpha=1.0):
119    """ Simple Laplacian smoothing of a graph. The first argument is the Graph, g, iter
120    is the number of iterations, and alpha is the weight. If the weight is high,
121    each iteration causes a lot of smoothing, and a high number of iterations
122    ensures that the effect of smoothing diffuses throughout the graph, i.e. that the
123    effect is more global than local. """
124    lib_py_gel.graph_smooth(g.obj, iter, alpha)
125
126def edge_contract(g: Graph, dist_thresh):
127    """ Simplifies a graph by contracting edges. The first argument, g, is the graph,
128    and only edges shorter than dist_thresh are contracted. When an edge is contracted
129    the merged vertices are moved to the average of their former positions. Thus,
130    the ordering in which contractions are carried out matters. Hence, edges are
131    contracted in the order of increasing length and edges are only considered if
132    neither end point is the result of a contraction, but the process is then repeated
133    until no more contractions are possible. Returns total number of contractions. """
134    return lib_py_gel.graph_edge_contract(g.obj, dist_thresh)
135
136def prune(g: Graph):
137    """ Prune leaves of a graph. The graph, g, is passed as the argument. This function
138        removes leaf nodes (valency 1) whose only neighbour has valency > 2. In practice
139        such isolated leaves are frequently spurious if the graph is a skeleton. Does not
140        return a value. """
141    lib_py_gel.graph_prune(g.obj)
142    
143def saturate(g: Graph, hops=2, dist_frac=1.001, rad=1e300):
144    """ Saturate the graph with edges. This is not a complete saturation. Edges are
145    introduced between a vertex and other vertices that are reachable in hops steps, i.e.
146    hops-order neighbors. dist_frac and rad are parameters used to govern the precise
147    behaviour. Two nodes are only connected if their distance is less than rad and if
148    their distance is less than dist_frac times the length of the path along existing
149    edges in the graph. If dist_frac is at approximately 1 and rad is enormous, these
150    two parameters make no difference. """
151    lib_py_gel.graph_saturate(g.obj, hops, dist_frac, rad)
152    
153def LS_skeleton(g: Graph, sampling=True):
154    """ Skeletonize a graph using the local separators approach. The first argument,
155        g, is the graph, and, sampling indicates whether we try to use all vertices
156        (False) as starting points for finding separators or just a sampling (True).
157        The function returns a new graph which is the skeleton of the input graph. """
158    skel = Graph()
159    mapping = IntVector()
160    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
161    return skel
162    
163def LS_skeleton_and_map(g: Graph, sampling=True):
164    """ Skeletonize a graph using the local separators approach. The first argument,
165        g, is the graph, and, sampling indicates whether we try to use all vertices
166        (False) as starting points for finding separators or just a sampling (True).
167        The function returns a tuple containing a new graph which is the skeleton of
168        the input graph and a map from the graph nodes to the skeletal nodes. """
169    skel = Graph()
170    mapping = IntVector()
171    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
172    return skel, mapping
173
174def MSLS_skeleton(g: Graph, grow_thresh=64):
175    """ Skeletonize a graph using the multi-scale local separators approach. The first argument,
176        g, is the graph, and, sampling indicates whether we try to use all vertices
177        (False) as starting points for finding separators or just a sampling (True).
178        The function returns a new graph which is the skeleton of the input graph. """
179    skel = Graph()
180    mapping = IntVector()
181    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
182    return skel
183    
184def MSLS_skeleton_and_map(g: Graph, grow_thresh=64):
185    """ Skeletonize a graph using the multi-scale local separators approach. The first argument,
186        g, is the graph, and, sampling indicates whether we try to use all vertices
187        (False) as starting points for finding separators or just a sampling (True).
188        The function returns a tuple containing a new graph which is the skeleton of
189        the input graph and a map from the graph nodes to the skeletal nodes. """
190    skel = Graph()
191    mapping = IntVector()
192    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
193    return skel, mapping
194
195
196def front_skeleton_and_map(g: Graph, colors, intervals=100):
197    """ Skeletonize a graph using the front separators approach. The first argument,
198        g, is the graph, and, colors is an nD array where each column contains a sequence
199        of floating point values - one for each node. We can have as many columns as needed
200        for the front separator computation. We can think of this as a coloring
201        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
202        of the nodes or some other function that indicates something about the structure of the
203        graph. The function returns a tuple containing a new graph which is the
204        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
205    skel = Graph()
206    mapping = IntVector()
207    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
208    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
209    print("N_col:", N_col)
210    pos = g.positions()
211    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)
212    return skel, mapping
213
214def front_skeleton(g: Graph, colors, intervals=100):
215    """ Skeletonize a graph using the front separators approach. The first argument,
216        g, is the graph, and, colors is a nD array where each column contains a sequence
217        of floating point values - one for each node. We can have as many columns as needed
218        for the front separator computation. We can think of this as a coloring
219        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
220        of the nodes or some other function that indicates something about the structure of the
221        graph. The function returns a tuple containing a new graph which is the
222        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
223    skel = Graph()
224    mapping = IntVector()
225    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
226    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
227    print("N_col:", N_col)
228    pos = g.positions()
229    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)
230    return skel
231
232def combined_skeleton_and_map(g: Graph, colors, intervals=100):
233    """ Skeletonize a graph using both the front separators approach and the multi scale local separators.
234        The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence
235        of floating point values - one for each node. We can have as many columns as needed
236        for the front separator computation. We can think of this as a coloring
237        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
238        of the nodes or some other function that indicates something about the structure of the
239        graph. The function returns a tuple containing a new graph which is the
240        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
241    skel = Graph()
242    mapping = IntVector()
243    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
244    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
245    print("N_col:", N_col)
246    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)
247    return skel, mapping
248
249def combined_skeleton(g: Graph, colors, intervals=100):
250    """ Skeletonize a graph using both the front separators approach and the multi scale local separators.
251        The first argument, g, is the graph, and, colors is an nD array where each column contains a sequence
252        of floating point values - one for each node. We can have as many columns as needed
253        for the front separator computation. We can think of this as a coloring
254        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
255        of the nodes or some other function that indicates something about the structure of the
256        graph. The function returns a new graph which is the
257        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
258    skel = Graph()
259    mapping = IntVector()
260    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
261    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
262    print("N_col:", N_col)
263    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)
264    return skel
265
266def minimum_spanning_tree(g: Graph, root_node=0):
267    """ Compute the minimum spanning tree of g using Prim's algorithm.
268    The second argument is the root node to start from. The spanning tree
269    of the connected component containing the root node is returned. """
270    mst = Graph()
271    lib_py_gel.graph_minimum_spanning_tree(g.obj, mst.obj, root_node)
272    return mst
273
274def close_chordless_cycles(g: Graph, node=None, hops=5, rad=None):
275    """ This function closes chordless cycles. A chordless cycle is a 
276    cycle in a graph such that two nodes that belong to the cycle are 
277    not connected unless they are adjacent in the cycle. The first 
278    argument is the graph, g, the second argument is the starting node. 
279    If none is provided, the procedure is executed for all nodes. hops 
280    indicates how far from the starting node we venture in the search 
281    for cycles. Finally, rad (if provided) indicates how far away the 
282    farthest node in the cycle is allowed to be."""
283    if rad is None:
284        rad = g.average_edge_length()
285    if node is None:
286        l = list(g.nodes())
287        shuffle(l)
288        for n in l:
289            lib_py_gel.graph_close_chordless_cycles(g.obj, n, hops, rad)
290    else:
291        lib_py_gel.graph_close_chordless_cycles(g.obj, node, hops, rad)

def from_mesh(m: 'Manifold'): View Source

77def from_mesh(m: Manifold):
78    """ Creates a graph from a mesh. The argument, m, is the input mesh,
79    and the function returns a graph with the same vertices and edges
80    as m."""
81    g = Graph()
82    lib_py_gel.graph_from_mesh(m.obj, g.obj)
83    return g

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.

def load(fn): View Source

85def load(fn):
86    """ Load a graph from a file. The argument, fn, is the filename which
87    is in a special format similar to Wavefront obj. The loaded graph is
88    returned by the function - or None if loading failed. """
89    s = ct.c_char_p(fn.encode('utf-8'))
90    g = Graph()
91    if lib_py_gel.graph_load(g.obj, s):
92        return g
93    return 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.

def save(fn, g: Graph): View Source

 95def save(fn, g: Graph):
 96    """ Save graph to a file. The first argument, fn, is the file name,
 97    and g is the graph. This function returns True if saving happened and
 98    False otherwise. """
 99    s = ct.c_char_p(fn.encode('utf-8'))
100    return lib_py_gel.graph_save(g.obj, s)

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.

def to_mesh_cyl(g: Graph, fudge=0.0): View Source

102def to_mesh_cyl(g: Graph, fudge=0.0):
103    """ Creates a Manifold mesh from the graph. The first argument, g, is the
104    graph we want converted, and fudge is a constant that is used to increase the radius
105    of every node. This is useful if the radii are 0. """
106    m = Manifold()
107    lib_py_gel.graph_to_mesh_cyl(g.obj, m.obj, fudge)
108    return m

Creates a Manifold mesh from the graph. The first argument, g, is the graph we want converted, and fudge is a constant that is used to increase the radius of every node. This is useful if the radii are 0.

def to_mesh_iso(g: Graph, fudge=0.0, res=256): View Source

110def to_mesh_iso(g: Graph, fudge=0.0, res=256):
111    """ Creates a Manifold mesh from the graph. The first argument, g, is the
112    graph we want converted, and fudge is a constant that is used to increase the radius
113    of every node. This is useful if the radii are 0. """
114    m = Manifold()
115    lib_py_gel.graph_to_mesh_iso(g.obj, m.obj, fudge, res)
116    return m

def smooth(g: Graph, iter=1, alpha=1.0): View Source

119def smooth(g: Graph, iter=1, alpha=1.0):
120    """ Simple Laplacian smoothing of a graph. The first argument is the Graph, g, iter
121    is the number of iterations, and alpha is the weight. If the weight is high,
122    each iteration causes a lot of smoothing, and a high number of iterations
123    ensures that the effect of smoothing diffuses throughout the graph, i.e. that the
124    effect is more global than local. """
125    lib_py_gel.graph_smooth(g.obj, iter, alpha)

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.

def edge_contract(g: Graph, dist_thresh): View Source

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

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.

def prune(g: Graph): View Source

137def prune(g: Graph):
138    """ Prune leaves of a graph. The graph, g, is passed as the argument. This function
139        removes leaf nodes (valency 1) whose only neighbour has valency > 2. In practice
140        such isolated leaves are frequently spurious if the graph is a skeleton. Does not
141        return a value. """
142    lib_py_gel.graph_prune(g.obj)

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.

def saturate(g: Graph, hops=2, dist_frac=1.001, rad=1e+300): View Source

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

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.

def LS_skeleton(g: Graph, sampling=True): View Source

154def LS_skeleton(g: Graph, sampling=True):
155    """ Skeletonize a graph using the local separators approach. The first argument,
156        g, is the graph, and, sampling indicates whether we try to use all vertices
157        (False) as starting points for finding separators or just a sampling (True).
158        The function returns a new graph which is the skeleton of the input graph. """
159    skel = Graph()
160    mapping = IntVector()
161    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
162    return skel

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.

def LS_skeleton_and_map(g: Graph, sampling=True): View Source

164def LS_skeleton_and_map(g: Graph, sampling=True):
165    """ Skeletonize a graph using the local separators approach. The first argument,
166        g, is the graph, and, sampling indicates whether we try to use all vertices
167        (False) as starting points for finding separators or just a sampling (True).
168        The function returns a tuple containing a new graph which is the skeleton of
169        the input graph and a map from the graph nodes to the skeletal nodes. """
170    skel = Graph()
171    mapping = IntVector()
172    lib_py_gel.graph_LS_skeleton(g.obj, skel.obj, mapping.obj, sampling)
173    return skel, mapping

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.

def MSLS_skeleton(g: Graph, grow_thresh=64): View Source

175def MSLS_skeleton(g: Graph, grow_thresh=64):
176    """ Skeletonize a graph using the multi-scale local separators approach. The first argument,
177        g, is the graph, and, sampling indicates whether we try to use all vertices
178        (False) as starting points for finding separators or just a sampling (True).
179        The function returns a new graph which is the skeleton of the input graph. """
180    skel = Graph()
181    mapping = IntVector()
182    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
183    return skel

Skeletonize a graph using the multi-scale 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.

def MSLS_skeleton_and_map(g: Graph, grow_thresh=64): View Source

185def MSLS_skeleton_and_map(g: Graph, grow_thresh=64):
186    """ Skeletonize a graph using the multi-scale local separators approach. The first argument,
187        g, is the graph, and, sampling indicates whether we try to use all vertices
188        (False) as starting points for finding separators or just a sampling (True).
189        The function returns a tuple containing a new graph which is the skeleton of
190        the input graph and a map from the graph nodes to the skeletal nodes. """
191    skel = Graph()
192    mapping = IntVector()
193    lib_py_gel.graph_MSLS_skeleton(g.obj, skel.obj, mapping.obj, grow_thresh)
194    return skel, mapping

Skeletonize a graph using the multi-scale 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.

def front_skeleton_and_map(g: Graph, colors, intervals=100): View Source

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

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.

def front_skeleton(g: Graph, colors, intervals=100): View Source

215def front_skeleton(g: Graph, colors, intervals=100):
216    """ Skeletonize a graph using the front separators approach. The first argument,
217        g, is the graph, and, colors is a nD array where each column contains a sequence
218        of floating point values - one for each node. We can have as many columns as needed
219        for the front separator computation. We can think of this as a coloring
220        of the nodes, hence the name. In practice, a coloring might just be the x-coordinate
221        of the nodes or some other function that indicates something about the structure of the
222        graph. The function returns a tuple containing a new graph which is the
223        skeleton of the input graph and a map from the graph nodes to the skeletal nodes. """
224    skel = Graph()
225    mapping = IntVector()
226    colors_flat = np.asarray(colors, dtype=ct.c_double, order='C')
227    N_col = 1 if len(colors_flat.shape)==1 else colors_flat.shape[1]
228    print("N_col:", N_col)
229    pos = g.positions()
230    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)
231    return skel

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 tuple containing a new graph which is the skeleton of the input graph and a map from the graph nodes to the skeletal nodes.

def combined_skeleton_and_map(g: Graph, colors, intervals=100): View Source

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

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.

def combined_skeleton(g: Graph, colors, intervals=100): View Source

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

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 and a map from the graph nodes to the skeletal nodes.

def minimum_spanning_tree(g: Graph, root_node=0): View Source

267def minimum_spanning_tree(g: Graph, root_node=0):
268    """ Compute the minimum spanning tree of g using Prim's algorithm.
269    The second argument is the root node to start from. The spanning tree
270    of the connected component containing the root node is returned. """
271    mst = Graph()
272    lib_py_gel.graph_minimum_spanning_tree(g.obj, mst.obj, root_node)
273    return mst

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.

def close_chordless_cycles(g: Graph, node=None, hops=5, rad=None): View Source

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

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.