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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/***********************************************************************
Moses - statistical machine translation system
Copyright (C) 2006-2011 University of Edinburgh
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
***********************************************************************/
#include "Subgraph.h"
#include "Node.h"
namespace Moses {
namespace GHKM {
void Subgraph::GetTargetLeaves(std::vector<const Node *> &result) const
{
result.clear();
GetTargetLeaves(m_root, result);
}
void Subgraph::GetTargetLeaves(const Node *root,
std::vector<const Node *> &result) const
{
if (root->GetType() == TARGET || m_leaves.find(root) != m_leaves.end()) {
result.push_back(root);
} else {
const std::vector<Node*> &children = root->GetChildren();
for (std::vector<Node *>::const_iterator p(children.begin());
p != children.end(); ++p) {
GetTargetLeaves(*p, result);
}
}
}
int Subgraph::CountNodes(const Node *n) const
{
if (n->GetType() != TREE) {
return 0;
}
if (IsTrivial()) {
return 1;
}
int count = 1;
const std::vector<Node*> &children = n->GetChildren();
for (std::vector<Node *>::const_iterator p = children.begin();
p != children.end(); ++p) {
const Node *child = *p;
if (m_leaves.find(child) == m_leaves.end()) {
count += CountNodes(child);
} else if (child->GetType() == TREE) {
++count;
}
}
return count;
}
int Subgraph::CalcSize(const Node *n) const
{
if (n->GetType() != TREE || n->IsPreterminal()) {
return 0;
}
if (IsTrivial()) {
return 1;
}
int count = 1;
const std::vector<Node*> &children = n->GetChildren();
for (std::vector<Node *>::const_iterator p = children.begin();
p != children.end(); ++p) {
if (m_leaves.find(*p) == m_leaves.end()) {
count += CalcSize(*p);
}
}
return count;
}
int Subgraph::CalcDepth(const Node *n) const
{
if (n->GetType() != TREE || n->IsPreterminal() || m_leaves.empty()) {
return 0;
}
int maxChildDepth = 0;
const std::vector<Node*> &children = n->GetChildren();
for (std::vector<Node *>::const_iterator p = children.begin();
p != children.end(); ++p) {
if (m_leaves.find(*p) == m_leaves.end()) {
maxChildDepth = std::max(maxChildDepth, CalcDepth(*p));
}
}
return maxChildDepth + 1;
}
} // namespace Moses
} // namespace GHKM
|
