Thread: Boost Graph Library

  1. #1
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895

    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  2. #2
    Moderately Rabid Decrypt's Avatar
    Join Date
    Feb 2005
    Location
    Milwaukee, WI, USA
    Posts
    300
    Do you need help with the alogrithm itself or the code needed to perform it?
    There is a difference between tedious and difficult.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. some help on downloading boost library
    By Masterx in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 03-01-2009, 10:13 AM
  2. Boost Auto-Linking
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 12-30-2007, 06:11 AM
  3. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  4. very weird .h problem
    By royuco77 in forum C++ Programming
    Replies: 1
    Last Post: 09-11-2005, 07:55 AM
  5. link error: with Boost date_time library
    By Hotman_x in forum C++ Programming
    Replies: 0
    Last Post: 01-14-2003, 07:54 AM