I'm working on an image segmentation algorithm. An essential part of the

algorithm is a graph to keep track of the connectivity between regions.

At the moment I have a working implementation, but it's not flexible

enough anymore and I need something more advanced. I already have a data

structure in mind, but I don't know how to implement that nicely in C++.

// Main class which holds the lists with

// edges and vertices. These lists are

// "normal" lists. (read further)

class graph {

// Edge list

edge_list edges;

// Vertex list

vertex_list vertices;

};

// Class which maintains a link between two

// vertices (neighboring regions of pixels

// in my application).

class edge {

// Source and target vertices.

vertex *source, *target;

};

// Class which represent a single region of

// pixels in my application. Each region has

// a list of incoming and outgoing edges.

// (For my application both lists contains the same

// elements but with source and target swapped.)

// Those lists are special because they consists

// of a subset of the elements of the edge list

// of the graph.

class vertex {

// Adjacency in list

// (Where for each element in the list,

// the source can be any other vertex and

// the target is always this vertex)

adj_in_list in_edges;

// Adjacency out list

// (Where for each element in the list,

// the source is always this vertex and

// the target can be any other vertex)

adj_out_list out_edges;

};

To implement this, i was thinking of using 4 kins of custom lists

(vertex_list, edge_list, adj_in_list, adj_out_list) which share the same

type of node (one for a vertex and for an edge) and differ only in the

way they are traversed.

struct vertex_node {

// Vertex data

vertex v;

// Successor and predecessor nodes (vertex list)

vertex_node *next, *prev;

};

struct edge_node {

// Edge data

edge e;

// Successor and predecessor nodes (adjacency in list)

edge_node *in_edges_next, *in_edges_prev;

// Successor and predecessor nodes (adjacency out list)

edge_node *out_edges_next , *out_edges_prev ;

// Successor and predecessor nodes (edge list)

edge_node *next, *prev;

};

Is this a workable implementation or will I encounter some problems

which I'm unaware of at the moment. One problem I don't know how to

solve is the constructors of the vertex and edge classes because they

have to know to which graph it belongs. (An edge between vertices of two

different graphs is an error and a vertex can only have edge which are

part of the same graph.) And I also don't see how I should implement the

copy constructor too.

All suggestions are welcome.