c++ design question?

[l3aDmOnKeY]

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.

[l3aDmOnKeY]

O well *sigh*

[smirc]

Ummm...post the code. I'm not sure if I fully understand the context of the problem.

[l3aDmOnKeY]

Thread Closed

I found a site that helped.
http://www.boost.org/libs/graph/doc/..._contents.html