SMTK  @SMTK_VERSION@
Simulation Modeling Tool Kit
ExplicitArcs.h
1 //=========================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 //
6 // This software is distributed WITHOUT ANY WARRANTY; without even
7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE. See the above copyright notice for more information.
9 //=========================================================================
10 
11 #ifndef smtk_graph_ExplicitArcs_h
12 #define smtk_graph_ExplicitArcs_h
13 
14 #include "smtk/common/UUID.h"
15 #include "smtk/common/Visit.h"
16 #include "smtk/graph/ArcProperties.h"
17 #include "smtk/string/Token.h"
18 
19 #include <unordered_map>
20 #include <unordered_set>
21 
22 namespace smtk
23 {
24 namespace graph
25 {
26 
30 template<typename ArcTraits>
32 {
33 public:
34  using Traits = ArcTraits; // Allow classes to inspect our input parameter.
35 
36  using FromType = typename ArcTraits::FromType;
37  using ToType = typename ArcTraits::ToType;
38  using Directed = typename ArcTraits::Directed;
39  using Ordered = std::false_type; // This class cannot represent ordered arcs.
40  using Mutable = typename ArcProperties<ArcTraits>::isMutable;
41  using BidirIndex =
42  negation<typename ArcProperties<ArcTraits>::template hasOnlyForwardIndex<ArcTraits>>;
43 
44  using UUID = smtk::common::UUID;
45 
46  static constexpr std::size_t MaxOutDegree = maxOutDegree<ArcTraits>(unconstrained());
47  static constexpr std::size_t MaxInDegree = maxInDegree<ArcTraits>(unconstrained());
48  static constexpr std::size_t MinOutDegree = maxOutDegree<ArcTraits>(unconstrained());
49  static constexpr std::size_t MinInDegree = maxInDegree<ArcTraits>(unconstrained());
50 
52  static_assert(
53  NoBadIndexing::value,
54  "Undirected arcs must be bidirectionally indexed (otherwise outVisitor cannot work).");
55 
58  template<typename Resource, typename Functor>
60  {
61  (void)rr;
62  bool didVisit = false;
64  std::set<const FromType*> visitedNodes; // Only used for auto-undirected visits
65  for (const auto& entry : m_forward)
66  {
67  if (!entry.second.empty())
68  {
69  didVisit = true;
70  if (visitor(entry.first) == smtk::common::Visit::Halt)
71  {
73  }
75  {
76  visitedNodes.insert(entry.first);
77  }
78  }
79  }
80  // If arc is auto-undirected, we must also check for
81  // nodes in reverse direction that we haven't already seen.
82  // Alternatively, we could have visited every node in
83  // entry.second in the loop above...
85  {
86  for (const auto& entry : m_reverse)
87  {
88  const auto* node = reinterpret_cast<const FromType*>(entry.first);
89  if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
90  {
91  if (visitor(node) == smtk::common::Visit::Halt)
92  {
94  }
95  }
96  }
97  }
99  }
100 
103  template<typename Resource, typename Functor>
105  {
106  (void)rr;
107  bool didVisit = false;
109  std::set<const ToType*> visitedNodes; // Only used for auto-undirected visits
110  for (const auto& entry : m_reverse)
111  {
112  if (!entry.second.empty())
113  {
114  didVisit = true;
115  if (visitor(entry.first) == smtk::common::Visit::Halt)
116  {
118  }
120  {
121  visitedNodes.insert(entry.first);
122  }
123  }
124  }
125  // If arc is auto-undirected, we must also check for
126  // nodes in reverse direction that we haven't already seen.
127  // Alternatively, we could have visited every node in
128  // entry.second in the loop above...
130  {
131  for (const auto& entry : m_forward)
132  {
133  const auto* node = reinterpret_cast<const ToType*>(entry.first);
134  if (!entry.second.empty() && visitedNodes.find(node) == visitedNodes.end())
135  {
136  if (visitor(node) == smtk::common::Visit::Halt)
137  {
139  }
140  }
141  }
142  }
144  }
145 
148  template<typename Functor>
149  smtk::common::Visited outVisitor(const FromType* node, Functor ff) const
150  {
151  if (!node)
152  {
153  throw std::invalid_argument("Null from node.");
154  }
155  auto resource = node->resource();
156  if (!resource)
157  {
158  throw std::invalid_argument("Input node has no parent resource.");
159  }
160 
162  bool didVisit = false;
163 
164  // Find matching forward arcs.
165  auto it = m_forward.find(node);
166  if (it != m_forward.end())
167  {
168  didVisit |= !it->second.empty();
169  for (const auto* other : it->second)
170  {
171  if (other)
172  {
173  if (visitor(other) == smtk::common::Visit::Halt)
174  {
176  }
177  }
178  }
179  }
180 
181  // If the graph is bidirectional and types match, find matching reverse arcs.
182  if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
183  {
184  auto rit = m_reverse.find(reinterpret_cast<const ToType*>(node));
185  if (rit != m_reverse.end())
186  {
187  didVisit = true;
188  for (const auto* other : rit->second)
189  {
190  if (other)
191  {
192  if (visitor(reinterpret_cast<const ToType*>(other)) == smtk::common::Visit::Halt)
193  {
195  }
196  }
197  else
198  {
199  throw std::runtime_error("Null node.");
200  }
201  }
202  }
203  }
204 
206  };
207 
210  template<typename Functor>
211  smtk::common::Visited inVisitor(const ToType* node, Functor ff) const
212  {
213  if (!node)
214  {
215  throw std::invalid_argument("Null to node.");
216  }
217  auto resource = node->resource();
218  if (!resource)
219  {
220  throw std::invalid_argument("Input node has no parent resource.");
221  }
222 
224  bool didVisit = false;
225 
226  // Find matching reverse arcs.
227  auto rit = m_reverse.find(node);
228  if (rit != m_reverse.end())
229  {
230  didVisit |= !rit->second.empty();
231  for (const auto* other : rit->second)
232  {
233  if (other)
234  {
235  if (visitor(other) == smtk::common::Visit::Halt)
236  {
238  }
239  }
240  }
241  }
242 
243  // If the graph is bidirectional and types match, find matching forward arcs.
244  if (std::is_same<FromType, ToType>::value && !Directed::value && BidirIndex::value)
245  {
246  auto it = m_forward.find(reinterpret_cast<const FromType*>(node));
247  if (it != m_forward.end())
248  {
249  didVisit = true;
250  for (const auto* other : it->second)
251  {
252  if (other)
253  {
254  if (visitor(reinterpret_cast<const FromType*>(other)) == smtk::common::Visit::Halt)
255  {
257  }
258  }
259  else
260  {
261  throw std::runtime_error("Null node.");
262  }
263  }
264  }
265  }
266 
268  }
269 
271  bool contains(const FromType* from, const ToType* to) const
272  {
273  if (!from || !to)
274  {
275  return false;
276  }
277  auto it = m_forward.find(from);
278  if (it != m_forward.end())
279  {
280  auto it2 = it->second.find(to);
281  return it2 != it->second.end();
282  }
283 
284  // Handle undirected arcs where std::is_same<FromType, ToType>:
285  if (std::is_same<FromType, ToType>::value && !Directed::value)
286  {
287  // We must also verify whether to → from exists.
288  auto rit = m_reverse.find(reinterpret_cast<const ToType*>(from));
289  if (rit != m_reverse.end())
290  {
291  auto it2 = rit->second.find(reinterpret_cast<const FromType*>(to));
292  return it2 != rit->second.end();
293  }
294  }
295 
296  return false;
297  }
298 
300  std::size_t outDegree(const FromType* node) const
301  {
302  std::size_t result = 0;
303  if (!node)
304  {
305  return result;
306  }
307  auto it = m_forward.find(node);
308  if (it != m_forward.end())
309  {
310  result = it->second.size();
311  }
312  if (std::is_same<FromType, ToType>::value && !Directed::value)
313  {
314  // Add any arcs "incoming" to the node.
315  auto rit = m_reverse.find(reinterpret_cast<const ToType*>(node));
316  if (rit != m_reverse.end())
317  {
318  result += rit->second.size();
319  }
320  }
321  return result;
322  }
323 
325  std::size_t inDegree(const ToType* node) const
326  {
327  std::size_t result = 0;
328  if (!node)
329  {
330  return result;
331  }
332  auto it = m_reverse.find(node);
333  if (it != m_reverse.end())
334  {
335  result = it->second.size();
336  }
337  if (std::is_same<FromType, ToType>::value && !Directed::value)
338  {
339  // Add any arcs "outgoing" to the node.
340  auto fit = m_forward.find(reinterpret_cast<const FromType*>(node));
341  if (fit != m_forward.end())
342  {
343  result += fit->second.size();
344  }
345  }
346  return result;
347  }
348 
359  template<bool MM = Mutable::value>
360  typename std::enable_if<!MM, bool>::type connect(
361  const FromType* from,
362  const ToType* to,
363  const FromType* beforeFrom = nullptr,
364  const ToType* beforeTo = nullptr)
365  {
366  (void)from;
367  (void)to;
368  (void)beforeFrom;
369  (void)beforeTo;
370  return false;
371  }
372 
373  template<bool MM = Mutable::value>
374  typename std::enable_if<MM, bool>::type connect(
375  const FromType* from,
376  const ToType* to,
377  const FromType* beforeFrom = nullptr,
378  const ToType* beforeTo = nullptr)
379  {
380  (void)beforeFrom;
381  (void)beforeTo;
382  if (!from || !to)
383  {
384  throw std::domain_error("Cannot connect null nodes.");
385  }
386  bool inserting = true;
387  // For auto-undirected arcs, we must verify that to → from does not
388  // already exist before inserting.
389  if (std::is_same<FromType, ToType>::value && !Directed::value)
390  {
391  auto it = m_forward.find(reinterpret_cast<const FromType*>(to));
392  if (
393  it != m_forward.end() &&
394  it->second.find(reinterpret_cast<const ToType*>(from)) != it->second.end())
395  {
396  // The arc already exists; do not allow insertion to proceed:
397  inserting = false;
398  }
399  }
400  // TODO: Also test when FromType != ToType, but arc could still have been reversed?
401  // (i.e., when From and ToTypes are distinct but share a common base class).
402 
403  // Verify that the in/out-degree constraints will be honored:
404  if (inserting && (MaxOutDegree != unconstrained() || MaxInDegree != unconstrained()))
405  {
406  if (MaxOutDegree != unconstrained())
407  {
408  inserting &= (MaxOutDegree > this->outDegree(from));
409  }
410  if (MaxInDegree != unconstrained())
411  {
412  inserting &= (MaxInDegree > this->inDegree(to));
413  }
414  }
415  // NB: We do not enforce MinInDegree or MinOutDegree because those
416  // conditions would frequently be validated. In the future,
417  // we may wish to mark our state as invalid if those (soft)
418  // constraints are invalid.
419  if (inserting)
420  {
421  // Insert from → to.
422  inserting = m_forward[from].insert(to).second;
423  if (BidirIndex::value)
424  {
425  inserting |= m_reverse[to].insert(from).second;
426  }
427  }
428  return inserting;
429  }
431 
442  template<bool MM = Mutable::value>
443  typename std::enable_if<!MM, bool>::type disconnect(const FromType* from, const ToType* to)
444  {
445  (void)from;
446  (void)to;
447  return false;
448  }
449 
450  template<bool MM = Mutable::value>
451  typename std::enable_if<MM, bool>::type disconnect(const FromType* from, const ToType* to)
452  {
453  if (!from)
454  {
455  throw std::domain_error("Cannot disconnect null nodes.");
456  }
457  auto it = m_forward.find(from);
458  bool didDisconnect = false;
459  if (!to)
460  {
461  // We are removing all arcs to/from "from".
462  // First handle forward arcs from "from".
463  if (it != m_forward.end())
464  {
465  didDisconnect = true;
466  if (BidirIndex::value)
467  {
468  for (const auto& other : it->second)
469  {
470  // Remove "from" from all of the reverse map's range.
471  m_reverse[other].erase(from);
472  if (m_reverse[other].empty())
473  {
474  m_reverse.erase(other);
475  }
476  }
477  }
478  // Remove "from" from the forward map's domain.
479  m_forward.erase(it);
480  }
481  if (std::is_same<FromType, ToType>::value && BidirIndex::value)
482  {
483  auto rit = m_reverse.find(reinterpret_cast<const ToType*>(from));
484  if (rit != m_reverse.end())
485  {
486  didDisconnect = true;
487  for (const auto& other : rit->second)
488  {
489  // Remove "from" from all of the forward map's range.
490  m_forward[reinterpret_cast<const FromType*>(other)].erase(
491  reinterpret_cast<const ToType*>(from));
492  if (m_forward[reinterpret_cast<const FromType*>(other)].empty())
493  {
494  m_forward.erase(reinterpret_cast<const FromType*>(other));
495  }
496  }
497  // Remove "from" from the reverse map's domain.
498  m_reverse.erase(rit);
499  }
500  }
501  return didDisconnect;
502  }
503  // We are only removing the single arc from → to.
504  if (it != m_forward.end())
505  {
506  didDisconnect = it->second.erase(to) > 0;
507  if (didDisconnect && BidirIndex::value)
508  {
509  // TODO: Check that this returns > 0:
510  m_reverse[to].erase(from);
511  if (m_reverse[to].empty())
512  {
513  m_reverse.erase(to);
514  }
515  }
516  }
517  else if (std::is_same<FromType, ToType>::value && !Directed::value)
518  {
519  // We may have stored this arc as to → from.
520  if (BidirIndex::value)
521  {
522  auto rit = m_reverse.find(reinterpret_cast<const ToType*>(from));
523  if (rit != m_reverse.end())
524  {
525  didDisconnect = rit->second.erase(reinterpret_cast<const FromType*>(to)) > 0;
526  if (didDisconnect)
527  {
528  m_forward[reinterpret_cast<const FromType*>(to)].erase(
529  reinterpret_cast<const ToType*>(from));
530  if (m_forward[reinterpret_cast<const FromType*>(to)].empty())
531  {
532  m_forward.erase(reinterpret_cast<const FromType*>(to));
533  }
534  }
535  }
536  }
537  else
538  {
539  it = m_forward.find(reinterpret_cast<const FromType*>(to));
540  if (it != m_forward.end())
541  {
542  didDisconnect = it->second.erase(reinterpret_cast<const ToType*>(from)) > 0;
543  if (didDisconnect && it->second.empty())
544  {
545  m_forward.erase(it);
546  }
547  }
548  }
549  }
550  return didDisconnect;
551  }
553 
554 protected:
555  std::unordered_map<const FromType*, std::unordered_set<const ToType*>> m_forward;
556  std::unordered_map<const ToType*, std::unordered_set<const FromType*>> m_reverse;
557 };
558 
559 } // namespace graph
560 } // namespace smtk
561 
562 #endif // smtk_graph_ExplicitArcs_h
smtk
The main namespace for the Simulation Modeling Tool Kit (SMTK).
Definition: doc.h:33
smtk::common::Visit::Halt
@ Halt
Stop visiting items immediately.
smtk::graph::ExplicitArcs::visitAllOutgoingNodes
smtk::common::Visited visitAllOutgoingNodes(Resource rr, Functor ff) const
Visit every node which has outgoing arcs of this type.
Definition: ExplicitArcs.h:59
smtk::common::Visited::All
@ All
The visitor was invoked on every item exhaustively.
smtk::graph::ExplicitArcs::visitAllIncomingNodes
smtk::common::Visited visitAllIncomingNodes(Resource rr, Functor ff) const
Visit every node which has incoming arcs of this type.
Definition: ExplicitArcs.h:104
smtk::common::Visited::Empty
@ Empty
The were no values to visit.
smtk::graph::ExplicitArcs::inVisitor
smtk::common::Visited inVisitor(const ToType *node, Functor ff) const
Visit incoming arcs to a node.
Definition: ExplicitArcs.h:211
smtk::graph::ExplicitArcs::connect
std::enable_if<!MM, bool >::type connect(const FromType *from, const ToType *to, const FromType *beforeFrom=nullptr, const ToType *beforeTo=nullptr)
Insert an arc from from to to, optionally ordered by beforeFrom and beforeTo.
Definition: ExplicitArcs.h:360
smtk::negation
A "polyfill" for std::negation, introduced in c++17.
Definition: Metaprogramming.h:62
smtk::common::UUID
Definition: UUID.h:38
smtk::disjunction
True when any template parameter is "truthy".
Definition: Metaprogramming.h:47
smtk::graph::ExplicitArcs::outDegree
std::size_t outDegree(const FromType *node) const
Return the number of outgoing arcs from the node.
Definition: ExplicitArcs.h:300
smtk::graph::ArcProperties::isMutable
Check whether the arc traits object (1) is implicit and has methods to insert and remove arcs; or (2)...
Definition: ArcProperties.h:253
smtk::graph::ArcProperties
Checks that can be performed on arc trait-types.
Definition: ArcProperties.h:42
smtk::graph::ExplicitArcs::outVisitor
smtk::common::Visited outVisitor(const FromType *node, Functor ff) const
Visit outgoing arcs from a node.
Definition: ExplicitArcs.h:149
smtk::graph::ExplicitArcs::disconnect
std::enable_if<!MM, bool >::type disconnect(const FromType *from, const ToType *to)
Remove an arc from from to to, optionally ordered by beforeFrom and beforeTo.
Definition: ExplicitArcs.h:443
smtk::common::Visited
Visited
Return value for functions/methods that accept visitors.
Definition: Visit.h:35
smtk::graph::unconstrained
constexpr std::size_t unconstrained()
Return a constant used to indicate the maximimum degree of an arc endpoint is unconstrained.
Definition: ArcProperties.h:29
smtk::graph::ExplicitArcs::contains
bool contains(const FromType *from, const ToType *to) const
Return true if an arc exists between from and to.
Definition: ExplicitArcs.h:271
Visit.h
smtk::graph::ExplicitArcs::inDegree
std::size_t inDegree(const ToType *node) const
Return the number of incoming arcs to the node.
Definition: ExplicitArcs.h:325
smtk::graph::ExplicitArcs
A wrapper around arc type-traits classes that provides explicit storage of arcs.
Definition: ExplicitArcs.h:31
smtk::common::Visited::Some
@ Some
A visitor signaled early termination.
smtk::graph::Resource
A resource for conceptual modeling of geometric components.
Definition: PublicPointerDefs.h:59
smtk::common::VisitorFunctor
A template for accepting visitors with different return types.
Definition: Visit.h:56