Help with initialization of graph (Boost Graph Library)

Discussion in 'C++' started by Jef Driesen, Jan 23, 2006.

  1. Jef Driesen

    Jef Driesen Guest

    I'm trying to create a graph from an image, where pixel values are
    regions labels. I have defined my graph to use lists instead of the
    vectors (because I need to add/remove vertices and edges) and one extra
    property for the vertex (the region label):

    typedef boost::adjacency_list<
    boost::listS, // Adjacency list
    boost::listS, // Vertex list
    boost::undirectedS, // Undirected graph
    unsigned int, // Vertex property (=label)
    boost::no_property, // Edge property
    boost::no_property, // Graph property
    boost::listS // Edge list
    > graph;

    typedef boost::graph_traits<graph>::vertex_descriptor vertex_t;
    typedef boost::graph_traits<graph>::edge_descriptor edge_t;

    I have the following pseudo code to populate the graph:

    graph g;
    for each pixel (i,j) {
    unsigned int u_label = image[j];
    for each neighbourhood pixel (k,l) {
    unsigned int v_label = image[k][l];
    if (u_label != v_label) {
    // Find/add both vertices
    vertex_t u = boost::add_vertex(u_label,g);
    vertex_t v = boost::add_vertex(v_label, g);
    // Find/add edge
    boost::add_edge(u, v, g);
    }
    }
    }

    But this creates many duplicates (with regard to the label) for both
    vertices and edges. How can i prevent this? Would using a set for the
    edges solves my problem? And how can I add a vertex only if it does not
    exist already?
     
    Jef Driesen, Jan 23, 2006
    #1
    1. Advertising

  2. Jef Driesen

    mlimber Guest

    Jef Driesen wrote:
    > I'm trying to create a graph from an image, where pixel values are
    > regions labels. I have defined my graph to use lists instead of the
    > vectors (because I need to add/remove vertices and edges) and one extra
    > property for the vertex (the region label):
    >
    > typedef boost::adjacency_list<
    > boost::listS, // Adjacency list
    > boost::listS, // Vertex list
    > boost::undirectedS, // Undirected graph
    > unsigned int, // Vertex property (=label)
    > boost::no_property, // Edge property
    > boost::no_property, // Graph property
    > boost::listS // Edge list
    > > graph;

    > typedef boost::graph_traits<graph>::vertex_descriptor vertex_t;
    > typedef boost::graph_traits<graph>::edge_descriptor edge_t;
    >
    > I have the following pseudo code to populate the graph:
    >
    > graph g;
    > for each pixel (i,j) {
    > unsigned int u_label = image[j];
    > for each neighbourhood pixel (k,l) {
    > unsigned int v_label = image[k][l];
    > if (u_label != v_label) {
    > // Find/add both vertices
    > vertex_t u = boost::add_vertex(u_label,g);
    > vertex_t v = boost::add_vertex(v_label, g);
    > // Find/add edge
    > boost::add_edge(u, v, g);
    > }
    > }
    > }
    >
    > But this creates many duplicates (with regard to the label) for both
    > vertices and edges. How can i prevent this? Would using a set for the
    > edges solves my problem? And how can I add a vertex only if it does not
    > exist already?


    This post is off-topic here (see FAQ 5.9). You probably want to post to
    the Boost users list:

    http://boost.org/more/mailing_lists.htm#users

    Cheers! --M
     
    mlimber, Jan 23, 2006
    #2
    1. Advertising

  3. Jef Driesen

    Jef Driesen Guest

    mlimber wrote:
    > Jef Driesen wrote:
    >> I'm trying to create a graph from an image, where pixel values are
    >> regions labels. I have defined my graph to use lists instead of the
    >> vectors (because I need to add/remove vertices and edges) and one extra
    >> property for the vertex (the region label):
    >>
    >> typedef boost::adjacency_list<
    >> boost::listS, // Adjacency list
    >> boost::listS, // Vertex list
    >> boost::undirectedS, // Undirected graph
    >> unsigned int, // Vertex property (=label)
    >> boost::no_property, // Edge property
    >> boost::no_property, // Graph property
    >> boost::listS // Edge list
    >> > graph;

    >> typedef boost::graph_traits<graph>::vertex_descriptor vertex_t;
    >> typedef boost::graph_traits<graph>::edge_descriptor edge_t;
    >>
    >> I have the following pseudo code to populate the graph:
    >>
    >> graph g;
    >> for each pixel (i,j) {
    >> unsigned int u_label = image[j];
    >> for each neighbourhood pixel (k,l) {
    >> unsigned int v_label = image[k][l];
    >> if (u_label != v_label) {
    >> // Find/add both vertices
    >> vertex_t u = boost::add_vertex(u_label,g);
    >> vertex_t v = boost::add_vertex(v_label, g);
    >> // Find/add edge
    >> boost::add_edge(u, v, g);
    >> }
    >> }
    >> }
    >>
    >> But this creates many duplicates (with regard to the label) for both
    >> vertices and edges. How can i prevent this? Would using a set for the
    >> edges solves my problem? And how can I add a vertex only if it does not
    >> exist already?

    >
    > This post is off-topic here (see FAQ 5.9). You probably want to post to
    > the Boost users list:
    >
    > http://boost.org/more/mailing_lists.htm#users


    I do not entirely agree with you that my post is off-topic here, but
    it's a good idea do post my question to the boost users list anyway. I
    wasn't even aware of the existence of that list.
     
    Jef Driesen, Jan 24, 2006
    #3
  4. Jef Driesen

    mlimber Guest

    Jef Driesen wrote:
    > mlimber wrote:
    > > This post is off-topic here (see FAQ 5.9). You probably want to post to
    > > the Boost users list:
    > >
    > > http://boost.org/more/mailing_lists.htm#users

    >
    > I do not entirely agree with you that my post is off-topic here, but
    > it's a good idea do post my question to the boost users list anyway. I
    > wasn't even aware of the existence of that list.


    I suppose the original post could be in the gray area for this
    newsgroup, but since the graph library is not part of TR1, you'll
    likely get better help from the Boost user's list.

    Cheers! --M
     
    mlimber, Jan 24, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fab
    Replies:
    21
    Views:
    6,618
    Simon Brooke
    Nov 16, 2006
  2. George Sakkis
    Replies:
    1
    Views:
    469
    Szabolcs Nagy
    Jan 29, 2007
  3. =?ISO-8859-2?Q?Miros=B3aw?= Makowiecki

    The boost.variant library and boost::make_recursive_variant

    =?ISO-8859-2?Q?Miros=B3aw?= Makowiecki, Jul 5, 2007, in forum: C++
    Replies:
    1
    Views:
    726
    dasjotre
    Jul 6, 2007
  4. Almoni
    Replies:
    0
    Views:
    3,127
    Almoni
    Jan 17, 2010
  5. Emilio Mayorga
    Replies:
    6
    Views:
    365
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page