Graph resources where arcs have inverses

[dcthomp]

Problem Statement

More often than not, when a node M in a graph resource is connected to another node N with an arc of some type T, there is also a reverse connection from N to M with an arc of type U. Thus, arc types T and U are inverses of one another. There is not currently a way to enforce the consistency of this bidirectional relationship (i.e., it is possible to remove the (M, N) arc of type T without removing the (N, M) arc of type U).

There are 2 broad classes of solution to this problem.

• Make a single arc class that handles relationships in both directions.
• Provide the existing unidirectional arc classes with information about their inverses.

Both have some common problems:

• Arcs of any type may have inverse arcs of any type (the “n-squared” problem), so there is significant combinatorial complexity when adding a new arc type – it must know how to accommodate inverses of all other arc types in the system. This also makes extensible systems difficult. Just considering the base arc types SMTK provides, we have:

  Arc Type	Inverse Arc Type	Note
  Arc	Arc	One-to-one in both directions
  Arc	Arcs	One-to-many + many-to-one
  Arcs	Arcs	One-to-many in both directions
  OrderedArcs	Arc	One-to-ordered + one-to-one
  OrderedArcs	Arcs	One-to-ordered + one-to-many
  OrderedArcs	OrderedArcs	One-to-ordered in both directions

• Updating inverse relationships may require application-specific knowledge. This is especially true for ordered arcs where there are additional constraints on how arcs are ordered relative to one another.

The question in both cases is how to provide developers with a way to

• specify how to update relationships in a consistent manner that is specific to the particular pair of arc types.
• edit arcs conveniently and consistently.

Use Cases

Groups

Group membership is often handled by a pair of arc types. The simplest case would be:

class Members : public smtk::graph::arcs::Arcs<Group, Node> { };
class ParentGroup : public smtk::graph::arcs::Arc<Node, Group> { };

However, frequently, a component may be allowed to have membership in multiple groups, so the ParentGroup arc may also subclass Arcs rather than Arc. This complicates removing a member from a group:

• In the single-group-membership case removing node N from group G must assign nullptr to that node N’s ParentGroup node (in addition to removing N from G’s membership).
• In the multiple-group-membership case, removing node N from group G must remove group G from node N’s set of parent groups.

If we instead had a single container for both arc directions we might express it like so:

class Membership :
  public smtk::graph::arcs::BidirectionalArc<
    One<Group>,
    Many<Node>
   >
{ };

The One<> and Many<> templates specialize storage to the particular type of relationships required, but now BidirectionalArc<> has 3 or 4 cases to handle (one-to-one, many-to-one, many-to-many, and possibly one-to-many depending on whether you consider it distinct).

Alternately, we could provide an inverse arc-type parameter to each of our initial unidirectional arcs:

class Members
  : public smtk::graph::arcs::Arcs<Group, Node, Inverse=ParentGroup>
{ };
class ParentGroup
  : public smtk::graph::arcs::Arc<Node, Group, Inverse=Members>
{ };

but now each arc type must either

• provide some uniform API so that inverse relationships can be updated, or
• handle each possible inverse arc type specially (and thus prevent extensibility to new inverse arc types).

Boundary Representation (BRep) Face Loops

A face loop is an ordered set of oriented edges that bound a face. Given a face and an integer index into the loop, we can get an edge (plus its orientation relative to the loop, achieved by examining which vertices are shared with neighboring arcs).

class Loop : public smtk::graph::arcs::OrderedArcs { };

Its inverse is each edge’s list of faces. Given an edge, we can obtain a list of faces that it participates in bounding:

class Faces : public smtk::graph::arcs::Arcs { };

If we remove a face, in the process of removing its arcs we should also remove references to the face in each edge participating in its boundary. Likewise, removing an edge should “break” the face loops of all attached faces.

However, in the latter case, there may be additional processing required to mark the loops as “open” rather than “closed” (say, by inserting a reference to a special edge with vertices “at infinity”). How can we provide this special processing to the arc classes?

One solution is to provide methods on the subclasses

class Loop : public smtk::graph::arcs::OrderedArcs
{
  void removeEdge(std::size_t indexOfEdge)
  {
    // Remove the edge from self, then
    // remove the face from the edge's Faces,
    // and finally insert an "edge at infinity."
  }
};
class Faces : public smtk::graph::arcs::Arcs
{
  void removeFace(const std::shared_ptr<Face>&)
  {
    // Remove the face from self and then
    // remove *all* edges from the face's Loop.
  }
};

However, now programmers must know that these specific methods must be called and know not to call the methods on the base arc classes.

Open Questions

