[Boost-users] [graph] non-contiguous edges?

From: Roman Schindlauer (roman_at_[hidden])
Date: 2006-01-28 04:52:49

Hello,

Warning ahead - this is a newbie question. I need to find weak and
strong components of a graph. So far, my code is as simple as it could
be (edges being a std::vector of std::pair<unsigned,unsigned>):

  typedef adjacency_list <vecS, vecS, undirectedS> Graph;
  Graph G;
  for (Edges::const_iterator ei = edges.begin(); ei != edges.end();++ei)
      add_edge((*ei).first, (*ei).second, G);
  std::vector<int> component(num_vertices(G));
  int num = connected_components(G, &component[0]);

However, my vertices are not contiguously numbered. Hence, the following edges

  (8, 9)
  (9, 10)
  (12, 13)

result in these connected components:

  0: 0
  1: 1
  2: 2
  3: 3
  4: 4
  5: 5
  6: 6
  7: 7
  8: 8, 9, 10
  9: 11
  10: 12, 13

which is not what I want (just two wcc: 8, 9, 10 and 12, 13). I was
reading into the property_map stuff, but as far as i understand, that
would not help here. Do I have to remap the indices beforehand or is
there a way to convince Boost that there are no other nodes than those
in the edges?

Best regards,
Roman