diff options
Diffstat (limited to 'runtimes/neurun/src/graph/verifier/Verifier.cc')
-rw-r--r-- | runtimes/neurun/src/graph/verifier/Verifier.cc | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/runtimes/neurun/src/graph/verifier/Verifier.cc b/runtimes/neurun/src/graph/verifier/Verifier.cc new file mode 100644 index 000000000..a5b53af85 --- /dev/null +++ b/runtimes/neurun/src/graph/verifier/Verifier.cc @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Verifier.h" + +#include "graph/Graph.h" + +#include "util/logging.h" + +namespace neurun +{ +namespace graph +{ +namespace verifier +{ + +// +// DAGChecker +// + +bool DAGChecker::verify(const Graph &graph) const +{ + auto &operations = graph.operations(); + bool cyclic = false; + + std::unordered_map<model::operation::Index, bool> visited; + operations.iterate([&](const model::operation::Index &index, const model::operation::Node &) { + visited[index] = false; + }); + std::unordered_map<model::operation::Index, bool> on_stack = visited; // Copy from visited + + std::function<void(const model::operation::Index &index, const model::operation::Node &)> + dfs_recursive = + [&](const model::operation::Index &index, const model::operation::Node &node) -> void { + if (on_stack[index]) + cyclic = true; + if (visited[index]) + return; + visited[index] = true; + on_stack[index] = true; + + for (auto output : node.getOutputs()) + { + const auto &operand = graph.operands().at(output); + for (const auto &use : operand.getUses().list()) + { + dfs_recursive(use, graph.operations().at(use)); + } + } + + on_stack[index] = false; + }; + + operations.iterate(dfs_recursive); + + return !cyclic; +} + +// +// EdgeConsistencyVerifier +// + +bool EdgeConsistencyChecker::verify(const Graph &graph) const +{ + auto &operations = graph.operations(); + uint32_t mismatches = 0; + operations.iterate([&](const model::operation::Index &index, const model::operation::Node &node) { + for (auto operand_index : node.getInputs()) + { + auto &operand = graph.operands().at(operand_index); + mismatches += (operand.getUses().contains(index) ? 0 : 1); + } + for (auto operand_index : node.getOutputs()) + { + auto &operand = graph.operands().at(operand_index); + mismatches += (operand.getDef().contains(index) ? 0 : 1); + } + }); + return mismatches == 0; +} + +} // namespace verifier +} // namespace graph +} // namespace neurun |