[BGL] Remove vertices/edges from a subgraph

What is the reason for vertex/edge removal functions in subgraphs being unimplemented? Is it simple oversight / lack of demand or would that pose some problems? Regards, Greg

On Thu, Jan 22, 2009 at 8:48 AM, Grzegorz Slodkowicz
What is the reason for vertex/edge removal functions in subgraphs being unimplemented? Is it simple oversight / lack of demand or would that pose some problems?
Probably because It can't be safely or efficiently implemented in a generic fashion. There's a tendency for the entire library to rely on vertex and edge indices as opaque references, and removing a vertex or edge can cause a kind of cascading renumbering of elements that is roughly O(V) or O(E) * N (the number of subgraphs). Andrew Sutton andrew.n.sutton@gmail.com

Probably because It can't be safely or efficiently implemented in a generic fashion. There's a tendency for the entire library to rely on vertex and edge indices as opaque references, and removing a vertex or edge can cause a kind of cascading renumbering of elements that is roughly O(V) or O(E) * N (the number of subgraphs).
I see. But suppose I have a graph that is attached to some root graph but has no subgraphs of its own, and I want to remove some nodes and edges (without affecting rest of the hierarchy at all), what would be the best way to do that? Regards, Greg

I see. But suppose I have a graph that is attached to some root graph but has no subgraphs of its own, and I want to remove some nodes and edges (without affecting rest of the hierarchy at all), what would be the best way to do that?
Carefully :) You mean that the subgraphs are disjoint and you want to remove elements form a disjoint subgraph and the root graph? You might need to create a new graph data structure - lets call it disjoint_subgraphs - that's kind of a flattened, inverted version of the subgraph system. Each subgraph is actually an independent, fully mutable adjacency_list (or whatever). The "root" graph could provide a read-only view over the subgraphs. Descriptors for the root graph would have to be redefined to reference descriptors from specific subgraphs (not too hard). Vertex and edge iterators would simply span the iterators of the subgraphs (also pretty easy). Does that sound like it might do the trick? Andrew Sutton andrew.n.sutton@gmail.com

You mean that the subgraphs are disjoint and you want to remove elements form a disjoint subgraph and the root graph? You might need to create a new graph data structure - lets call it disjoint_subgraphs - that's kind of a flattened, inverted version of the subgraph system. Each subgraph is actually an independent, fully mutable adjacency_list (or whatever). The "root" graph could provide a read-only view over the subgraphs. Descriptors for the root graph would have to be redefined to reference descriptors from specific subgraphs (not too hard). Vertex and edge iterators would simply span the iterators of the subgraphs (also pretty easy).
Come to think of it, I have only one subgraph and don't want to affect the root graph, so perhaps I shouldn't use subgraph<> at all (I use the induced subgraph functionality but implementing it on my own would be faster than re-inventing subgraphs). Thanks for the explanations. Best regards, Greg
participants (2)
-
Andrew Sutton
-
Grzegorz Slodkowicz