Boost logo

Boost Users :

From: Stephen Torri (storri_at_[hidden])
Date: 2007-04-12 16:17:00


BOOST: 1.33.1
GCC: 4.1.1
OS: Fedora Core 6

I am receiving a abort signal from glibc when I am running the test
program that is attached. You will find that the program is suppose to
create a directed graph of five vertexes. I have printed out how the
edges are structured so you will have a picture of the graph. I hope
someone is able to help me figure out what is going wrong with this test
program. So far I am stumped as to what is wrong. Figuring out the
problem and its solution will help me figure out a much larger problem.

So the questions I have are:

1. Is there a problem with the definition of the graph?

2. Did I fail to do something in the initialization of the graph?

3. Is this the right forum for me asking my questions?

Stephen

-----------------------------------------
                   OUTPUT
-----------------------------------------
[storri_at_localhost infrastructure]$ ./test_dag
Added edge: 1 -> 20
Added edge: 1 -> 30
Added edge: 1 -> 40
Added edge: 1 -> 5
Added edge: 20 -> 5
Added edge: 30 -> 5
Added edge: 40 -> 5
*** glibc detected *** ./test_dag: free(): invalid next size (fast):
0x09f08780 ***
======= Backtrace: =========
/lib/libc.so.6[0x47c1709d]
/lib/libc.so.6(cfree+0x90)[0x47c1a6f0]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0x48058ef1]
./test_dag[0x8053357]
./test_dag[0x8053381]
./test_dag[0x80533bb]
./test_dag[0x8053db1]
./test_dag[0x805f2bd]
./test_dag[0x805f3e9]
./test_dag[0x805f434]
./test_dag[0x805f468]
./test_dag[0x804a858]
/lib/libc.so.6(__libc_start_main+0xdc)[0x47bc6f2c]
./test_dag(_ZNSt15basic_streambufIcSt11char_traitsIcEE6xsputnEPKci
+0x7d)[0x804a251]
======= Memory map: ========
003e3000-003e4000 r-xp 003e3000 00:00 0 [vdso]
08048000-08068000 r-xp 00000000 fd:00
3178562 /home/storri/src/libreverse/src/infrastructure/test_dag
08068000-08069000 rwxp 0001f000 fd:00
3178562 /home/storri/src/libreverse/src/infrastructure/test_dag
09f08000-09f29000 rwxp 09f08000 00:00 0
47b94000-47bad000 r-xp 00000000 fd:00 458769 /lib/ld-2.5.so
47bad000-47bae000 r-xp 00018000 fd:00 458769 /lib/ld-2.5.so
47bae000-47baf000 rwxp 00019000 fd:00 458769 /lib/ld-2.5.so
47bb1000-47ce8000 r-xp 00000000 fd:00 458776 /lib/libc-2.5.so
47ce8000-47cea000 r-xp 00137000 fd:00 458776 /lib/libc-2.5.so
47cea000-47ceb000 rwxp 00139000 fd:00 458776 /lib/libc-2.5.so
47ceb000-47cee000 rwxp 47ceb000 00:00 0
47cf0000-47d15000 r-xp 00000000 fd:00 458802 /lib/libm-2.5.so
47d15000-47d16000 r-xp 00024000 fd:00 458802 /lib/libm-2.5.so
47d16000-47d17000 rwxp 00025000 fd:00 458802 /lib/libm-2.5.so
47f97000-47fa2000 r-xp 00000000 fd:00
458837 /lib/libgcc_s-4.1.1-20070105.so.1
47fa2000-47fa3000 rwxp 0000a000 fd:00
458837 /lib/libgcc_s-4.1.1-20070105.so.1
47fa5000-48085000 r-xp 00000000 fd:00 12363696 /usr/lib/libstdc
++.so.6.0.8
48085000-48088000 r-xp 000e0000 fd:00 12363696 /usr/lib/libstdc
++.so.6.0.8
48088000-4808a000 rwxp 000e3000 fd:00 12363696 /usr/lib/libstdc
++.so.6.0.8
4808a000-48090000 rwxp 4808a000 00:00 0
b7e00000-b7e21000 rw-p b7e00000 00:00 0
b7e21000-b7f00000 ---p b7e21000 00:00 0
b7f4c000-b7f4e000 rw-p b7f4c000 00:00 0
b7f60000-b7f62000 rw-p b7f60000 00:00 0
bfa5e000-bfa73000 rw-p bfa5e000 00:00 0 [stack]
Aborted

