Boost logo

Boost Users :

Subject: [Boost-users] [Graph] Need help with Subgraph and adjacent_vertices.
From: Marcus Fontaine (mfontai5_at_[hidden])
Date: 2010-04-05 17:59:53


I'm having trouble finding the adjacent vertices in a subgraph, using
the adjacent_vertices function. Although, it seems to work fine on a
graph that isn't the subgraph of another.

I'm using the g++ compiler, along with boost_1_37_0.

The following code demonstrates the problem; the adjacent vertices to 4
in subG should be 2 and 3. However, I get 5 when I run the program.

Any fixes or suggestions would be greatly appreciated.

#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>

using namespace std;
using namespace boost;

typedef subgraph< adjacency_list<vecS, vecS, undirectedS,
    property<vertex_index_t, int>, property<edge_index_t, int> > > Graph;

int main()
{
    Graph G;

    add_edge(0, 1, G);
    add_edge(1, 2, G);
    add_edge(2, 3, G);
    add_edge(1, 5, G);
    add_edge(5, 6, G);
    add_edge(6, 8, G);
    add_edge(6, 7, G);
    add_edge(7, 8, G);
    
    add_edge(4, 2, G);
    add_edge(4, 3, G);
    add_edge(4, 6, G);

    Graph subG = G.create_subgraph();

    add_vertex(1, subG);
    add_vertex(2, subG);
    add_vertex(3, subG);
    add_vertex(4, subG);
    add_vertex(7, subG);
    add_vertex(8, subG);

    graph_traits<Graph>::adjacency_iterator ai;
    graph_traits<Graph>::adjacency_iterator ai_end;

    cout << "Adjacent vertices of 4 in G: ";
    //Should be (and is): 2 3 6

    for(tie(ai, ai_end) = adjacent_vertices(4, G); ai != ai_end; ++ai)
    {
        cout << *ai << " ";
    }
    cout << endl;

//------------------------------------------------------------------------

    cout << "Adjacent vertices of 4 in subG: ";
    //Should be (is not): 2 3

    for(tie(ai, ai_end) = adjacent_vertices(4, subG); ai != ai_end; ++ai)
    {
        cout << *ai << " ";
    }
    cout << 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