1. Is a single, bidirectional arc class preferable to two complementary unidirectional arcs classes?
2. Is there a simple mechanism for application-specific graph resources to provide methods for editing bidirectional relationships consistently?

[Ryan_Krattiger]

Bi-directional arcs should be individual classes unless we want to change how arcs are stored, which I don’t think could be lead to much in the way of benefits overall and would be a pretty radical API change.

Instead of an extra template parameter, adding an arc trait BidirectionalArc might be better. This could give us more control on handling some of the more subtle issues that come up once rather than for each arc type. For example, the add/remove APIs can check to see if the arc is a bidirectional and the adding/removing can be done at the graph level with some tagged helper functions rather than trying to make the Arc figure out how to remove itself from the graph.

struct FooArc : smtk::graph::Arc<Foo,Bar>
{
  using arc_type = smtk::graph::BidirectionalArc<BarArc>;
};

struct BarArc : smtk::graph::Arc<Bar,Foo>
{
  using arc_type = smtk::graph::BidirectionalArc<FooArc>;
};

By default, arc_type is whatever the base arc type is, ie. Arc here.

I think if arcs provide consistent interfaces for insert, remove, and empty there should be sufficient information for the graph to handle them properly.

[dcthomp]

@Ryan_Krattiger I like using a trait type-alias, but it does greatly complicate the arc API classes; right now the API objects return a node or container of nodes directly. But If we want the current methods for manipulating arcs to work (and I do, because it’s what developers expect), we have a problem. Say we have this pair of arc types:

class GroupMembers : public Arcs<Group, Node>
{
public:
  using ArcTraits = Inverse<ParentGroup>;
};
class ParentGroup : public Arc<Node, Group>
{
public:
  using ArcTraits = Inverse<GroupMembers>;
};
std::shared_ptr<Group> g1, g2;
std::shared_ptr<Node> n1, n2;

Now, creating/remove either type of relationship must force the other:

// Automatically calls g1->get<GroupMembers>().insert(n1):
n1->get<ParentGroup>() = g1;
// Automatically calls g1->get<GroupMembers>().erase(n1):
n1->get<ParentGroup>() = nullptr;

but note that n1->get<ParentGroup>() currently returns a reference to n1's m_to member. If the user assigns a new value to it, there is no way for us to know about it. To allow the inverse to be updated, we must return a wrapper around the destination node-pointer (some object with an assignment operator that looks for the Inverse and updates it as well).

Conversely,

// Automatically calls n2->get<ParentGroup>() = g2;
g2->get<GroupMembers>().insert(n2);
// Automatically calls n2->get<ParentGroup>() = nullptr;
g2->get<GroupMembers>().erase(n2);

The same would have to happen for the containers returned by Arcs and OrderedArcs. It’s not impossible, but it would be ugly.

[Ryan_Krattiger]

If this is the path to go down, it would be beneficial to enforce that only graphResource->{add,remove}<ParentGroup>(arc); is allowed to add/remove arcs. This way, instead of the arc itself having extra code/storage to inspect back on the graph, the graph would handle enforcing arc relationships. If arc types were made friends of smtk::graph::Resource, the APIs to modify an arc could be protected to prevent misuse.

{
  return this->removeImpl(arc, ParentGroup::AcrTraits())
}

// Remove an arc that has an inverse
template <typename Arc, typename InverseArc>
bool removeImpl(Arc& arc, Inverse<InverseArc>)
{
  auto from = arc->from();
  for (auto& to : arc->to())
  {
    from->get<Arc>()->erase(to);
    to->get<InverseArc>()->erase(from);
  }
}

// Remove and arc that does not have an inverse
template <typename Arc, typename Tag>
bool removeImpl(Arc& arc, Tag)
{
  auto from = arc->from();
  for (auto& to : arc->to())
  {
    from->get<Arc>()->erase(to);
  }
}

[dcthomp]

@Ryan_Krattiger

If this is the path to go down, it would be beneficial to enforce that only graphResource->{add,remove}<ParentGroup>(arc); is allowed to add/remove arcs.

But this is not possible while retaining an intuitive API. For instance, the Arc class provides an API object with

const ToType& get(const FromType& lhs) const
{ return self(lhs).to(); }

ToType& get(const FromType& lhs)
{ return self(lhs).to(); }

Note that ToType is not a shared pointer, but a reference. We need some way to return access to a non-const version of the endpoint node. But

1. We cannot return by value (components do (or should) delete their copy constructors and it would be misleading to provide a writable copy not held by the resource).
2. We cannot tell the difference between assignment to the reference (which we must intercept) and modification of the referred object (which we want to allow but do not want to intercept).

