00001 #pragma once
00002
00003 #include <vector>
00004
00005 #include <boost/unordered_map.hpp>
00006 #include <boost/unordered_set.hpp>
00007
00008 #include "Forest.h"
00009
00010 namespace Moses
00011 {
00012 namespace Syntax
00013 {
00014 namespace F2S
00015 {
00016
00017 class TopologicalSorter
00018 {
00019 public:
00020 void Sort(const Forest &, std::vector<const Forest::Vertex *> &);
00021
00022 private:
00023 typedef boost::unordered_set<const Forest::Vertex *> VertexSet;
00024
00025 void BuildPredSets(const Forest &);
00026 void Visit(const Forest::Vertex &, std::vector<const Forest::Vertex *> &);
00027
00028 boost::unordered_set<const Forest::Vertex *> m_visited;
00029 boost::unordered_map<const Forest::Vertex *, VertexSet> m_predSets;
00030 };
00031
00032 }
00033 }
00034 }