Adjacency list representation

[Jef Driesen]

I need some help to implement the adjacency list representation of a
(undirected) graph. The data structure I need is something like the
picture on the website http://www.pagebox.net/graph.html#toc3.

Basically, I want the vertices in the graph to represent regions of
pixels in a 2D image. And the edges denotes adjacent regions. I need
this data structure to implement a region merging segmentation
algorithm. The graph will be constructed from 'scanning' an image where
a pixel value is the region label.

Each region should have some basic properties:

class region {
std::size_t m_label; // Unique label
std::list<point> m_pixels; // Pixel coordinates (x,y)
};

But every variant of the segmentation algorithms will need some
additional (statistical) properties. These parameters are calculated
from the corresponding pixels inside the region and one (or two) other
images (not the one with the labels).

class region_a : public region {
... // Properties for regions of type a
};
class region_b : public region {
... // Properties for regions of type b
};

The actual properties are not important and are only used for comparing
two regions (and of course in the construction phase). So I can add this
functionallity in the base class as a virtual function, and override it
in the derived classes.

The basic structure should have the same functionality for all types of
regions, like accessing adjacent regions, merging two small regions in a
new larger region, ... And this is where I'm having trouble. I tried
some different implementations (see below) but they don't offer the
flexibility I want. The problem is often the m_neighbors member. Any
suggestions are welcome.

// METHOD 1:

template <class R>
class region {
public:
std::size_t m_label;
std::list<point> m_pixels;
std::list<region*> m_neighbors;
};
template <class R>
class rag {
public:
std::vector<R*> m_regions;
};

class region_a : public region<region_a> {
...
};
class rag_a : public rag<region_a> {
...
};

METHOD 2:

template <typename P>
class rag {
public:
class region {
public:
std::size_t m_label;
std::list<point> m_pixels;
std::list<region*> m_neighbors;
P m_property;
};
std::vector<region*> m_regions;
};