From e2cf2ab253d32147e079a817f692f5c87b635c7e Mon Sep 17 00:00:00 2001 From: Jonas Suhr Christensen Date: Thu, 3 May 2012 17:14:23 +0200 Subject: Added breadth first search tour --- src/tasktree.cc | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'src/tasktree.cc') diff --git a/src/tasktree.cc b/src/tasktree.cc index 3a72046..0a9ad46 100644 --- a/src/tasktree.cc +++ b/src/tasktree.cc @@ -177,6 +177,35 @@ task_t TaskTree::getData(taskid_t id) return t; } +// bfs search from id in tree +TaskIdList TaskTree::bfs(taskid_t id) + throw (std::exception) { + + TaskIdList lst; + lst.push_back(id); + + std::list queue; + node_t* current = id2node.at(id); + while(true) { + NodeList children = current->children; + for(NodeList::iterator it = children.begin(); it != children.end(); it++) { + node_t* child = *it; + queue.push_back(child); + lst.push_back(child->id); + } + + if(!queue.empty()) { + current = queue.front(); + queue.pop_front(); + } + else { + break; + } + } + + return lst; +} + TaskIdList TaskTree::ancestorList(taskid_t id) throw (std::exception) { -- cgit v1.2.3