 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Daniel T.
Guest
|
 Posted: Sat Feb 18, 2006 2:06 am Post subject: Help me remove duplication... |
 |
|
The code below is a part of my Graph class. It should compile and run
fine, and if you remove the 'private:' keyword you can even call the
traverse function.
As you can see, the two functions are very much alike (they use the same
algorithm but produce different results,) but I'm having trouble finding
the best way to remove the duplication. Any help would be appreciated,
thanks.
@begin code
template < typename T >
class Graph {
public:
template < typename InIt >
void BFS( T start, InIt result )
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
while ( !Q.empty() ) {
*result++ = Q.front();
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end(); ++it )
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
}
Q.pop_front();
}
}
// other public functions, one of which uses 'traverse' below
private :
struct aux {
T current;
int prev;
aux( T c, int p ): current( c ), prev( p ) { }
};
template < typename InIt >
bool traverse( T start, T target, InIt result )
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
bool found = false;
int p = 0;
*result++ = aux( start, p );
while ( !Q.empty() && !found ) {
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end() && !found; ++it ) {
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
*result++ = aux( *it, p );
if ( *it == target ) found = true;
}
}
Q.pop_front();
++p;
}
return found;
}
typedef std::deque<T> Children;
typedef std::map< T, Children > Tree;
Tree A;
};
@end code
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Thomas Maeder
Guest
|
| Posted: Sat Feb 18, 2006 1:06 pm Post subject: Re: Help me remove duplication... |
|
|
"Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
| Quote: | As you can see, the two functions are very much alike (they use the same
algorithm but produce different results,) but I'm having trouble finding
the best way to remove the duplication. Any help would be appreciated,
thanks.
template < typename T
class Graph {
public:
template < typename InIt
void BFS( T start, InIt result )
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
while ( !Q.empty() ) {
*result++ = Q.front();
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end(); ++it )
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
}
Q.pop_front();
}
}
// other public functions, one of which uses 'traverse' below
private :
struct aux {
T current;
int prev;
aux( T c, int p ): current( c ), prev( p ) { }
};
template < typename InIt
|
This should be called OutIt, shouldn't it?
| Quote: | bool traverse( T start, T target, InIt result )
{
|
Hmm. What should happen of start==target?
| Quote: | std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
bool found = false;
int p = 0;
*result++ = aux( start, p );
while ( !Q.empty() && !found ) {
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end() && !found; ++it ) {
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
*result++ = aux( *it, p );
if ( *it == target ) found = true;
}
}
Q.pop_front();
++p;
}
return found;
}
|
What about
template <typename Predicate>
bool find(T start, Predicate pred)
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
pred(start); // WE SHOULD PROBABLY CHECK THIS RETURN VALUE
while ( !Q.empty() ) {
Children& nodes = A[Q.front()];
typedef typename Children::iterator iterator;
for (iterator it = nodes.begin(); it != nodes.end(); ++it )
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
if (pred(*it))
return true;
}
Q.pop_front();
}
return false;
}
, and to emulate BFS(), pass as Predicate an instance of something
like
template <typename T>
struct False
{
bool operator()(T const &) const
{
return false;
}
};
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Sat Feb 18, 2006 1:06 pm Post subject: Re: Help me remove duplication... |
|
|
"Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
| Quote: | The code below is a part of my Graph class. It should compile and run
fine, and if you remove the 'private:' keyword you can even call the
traverse function.
As you can see, the two functions are very much alike (they use the same
algorithm but produce different results,) but I'm having trouble finding
the best way to remove the duplication. Any help would be appreciated,
thanks.
|
The fastest way to remove all the duplication from your code would be
to use the Boost graph library. Then you can throw out your BFS and
traverse functions, and just keep your graph (if the graph data
structures in Boost don't suit your needs). Boost contains all the
traversal algorithms you need.
http://www.boost.org/libs/graph
HTH,
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Sun Feb 19, 2006 12:06 pm Post subject: Re: Help me remove duplication... |
|
|
In article <upslls6vd.fsf@boost-consulting.com>,
David Abrahams <dave@boost-consulting.com> wrote:
| Quote: | "Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
The code below is a part of my Graph class. It should compile and run
fine, and if you remove the 'private:' keyword you can even call the
traverse function.
As you can see, the two functions are very much alike (they use the same
algorithm but produce different results,) but I'm having trouble finding
the best way to remove the duplication. Any help would be appreciated,
thanks.
The fastest way to remove all the duplication from your code would be
to use the Boost graph library. Then you can throw out your BFS and
traverse functions, and just keep your graph (if the graph data
structures in Boost don't suit your needs). Boost contains all the
traversal algorithms you need.
http://www.boost.org/libs/graph
|
Yes, however if I did that, I wouldn't learn as much. If I just want to
use some algorithm for a larger project, I'm happy to use libraries,
when I'm trying to learn about the algorithms themselves, I need to
write them out myself.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Sun Feb 19, 2006 12:06 pm Post subject: Re: Help me remove duplication... |
|
|
In article <m2k6bths2i.fsf (AT) glue (DOT) ch>, Thomas Maeder <maeder (AT) glue (DOT) ch>
wrote:
| Quote: | "Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
As you can see, the two functions are very much alike (they use the same
algorithm but produce different results,) but I'm having trouble finding
the best way to remove the duplication. Any help would be appreciated,
thanks.
template < typename T
class Graph {
public:
template < typename InIt
void BFS( T start, InIt result )
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
while ( !Q.empty() ) {
*result++ = Q.front();
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end(); ++it )
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
}
Q.pop_front();
}
}
// other public functions, one of which uses 'traverse' below
private :
struct aux {
T current;
int prev;
aux( T c, int p ): current( c ), prev( p ) { }
};
template < typename InIt
This should be called OutIt, shouldn't it?
|
My bad... I keep forgetting, if your putting data in, then it's an
output iterator, taking data out means it's an input iterator... Got it.
| Quote: | bool traverse( T start, T target, InIt result )
{
Hmm. What should happen of start==target?
|
'traverse' is a private function, the caller doesn't let such a thing
happen.
| Quote: | What about
[snipped idea about function taking a function object to do the extra |
work]
Your idea worked great, not as simple as your code made it look, but it
worked. Here is what I ended up with. Any critiques?
@code start
template < typename T >
class Graph {
public:
template < typename OutIt >
void BFS( T start, OutIt result )
{
traverse( start, BFS_helper<OutIt>( result ) );
return;
}
// other public members, one of which calls:
// std::vector<aux> backtrack;
// bool found = traverse( start, minPath_helper( target,
// back_inserter( backtrack ) ) );
private :
struct aux {
T current;
int prev;
aux( T c, int p ): current( c ), prev( p ) { }
};
template < typename OutIt >
struct BFS_helper {
OutIt result;
BFS_helper( OutIt it ): result( it ) { }
void prepare( T start ) { *result++ = start; }
bool inner_loop( T node ) { *result++ = node; return false; }
void outer_loop() { }
};
template < typename OutIt >
struct minPath_helper_t {
int p;
T target;
OutIt result;
minPath_helper_t( T tar, OutIt it ): p( 0 ), target( tar ),
result( it ) { }
void prepare( T start ) {
*result++ = aux( start, p );
}
bool inner_loop( T node ) {
bool found = false;
*result++ = aux( node, p );
if ( node == target ) found = true;
return found;
}
void outer_loop() {
++p;
}
};
template < typename OutIt >
minPath_helper_t<OutIt> minPath_helper( T target, OutIt it ) {
return minPath_helper_t<OutIt>( target, it );
}
template < typename Func >
bool traverse( T start, Func fn )
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
fn.prepare( start );
bool found = false;
while ( !Q.empty() && !found ) {
Children& nodes = A[Q.front()];
for ( typename Children::iterator it = nodes.begin();
it != nodes.end() && !found; ++it ) {
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
found = fn.inner_loop( *it );
}
}
Q.pop_front();
fn.outer_loop();
}
return found;
}
};
@code end
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Sun Feb 19, 2006 12:06 pm Post subject: Re: Help me remove duplication... |
|
|
Thomas Maeder <maeder (AT) glue (DOT) ch> writes:
| Quote: | What about
template <typename Predicate
bool find(T start, Predicate pred)
{
std::deque<T> Q;
Q.push_back( start );
std::map<T, bool> visited;
visited[start] = true;
pred(start); // WE SHOULD PROBABLY CHECK THIS RETURN VALUE
while ( !Q.empty() ) {
Children& nodes = A[Q.front()];
typedef typename Children::iterator iterator;
for (iterator it = nodes.begin(); it != nodes.end(); ++it )
if ( !visited[*it] ) {
Q.push_back( *it );
visited[*it] = true;
if (pred(*it))
return true;
}
Q.pop_front();
}
return false;
}
|
And, thinking about it again, the logical next step would be to evolve
this into an iterator class, allowing you to use Standard Library
alogrithms like std::find().
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Mon Feb 20, 2006 9:06 am Post subject: Re: Help me remove duplication... |
|
|
"Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
| Quote: | In article <upslls6vd.fsf@boost-consulting.com>,
The fastest way to remove all the duplication from your code would be
to use the Boost graph library. Then you can throw out your BFS and
traverse functions, and just keep your graph (if the graph data
structures in Boost don't suit your needs). Boost contains all the
traversal algorithms you need.
http://www.boost.org/libs/graph
Yes, however if I did that, I wouldn't learn as much.
|
Au contraire. The Graph library is an incredibly clever and well
worked-out generic design. In fact, it's probably the most evolved
example of the generic programming ideas established by the STL. You
can learn more by studying it than you can by building less effective
designs yourself.
| Quote: | If I just want to use some algorithm for a larger project, I'm happy
to use libraries, when I'm trying to learn about the algorithms
themselves, I need to write them out myself.
|
I think you'd learn a lot more about the algorithms by getting
yourself a good book that includes some graph theory (like the one
shown here: http://www.boost.org/libs/graph/doc/index.html) and by
playing with the graph library's algorithms interactively using its
Python bindings: http://www.osl.iu.edu/~dgregor/bgl-python/
My 2 cents, now I'm done.
Regards,
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Mon Feb 20, 2006 2:06 pm Post subject: Re: Help me remove duplication... |
|
|
In article <u64nbe3xb.fsf@boost-consulting.com>,
David Abrahams <dave@boost-consulting.com> wrote:
| Quote: | "Daniel T." <postmaster (AT) earthlink (DOT) net> writes:
In article <upslls6vd.fsf@boost-consulting.com>,
The fastest way to remove all the duplication from your code would be
to use the Boost graph library. Then you can throw out your BFS and
traverse functions, and just keep your graph (if the graph data
structures in Boost don't suit your needs). Boost contains all the
traversal algorithms you need.
http://www.boost.org/libs/graph
Yes, however if I did that, I wouldn't learn as much.
Au contraire. The Graph library is an incredibly clever and well
worked-out generic design. In fact, it's probably the most evolved
example of the generic programming ideas established by the STL. You
can learn more by studying it than you can by building less effective
designs yourself.
|
Thanks for the help David. Personally I think I can learn the most by
doing all of the above: studying other's designs, reading good books
*and* trying to develop good designs myself (and having them critiqued
when I can.)
I didn't mean to make it sound like I do any one of the above at the
expense of all the others.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
