c++ design question?
Results 1 to 4 of 4

Thread: c++ design question?

  1. #1
    Senior Member
    Join Date
    Sep 2001
    Posts
    193

    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.
    [shadow]l3aDmOnKeY[/shadow]

  2. #2
    Senior Member
    Join Date
    Sep 2001
    Posts
    193
    O well *sigh*
    [shadow]l3aDmOnKeY[/shadow]

  3. #3
    Senior Member
    Join Date
    Oct 2001
    Posts
    638
    Ummm...post the code. I'm not sure if I fully understand the context of the problem.
    OpenBSD - The proactively secure operating system.

  4. #4
    Senior Member
    Join Date
    Sep 2001
    Posts
    193
    Thread Closed

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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •