Traversals

Usage

data = M.mesh.load("my/super/data.mesh")

tree = M.processing.trees.EdgeSpanningTree(data)() # the () calls tree.compute()
for (parent,child) in tree.traverse():
  print(parent,"->",child)

Spanning trees of a disk mesh (left: EdgeSpanningTree, right: FaceSpanningTree)

EdgeSpanningTree

Bases: SpanningTree

A spanning tree defined over the connectivity of a mesh. Edges of a polyline, surface mesh or volume mesh form an undirected graph, from which we can extract a spanning tree

Warning

This tree considers a unique starting point and stops when all reachable vertices are visited. If the mesh is disconnected, the tree will be incomplete. In this case, use EdgeSpanningForest class instead.

Attributes:

Name	Type	Description
parent	list	the list of indices of the parent node in the tree. None for the root.
children	list	list of indices of children nodes.
edges	list	list of edges that form the tree.

Parameters:

Name	Type	Description	Default
mesh	Mesh	the input mesh (Polyline, Surface or Volume)	required
starting_vertex	int	Index of the root of the tree. If None is provided, root is chosen at random. Defaults to None.	None
avoid_boundary	bool	If True, boundary edges of a SurfaceMesh will not be traversed by the tree. Defaults to False.	False
avoid_edges	set	Set of edges that should not be travelled by the tree. /!\ If this set disconnects the mesh, the tree will be incomplete. Defaults to None.	None

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree. Returns tuple of form (node, parent)

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

EdgeMinimalSpanningTree

Bases: EdgeSpanningTree

Same as EdgeSpanningTree but uses Kruskal's algorithm instead of a Breadth First Search. This implies that the resulting spanning tree is minimal in term of edge lengths.

Inherits from EdgeSpanningTree.

Warning

This tree considers a unique starting point and stops when all reachable vertices are visited. If the mesh is disconnected, the tree will be incomplete. In this case, use EdgeSpanningForest class instead.

Parameters:

Name	Type	Description	Default
mesh	Mesh	the input mesh (Polyline, Surface or Volume)	required
starting_vertex	int	Index of the root of the tree. If None is provided, root is chosen at random. Defaults to None.	None
avoid_boundary	bool	If True, boundary edges will not be traversed by the tree. Defaults to False.	False
weights	str | dict)	provided weights of each edge. Options are: - "one" : uniform weight = 1 for every edge - "length" : use the length of the edge - any dict : custom weights	'length'

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree. Returns tuple of form (node, parent)

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

EdgeSpanningForest

Bases: SpanningForest

A spanning forest that runs on edges. Unlike a spanning tree, will create new roots and expand trees until all vertices of the mesh have been visited

edges: list property

List of edges in the trees

Returns:

Name	Type	Description
list	list	list of edges

n_trees: int property

Number of trees in the forest

Returns:

Name	Type	Description
int	int

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

FaceSpanningTree

Bases: SpanningTree

A spanning tree defined over the connectivity of a mesh, built over dual edges.

Warning

This tree considers a unique starting point and stops when all reachable faces are visited. If the mesh is disconnected, the tree will be incomplete. In this case, use FaceSpanningForest class instead.

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine		the tree

traverse(order='BFS')

Iterator on the nodes of a tree. Returns tuple of form (node, parent)

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

FaceSpanningForest

Bases: SpanningForest

A spanning forest that runs on dual edges. Unlike a spanning tree, will create new roots and expand trees until all faces of the mesh have been visited

edges: list property

List of edges in the trees

Returns:

Name	Type	Description
list	list	list of edges

n_trees: int property

Number of trees in the forest

Returns:

Name	Type	Description
int	int

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

CellSpanningTree

Bases: SpanningTree

A spanning tree defined over the connectivity of a volume mesh.

Warning

This tree considers a unique starting point and stops when all reachable vertices are visited. If the mesh is disconnected, the tree will be incomplete. In this case, use CellSpanningForest class instead.

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree. Returns tuple of form (node, parent)

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'

CellSpanningForest

Bases: SpanningForest

A spanning forest that runs between cells. Unlike a spanning tree, will create new roots and expand trees until all cells of the mesh have been visited

edges: list property

List of edges in the trees

Returns:

Name	Type	Description
list	list	list of edges

n_trees: int property

Number of trees in the forest

Returns:

Name	Type	Description
int	int

build_tree_as_polyline()

Builds the tree as a new polyline object. Useful for debug and visualization purposes

Returns:

Name	Type	Description
PolyLine	PolyLine	the tree

traverse(order='BFS')

Iterator on the nodes of a tree

Parameters:

Name	Type	Description	Default
order	str	BFS or DFS order. Defaults to "BFS".	'BFS'