J
Jef Driesen
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.
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.