00001 #include "TopologicalSorter.h"
00002
00003 namespace Moses
00004 {
00005 namespace Syntax
00006 {
00007 namespace F2S
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<Forest::Vertex *>::const_iterator
00017 p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
00018 if (m_visited.find(*p) == 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<Forest::Vertex *>::const_iterator
00028 p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
00029 const Forest::Vertex *head = *p;
00030 for (std::vector<Forest::Hyperedge *>::const_iterator
00031 q = head->incoming.begin(); q != head->incoming.end(); ++q) {
00032 for (std::vector<Forest::Vertex *>::const_iterator
00033 r = (*q)->tail.begin(); r != (*q)->tail.end(); ++r) {
00034 m_predSets[head].insert(*r);
00035 }
00036 }
00037 }
00038 }
00039
00040 void TopologicalSorter::Visit(const Forest::Vertex &v,
00041 std::vector<const Forest::Vertex *> &permutation)
00042 {
00043 m_visited.insert(&v);
00044 const VertexSet &predSet = m_predSets[&v];
00045 for (VertexSet::const_iterator p = predSet.begin(); p != predSet.end(); ++p) {
00046 if (m_visited.find(*p) == m_visited.end()) {
00047 Visit(**p, permutation);
00048 }
00049 }
00050 permutation.push_back(&v);
00051 }
00052
00053 }
00054 }
00055 }