[Boost-users] Where is vertex_name and vertex_index defined in the boost graph code?

From: Stephen Torri (storri_at_[hidden])
Date: 2007-04-11 22:49:59

I have the following example that I am using as a test. It is to figure
why my method of creating a directed graph fails to meet the boost
requirement of a directed graph when using topological_sort. I cannot
figure out why my fuller code compiles fine and this example does not. I
am trying to be explicit and not use 'using namespace boost' for
example. I want to declare its found in namespace x::y::z for example.

Stephen

------------
#include <boost/graph/adjacency_list.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/cstdint.hpp>
#include <boost/format.hpp>
#include <boost/graph/topological_sort.hpp>
#include <iostream>
#include <map>

class Component;

class Graph_Base
{
public:
    
    typedef boost::property< boost::vertex_index_t,
                             boost::uint32_t,
                             boost::property< boost::vertex_name_t,
                                              boost::shared_ptr<Component> > >
    VertexProperty_t;

    typedef boost::adjacency_list< boost::setS, // OutEdgeList
                                   boost::setS, // VertexList
                                   boost::directedS, // Directed
                                   VertexProperty_t > // VertexProperties
    Graph_t;
};

class Component {
public:

        typedef boost::shared_ptr<Component> ptr_t;

    Component ( boost::uint32_t id )
        : m_id ( id )
    {}

    ~Component ()
    {
        m_source_list.clear();
    }

    // Now part of Component_Data
    void set_Data_Source ( uint32_t id )
    {
        if ( ! m_source_list.insert ( std::make_pair ( id, false ) ).second )
            {
                std::cerr << "WARNING: Attempted to add a duplicate component id.";
                std::cerr << std::endl;
                std::cerr << "Ignoring component id." << std::endl;
            }
    }

    std::map<boost::uint32_t, bool>::const_iterator
    get_Source_List_Begin() const
    {
        return m_source_list.begin();
    }

    std::map<boost::uint32_t, bool>::const_iterator
    get_Source_List_End() const
    {
        return m_source_list.end();
    }

    boost::uint32_t
    get_ID (void) const
    {
        return m_id;
    }

private:

        boost::uint32_t m_id;

        std::map<boost::uint32_t, bool> m_source_list;
};

class Component_Graph {
public:

    typedef boost::graph_traits<Graph_Base::Graph_t>::vertex_descriptor Vertex_t;
    typedef boost::graph_traits<Graph_Base::Graph_t>::edge_descriptor Edge_t;

    typedef std::map<uint32_t, Vertex_t> IdVertexMap_t;

    Component_Graph ()
    {}

    void
    add_Component ( Component::ptr_t obj_ptr )
    {
        bool no_duplicate;
        IdVertexMap_t::iterator pos;
        Vertex_t node;

        if ( obj_ptr.get() == 0 )
            {
                std::cerr << boost::format("Exception throw in %s at line %d")
                    % __FILE__
                    % __LINE__
                          << std::endl;

                return;
            }

        boost::tie (pos, no_duplicate) = m_index.insert
            (std::make_pair(obj_ptr->get_ID(), node));

        if ( no_duplicate )
            {
                // Insertion was successful
                // Make a new vertex and return handle to 'node'
                node = add_vertex(m_graph);

                // Get list of Components
                boost::property_map<Graph_Base::Graph_t, boost::vertex_name_t>::type clist
                    = boost::get(vertex_name, m_graph);

                // Assign component to vertex position
                clist[node] = obj_ptr;

                // Add vertex handle to map position
                pos->second = node;

                // Get list of indexes
                boost::property_map<Graph_Base::Graph_t,
                    boost::vertex_index_t>::type ilist
                    = get(vertex_index, m_graph);

                ilist[node] = obj_ptr->get_ID();

                for ( std::map<boost::uint32_t,bool>::const_iterator cpos =
                          obj_ptr->get_Source_List_Begin();
                      cpos != obj_ptr->get_Source_List_End();
                      ++cpos )
                    {
                        this->add_Child ( (*cpos).first, obj_ptr );
                    }
            }
        else
            {
                std::cerr << "ERROR: Duplicate source found. Skipping Component"
                          << std::endl;
                return;
            }
    }

    void
    add_Child ( uint32_t parent_id,
                                 Component::ptr_t obj_ptr )
    {
        IdVertexMap_t::iterator pos;
        IdVertexMap_t::iterator cpos;

        if ( obj_ptr.get() == 0 )
            {
                std::cerr << boost::format("Exception throw in %s at line %d")
                    % __FILE__
                    % __LINE__
                          << std::endl;

                return;
            }

        pos = m_index.find (parent_id);
        cpos = m_index.find ( obj_ptr->get_ID() );

        if (pos == m_index.end())
            {
                std::cerr << "ERROR: Cannot find parent. Skipping adding component #"
                          << obj_ptr->get_ID() << std::endl;
                return;
            }

        // Add edge from parent to child
        Edge_t link;

        if (! (add_edge ( pos->second, cpos->second, m_graph).second))
            {
                std::cerr << "ERROR: Duplicate edge exists from " << parent_id
                          << " to " << obj_ptr->get_ID() << std::endl;
                return;
            }
    }

    Graph_Base::Graph_t const&
    get_Graph () const
    {
        return m_graph;
    }

    private:

        Graph_Base::Graph_t m_graph;

        IdVertexMap_t m_index;

};

int main (int, char**)
{
        // CREATE Component_Graph
    Component_Graph m_graph;

        // Create Components
    Component::ptr_t node_one ( new Component ( 1 ) );
    Component::ptr_t node_twenty ( new Component ( 20 ) );
    node_twenty->set_Data_Source ( 1 );
    Component::ptr_t node_thirty ( new Component ( 30 ) );
    node_thirty->set_Data_Source ( 1 );
    Component::ptr_t node_forty ( new Component ( 40 ) );
    node_forty->set_Data_Source ( 1 );
    Component::ptr_t node_five ( new Component ( 5 ) );
    node_five->set_Data_Source ( 1 );
    node_five->set_Data_Source ( 20 );
    node_five->set_Data_Source ( 30 );
    node_five->set_Data_Source ( 40 );

        // Add Components to Graph
    m_graph.add_Component ( node_one );
    m_graph.add_Component ( node_twenty );
    m_graph.add_Component ( node_thirty );
    m_graph.add_Component ( node_forty );
    m_graph.add_Component ( node_five );

        // Call topological_sort on graph
    typedef std::vector<Component_Graph::Vertex_t> m_container;

    m_container comp_list;

    boost::topological_sort ( m_graph.get_Graph(),
                              std::back_inserter ( comp_list ) );

        return 0;
}