Blame view

morfeusz/InflexionGraph.cpp 7.73 KB
Michał Lenart authored
1
Michał Lenart authored
2
#include <string>
Michał Lenart authored
3
#include <cassert>
Michał Lenart authored
4
#include <climits>
Michał Lenart authored
5
#include <vector>
Michał Lenart authored
6
#include <iostream>
Michał Lenart authored
7
#include "utils.hpp"
Michał Lenart authored
8
#include "InflexionGraph.hpp"
Michał Lenart authored
9
Michał Lenart authored
10
11
using namespace std;
Michał Lenart authored
12
13
namespace morfeusz {
Michał Lenart authored
14
void InflexionGraph::addStartEdge(const Edge& e) {
Michał Lenart authored
15
    if (this->graph.empty()) {
Michał Lenart authored
16
        assert(this->node2ChunkStartPtr.empty());
Michał Lenart authored
17
        this->graph.push_back(vector<Edge>());
Michał Lenart authored
18
        this->node2ChunkStartPtr.push_back(e.chunk.textStartPtr);
Michał Lenart authored
19
    }
Michał Lenart authored
20
    assert(this->node2ChunkStartPtr[0] == e.chunk.textStartPtr);
Michał Lenart authored
21
22
    this->graph[0].push_back(e);
}
Michał Lenart authored
23
Michał Lenart authored
24
void InflexionGraph::addMiddleEdge(unsigned int startNode, const Edge& e) {
Michał Lenart authored
25
26
27
28
    assert(startNode < e.nextNode);
    assert(startNode == this->graph.size());
    if (startNode == this->graph.size()) {
        this->graph.push_back(vector<Edge>());
Michał Lenart authored
29
        this->node2ChunkStartPtr.push_back(e.chunk.textStartPtr);
Michał Lenart authored
30
31
    }
    this->graph[startNode].push_back(e);
Michał Lenart authored
32
33
}
Michał Lenart authored
34
static inline bool chunkIsAtFront(
Michał Lenart authored
35
        const InterpretedChunk& chunk,
Michał Lenart authored
36
37
38
39
40
41
42
43
44
        const std::vector<InterpretedChunk>& path) {
    unsigned int i;
    for (i = 0; i < path.size() - 1 && path[i].orthWasShifted; i++) {
    }
    assert(!path[i].orthWasShifted);
    return &chunk == &(path[i]);
}

static inline bool chunkIsAtBack(
Michał Lenart authored
45
        const InterpretedChunk& chunk,
Michał Lenart authored
46
47
48
49
50
        const std::vector<InterpretedChunk>& path) {
    return &chunk == &(path.back());
}

static inline bool chunkIsTheOnlyOne(
Michał Lenart authored
51
        const InterpretedChunk& chunk,
Michał Lenart authored
52
53
54
55
        const std::vector<InterpretedChunk>& path) {
    return chunkIsAtFront(chunk, path) && chunkIsAtBack(chunk, path);
}
Michał Lenart authored
56
void InflexionGraph::addPath(const std::vector<InterpretedChunk>& path, bool weak) {
Michał Lenart authored
57
Michał Lenart authored
58
59
60
61
    if (weak && !this->empty() && !this->onlyWeakPaths) {
        return;
    }
    else if (this->onlyWeakPaths && !weak) {
Michał Lenart authored
62
63
        this->graph.resize(0);
        this->node2ChunkStartPtr.resize(0);
Michał Lenart authored
64
65
        this->onlyWeakPaths = false;
    }
Michał Lenart authored
66
67
    for (unsigned int i = 0; i < path.size(); i++) {
        const InterpretedChunk& chunk = path[i];
Michał Lenart authored
68
        if (!chunk.orthWasShifted) {
Michał Lenart authored
69
            if (chunkIsTheOnlyOne(chunk, path)) {
Michał Lenart authored
70
71
                Edge e = {chunk, UINT_MAX};
                this->addStartEdge(e);
Michał Lenart authored
72
            }
Michał Lenart authored
73
            else if (chunkIsAtFront(chunk, path)) {
Michał Lenart authored
74
75
                Edge e = {chunk, this->graph.empty() ? 1 : (unsigned int) this->graph.size()};
                this->addStartEdge(e);
Michał Lenart authored
76
            }
Michał Lenart authored
77
            else if (chunkIsAtBack(chunk, path)) {
Michał Lenart authored
78
79
                Edge e = {chunk, UINT_MAX};
                this->addMiddleEdge((unsigned int) this->graph.size(), e);
Michał Lenart authored
80
81
            }
            else {
Michał Lenart authored
82
                Edge e = {chunk, (unsigned int) this->graph.size() + 1};
Michał Lenart authored
83
84
                this->addMiddleEdge((unsigned int) this->graph.size(), e);
            }
Michał Lenart authored
85
86
87
88
        }
    }
}
Michał Lenart authored
89
bool InflexionGraph::canMergeNodes(unsigned int node1, unsigned int node2) {
Michał Lenart authored
90
    return this->node2ChunkStartPtr[node1] == this->node2ChunkStartPtr[node2]
Michał Lenart authored
91
92
93
            && this->getPossiblePaths(node1) == this->getPossiblePaths(node2);
}
Michał Lenart authored
94
set<InflexionGraph::Path> InflexionGraph::getPossiblePaths(unsigned int node) {
Michał Lenart authored
95
    if (node == UINT_MAX || node == this->graph.size() - 1) {
Michał Lenart authored
96
        return set<InflexionGraph::Path>();
Michał Lenart authored
97
98
    }
    else {
Michał Lenart authored
99
        set<InflexionGraph::Path> res;
Michał Lenart authored
100
101
102
        vector<Edge>& edges = this->graph.at(node);
        for (unsigned int i = 0; i < edges.size(); i++) {
            Edge& e = edges[i];
Michał Lenart authored
103
            InflexionGraph::PathElement pathElem(e.chunk.textStartPtr, e.chunk.segmentType);
Michał Lenart authored
104
105
106
107
108
109
110
111
            if (e.nextNode != this->graph.size()) {
                set<Path> possiblePaths = this->getPossiblePaths(e.nextNode);
                vector<Path> nextPaths(possiblePaths.begin(), possiblePaths.end());
                vector<Path>::iterator it;
                for (it = nextPaths.begin(); it != nextPaths.end(); ++it) {
                    (*it).insert(pathElem);
                }
                res.insert(nextPaths.begin(), nextPaths.end());
Michał Lenart authored
112
113
114
115
116
117
            }
        }
        return res;
    }
}
Michał Lenart authored
118
static bool containsEqualEdge(const vector<InflexionGraph::Edge>& edges, const InflexionGraph::Edge& e) {
Michał Lenart authored
119
    for (unsigned int i = 0; i < edges.size(); i++) {
Michał Lenart authored
120
        const InflexionGraph::Edge& e1 = edges[i];
Michał Lenart authored
121
        if (e1.chunk.textStartPtr == e.chunk.textStartPtr
Michał Lenart authored
122
123
                && e1.chunk.textStartPtr == e.chunk.textStartPtr
                && e1.chunk.textEndPtr == e.chunk.textEndPtr
Michał Lenart authored
124
                && e1.chunk.segmentType == e.chunk.segmentType
Michał Lenart authored
125
126
127
128
129
                && e1.nextNode == e.nextNode) {
            return true;
        }
    }
    return false;
Michał Lenart authored
130
131
}
Michał Lenart authored
132
void InflexionGraph::redirectEdges(unsigned int fromNode, unsigned int toNode) {
Michał Lenart authored
133
134
    for (unsigned int node = 0; node < fromNode; node++) {
        vector<Edge>& edges = this->graph[node];
Michał Lenart authored
135
        vector<Edge>::iterator edgesIt = edges.begin();
Michał Lenart authored
136
        while (edgesIt != edges.end()) {
Michał Lenart authored
137
138
139
            Edge& oldEdge = *edgesIt;
            if (oldEdge.nextNode == fromNode) {
                Edge newEdge = {oldEdge.chunk, toNode};
Michał Lenart authored
140
                if (!containsEqualEdge(edges, newEdge)) {
Michał Lenart authored
141
142
143
                    // if newEdge is not in edges, redirect edgeEdge
                    // so it becomes newEdge
                    oldEdge.nextNode = toNode;
Michał Lenart authored
144
145
                }
                else {
Michał Lenart authored
146
147
                    // if newEdge is already there, just remove old edge
                    edges.erase(edgesIt);
Michał Lenart authored
148
                }
Michał Lenart authored
149
150
            }
            else {
Michał Lenart authored
151
                ++edgesIt;
Michał Lenart authored
152
            }
Michał Lenart authored
153
154
155
        }
    }
}
Michał Lenart authored
156
Michał Lenart authored
157
void InflexionGraph::doRemoveNode(unsigned int node) {
Michał Lenart authored
158
159
160
    for (unsigned int i = node + 1; i < this->graph.size(); i++) {
        redirectEdges(i, i - 1);
        this->graph[i - 1] = this->graph[i];
Michał Lenart authored
161
        this->node2ChunkStartPtr[i - 1] = this->node2ChunkStartPtr[i];
Michał Lenart authored
162
163
    }
    this->graph.pop_back();
Michał Lenart authored
164
    this->node2ChunkStartPtr.pop_back();
Michał Lenart authored
165
166
}
Michał Lenart authored
167
void InflexionGraph::doMergeNodes(unsigned int node1, unsigned int node2) {
Michał Lenart authored
168
169
    if (node1 > node2) {
        doMergeNodes(node2, node1);
Michał Lenart authored
170
171
    }
    else {
Michał Lenart authored
172
        // node1 < node2
Michał Lenart authored
173
174
        for (unsigned int i = 0; i < this->graph[node2].size(); i++) {
            Edge& e = this->graph[node2][i];
Michał Lenart authored
175
176
177
178
            if (!containsEqualEdge(graph[node1], e)) {
                this->graph[node1].push_back(e);
            }
        }
Michał Lenart authored
179
180
        //        DEBUG("1");
        //        debugGraph(this->graph);
Michał Lenart authored
181
        this->redirectEdges(node2, node1);
Michał Lenart authored
182
183
        //        DEBUG("2");
        //        debugGraph(this->graph);
Michał Lenart authored
184
        this->doRemoveNode(node2);
Michał Lenart authored
185
186
        //        DEBUG("3");
        //        debugGraph(this->graph);
Michał Lenart authored
187
188
189
    }
}
Michał Lenart authored
190
bool InflexionGraph::tryToMergeTwoNodes() {
Michał Lenart authored
191
    for (unsigned int node1 = 0; node1 < this->graph.size(); node1++) {
Michał Lenart authored
192
        for (unsigned int node2 = (unsigned int) this->graph.size() - 1; node2 > node1; node2--) {
Michał Lenart authored
193
194
195
196
197
198
199
200
201
            if (this->canMergeNodes(node1, node2)) {
                this->doMergeNodes(node1, node2);
                return true;
            }
        }
    }
    return false;
}
Michał Lenart authored
202
void InflexionGraph::minimizeGraph() {
Michał Lenart authored
203
    if (this->graph.size() > 2) {
Michał Lenart authored
204
        //        debugGraph(this->graph);
Michał Lenart authored
205
        while (this->tryToMergeTwoNodes()) {
Michał Lenart authored
206
            //            debugGraph(this->graph);
Michał Lenart authored
207
208
209
210
        }
    }
}
Michał Lenart authored
211
bool InflexionGraph::empty() const {
Michał Lenart authored
212
213
    return this->graph.empty();
}
Michał Lenart authored
214
Michał Lenart authored
215
void InflexionGraph::repairLastNodeNumbers() {
Michał Lenart authored
216
217
218
219
    for (unsigned int i = 0; i < this->graph.size(); i++) {
        vector<Edge>& edges = this->graph[i];
        for (unsigned int j = 0; j < edges.size(); j++) {
            Edge& e = edges[j];
Michał Lenart authored
220
            if (e.nextNode == UINT_MAX) {
Michał Lenart authored
221
                e.nextNode = (unsigned int) this->graph.size();
Michał Lenart authored
222
223
224
225
            }
        }
    }
}
Michał Lenart authored
226
Michał Lenart authored
227
228
229
230
231
232
const vector< vector<InflexionGraph::Edge> >& InflexionGraph::getTheGraph() {
    minimizeGraph();
    repairLastNodeNumbers();
    return this->graph;
}
Michał Lenart authored
233
void InflexionGraph::clear() {
Michał Lenart authored
234
235
    graph.resize(0);
    node2ChunkStartPtr.resize(0);
Michał Lenart authored
236
    onlyWeakPaths = true;
Michał Lenart authored
237
}
Michał Lenart authored
238
239

}