Find all reachable vertices in a Boost BGL graph efficiently

1
votes

I'm new to boost graph library and trying to solve the following problem:

In a graph (boost::adjacency_list) I have 3 different vertex types (implemented using std::variant) and currently undirected edges:

  1. Connector (1)
  2. Switch (2)
  3. SwitchState (3) - (ON/OFF)

A typical hierarchy in my graph is like this:

(1a) - (2a) - (1b) - (1d) - (2b) - (1e)
        |                    |
       (3a)                 (3b)
        |                    |
       (1c)

What I need to do is to find all reachable vertices from a certain starting point (e.g. 1a):

1a -> 2a -> 1b -> 1d -> 2b -> 1e

Of course just using BFS or DFS come to mind immediately! :-)

However: The state of vertex (2) (a switch or relais) is controlled by the state (boolean) of the directly connected vertex (3). That means that there's no way to traverse from (1a) to (1b) via vertex (2a) if (3a) is (let's say) false. And at last: One cannot traverse from type (2) to type (3) vertices.

My question is: Does anyone have suggestions about how to implement such a graph traversal efficiently? I have implemented this in plain C++ using lots of vectors/maps etc. and DFS already but would like to move code to a higher, more abstract (but hopefully still efficient) implementation of the underlying graph!

I'm unsure if I should:

  1. Use a filtered_graph and just use BFS or DFS to traverse?
  2. Create a sub_graph depending on the type 3 vertices state then and apply BFS/DFS?
  3. There's a way to achieve this "on the fly" while searching via BFS/DFSvisitor?
  4. Another solution?

Helpful ideas are very welcome!

PS: The code is used to simulate an electrical network - just in case.

1
c++boostgraphdepth-first-searchboost-graph

1 Answers

2
votes

Use a filtered_graph and just use BFS or DFS to traverse?

A filtered graph to "hide" switched-off edges seems conceptually simplest to me. If your property bundles are sufficiently simple (no dynamic allocations and no references to aid with aliasing rules) the compiler will do a surprisingly great job optimizing it all.

Create a sub_graph depending on the type 3 vertices state then and apply BFS/DFS?

Subgraphs have considerable overhead so they don't seem like your ticket here.

There's a way to achieve this "on the fly" while searching via BFS/DFSvisitor?

I think so. You could have a visitor act on the the "examine_edge" event and mark downstream vertex in the color map. You should check the algorithm documentation to see whether the semantics of the color map are documented.

If so, this would seem to be likely the most optimal solution, even though conceptually it is a little bit more complex than the filtered_graph approach.

If not, I'd think twice before basing an optimization on undocumented implementation details. It might break in future versions, or have surprising interactions with e.g. hidden special cases in the library.