Skip to content

Instantly share code, notes, and snippets.

@codemonkey-uk
Last active January 2, 2016 03:19
Show Gist options
  • Save codemonkey-uk/8243202 to your computer and use it in GitHub Desktop.
Save codemonkey-uk/8243202 to your computer and use it in GitHub Desktop.
Provide self contained function template implementing the Breadth First Search algorithm.Does not depend on STL, or any other library code. Circa 2003.
// -------------------------------------------------------------------------
// bfs.h
// Version: 1.1
// Date: 2003/04/14
// Purpose: Provide template for Breadth First Search algorithm
// Note: Self contained, does not depend on STL, or any other library code
// (c) T.Frogley 2003-2015
// -------------------------------------------------------------------------
#ifndef TFROGLEY_BFS_H_2003
#define TFROGLEY_BFS_H_2003
namespace bfs {
// helper type(s), do not overload, specialise etc
namespace helper{
template<typename T>
struct node_link {
node_link( const T& node, node_link<T>* parent=0 )
: m_node(node)
, m_parent(parent)
, m_next(0)
, m_last(0)
{ }
T m_node;
node_link<T>* const m_parent;
node_link<T>* m_next;
node_link<T>* m_last;
};
}
// function template, bfs
// Does a Breadth First Search from 'a' until it finds 'b'
// If a path/route is found, returns true and
// Outputs into 'results' full path, including end nodes
// Else, returns false.
// NodeType requirements:
// * NodeType must appear to be a Container of NodeTypes, that is:
// -> Must have a "iterator" type, and have begin() and end()
// -> Assignable (Copy Constructible)
// * Comparison operators: == and !=
template<typename NodeType, typename OutputIterator>
bool bfs(const NodeType a, const NodeType b, OutputIterator results)
{
bool found_route = false;
typedef bfs::helper::node_link<NodeType> node;
typedef typename NodeType::iterator NodeItr;
node * head = new node(a);
node * tail = head;
node * current = head;
while(current && current->m_node != b){
//add child nodes to graph
const NodeItr end = current->m_node.end();
for(NodeItr i = current->m_node.begin();i!=end;++i){
//check for circular paths
node * search_back = tail;
do{
if (search_back->m_node == *i){
//already visited this node
break;
}
//search_back = search_back->m_parent;
search_back = search_back->m_last;
}while(search_back);
if (!search_back){
tail->m_next = new node(*i,current);
tail->m_next->m_last = tail;
tail = tail->m_next;
}
}
//move to next node
current = current->m_next;
}
//found a route!
if (current){
found_route = true;
//work back up route
do{
//results.push_front( current->m_node );
*results++ = current->m_node;
current = current->m_parent;
}while(current);
}
//clean up memory
do{
current = head->m_next;
delete head;
head = current;
}while(head);
return found_route;
}
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment