11 #ifndef smtk_graph_ExplicitArcs_h
12 #define smtk_graph_ExplicitArcs_h
14 #include "smtk/common/UUID.h"
16 #include "smtk/graph/ArcProperties.h"
17 #include "smtk/resource/Component.h"
18 #include "smtk/string/Token.h"
20 #include <unordered_map>
21 #include <unordered_set>
31 template<
typename ArcTraits>
35 using Traits = ArcTraits;
37 using FromType =
typename ArcTraits::FromType;
38 using ToType =
typename ArcTraits::ToType;
39 using Directed =
typename ArcTraits::Directed;
40 using Ordered = std::false_type;
47 static constexpr std::size_t MaxOutDegree = maxOutDegree<ArcTraits>(
unconstrained());
48 static constexpr std::size_t MaxInDegree = maxInDegree<ArcTraits>(
unconstrained());
49 static constexpr std::size_t MinOutDegree = maxOutDegree<ArcTraits>(
unconstrained());
50 static constexpr std::size_t MinInDegree = maxInDegree<ArcTraits>(
unconstrained());
55 "Undirected arcs must be bidirectionally indexed (otherwise outVisitor cannot work).");
59 template<
typename Resource,
typename Functor>
63 bool didVisit =
false;
65 std::set<const FromType*> visitedNodes;
66 for (
const auto& entry : m_forward)
68 if (!entry.second.empty())
77 visitedNodes.insert(entry.first);
87 for (
const auto& entry : m_reverse)
89 const auto* node =
reinterpret_cast<const FromType*
>(entry.first);
90 if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
104 template<
typename Resource,
typename Functor>
108 bool didVisit =
false;
110 std::set<const ToType*> visitedNodes;
111 for (
const auto& entry : m_reverse)
113 if (!entry.second.empty())
122 visitedNodes.insert(entry.first);
132 for (
const auto& entry : m_forward)
134 const auto* node =
reinterpret_cast<const ToType*
>(entry.first);
135 if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
149 template<
typename Functor>
154 throw std::invalid_argument(
"Null from node.");
159 throw std::invalid_argument(
"Input node has no parent resource.");
163 bool didVisit =
false;
166 auto it = m_forward.find(node);
167 if (it != m_forward.end())
169 didVisit |= !it->second.empty();
170 for (
const auto* other : it->second)
183 if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
185 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(node));
186 if (rit != m_reverse.end())
189 for (
const auto* other : rit->second)
200 throw std::runtime_error(
"Null node.");
211 template<
typename Functor>
216 throw std::invalid_argument(
"Null to node.");
221 throw std::invalid_argument(
"Input node has no parent resource.");
225 bool didVisit =
false;
228 auto rit = m_reverse.find(node);
229 if (rit != m_reverse.end())
231 didVisit |= !rit->second.empty();
232 for (
const auto* other : rit->second)
245 if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
247 auto it = m_forward.find(
reinterpret_cast<const FromType*
>(node));
248 if (it != m_forward.end())
251 for (
const auto* other : it->second)
262 throw std::runtime_error(
"Null node.");
272 bool contains(
const FromType* from,
const ToType* to)
const
278 auto it = m_forward.find(from);
279 if (it != m_forward.end())
281 auto it2 = it->second.find(to);
282 return it2 != it->second.end();
286 if (std::is_same<FromType, ToType>::value && !Directed::value)
289 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
290 if (rit != m_reverse.end())
292 auto it2 = rit->second.find(
reinterpret_cast<const FromType*
>(to));
293 return it2 != rit->second.end();
303 std::size_t result = 0;
308 auto it = m_forward.find(node);
309 if (it != m_forward.end())
311 result = it->second.size();
313 if (std::is_same<FromType, ToType>::value && !Directed::value)
316 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(node));
317 if (rit != m_reverse.end())
319 result += rit->second.size();
328 std::size_t result = 0;
333 auto it = m_reverse.find(node);
334 if (it != m_reverse.end())
336 result = it->second.size();
338 if (std::is_same<FromType, ToType>::value && !Directed::value)
341 auto fit = m_forward.find(
reinterpret_cast<const FromType*
>(node));
342 if (fit != m_forward.end())
344 result += fit->second.size();
360 template<
bool MM = Mutable::value>
361 typename std::enable_if<!MM, bool>::type
connect(
362 const FromType* from,
364 const FromType* beforeFrom =
nullptr,
365 const ToType* beforeTo =
nullptr)
374 template<
bool MM = Mutable::value>
375 typename std::enable_if<MM, bool>::type
connect(
376 const FromType* from,
378 const FromType* beforeFrom =
nullptr,
379 const ToType* beforeTo =
nullptr)
385 throw std::domain_error(
"Cannot connect null nodes.");
387 bool inserting =
true;
390 if (std::is_same<FromType, ToType>::value && !Directed::value)
392 auto it = m_forward.find(
reinterpret_cast<const FromType*
>(to));
394 it != m_forward.end() &&
395 it->second.find(
reinterpret_cast<const ToType*
>(from)) != it->second.end())
409 inserting &= (MaxOutDegree > this->
outDegree(from));
413 inserting &= (MaxInDegree > this->
inDegree(to));
423 inserting = m_forward[from].insert(to).second;
424 if (BidirIndex::value)
426 inserting |= m_reverse[to].insert(from).second;
443 template<
bool MM = Mutable::value>
444 typename std::enable_if<!MM, bool>::type
disconnect(
const FromType* from,
const ToType* to)
451 template<
bool MM = Mutable::value>
452 typename std::enable_if<MM, bool>::type
disconnect(
const FromType* from,
const ToType* to)
456 throw std::domain_error(
"Cannot disconnect null nodes.");
458 bool didDisconnect =
false;
463 auto it = m_reverse.find(to);
464 if (it != m_reverse.end())
466 didDisconnect =
true;
467 if (BidirIndex::value)
469 for (
const auto& other : it->second)
472 m_forward[other].erase(to);
473 if (m_forward[other].empty())
475 m_forward.erase(other);
482 if (std::is_base_of<FromType, ToType>::value && BidirIndex::value)
484 auto fit = m_forward.find(
reinterpret_cast<const FromType*
>(to));
485 if (fit != m_forward.end())
487 didDisconnect =
true;
488 for (
const auto& other : fit->second)
491 m_reverse[
reinterpret_cast<const ToType*
>(other)].erase(
492 reinterpret_cast<const FromType*
>(to));
493 if (m_reverse[
reinterpret_cast<const ToType*
>(other)].empty())
495 m_reverse.erase(
reinterpret_cast<const ToType*
>(other));
499 m_forward.erase(fit);
502 else if (!BidirIndex::value)
506 for (
auto& entry : m_forward)
508 auto fit = entry.second.find(to);
509 if (fit != entry.second.end())
511 didDisconnect =
true;
512 entry.second.erase(fit);
516 return didDisconnect;
518 auto it = m_forward.find(from);
523 if (it != m_forward.end())
525 didDisconnect =
true;
526 if (BidirIndex::value)
528 for (
const auto& other : it->second)
531 m_reverse[other].erase(from);
532 if (m_reverse[other].empty())
534 m_reverse.erase(other);
541 if (std::is_base_of<ToType, FromType>::value)
543 if (BidirIndex::value)
545 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
546 if (rit != m_reverse.end())
548 didDisconnect =
true;
549 for (
const auto& other : rit->second)
552 m_forward[
reinterpret_cast<const FromType*
>(other)].erase(
553 reinterpret_cast<const ToType*
>(from));
554 if (m_forward[
reinterpret_cast<const FromType*
>(other)].empty())
556 m_forward.erase(
reinterpret_cast<const FromType*
>(other));
560 m_reverse.erase(rit);
567 for (
auto& entry : m_forward)
569 auto fit = entry.second.find(
reinterpret_cast<const ToType*
>(from));
570 if (fit != entry.second.end())
572 didDisconnect =
true;
573 entry.second.erase(fit);
578 return didDisconnect;
581 if (it != m_forward.end())
583 didDisconnect = it->second.erase(to) > 0;
584 if (didDisconnect && BidirIndex::value)
587 m_reverse[to].erase(from);
588 if (m_reverse[to].empty())
594 else if (std::is_same<FromType, ToType>::value && !Directed::value)
597 if (BidirIndex::value)
599 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
600 if (rit != m_reverse.end())
602 didDisconnect = rit->second.erase(
reinterpret_cast<const FromType*
>(to)) > 0;
605 m_forward[
reinterpret_cast<const FromType*
>(to)].erase(
606 reinterpret_cast<const ToType*
>(from));
607 if (m_forward[
reinterpret_cast<const FromType*
>(to)].empty())
609 m_forward.erase(
reinterpret_cast<const FromType*
>(to));
616 it = m_forward.find(
reinterpret_cast<const FromType*
>(to));
617 if (it != m_forward.end())
619 didDisconnect = it->second.erase(
reinterpret_cast<const ToType*
>(from)) > 0;
620 if (didDisconnect && it->second.empty())
627 return didDisconnect;
632 std::unordered_map<const FromType*, std::unordered_set<const ToType*>> m_forward;
633 std::unordered_map<const ToType*, std::unordered_set<const FromType*>> m_reverse;
639 #endif // smtk_graph_ExplicitArcs_h