[Boost-users] BGL: Very dense adjacency_matrix

Subject: [Boost-users] BGL: Very dense adjacency_matrix
From: Mathieu Malaterre (mathieu.malaterre_at_[hidden])
Date: 2009-09-17 12:13:06

Hi there,

  Has anyone worked on very dense graph ? Basically the relation is
implicitly given by the position in the grid:

Eg, consider the following structured grid

  A B C
  D E F
  G H I

it would lead to the following (undirected) graph:

  Graph g(9);
  add_edge(A, B, g);
  add_edge(A, D, g);
  add_edge(B, C, g);
  add_edge(B, E, g);
  add_edge(C, F, g);
  add_edge(D, E, g);
  add_edge(D, G, g);
  add_edge(E, F, g);
  add_edge(E, H, g);
  add_edge(F, I, g);
  add_edge(G, H, g);
  add_edge(H, I, g);

When the structured grid is full (no broken link) I would think there
are better data structure (ie. no data at all) suited to represent the
graph. And as we break link (say, edge(A,B)), we would use an opposite
definition of adjacency_list, to list what edge is actually *missing*.

 As far as I know adjacency_matrix is not implemented in PBGL, so I'll
need to work around that issue /real time soon/.

Thanks for your help,
-- 
Mathieu