# trimesh.graph module¶

## graph.py¶

Deal with graph operations. Primarily deal with graphs in (n,2) edge list form, and abstract the backend graph library being used.

Currently uses networkx, scipy.sparse.csgraph, or graph_tool backends.

Functions

 `connected_component_labels`(edges[, node_count]) Label graph nodes from an edge list, using scipy.sparse.csgraph `connected_components`(edges[, min_len, …]) Find groups of connected nodes from an edge list. `edges_to_coo`(edges[, count, data]) Given an edge list, return a boolean scipy.sparse.coo_matrix representing the edges in matrix form. `face_adjacency`([faces, mesh, return_edges]) Returns an (n,2) list of face indices. Compute an approximate radius between adjacent faces. Return the vertex index of the two vertices not in the shared `facets`(mesh[, engine]) Find the list of parallel adjacent faces. `fill_traversals`(traversals, edges[, edges_hash]) Convert a traversal of a list of edges into a sequence of `graph_to_svg`(graph) Turn a networkx graph into an SVG string using graphviz dot. `is_watertight`(edges[, edges_sorted]) param edges List of vertex indices `multigraph_collect`(G, traversal[, attrib]) Given a MultiDiGraph traversal, collect attributes along it. `multigraph_paths`(G, source[, cutoff]) For a networkx MultiDiGraph, find all paths from a source node to leaf nodes. `shared_edges`(faces_a, faces_b) Given two sets of faces, find the edges which are in both sets. `smoothed`(mesh[, angle, facet_minarea]) Return a non- watertight version of the mesh which will render nicely with smooth shading by disconnecting faces at sharp angles to each other. `split`(mesh[, only_watertight, adjacency, engine]) Split a mesh into multiple meshes from face connectivity. `split_traversal`(traversal, edges[, edges_hash]) Given a traversal as a list of nodes, split the traversal if a sequential index pair is not in the given edges. `traversals`(edges[, mode]) Given an edge list generate a sequence of ordered depth first search traversals using scipy.csgraph routines. Returns a networkx graph representing the vertices and their connections in the mesh.
`trimesh.graph.``connected_component_labels`(edges, node_count=None)

Label graph nodes from an edge list, using scipy.sparse.csgraph

Parameters
• edges ((n, 2) int) – Edges of a graph

• node_count (int, or None) – The largest node in the graph.

Returns

labels – Component labels for each node

Return type

(node_count,) int

