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;
49 : m_traits(std::move(
traits))
57 static constexpr std::size_t MaxOutDegree = maxOutDegree<ArcTraits>(
unconstrained());
58 static constexpr std::size_t MaxInDegree = maxInDegree<ArcTraits>(
unconstrained());
59 static constexpr std::size_t MinOutDegree = maxOutDegree<ArcTraits>(
unconstrained());
60 static constexpr std::size_t MinInDegree = maxInDegree<ArcTraits>(
unconstrained());
65 "Undirected arcs must be bidirectionally indexed (otherwise outVisitor cannot work).");
69 template<
typename Resource,
typename Functor>
73 bool didVisit =
false;
75 std::set<const FromType*> visitedNodes;
76 for (
const auto& entry : m_forward)
78 if (!entry.second.empty())
87 visitedNodes.insert(entry.first);
97 for (
const auto& entry : m_reverse)
99 const auto* node =
reinterpret_cast<const FromType*
>(entry.first);
100 if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
114 template<
typename Resource,
typename Functor>
118 bool didVisit =
false;
120 std::set<const ToType*> visitedNodes;
121 for (
const auto& entry : m_reverse)
123 if (!entry.second.empty())
132 visitedNodes.insert(entry.first);
142 for (
const auto& entry : m_forward)
144 const auto* node =
reinterpret_cast<const ToType*
>(entry.first);
145 if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
159 template<
typename Functor>
164 throw std::invalid_argument(
"Null from node.");
169 throw std::invalid_argument(
"Input node has no parent resource.");
173 bool didVisit =
false;
176 auto it = m_forward.find(node);
177 if (it != m_forward.end())
179 didVisit |= !it->second.empty();
180 for (
const auto* other : it->second)
193 if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
195 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(node));
196 if (rit != m_reverse.end())
199 for (
const auto* other : rit->second)
210 throw std::runtime_error(
"Null node.");
221 template<
typename Functor>
226 throw std::invalid_argument(
"Null to node.");
231 throw std::invalid_argument(
"Input node has no parent resource.");
235 bool didVisit =
false;
238 auto rit = m_reverse.find(node);
239 if (rit != m_reverse.end())
241 didVisit |= !rit->second.empty();
242 for (
const auto* other : rit->second)
255 if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
257 auto it = m_forward.find(
reinterpret_cast<const FromType*
>(node));
258 if (it != m_forward.end())
261 for (
const auto* other : it->second)
272 throw std::runtime_error(
"Null node.");
282 bool contains(
const FromType* from,
const ToType* to)
const
288 auto it = m_forward.find(from);
289 if (it != m_forward.end())
291 auto it2 = it->second.find(to);
292 return it2 != it->second.end();
296 if (std::is_same<FromType, ToType>::value && !Directed::value)
299 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
300 if (rit != m_reverse.end())
302 auto it2 = rit->second.find(
reinterpret_cast<const FromType*
>(to));
303 return it2 != rit->second.end();
313 std::size_t result = 0;
318 auto it = m_forward.find(node);
319 if (it != m_forward.end())
321 result = it->second.size();
323 if (std::is_same<FromType, ToType>::value && !Directed::value)
326 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(node));
327 if (rit != m_reverse.end())
329 result += rit->second.size();
338 std::size_t result = 0;
343 auto it = m_reverse.find(node);
344 if (it != m_reverse.end())
346 result = it->second.size();
348 if (std::is_same<FromType, ToType>::value && !Directed::value)
351 auto fit = m_forward.find(
reinterpret_cast<const FromType*
>(node));
352 if (fit != m_forward.end())
354 result += fit->second.size();
361 template<typename U = typename ArcProperties<Traits>::template hasConnect<Traits>>
362 typename std::enable_if<!U::value, bool>::type runtimeConnectionCheck(
363 const FromType* from,
365 const FromType* beforeFrom,
366 const ToType* beforeTo)
const
378 template<typename U = typename ArcProperties<Traits>::template hasConnect<Traits>>
379 typename std::enable_if<U::value, bool>::type runtimeConnectionCheck(
380 const FromType* from,
382 const FromType* beforeFrom,
383 const ToType* beforeTo)
const
390 auto*
traits =
const_cast<Traits*
>(&m_traits);
391 return traits->connect(from, to, beforeFrom, beforeTo);
401 template<
bool MM = Mutable::value>
402 typename std::enable_if<!MM, bool>::type
accepts(
403 const FromType* from,
405 const FromType* beforeFrom =
nullptr,
406 const ToType* beforeTo =
nullptr)
const
415 template<
bool MM = Mutable::value>
416 typename std::enable_if<MM, bool>::type
accepts(
417 const FromType* from,
419 const FromType* beforeFrom =
nullptr,
420 const ToType* beforeTo =
nullptr)
const
428 bool inserting =
true;
431 if (std::is_same<FromType, ToType>::value && !Directed::value)
433 auto it = m_forward.find(
reinterpret_cast<const FromType*
>(to));
435 it != m_forward.end() &&
436 it->second.find(
reinterpret_cast<const ToType*
>(from)) != it->second.end())
450 inserting &= (MaxOutDegree > this->
outDegree(from));
454 inserting &= (MaxInDegree > this->
inDegree(to));
458 inserting &= this->runtimeConnectionCheck(from, to, beforeFrom, beforeTo);
478 const FromType* from,
480 const FromType* beforeFrom =
nullptr,
481 const ToType* beforeTo =
nullptr)
487 throw std::domain_error(
"Cannot connect null nodes.");
489 bool inserting = this->
accepts(from, to, beforeFrom, beforeTo);
493 inserting = m_forward[from].insert(to).second;
494 if (BidirIndex::value)
496 inserting |= m_reverse[to].insert(from).second;
513 template<
bool MM = Mutable::value>
514 typename std::enable_if<!MM, bool>::type
disconnect(
const FromType* from,
const ToType* to)
521 template<
bool MM = Mutable::value>
522 typename std::enable_if<MM, bool>::type
disconnect(
const FromType* from,
const ToType* to)
526 throw std::domain_error(
"Cannot disconnect null nodes.");
528 bool didDisconnect =
false;
533 auto it = m_reverse.find(to);
534 if (it != m_reverse.end())
536 didDisconnect =
true;
537 if (BidirIndex::value)
539 for (
const auto& other : it->second)
542 m_forward[other].erase(to);
543 if (m_forward[other].
empty())
545 m_forward.erase(other);
552 if (std::is_base_of<FromType, ToType>::value && BidirIndex::value)
554 auto fit = m_forward.find(
reinterpret_cast<const FromType*
>(to));
555 if (fit != m_forward.end())
557 didDisconnect =
true;
558 for (
const auto& other : fit->second)
561 m_reverse[
reinterpret_cast<const ToType*
>(other)].erase(
562 reinterpret_cast<const FromType*
>(to));
563 if (m_reverse[
reinterpret_cast<const ToType*
>(other)].empty())
565 m_reverse.erase(
reinterpret_cast<const ToType*
>(other));
569 m_forward.erase(fit);
572 else if (!BidirIndex::value)
576 for (
auto& entry : m_forward)
578 auto fit = entry.second.find(to);
579 if (fit != entry.second.end())
581 didDisconnect =
true;
582 entry.second.erase(fit);
586 return didDisconnect;
588 auto it = m_forward.find(from);
593 if (it != m_forward.end())
595 didDisconnect =
true;
596 if (BidirIndex::value)
598 for (
const auto& other : it->second)
601 m_reverse[other].erase(from);
602 if (m_reverse[other].
empty())
604 m_reverse.erase(other);
611 if (std::is_base_of<ToType, FromType>::value)
613 if (BidirIndex::value)
615 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
616 if (rit != m_reverse.end())
618 didDisconnect =
true;
619 for (
const auto& other : rit->second)
622 m_forward[
reinterpret_cast<const FromType*
>(other)].erase(
623 reinterpret_cast<const ToType*
>(from));
624 if (m_forward[
reinterpret_cast<const FromType*
>(other)].empty())
626 m_forward.erase(
reinterpret_cast<const FromType*
>(other));
630 m_reverse.erase(rit);
637 for (
auto& entry : m_forward)
639 auto fit = entry.second.find(
reinterpret_cast<const ToType*
>(from));
640 if (fit != entry.second.end())
642 didDisconnect =
true;
643 entry.second.erase(fit);
648 return didDisconnect;
651 if (it != m_forward.end())
653 didDisconnect = it->second.erase(to) > 0;
654 if (didDisconnect && BidirIndex::value)
657 m_reverse[to].erase(from);
658 if (m_reverse[to].
empty())
664 else if (std::is_same<FromType, ToType>::value && !Directed::value)
667 if (BidirIndex::value)
669 auto rit = m_reverse.find(
reinterpret_cast<const ToType*
>(from));
670 if (rit != m_reverse.end())
672 didDisconnect = rit->second.erase(
reinterpret_cast<const FromType*
>(to)) > 0;
675 m_forward[
reinterpret_cast<const FromType*
>(to)].erase(
676 reinterpret_cast<const ToType*
>(from));
677 if (m_forward[
reinterpret_cast<const FromType*
>(to)].empty())
679 m_forward.erase(
reinterpret_cast<const FromType*
>(to));
686 it = m_forward.find(
reinterpret_cast<const FromType*
>(to));
687 if (it != m_forward.end())
689 didDisconnect = it->second.erase(
reinterpret_cast<const ToType*
>(from)) > 0;
690 if (didDisconnect && it->second.empty())
697 return didDisconnect;
702 bool empty()
const {
return m_forward.empty(); }
705 std::size_t
size()
const {
return m_forward.size(); }
708 const Traits&
traits()
const {
return m_traits; }
709 Traits&
traits() {
return m_traits; }
712 std::unordered_map<const FromType*, std::unordered_set<const ToType*>> m_forward;
713 std::unordered_map<const ToType*, std::unordered_set<const FromType*>> m_reverse;
720 #endif // smtk_graph_ExplicitArcs_h