The solution I see is to return a wrapper-object that behaves like a reference but intercepts assignment to handle inverse arc-type updates. Something like

template<typename NodeType>
class ArcWrapper
{
public:
  ArcWrapper(const ArcWrapper<NodeType>&) = default;
  ArcWrapper(NodeType& node) : m_data(node) { }

  NodeType* operator -> () const { return &m_data; }
  NodeType& operator * () const { return m_data; }

  // Handle both assignment and bidirectional arc update:
  NodeType& operator = (const NodeType& other);

protected:
  NodeType& m_data;
};

class API
{
  ArcWrapper<ToType> get(const FromType& lhs);
};

@Ryan_Krattiger Am I missing something?

[Ryan_Krattiger]

So for the stuff that seems to be working the best, arc APIs are now going to return the arc type, not the underlying container for to. This makes it so you don’t have to write multiple wrappers around the storage of the to nodes.

The basic API requirements for an arc type are to be iterable, assignable, and provide APIs for insertion and erasure that are used by the inverse handler.

** Note ** There is a second argument inverse for the insert and erase APIs. These are used to denote whether or not the API should (true) or should not (false) attempt to also perform the operation for the inverse arc. From a normal API call, these should not be specified, but in the smtk::graph::Inverse handler this argument is used as an exit condition to prevent infinite recursion and should always be false.

class ArcType
{
   using FromType = /* ... */;
   using ToType = /* ... */;
   using InverseArc = Inverse</* ... */>;

   ArcType& operator=(const ArcType& other);
   ArcType& operator=(/* ... */);

   Iterator begin();
   Iterator end();
   ConstIterator begin() const;
   ConstIterator end() const;

   // Optional
   std::pair<Iterator,bool> insert(const ToType& to, bool inverse = true);

   // Required
   std::size_t erase(const ToType& to, bool inverse = true);
};

The default behavior of operations for each type of arc type when inserted as the inverse are as follows.

Self Arc Type	Inverse Arc Type	Assign	Insert	Erase
Arc	Arc	Overwrite self, remove current inverse, insert new inverse.	Insert inverse if valid to insert self, insert self if inverse successfully inserted.	Unset self and erase inverse.
Arc	Arcs	Overwrite self, remove current inverses, insert new inverse.	Insert inverse if valid to insert self, insert self if inverse successfully inserted.	Unset self and erase inverse.
Arcs	Arc	Overwrite self, remove current inverses, insert new inverses.	Insert self, if successful insert inverse, if inverse failed remove self and report failure.	Erase inverse and self.
Arcs	Arcs	Overwrite self, remove current inverses, insert new inverses	Insert self, if successful insert inverse, if inverse failed remove self and report failure.	Erase inverse and self.
OrderedArcs	Arc	Overwrite self, remove current inverses, insert new inverses.	Insert inverse, if successful insert self.	Erase inverse and self.
OrderedArcs	Arcs	Overwrite self, remove current inverses, insert new inverses.	Insert inverse, if successful insert self.	Erase inverse and self.
Arc or Arcs	OrderedArcs	Throw std::logic_error exception.	Throw std::logic_error exception.	Erase self and first matching inverse.
OrderedArcs	OrderedArcs	Won’t compile.	Won’t compile.	Won’t compile.

All behaviors can be overwritten by providing a specialization of smtk::graph::Inverse which handles inserting and erasing behavior of an inverse to an arc type. Here is an example of providing a custom implementation for MyArcType which has an inverse that is of arc type OrderedArcs.

namespace smtk::graph
{
template <>
struct Inverse<MyArcType> /* MyArcType has an inverse that is an OrderedArcs type */
{
   // Always insert to in the back of the inverse of MyArcType, it is always successful
   bool insert(const MyArcType::ToType& from, MyArcType::FromType& to)
   {
      using InverseAPI = MyArcType::InverseArcType::template API<InverseArcType>;
      InverseAPI().get(from).insert_back(to, false
      /* false here tells the InverseArcType to not attempt to insert an inverse */);
      return true;
   }
   // Erase all of the arcs that match, not just the first one
   std::size_t erase(const MyArcType::ToType& from, const MyArcType::FromType& to)
   {
      using InverseAPI = MyArcType::InverseArcType::template API<InverseArcType>;
      std::size_t erased = 0;
      auto& toVec = InverseAPI().get(from).to();
      auto it = toVec.begin();
      while ((auto foundIt = std::find(it, toVec.end(), compareValidWeakRefsById)) != toVec.end())
      {
         it = toVec.erase(foundIt);
         erased++;
      }
      return erased;
   }
};
} // namesapce smtk::graph

Edit: Fixed some typos, removed const on to in Inverse<>::insert.