`trimesh.graph.``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’, ‘graphtool’)

Returns

components – Nodes which are connected

Return type

(n,) sequence of (*,) int

`trimesh.graph.``edges_to_coo`(edges, count=None, data=None)

Given an edge list, return a boolean scipy.sparse.coo_matrix representing the edges in matrix form.

Parameters
• edges ((n,2) int) – Edges of a graph

• count (int) – The total number of nodes in the graph if None: count = edges.max() + 1

• data ((n,) any) – Assign data to each edge, if None will be bool True for each specified edge

Returns

matrix – Sparse COO

Return type

(count, count) scipy.sparse.coo_matrix

`trimesh.graph.``face_adjacency`(faces=None, mesh=None, return_edges=False)

Returns an (n,2) list of face indices. Each pair of faces in the list shares an edge, making them adjacent.

Parameters
• faces ((n, 3) int, or None) – Vertex indices representing triangles

• mesh (Trimesh object) – If passed will used cached edges instead of generating from faces

• return_edges (bool) – Return the edges shared by adjacent faces

Returns

• adjacency ((m, 2) int) – Indexes of faces that are adjacent

• edges ((m, 2) int) – Only returned if return_edges is True Indexes of vertices which make up the edges shared by the adjacent faces

Examples

This is useful for lots of things such as finding face- connected components: >>> graph = nx.Graph() >>> graph.add_edges_from(mesh.face_adjacency) >>> groups = nx.connected_components(graph_connected)

`trimesh.graph.``face_adjacency_radius`(mesh)

Parameters

mesh (trimesh.Trimesh) –

Returns

• radii ((len(self.face_adjacency),) float) – Approximate radius between faces Parallel faces will have a value of np.inf

• span ((len(self.face_adjacency),) float) – Perpendicular projection distance of two unshared vertices onto the shared edge

`trimesh.graph.``face_adjacency_unshared`(mesh)

Return the vertex index of the two vertices not in the shared edge between two adjacent faces

Parameters

mesh (Trimesh object) – Input mesh

Returns

vid_unshared – Indexes of mesh.vertices for degenerate faces without exactly one unshared vertex per face it will be -1

Return type

`trimesh.graph.``facets`(mesh, engine=None)

Find the list of parallel adjacent faces.

Parameters
• mesh (trimesh.Trimesh) –

• engine (str) – Which graph engine to use: (‘scipy’, ‘networkx’, ‘graphtool’)

Returns

facets – Groups of face indexes of parallel adjacent faces.

Return type

sequence of (n,) int

`trimesh.graph.``fill_traversals`(traversals, edges, edges_hash=None)

Convert a traversal of a list of edges into a sequence of traversals where every pair of consecutive node indexes is an edge in a passed edge list

Parameters
• traversals (sequence of (m,) int) – Node indexes of traversals of a graph

• edges ((n, 2) int) – Pairs of connected node indexes

• edges_hash (None, or (n,) int) – Edges sorted along axis 1 then hashed using grouping.hashable_rows

Returns

splits – Node indexes of connected traversals

Return type

sequence of (p,) int

`trimesh.graph.``graph_to_svg`(graph)

Turn a networkx graph into an SVG string using graphviz dot.

Parameters

graph (networkx graph) –

Returns

svg

Return type

string, pictoral layout in SVG format

`trimesh.graph.``is_watertight`(edges, edges_sorted=None)
Parameters
• edges ((n, 2) int) – List of vertex indices

• edges_sorted ((n, 2) int) – Pass vertex indices sorted on axis 1 as a speedup

Returns

• watertight (boolean) – Whether every edge is shared by an even number of faces

• winding (boolean) – Whether every shared edge is reversed

`trimesh.graph.``multigraph_collect`(G, traversal, attrib=None)

Given a MultiDiGraph traversal, collect attributes along it.

Parameters
• G (networkx.MultiDiGraph) –

• traversal

• attrib (dict key, name to collect. If None, will return all) –

Returns

collected

Return type

(len(traversal) - 1) list of attributes

`trimesh.graph.``multigraph_paths`(G, source, cutoff=None)

For a networkx MultiDiGraph, find all paths from a source node to leaf nodes. This function returns edge instance numbers in addition to nodes, unlike networkx.all_simple_paths.

Parameters
• G (networkx.MultiDiGraph) – Graph to evaluate

• source (hashable) – Node to start traversal at

• cutoff (int) – Number of nodes to visit If None will visit all nodes

Returns

traversals – Traversals of the multigraph

Return type

(n,) list of [(node, edge instance index), ] paths

`trimesh.graph.``shared_edges`(faces_a, faces_b)

Given two sets of faces, find the edges which are in both sets.

Parameters
• faces_a ((n, 3) int) – Array of faces

• faces_b ((m, 3) int) – Array of faces

Returns

shared – Edges shared between faces

Return type

(p, 2) int

`trimesh.graph.``smoothed`(mesh, angle=None, facet_minarea=15)

Return a non- watertight version of the mesh which will render nicely with smooth shading by disconnecting faces at sharp angles to each other.

Parameters
• mesh (trimesh.Trimesh) – Source geometry

• angle (float or None) – Angle in radians face pairs with angles smaller than this will appear smoothed

• facet_minarea (float or None) – Minimum area fraction to consider IE for facets_minarea=25 only facets larger than mesh.area / 25 will be considered.

Returns

smooth – Geometry with disconnected face patches

Return type

trimesh.Trimesh

`trimesh.graph.``split`(mesh, only_watertight=True, adjacency=None, engine=None)

Split a mesh into multiple meshes from face connectivity.

If only_watertight is true it will only return watertight meshes and will attempt to repair single triangle or quad holes.

Parameters
• mesh (trimesh.Trimesh) –

• only_watertight (bool) – Only return watertight components

• adjacency ((n, 2) int) – Face adjacency to override full mesh

• engine (str or None) – Which graph engine to use

Returns

meshes – Results of splitting

Return type

(m,) trimesh.Trimesh

`trimesh.graph.``split_traversal`(traversal, edges, edges_hash=None)

Given a traversal as a list of nodes, split the traversal if a sequential index pair is not in the given edges.

Parameters
• edges ((n, 2) int) – Graph edge indexes

• traversal ((m,) int) – Traversal through edges

• edge_hash ((n,)) – Edges sorted on axis=1 and passed to grouping.hashable_rows

Returns

split

Return type

sequence of (p,) int

`trimesh.graph.``traversals`(edges, mode='bfs')

Given an edge list generate a sequence of ordered depth first search traversals using scipy.csgraph routines.

Parameters
• edges ((n, 2) int) – Undirected edges of a graph

• mode (str) – Traversal type, ‘bfs’ or ‘dfs’

Returns

traversals – Ordered DFS or BFS traversals of the graph.

Return type

(m,) sequence of (p,) int

`trimesh.graph.``vertex_adjacency_graph`(mesh)

Returns a networkx graph representing the vertices and their connections in the mesh.

Parameters

mesh (Trimesh object) –

Returns

graph – Graph representing vertices and edges between them where vertices are nodes and edges are edges

Return type

networkx.Graph

Examples

This is useful for getting nearby vertices for a given vertex, potentially for some simple smoothing techniques. >>> graph = mesh.vertex_adjacency_graph >>> graph.neighbors(0) > [1,3,4]