104 lines
2.2 KiB
C++
Executable File
104 lines
2.2 KiB
C++
Executable File
|
|
#pragma once
|
|
|
|
|
|
#include <functional>
|
|
#include <set>
|
|
|
|
namespace wfr {
|
|
namespace wep {
|
|
class AbstractWepNode;
|
|
}
|
|
|
|
namespace utils {
|
|
namespace wep {
|
|
|
|
|
|
|
|
template<typename VisitType>
|
|
void wepDepthFirstSearch(wfr::wep::AbstractWepNode* startNode, const VisitType& visitFunction,
|
|
std::set<wfr::wep::AbstractWepNode*>* visitedNodes = nullptr) {
|
|
bool deleteVisitedNodeSet = false;
|
|
if (visitedNodes == nullptr) {
|
|
visitedNodes = new std::set<wfr::wep::AbstractWepNode*>();
|
|
deleteVisitedNodeSet = true;
|
|
}
|
|
visitedNodes->insert(startNode);
|
|
if (visitFunction(startNode)) {
|
|
for (auto c : startNode->getSuccessors()) {
|
|
if (visitedNodes->find(c) == visitedNodes->end()) {
|
|
wepDepthFirstSearch(c, visitFunction, visitedNodes);
|
|
}
|
|
}
|
|
}
|
|
if (deleteVisitedNodeSet) {
|
|
delete visitedNodes;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template<typename VisitType>
|
|
void wepBreadthFirstSearch(wfr::wep::AbstractWepNode* startNode, const VisitType& visitFunction) {
|
|
std::vector<wfr::wep::AbstractWepNode*> nodeQueue;
|
|
std::set<wfr::wep::AbstractWepNode*> visitedNodes;
|
|
nodeQueue.push_back(startNode);
|
|
while (!nodeQueue.empty()) {
|
|
auto cn = nodeQueue.front();
|
|
visitedNodes.insert(cn);
|
|
nodeQueue.erase(nodeQueue.begin());
|
|
if (visitFunction(cn)) {
|
|
for (auto c : cn->getSuccessors()) {
|
|
if (visitedNodes.find(c) == visitedNodes.end()) {
|
|
bool isInQueue = false;
|
|
for (auto e : nodeQueue) {
|
|
if (c == e) {
|
|
isInQueue = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!isInQueue) {
|
|
nodeQueue.push_back(c);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template<typename VisitType>
|
|
void wepBreadthFirstReverseSearch(wfr::wep::AbstractWepNode* startNode, const VisitType& visitFunction) {
|
|
std::vector<wfr::wep::AbstractWepNode*> nodeQueue;
|
|
std::set<wfr::wep::AbstractWepNode*> visitedNodes;
|
|
nodeQueue.push_back(startNode);
|
|
while (!nodeQueue.empty()) {
|
|
auto cn = nodeQueue.front();
|
|
visitedNodes.insert(cn);
|
|
nodeQueue.erase(nodeQueue.begin());
|
|
if (visitFunction(cn)) {
|
|
for (auto c : cn->getPredecessors()) {
|
|
if (visitedNodes.find(c) == visitedNodes.end()) {
|
|
bool isInQueue = false;
|
|
for (auto e : nodeQueue) {
|
|
if (c == e) {
|
|
isInQueue = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!isInQueue) {
|
|
nodeQueue.push_back(c);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
}
|
|
}
|
|
}
|
|
|