mirror of
https://gitee.com/openharmony/distributeddatamgr_udmf
synced 2024-10-07 05:43:56 +00:00
135 lines
3.8 KiB
C++
135 lines
3.8 KiB
C++
/*
|
|
* Copyright (c) 2023 Huawei Device Co., Ltd.
|
|
* 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.
|
|
*/
|
|
#define LOG_TAG "Graph"
|
|
#include "graph.h"
|
|
#include "logger.h"
|
|
namespace OHOS {
|
|
namespace UDMF {
|
|
Graph::Graph(uint32_t vertexNum, const std::map<std::string, uint32_t> &typeIdIndex)
|
|
: vertexNum_(vertexNum), typeIdIndex_(typeIdIndex)
|
|
{
|
|
for (uint32_t node = 0; node < vertexNum_; node++) {
|
|
adjList_.push_back({node, nullptr});
|
|
}
|
|
visited_.resize(vertexNum_);
|
|
fill(visited_.begin(), visited_.end(), 0);
|
|
}
|
|
|
|
Graph::~Graph()
|
|
{
|
|
for (const auto &vertexNode : adjList_) {
|
|
EdgeNode *edge = vertexNode.firstEdge;
|
|
while (edge != nullptr) {
|
|
EdgeNode *nextEdge = edge->next;
|
|
delete edge;
|
|
edge = nextEdge;
|
|
}
|
|
}
|
|
}
|
|
|
|
void Graph::AddEdge(const std::string &startNode, const std::string &endNode)
|
|
{
|
|
int32_t start = GetIndex(startNode);
|
|
int32_t end = GetIndex(endNode);
|
|
if (start < 0 || end < 0) {
|
|
LOG_WARN(UDMF_CLIENT, "abnormal edge, startNode:%{public}s, endNode:%{public}s. ",
|
|
startNode.c_str(), endNode.c_str());
|
|
return;
|
|
}
|
|
AddEdge(start, end);
|
|
}
|
|
|
|
void Graph::AddEdge(uint32_t start, uint32_t end)
|
|
{
|
|
EdgeNode *edge = new EdgeNode; // add new edge
|
|
edge->adjIndex = end;
|
|
edge->next = adjList_[start].firstEdge;
|
|
adjList_[start].firstEdge = edge;
|
|
}
|
|
|
|
bool Graph::Dfs(uint32_t startNode, Action action, bool isInit)
|
|
{
|
|
if (isInit) {
|
|
visited_.resize(vertexNum_);
|
|
fill(visited_.begin(), visited_.end(), 0);
|
|
}
|
|
std::stack<uint32_t> nodes;
|
|
EdgeNode *edge = nullptr;
|
|
visited_[startNode] = 1;
|
|
nodes.push(startNode);
|
|
if (action(adjList_[startNode].value)) {
|
|
return true;
|
|
}
|
|
while (!nodes.empty()) {
|
|
edge = adjList_[nodes.top()].firstEdge;
|
|
while (edge) {
|
|
if (visited_[edge->adjIndex] == 0) {
|
|
visited_[edge->adjIndex] = 1;
|
|
nodes.push(edge->adjIndex);
|
|
if (action(adjList_[edge->adjIndex].value)) {
|
|
return true;
|
|
}
|
|
edge = adjList_[edge->adjIndex].firstEdge;
|
|
} else if (visited_[edge->adjIndex] == 1) {
|
|
return false;
|
|
} else {
|
|
edge = edge->next;
|
|
}
|
|
}
|
|
visited_[nodes.top()] = 2; // 2: all edge of the adj is visited.
|
|
nodes.pop();
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool Graph::DfsUnconnectedGraph(Action action)
|
|
{
|
|
visited_.resize(vertexNum_);
|
|
fill(visited_.begin(), visited_.end(), 0);
|
|
for (uint32_t node = 0; node < vertexNum_; node++) {
|
|
if (!visited_[node]) {
|
|
if (!Dfs(node, action, false)) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool Graph::IsValidType(const std::string &node)
|
|
{
|
|
if (typeIdIndex_.find(node) == typeIdIndex_.end()) {
|
|
LOG_ERROR(UDMF_CLIENT, "invalid typeId. typeId:%{public}s ", node.c_str());
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int32_t Graph::GetIndex(const std::string &node)
|
|
{
|
|
auto idx = typeIdIndex_.find(node);
|
|
if (idx == typeIdIndex_.end()) {
|
|
return -1;
|
|
}
|
|
return idx->second;
|
|
}
|
|
|
|
bool Graph::IsDAG()
|
|
{
|
|
return DfsUnconnectedGraph([&](uint32_t currNode) -> bool { return false; });
|
|
}
|
|
} // namespace UDMF
|
|
} // namespace OHOS
|