-
c++ design question?
i am trying to implement a topological-sort algorithm, trying to reuse
an existing depth-first-search algorithm. My algorithms are
encapsulated in classes, something like this:
struct depth_first_search {
depth_first_search( const graph& g );
void run( node p_start_node ); // init and call visit()
protected:
void visit( node p ); // recursively called
};
struct topological_sort {
topological_sort( const graph& g );
void run( node p_start_node );
};
A topological sort (ts) uses a depth-first-search (dfs) algorithm and
inserts a node into a linked list after a node has been visited.
Basically, my question is, how should I design this? I want to
maximize code reuse and don't want to re-write the dfs algorithm
inside ts.
My candadate solutions are as follows:
Solution 1. Inheritance would seem like a logical choice: basically
override the visit method (must make visit virtual). But still that
means rewriting a lot of intricate code from the dfs visit method.
Solution 2. Redesign dfs to be very generic and accept a functor
object with a well-defined interface of methods that are called at
some specific locations in the algorithm, for example:
struct dfs_functions {
virtual void pre_visit( node p ) {};
virtual void post_visit( node p ) {};
...
};
struct depth_first_search {
depth_first_search( const graph& g, dfs_functions& f );
...
void visit( node p ) {
f.pre_visit(p);
...
f.post_visit(p);
}
};
Problem here is complexity of the ts specific derived class of
dfs_functions, in that it would need to keep state of the linked list,
etc. Also, many other dfs_functions are called but do nothing
impacting performance.
Solution 3: Utilize a template method (design pattern) redesign of dfs
class:
struct depth_first_search {
depth_first_search( const graph& g );
virtual void pre_visit( node p ) {};
virtual void post_visit( node p ) {};
...
};
struct topological_sort : public depth_first_search {
...
virtual void post_visit( node p ) { ... }
};
This is similar to solution 2.
Solution 4: ?
I'm interested to hear comments about the advantages/disadvantages to
these solutions, or other solutions to this problem.
-
-
Ummm...post the code. I'm not sure if I fully understand the context of the problem.
-
