00001 #include "TopologicalSorter.h"
00002
00003 namespace MosesTraining
00004 {
00005 namespace Syntax
00006 {
00007 namespace PostprocessEgretForests
00008 {
00009
00010 void TopologicalSorter::Sort(const Forest &forest,
00011 std::vector<const Forest::Vertex *> &permutation)
00012 {
00013 permutation.clear();
00014 BuildPredSets(forest);
00015 m_visited.clear();
00016 for (std::vector<boost::shared_ptr<Forest::Vertex> >::const_iterator
00017 p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
00018 if (m_visited.find(p->get()) == m_visited.end()) {
00019 Visit(**p, permutation);
00020 }
00021 }
00022 }
00023
00024 void TopologicalSorter::BuildPredSets(const Forest &forest)
00025 {
00026 m_predSets.clear();
00027 for (std::vector<boost::shared_ptr<Forest::Vertex> >::const_iterator
00028 p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
00029 const Forest::Vertex &head = **p;
00030 for (std::vector<boost::shared_ptr<Forest::Hyperedge> >::const_iterator
00031 q = head.incoming.begin(); q != head.incoming.end(); ++q) {
00032 const Forest::Hyperedge &e = **q;
00033 for (std::vector<Forest::Vertex *>::const_iterator
00034 r = e.tail.begin(); r != e.tail.end(); ++r) {
00035 m_predSets[&head].insert(*r);
00036 }
00037 }
00038 }
00039 }
00040
00041 void TopologicalSorter::Visit(const Forest::Vertex &v,
00042 std::vector<const Forest::Vertex *> &permutation)
00043 {
00044 m_visited.insert(&v);
00045 const VertexSet &predSet = m_predSets[&v];
00046 for (VertexSet::const_iterator p = predSet.begin(); p != predSet.end(); ++p) {
00047 if (m_visited.find(*p) == m_visited.end()) {
00048 Visit(**p, permutation);
00049 }
00050 }
00051 permutation.push_back(&v);
00052 }
00053
00054 }
00055 }
00056 }