creation of nested subgraphs by vertex descriptors is broken/unintuitive

[reuther-genisys]

When using subgraph::create_subgraph(VertexIterator first, VertexIterator last), the vertex descriptors are interpreted as vertex descriptors into the root graph. (add_vertex expects the given descriptor to be a root graph descriptor).

My expectation is that the vertex descriptors should be interpreted as descriptors for the subgraph on which create_subgraph is called on. This way you can get a subgraph object, do some vertex selection logic on it and pass the set of selected vertices to create_subgraph without ever needing to worry where the graph is situated in the subgraph tree.

The fix is to replace line 197 add_vertex(*first, *m_children.back()); with add_vertex(local_to_global(*first), *m_children.back());.

[jeremy-murphy]

I'm a little nervous about changing behaviour in a way that might break existing code, although I agree that the current implementation does not sound ideal.

Do you mind giving a more full example that demonstrates how unintuitive the current implementation is?

[reuther-genisys]

The current approach breaks for all algorithms where a graph is recursively split into smaller subgraphs.

My application is the decomposition of a cycle-free graph into a complete set of longest-possible traversal paths. (Complete here means that every vertex belongs to exactly one resulting traversal path). The approach is recursive and looks like this:

using Graph = boost::subgraph<G>;
using VertexD = boost::graph_traits<Graph>::vertex_descriptor;

void recurse(Graph graph, std::vector<std::vector<Object>>& paths)
{
  std::vector<std::set<VertexD> > components = ComponentDecomposition(); // essentially connected_components(), sorting the result into sets for ease of use

  for (auto&& component: components)
  {
    Graph componentGraph = graph.create_subgraph(component.begin(), component.end()); 

    std::vector<VertexD> path = GetLongestPath(componentGraph);  // essentially bfs starting at each vertex of degree 1

    paths.push_back(GetPathObjects(path)); // extract the Object properties from the path vertices

    std::set<VertexD> remainingVertices(vertices(componentGraph).first, vertices(componentGraph).second);
    for (auto&& v: path)
       remainingVertices.erase(v);

    recurse(componentGraph.create_subgraph(remainingVertices.begin(), remainingVertices.end()), paths);
}

Both create_subgraph calls here operate on vertex descriptors obtained from the present graph. With the current behavior, this code breaks immediately on the second create_subgraph call..

If you do not want to change behavior, the documentation should at least be updated (for all versions!) to reflect the behavior:

When calling create_subgraph, transform all vertex descriptors in the iterator range to global descriptors using local_to_global first.

[jeremy-murphy]

Let me get this straight in my head with some hierarchical labelling. I'll use A, B, C to denote graphs, a, b, c to denote vertices from their respective graphs. By definition of sequence, C is a subgraph of B, B is a subgraph of A, etc.

When we call ComponentDecomposition() that's called on A, and so component is a list of a.
Then at the top of the loop, we call A.create_subgraph(a), yielding a B (componentGraph).
remainingVertices is a b because it comes from B.
It then calls B.create_subgraph(b) in the call to recurse.

Intuitively, yes, it looks like that second call, B.create_subgraph(b), should just work without transforming local vertex descriptors to global ones, especially as the documentation for create_subgraph. Let me look through some more examples and documentation to be sure I haven't missed something.

One thing that concerns me in your algorithm, which is somewhat related, is that it looks like paths will contain lists of local vertex descriptors for subgraphs that no longer exist? Or do you convert them to global vertex descriptors in your actual implementation?

Another thing, just a performance hint, but you're probably better of using std::vector and the std::set_ algorithms rather than using std::set.

[jeremy-murphy]

I'd better take #161 into consideration when I look at this.

[reuther-genisys]

When we call ComponentDecomposition() that's called on A, and so component is a list of a. Then at the top of the loop, we call A.create_subgraph(a), yielding a B (componentGraph). remainingVertices is a b because it comes from B. It then calls B.create_subgraph(b) in the call to recurse.

Intuitively, yes, it looks like that second call, B.create_subgraph(b), should just work without transforming local vertex descriptors to global ones, especially as the documentation for create_subgraph. Let me look through some more examples and documentation to be sure I haven't missed something.

Exactly: This is the (first) call that will yield wrong results. It can even modify B^*.

One thing that concerns me in your algorithm, which is somewhat related, is that it looks like paths will contain lists of local vertex descriptors for subgraphs that no longer exist? Or do you convert them to global vertex descriptors in your actual implementation?

I extract vertex properties ("Object", by calling GetPathObjects ⁺) and store these in the resulting paths. However, please consider my example to be mock code ;).

Another thing, just a performance hint, but you're probably better of using std::vector and the std::set_ algorithms rather than using std::set.

Thank you for the hint, I will look into these.

^{* When adding vertices to the newly created subgraph by add_vertex, vertices can also be added to the subgraphs parent (subgraph.h:417ff)}

^{+ Yes, GetGraphObjects should also get componentGraph as parameter for this to work. As I said, mock code...}