23namespace service_discovery {
25using base::AtomicRWLock;
26using base::ReadLockGuard;
27using base::WriteLockGuard;
37 this->value_ = rhs.value_;
43 return this->value_ == rhs.value_;
47 return this->value_ != rhs.value_;
57 this->src_ = other.src_;
58 this->dst_ = other.dst_;
59 this->value_ = other.value_;
63 : src_(src), dst_(dst), value_(val) {}
69 this->src_ = rhs.src_;
70 this->dst_ = rhs.dst_;
71 this->value_ = rhs.value_;
77 return this->src_ == rhs.src_ && this->dst_ == rhs.dst_ &&
78 this->value_ == rhs.value_;
105 auto& e_v = e.
value();
106 if (edges_.find(e_v) == edges_.end()) {
107 edges_[e_v] = RelatedVertices();
111 InsertOutgoingEdge(e);
114 InsertIncomingEdge(e);
123 auto& e_v = e.
value();
124 if (edges_.find(e_v) == edges_.end()) {
129 DeleteOutgoingEdge(e);
132 DeleteIncomingEdge(e);
139 for (
auto& item : list_) {
140 num +=
static_cast<int>(item.second.size());
150 if (list_.count(lhs.
GetKey()) == 0 || list_.count(rhs.
GetKey()) == 0) {
153 if (LevelTraverse(lhs, rhs)) {
156 if (LevelTraverse(rhs, lhs)) {
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()) {
170 src_v_set[v_k] = src_v;
172 auto& dst_v_set = edges_[e_v].dst;
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);
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()) {
190 dst_v_set[v_k] = dst_v;
192 auto& src_v_set = edges_[e_v].src;
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);
202void Graph::InsertCompleteEdge(
const Edge& e) {
203 auto& src_v_k = e.src().GetKey();
204 if (list_.find(src_v_k) == list_.end()) {
207 auto& dst_v_k = e.dst().GetKey();
208 if (list_.find(dst_v_k) == list_.end()) {
211 list_[src_v_k][e.GetKey()] = e.dst();
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()) {
222 src_v_set.erase(v_k);
224 auto& dst_v_set = edges_[e_v].dst;
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);
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()) {
242 dst_v_set.erase(v_k);
244 auto& src_v_set = edges_[e_v].src;
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);
254void Graph::DeleteCompleteEdge(
const Edge& e) {
255 auto& src_v_k = e.src().GetKey();
256 list_[src_v_k].erase(e.GetKey());
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();
267 if (visited[curr.GetKey()]) {
270 visited[curr.GetKey()] =
true;
274 for (
auto& item : list_[curr.GetKey()]) {
275 unvisited.push(item.second);
278 return visited[end.GetKey()];
const std::string & value() const
const Vertice & src() const
std::string GetKey() const
Edge & operator=(const Edge &rhs)
bool operator==(const Edge &rhs) const
const Vertice & dst() const
void Insert(const Edge &e)
FlowDirection GetDirectionOf(const Vertice &lhs, const Vertice &rhs)
void Delete(const Edge &e)
std::unordered_map< std::string, Vertice > VerticeSet
bool operator==(const Vertice &rhs) const
const std::string & GetKey() const
bool operator!=(const Vertice &rhs) const
Vertice & operator=(const Vertice &rhs)
Vertice(const std::string &val="")
FlowDirection
describe the flow direction between nodes As the DAG below A-—>B--—>C<--—D GetDirectionOf(A,...