# Graph resources where arcs have inverses
**URL:** https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760
**Category:** Design
**Created:** [January 22, 2022, 9:52pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760 "2022-01-22T21:52:33Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@dcthomp](https://discourse.kitware.com/u/dcthomp)
#### Post date: [January 22, 2022, 9:52pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/1 "2022-01-22T21:52:33Z")
# 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:
```c++
class Members : public smtk::graph::arcs::Arcs { };
class ParentGroup : public smtk::graph::arcs::Arc { };
```
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:
```c++
class Membership :
public smtk::graph::arcs::BidirectionalArc<
One,
Many
>
{ };
```
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:
```c++
class Members
: public smtk::graph::arcs::Arcs
{ };
class ParentGroup
: public smtk::graph::arcs::Arc
{ };
```
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).
```c++
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:
```c++
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
```c++
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&)
{
// 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?
---
### Author:  [@Ryan\_Krattiger](https://discourse.kitware.com/u/Ryan_Krattiger)
#### Post date: [January 24, 2022, 5:21pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/2 "2022-01-24T17:21:16Z")
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.
```auto
struct FooArc : smtk::graph::Arc
{
using arc_type = smtk::graph::BidirectionalArc;
};
struct BarArc : smtk::graph::Arc
{
using arc_type = smtk::graph::BidirectionalArc;
};
```
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.
---
### Author:  [@dcthomp](https://discourse.kitware.com/u/dcthomp)
#### Post date: [January 24, 2022, 7:53pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/3 "2022-01-24T19:53:39Z")
@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:
```auto
class GroupMembers : public Arcs
{
public:
using ArcTraits = Inverse;
};
class ParentGroup : public Arc
{
public:
using ArcTraits = Inverse;
};
std::shared_ptr g1, g2;
std::shared_ptr n1, n2;
```
Now, creating/remove either type of relationship must force the other:
```auto
// Automatically calls g1->get().insert(n1):
n1->get() = g1;
// Automatically calls g1->get().erase(n1):
n1->get() = nullptr;
```
but note that `n1->get()` 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,
```auto
// Automatically calls n2->get() = g2;
g2->get().insert(n2);
// Automatically calls n2->get() = nullptr;
g2->get().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.
---
### Author:  [@Ryan\_Krattiger](https://discourse.kitware.com/u/Ryan_Krattiger)
#### Post date: [January 24, 2022, 10:05pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/4 "2022-01-24T22:05:34Z")
If this is the path to go down, it would be beneficial to enforce that only `graphResource->{add,remove}(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.
```auto
{
return this->removeImpl(arc, ParentGroup::AcrTraits())
}
// Remove an arc that has an inverse
template
bool removeImpl(Arc& arc, Inverse)
{
auto from = arc->from();
for (auto& to : arc->to())
{
from->get()->erase(to);
to->get()->erase(from);
}
}
// Remove and arc that does not have an inverse
template
bool removeImpl(Arc& arc, Tag)
{
auto from = arc->from();
for (auto& to : arc->to())
{
from->get()->erase(to);
}
}
```
---
### Author:  [@dcthomp](https://discourse.kitware.com/u/dcthomp)
#### Post date: [January 25, 2022, 2:54am UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/5 "2022-01-25T02:54:01Z")
> [@Ryan\_Krattiger](#):
>
> If this is the path to go down, it would be beneficial to enforce that only `graphResource->{add,remove}(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
```c++
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
```c++
template
class ArcWrapper
{
public:
ArcWrapper(const ArcWrapper&) = 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 get(const FromType& lhs);
};
```
@Ryan_Krattiger Am I missing something?
---
### Author:  [@Ryan\_Krattiger](https://discourse.kitware.com/u/Ryan_Krattiger)
#### Post date: [February 14, 2022, 8:31pm UTC](https://discourse.kitware.com/t/graph-resources-where-arcs-have-inverses/760/6 "2022-02-14T20:31:11Z")
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.
```auto
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 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`.
```auto
namespace smtk::graph
{
template <>
struct Inverse /* 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;
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;
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`.