# trimesh.graph¶

## 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 or scipy.sparse.csgraph backend.

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 edge between two adjacent faces `faces_to_edges`(faces[, return_index]) Given a list of faces (n,3), return a list of edges (n*3,2) `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 traversals where every pair of consecutive node indexes is an edge in a passed edge list `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. `neighbors`(edges[, max_index, directed]) Find the neighbors for each node in an edgelist graph. `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.

Classes:

 `coo_matrix`(arg1[, shape, dtype, copy]) A sparse matrix in COOrdinate format.
`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’)

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’)

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.``neighbors`(edges, max_index=None, directed=False)

Find the neighbors for each node in an edgelist graph.

TODO : re-write this with sparse matrix operations

Parameters
• edges ((n, 2) int) – Connected nodes

• directed (bool) – If True, only connect edges in one direction

Returns

neighbors – Vertex index corresponds to set of other vertex indices

Return type

sequence

`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, **kwargs)

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]