Is there a way to copy/isolate part of a graph into a new graph?

[alxarch]

It would be useful to be able to create subgraphs that restrict all traversals and manipulations to only part of the mesh. Is there such a functionality currently (cannot seem to find something like this in the docs).

(PS I'm sorry for abusing the issues page to ask for help using plexus. If you prefer I can send emails.)

[olson-sean-k]

There is no API for this at the moment, but it's something I've been thinking about. There are two mechanisms that I think may be useful:

1. A method that splits a graph into its disjoint subgraphs.
2. A kind of "cursor" (perhaps a wrapper type) that selects a contiguous subgraph and ignores arcs that leave it.

Implementing the first mechanism shouldn't be too hard, but the "cursor" idea includes some tricky details and I'm not sure what the API would look like. Would these cover your use cases?

I'm sorry for abusing the issues page to ask for help using plexus. If you prefer I can send emails.

No problem! I don't consider it an abuse. I'm also happy to answer questions via e-mail and Gitter though, so feel free to reach out that way too.

[olson-sean-k]

Here's a first stab at isolating disjoint subgraphs. It comes with basic vertex traversal features on the same branch. disjoint_subgraphs returns an iterator over arbitrary vertices in each disjoint subgraph.

Splitting a MeshGraph into separate MeshGraphs for each subgraph will be more difficult and raises some questions about the internal API.

[alxarch]

What I had in mind was more like having some sort of user defined predicate that decides on what consists disjoint topology. (ie material_id in Geomertry.Face). The cursor type seems like a possible solution but it would just be hiding some sort of filter over the iteration. For my use case just having an operation that could split a Vertex/Edge for me to slice my geometry at the borders of subgraphs would suffice. This affects the topology and adds an actual boundary at the borders but it's also the only way to do it without copying large parts of the mesh. The simplest method if copying wasn't an issue would probably be to copy the whole graph and delete unneeded geometry.

[olson-sean-k]

I've been thinking of another way to approach this that may be useful. MeshGraph could provide a split_at_path function. This would accept a path and "cut" the graph into two sub-graphs along it.

The path would need to completely subdivide a manifold. This means the path:

• must not cross itself (never visit a given vertex more than once)
• if open (not a loop), must terminate within a single ring
• if closed, must be well-formed (no "tail" entering the loop)

If a path meets those requirements, then it will completely subdivide sub-graphs. Such a split_at_path function should make it possible to slice and dice a graph, splitting it in two each time. It may also be worthwhile to introduce types to represent paths, though that could lead to confusion with std::path...

[olson-sean-k]

The API for this could look something like the following:

let mut path = graph.arc_mut(key).unwrap().into_path();
path.push(ByIndex(1)).unwrap();
...
let (a, b) = MeshGraph::split_at_path(path).unwrap();

This example uses a PathView type. Like RingView, this super-view requires consistency and does not directly expose a payload (geometry). To make it more clear that the graph is being split (rather than the path), split_at_path is a member of MeshGraph and accepts a mutable PathView. If successful, split_at_path returns a pair of VertexViews belonging to each sub-graph. This is similar to disjoint_subgraph_vertices.

PathView borrows its graph and ensures that the path is valid until it is consumed. The push function accepts a Selector<VertexKey> and fails if pushing the arc between its endpoint and the given vertex results in a malformed path.

I've pushed a sketch of this to the path branch.

[olson-sean-k]

I've also started experimenting with an into_disjoint_subgraphs function for MeshGraph as mentioned above. This would allow disjoint sub-graphs that are a member of the same graph to be decomposed into separate graph instances. Here's an example of this used together with split_at_path:

MeshGraph::split_at_path(path).unwrap();
let graphs = graph.into_disjoint_subgraphs();
for graph in graphs {
    // ...
}

It's important to note that this would require copying and/or rekeying in the storage layer, so this could be a relatively expensive operation. However, it should still be significantly cheaper and much more ergonomic than copying a graph and removing unwanted topology from the copies.