trimesh's usage of NetworkX: API usage and slowdowns

[nv-rliu]

Hi. I would like to understand what parts of trimesh depend on algorithms from Networkx. What nx API calls it uses the most, for what purposes, and if you've ever experienced any slowdowns when scaling up graph sizes?

I did a quick search for previous issues related to NetworkX Usage, but I was wondering if you had any more insight into this topic. Thank you

[mikedh]

Hey, actually connected components are used a lot for some reason, and the existing implementation supports and benchmarks multiple graph backends (networkx and scipy.sparse.csgraph):

trimesh/trimesh/graph.py

Lines 376 to 476 in 2fcb2b2

	def connected_components(edges, min_len=1, nodes=None, engine=None):
	"""
	Find groups of connected nodes from an edge list.
	Parameters
	-----------
	edges : (n, 2) int
	Edges between nodes
	nodes : (m, ) int or None
	List of nodes that exist
	min_len : int
	Minimum length of a component group to return
	engine : str or None
	Which graph engine to use (None for automatic):
	(None, 'networkx', 'scipy')
	Returns
	-----------
	components : (n,) sequence of (*,) int
	Nodes which are connected
	"""
	def components_networkx():
	"""
	Find connected components using networkx
	"""
	graph = nx.from_edgelist(edges)
	# make sure every face has a node, so single triangles
	# aren't discarded (as they aren't adjacent to anything)
	if min_len <= 1:
	graph.add_nodes_from(nodes)
	return [list(i) for i in nx.connected_components(graph)]
	def components_csgraph():
	"""
	Find connected components using scipy.sparse.csgraph
	"""
	# label each node
	labels = connected_component_labels(edges, node_count=node_count)
	# we have to remove results that contain nodes outside
	# of the specified node set and reindex
	contained = np.zeros(node_count, dtype=bool)
	contained[nodes] = True
	index = np.arange(node_count, dtype=np.int64)[contained]
	components = grouping.group(labels[contained], min_len=min_len)
	return [index[c] for c in components]
	return components
	# check input edges
	edges = np.asanyarray(edges, dtype=np.int64)
	# if no nodes were specified just use unique
	if nodes is None:
	nodes = np.unique(edges)
	# exit early if we have no nodes
	if len(nodes) == 0:
	return []
	elif len(edges) == 0:
	if min_len <= 1:
	return np.reshape(nodes, (-1, 1)).tolist()
	else:
	return []
	if not util.is_shape(edges, (-1, 2)):
	raise ValueError("edges must be (n, 2)!")
	# find the maximum index referenced in either nodes or edges
	counts = [0]
	if len(edges) > 0:
	counts.append(edges.max())
	if len(nodes) > 0:
	counts.append(nodes.max())
	node_count = np.max(counts) + 1
	# remove edges that don't have both nodes in the node set
	mask = np.zeros(node_count, dtype=bool)
	mask[nodes] = True
	edges_ok = mask[edges].all(axis=1)
	edges = edges[edges_ok]
	# networkx is pure python and is usually 5-10x slower than scipy
	engines = collections.OrderedDict(
	(("scipy", components_csgraph), ("networkx", components_networkx))
	)
	# if a graph engine has explicitly been requested use it
	if engine in engines:
	return engines[engine]()
	# otherwise, go through our ordered list of graph engines
	# until we get to one that has actually been installed
	for function in engines.values():
	try:
	return function()
	# will be raised if the library didn't import correctly above
	except BaseException:
	continue
	raise ImportError("no graph engines available!")

If you were looking at adding another backend that would be a great place to benchmark!

[nv-rliu]

Connected components is supported in a zero code change GPU accelerated backend to NetworkX called nx-cugraph.

Are you interested in integrating that as one of the engine options for that function?