Apollo 10.0
自动驾驶开放平台
graph.cc
浏览该文件的文档.
1/******************************************************************************
2 * Copyright 2018 The Apollo Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *****************************************************************************/
16
18
19#include <queue>
20
21namespace apollo {
22namespace cyber {
23namespace service_discovery {
24
25using base::AtomicRWLock;
26using base::ReadLockGuard;
27using base::WriteLockGuard;
28
29Vertice::Vertice(const std::string& val) : value_(val) {}
30
31Vertice::Vertice(const Vertice& other) { this->value_ = other.value_; }
32
34
36 if (this != &rhs) {
37 this->value_ = rhs.value_;
38 }
39 return *this;
40}
41
42bool Vertice::operator==(const Vertice& rhs) const {
43 return this->value_ == rhs.value_;
44}
45
46bool Vertice::operator!=(const Vertice& rhs) const {
47 return this->value_ != rhs.value_;
48}
49
50bool Vertice::IsDummy() const { return value_.empty(); }
51
52const std::string& Vertice::GetKey() const { return value_; }
53
55
56Edge::Edge(const Edge& other) {
57 this->src_ = other.src_;
58 this->dst_ = other.dst_;
59 this->value_ = other.value_;
60}
61
62Edge::Edge(const Vertice& src, const Vertice& dst, const std::string& val)
63 : src_(src), dst_(dst), value_(val) {}
64
66
68 if (this != &rhs) {
69 this->src_ = rhs.src_;
70 this->dst_ = rhs.dst_;
71 this->value_ = rhs.value_;
72 }
73 return *this;
74}
75
76bool Edge::operator==(const Edge& rhs) const {
77 return this->src_ == rhs.src_ && this->dst_ == rhs.dst_ &&
78 this->value_ == rhs.value_;
79}
80
81bool Edge::IsValid() const {
82 if (value_.empty()) {
83 return false;
84 }
85 if (src_.IsDummy() && dst_.IsDummy()) {
86 return false;
87 }
88 return true;
89}
90
91std::string Edge::GetKey() const { return value_ + "_" + dst_.GetKey(); }
92
94
96 edges_.clear();
97 list_.clear();
98}
99
100void Graph::Insert(const Edge& e) {
101 if (!e.IsValid()) {
102 return;
103 }
104 WriteLockGuard<AtomicRWLock> lock(rw_lock_);
105 auto& e_v = e.value();
106 if (edges_.find(e_v) == edges_.end()) {
107 edges_[e_v] = RelatedVertices();
108 }
109
110 if (!e.src().IsDummy()) {
111 InsertOutgoingEdge(e);
112 }
113 if (!e.dst().IsDummy()) {
114 InsertIncomingEdge(e);
115 }
116}
117
118void Graph::Delete(const Edge& e) {
119 if (!e.IsValid()) {
120 return;
121 }
122 WriteLockGuard<AtomicRWLock> lock(rw_lock_);
123 auto& e_v = e.value();
124 if (edges_.find(e_v) == edges_.end()) {
125 return;
126 }
127
128 if (!e.src().IsDummy()) {
129 DeleteOutgoingEdge(e);
130 }
131 if (!e.dst().IsDummy()) {
132 DeleteIncomingEdge(e);
133 }
134}
135
137 ReadLockGuard<AtomicRWLock> lock(rw_lock_);
138 uint32_t num = 0;
139 for (auto& item : list_) {
140 num += static_cast<int>(item.second.size());
141 }
142 return num;
143}
144
146 if (lhs.IsDummy() || rhs.IsDummy()) {
147 return UNREACHABLE;
148 }
149 ReadLockGuard<AtomicRWLock> lock(rw_lock_);
150 if (list_.count(lhs.GetKey()) == 0 || list_.count(rhs.GetKey()) == 0) {
151 return UNREACHABLE;
152 }
153 if (LevelTraverse(lhs, rhs)) {
154 return UPSTREAM;
155 }
156 if (LevelTraverse(rhs, lhs)) {
157 return DOWNSTREAM;
158 }
159 return UNREACHABLE;
160}
161
162void Graph::InsertOutgoingEdge(const Edge& e) {
163 auto& e_v = e.value();
164 auto& src_v_set = edges_[e_v].src;
165 auto& src_v = e.src();
166 auto& v_k = src_v.GetKey();
167 if (src_v_set.find(v_k) != src_v_set.end()) {
168 return;
169 }
170 src_v_set[v_k] = src_v;
171
172 auto& dst_v_set = edges_[e_v].dst;
173 Edge insert_e;
174 insert_e.set_src(src_v);
175 insert_e.set_value(e.value());
176 for (auto& item : dst_v_set) {
177 insert_e.set_dst(item.second);
178 InsertCompleteEdge(insert_e);
179 }
180}
181
182void Graph::InsertIncomingEdge(const Edge& e) {
183 auto& e_v = e.value();
184 auto& dst_v_set = edges_[e_v].dst;
185 auto& dst_v = e.dst();
186 auto& v_k = dst_v.GetKey();
187 if (dst_v_set.find(v_k) != dst_v_set.end()) {
188 return;
189 }
190 dst_v_set[v_k] = dst_v;
191
192 auto& src_v_set = edges_[e_v].src;
193 Edge insert_e;
194 insert_e.set_dst(dst_v);
195 insert_e.set_value(e.value());
196 for (auto& item : src_v_set) {
197 insert_e.set_src(item.second);
198 InsertCompleteEdge(insert_e);
199 }
200}
201
202void Graph::InsertCompleteEdge(const Edge& e) {
203 auto& src_v_k = e.src().GetKey();
204 if (list_.find(src_v_k) == list_.end()) {
205 list_[src_v_k] = VerticeSet();
206 }
207 auto& dst_v_k = e.dst().GetKey();
208 if (list_.find(dst_v_k) == list_.end()) {
209 list_[dst_v_k] = VerticeSet();
210 }
211 list_[src_v_k][e.GetKey()] = e.dst();
212}
213
214void Graph::DeleteOutgoingEdge(const Edge& e) {
215 auto& e_v = e.value();
216 auto& src_v_set = edges_[e_v].src;
217 auto& src_v = e.src();
218 auto& v_k = src_v.GetKey();
219 if (src_v_set.find(v_k) == src_v_set.end()) {
220 return;
221 }
222 src_v_set.erase(v_k);
223
224 auto& dst_v_set = edges_[e_v].dst;
225 Edge delete_e;
226 delete_e.set_src(src_v);
227 delete_e.set_value(e.value());
228 for (auto& item : dst_v_set) {
229 delete_e.set_dst(item.second);
230 DeleteCompleteEdge(delete_e);
231 }
232}
233
234void Graph::DeleteIncomingEdge(const Edge& e) {
235 auto& e_v = e.value();
236 auto& dst_v_set = edges_[e_v].dst;
237 auto& dst_v = e.dst();
238 auto& v_k = dst_v.GetKey();
239 if (dst_v_set.find(v_k) == dst_v_set.end()) {
240 return;
241 }
242 dst_v_set.erase(v_k);
243
244 auto& src_v_set = edges_[e_v].src;
245 Edge delete_e;
246 delete_e.set_dst(dst_v);
247 delete_e.set_value(e.value());
248 for (auto& item : src_v_set) {
249 delete_e.set_src(item.second);
250 DeleteCompleteEdge(delete_e);
251 }
252}
253
254void Graph::DeleteCompleteEdge(const Edge& e) {
255 auto& src_v_k = e.src().GetKey();
256 list_[src_v_k].erase(e.GetKey());
257}
258
259bool Graph::LevelTraverse(const Vertice& start, const Vertice& end) {
260 std::unordered_map<std::string, bool> visited;
261 visited[end.GetKey()] = false;
262 std::queue<Vertice> unvisited;
263 unvisited.emplace(start);
264 while (!unvisited.empty()) {
265 auto curr = unvisited.front();
266 unvisited.pop();
267 if (visited[curr.GetKey()]) {
268 continue;
269 }
270 visited[curr.GetKey()] = true;
271 if (curr == end) {
272 break;
273 }
274 for (auto& item : list_[curr.GetKey()]) {
275 unvisited.push(item.second);
276 }
277 }
278 return visited[end.GetKey()];
279}
280
281} // namespace service_discovery
282} // namespace cyber
283} // namespace apollo
const std::string & value() const
Definition graph.h:84
const Vertice & src() const
Definition graph.h:78
Edge & operator=(const Edge &rhs)
Definition graph.cc:67
bool operator==(const Edge &rhs) const
Definition graph.cc:76
const Vertice & dst() const
Definition graph.h:81
FlowDirection GetDirectionOf(const Vertice &lhs, const Vertice &rhs)
Definition graph.cc:145
std::unordered_map< std::string, Vertice > VerticeSet
Definition graph.h:95
bool operator==(const Vertice &rhs) const
Definition graph.cc:42
const std::string & GetKey() const
Definition graph.cc:52
bool operator!=(const Vertice &rhs) const
Definition graph.cc:46
Vertice & operator=(const Vertice &rhs)
Definition graph.cc:35
Vertice(const std::string &val="")
Definition graph.cc:29
FlowDirection
describe the flow direction between nodes As the DAG below A-—>B--—>C<--—D GetDirectionOf(A,...
Definition graph.h:39
class register implement
Definition arena_queue.h:37