-----------------------------------------
               GDB OUTPUT
-----------------------------------------
(gdb) bt
#0 0x009af402 in __kernel_vsyscall ()
#1 0x47bd9d40 in raise () from /lib/libc.so.6
#2 0x47bdb591 in abort () from /lib/libc.so.6
#3 0x47c0f33b in __libc_message () from /lib/libc.so.6
#4 0x47c1709d in _int_free () from /lib/libc.so.6
#5 0x47c1a6f0 in free () from /lib/libc.so.6
#6 0x48058ef1 in operator delete () from /usr/lib/libstdc++.so.6
#7 0x08053357 in __gnu_cxx::new_allocator<boost::default_color_type>::deallocate (this=0xbfcf7974,
    __p=0x97fe780)
    at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/ext/new_allocator.h:94
#8 0x08053381 in std::_Vector_base<boost::default_color_type, std::allocator<boost::default_color_type> >::_M_deallocate (this=0xbfcf7974, __p=0x97fe780, __n=5)
    at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:133
#9 0x080533bb in ~_Vector_base (this=0xbfcf7974)
    at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:119
#10 0x08053db1 in ~vector (this=0xbfcf7974)
    at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:272
#11 0x0805f2bd in boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, void*, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, vis=
        {<boost::dfs_visitor<boost::null_visitor>> = {m_vis = {<> = {<No data fields>}, <No data fields>}}, m_iter = {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}}, start_vertex=0x97fe220, params=@0xbfcf7a34) at /usr/include/boost/graph/depth_first_search.hpp:246
#12 0x0805f3e9 in boost::depth_first_search<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, params=@0xbfcf7a34)
    at /usr/include/boost/graph/depth_first_search.hpp:324
#13 0x0805f434 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >, int, boost::buffer_param_t, boost::no_property> (
    g=@0xbfcf7ac4, result=
      {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}, params=@0xbfcf7a74) at /usr/include/boost/graph/topological_sort.hpp:64
#14 0x0805f468 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > > (g=@0xbfcf7ac4, result=
      {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}) at /usr/include/boost/graph/topological_sort.hpp:70
#15 0x0804a858 in main () at test_dag.cpp:256

-------------------------------
       TEST PROGRAM
--------------------------------
#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;

    typedef boost::adj_list_vertex_property_map<Graph_Base::Graph_t,
                                                boost::shared_ptr<Component>,
                                                const boost::shared_ptr<Component>&,
                                                boost::vertex_name_t>
    Property_Map_const_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(boost::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(boost::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;
            }
        else
            {
                std::cout << boost::format("Added edge: %d -> %d")
                    % parent_id
                    % obj_ptr->get_ID()
                          << std::endl;
            }
    }

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

    Component::ptr_t
    get_Component (const Vertex_t& node) const
    {
        Graph_Base::Property_Map_const_t clist = get(boost::vertex_name, m_graph);

        return clist[node];
    }

    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 ) );

    std::cout << "A topological ordering: ";

    for ( m_container::reverse_iterator ii = comp_list.rbegin();
          ii != comp_list.rend();
          ++ii )
    {
        Component::ptr_t comp_ptr = m_graph.get_Component ( *ii );
        std::cout << comp_ptr->get_ID() << " ";
    }
    std::cout << std::endl;

    return 0;
}


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net