-
Boost Graph Library
I've given up on trying to understand the documentation on the subject, so I'm turning to you in the hopes that you can tell me what I need to do.
My problem is deceptively simple. I have a directed graph. Each vertex has two properties, a pointer and a numeric ID. Using the bundled properties, this is easy to implement. The edges have no properties.
I know how to add and remove vertices and edges. This is not a problem either.
At one point, I want to grab all vertices with the ID 0 or 1 (OID_NULLOBJ and OID_EXPECT in my code) and start a DFS/BFS (doesn't really matter) visit from each one, colouring vertices as I go. After I've done this, I want to find all uncoloured vertices.
In other words, I want to find all vertices that are not reachable from any of my start vertices.
The problem I have is with the external property map I need for the algorithm, and the visitor.
To illustrate:
Code:
A ---> B <---> C
D ---> E
\ |
\ V
--> F <--- I
G <---> H
If A and D are my start vertices, I want I, G and H to be uncoloured after I'm done.
Any help greatly appreciated.
-
Do you need help with the alogrithm itself or the code needed to perform it?
-
Only the code. The algorithm is pretty straight-forward. I just need to paint all vertices reachable from the root vertices, and afterwards collected the unpainted ones.