File size: 1,680 Bytes
fd49381 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include "TopologicalSorter.h"
namespace MosesTraining
{
namespace Syntax
{
namespace PostprocessEgretForests
{
void TopologicalSorter::Sort(const Forest &forest,
std::vector<const Forest::Vertex *> &permutation)
{
permutation.clear();
BuildPredSets(forest);
m_visited.clear();
for (std::vector<boost::shared_ptr<Forest::Vertex> >::const_iterator
p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
if (m_visited.find(p->get()) == m_visited.end()) {
Visit(**p, permutation);
}
}
}
void TopologicalSorter::BuildPredSets(const Forest &forest)
{
m_predSets.clear();
for (std::vector<boost::shared_ptr<Forest::Vertex> >::const_iterator
p = forest.vertices.begin(); p != forest.vertices.end(); ++p) {
const Forest::Vertex &head = **p;
for (std::vector<boost::shared_ptr<Forest::Hyperedge> >::const_iterator
q = head.incoming.begin(); q != head.incoming.end(); ++q) {
const Forest::Hyperedge &e = **q;
for (std::vector<Forest::Vertex *>::const_iterator
r = e.tail.begin(); r != e.tail.end(); ++r) {
m_predSets[&head].insert(*r);
}
}
}
}
void TopologicalSorter::Visit(const Forest::Vertex &v,
std::vector<const Forest::Vertex *> &permutation)
{
m_visited.insert(&v);
const VertexSet &predSet = m_predSets[&v];
for (VertexSet::const_iterator p = predSet.begin(); p != predSet.end(); ++p) {
if (m_visited.find(*p) == m_visited.end()) {
Visit(**p, permutation);
}
}
permutation.push_back(&v);
}
} // namespace PostprocessEgretForests
} // namespace Syntax
} // namespace MosesTraining
|