Repository: incubator-singa Updated Branches: refs/heads/master cce3aebef -> ea7cfea49
SINGA-28 Fix a bug from toplogy sort of Graph There is a bug in the Sort function of graph.cc, which would push one node into the 'tmp' queue for multiple times if this node has multiple source nodes. Solution: use an unordered_set to store all nodes in the queue; push a node only when it is not in the 'tmp' queue. Project: http://git-wip-us.apache.org/repos/asf/incubator-singa/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-singa/commit/ea7cfea4 Tree: http://git-wip-us.apache.org/repos/asf/incubator-singa/tree/ea7cfea4 Diff: http://git-wip-us.apache.org/repos/asf/incubator-singa/diff/ea7cfea4 Branch: refs/heads/master Commit: ea7cfea499e9bb4cb025a73bfecfb4e194544442 Parents: cce3aeb Author: wang wei <[email protected]> Authored: Mon Jul 6 20:55:14 2015 +0800 Committer: wang wei <[email protected]> Committed: Mon Jul 6 20:55:14 2015 +0800 ---------------------------------------------------------------------- src/utils/graph.cc | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-singa/blob/ea7cfea4/src/utils/graph.cc ---------------------------------------------------------------------- diff --git a/src/utils/graph.cc b/src/utils/graph.cc index 6fff83b..b1f5b9f 100644 --- a/src/utils/graph.cc +++ b/src/utils/graph.cc @@ -1,5 +1,6 @@ #include <algorithm> #include <queue> +#include <unordered_set> #include "utils/graph.h" const string Graph::ToString() const { @@ -89,8 +90,10 @@ void Graph::Sort() { visited[node->name()]=false; } int n=nodes_.size(); + std::unordered_set<SNode> pushed; std::queue<SNode> tmp; tmp.push(start); + pushed.insert(start); nodes_.clear(); while(!tmp.empty()){ auto node=tmp.front(); @@ -105,12 +108,13 @@ void Graph::Sort() { nodes_.push_back(node); visited[node->name()]=true; for(auto dst: node->dstnodes()){ - CHECK(visited.find(dst->name())!=visited.end())<<dst->name(); - if(visited[dst->name()]==false){ + if(pushed.find(dst) == pushed.end()){ tmp.push(dst); + pushed.insert(dst); } } - } + }else + tmp.push(node); } CHECK_EQ(nodes_.size(), n); }
