Nodes and Arcs ============== The graph session has been designed to accommodate a broad range of use cases, including situations where the graph's arc data exist in an external modeling kernel and are "discovered" as they are accessed. This level of flexibility is achieved by using generic programming principles to describe the graph's node and arc types and API, while recovering compile-time type safety using the graph resource's traits class that lists its available nodes and arcs. The relationship between nodes and arcs is modeled using a generic accessor pattern, where the nodes are the first-class elements of the graph and the arcs augment the nodes' API to access neighboring nodes. To declare the node and arc types a resource accepts, define a graph-traits class with type-aliases named ``NodeTypes`` and ``ArcTypes`` that are ``std::tuple`` objects listing types for nodes (which must inherit :smtk:`smtk::graph::Component`) and arcs (which must provide type-aliases described below), respectively. .. literalinclude:: ../../../smtk/graph/testing/cxx/TestArcs.h :language: c++ :start-after: // ++ 1 ++ :end-before: // -- 1 -- :linenos: Although not present in the example above, you may also provide a type-alias named ``NodeContainer`` that names the type of container the resource should use to hold references to its nodes. If present, the ``NodeContainer`` class will be publicly inherited by your resource, making its storage available as you see fit. By default, :smtk:`smtk::graph::NodeSet` is used, which is simply a set of shared-pointers to components. You may wish to consider the boost multi-index container as an alternative, since it may be indexed by node type (a common query). In that case, see the NodeSet API required for custom storage. The type-traits class, such as the ``ExampleTraits`` class above, is used by several templated classes to compose implementations of methods used to access nodes and arcs in resources and components as shown below. We will cover these in more detail in the following sections. .. findfigure:: graph-arcs-decoration.* :align: center :width: 95% How graph-traits type-aliases are processed with templates into actual node and arc implementations. In most cases, you will not need to implement storage for arcs. Nodes ----- As the first-class element of the graph structure, :smtk:`Component ` (and types that derive from it) have access to the parent resource and node id. The remainder of its API (``outgoing()``, ``incoming()``, ``set()``, and ``get()``) exists to provide access to other nodes related by arc types as described below. Graph components (nodes) do not store arcs themselves – they expose arcs from their parent resource. This separation of API implementation from the node to the arc facilitates the traversal of arcs or sets of arcs with different storage layouts without modifying the node class description. Note that, unlike arcs – whose storage is segregated by type – nodes must be globally indexed (by UUID at a minimum). Otherwise we would use the same storage pattern that arcs use. You can specify a type-alias, named ``Serializable`` on a node type indicating you would like it to be serialized when saving the resource. Otherwise, nodes are not serialized to file. Arcs ---- As mentioned above, any class (or struct; we'll use class here for simplicity) may describe a type of arc; inheriting a common base class is not required. Instead, arc classes are used as type-traits objects that specify how arcs behave via type-aliases and class-static methods. Note that each type of arc is responsible for storing *all* arcs of that type for the entire resource. This table summarizes the type-aliases available (some of which are mandatory): .. list-table:: Type aliases for graph-arc objects. (☑ = mandatory; ☐ = optional) :widths: 10 5 35 :header-rows: 1 * - Type alias - ☐/☑ - Description * - ``FromType`` - ☑ - The type of node serving as the source (origin) of the arc. * - ``ToType`` - ☑ - The type of node serving as the destination (end) of the arc. * - ``Directed`` - ☑ - True (``std::true_type``) or false (``std::false_type``) indicating whether the arcs are directed (true) or undirected (false). * - ``ForwardIndexOnly`` - ☐ - If present and true (``std::true_type``), it indicates that no method exists to discover connected nodes given a destination node (i.e., you may only visit, count, or test connections from outgoing (source) nodes). When this type-alias is absent, bidirectional indexing is presumed. In that case, you must provide an ``inVisitor`` method as described below. This tag is unsupported and will cause an assertion at compile time if the arc type is undirected. * - ``Immutable`` - ☐ - If present and true, this mark forces the arc editing methods on the :smtk:`smtk::graph::ArcImplementation` to have no effect (and always return false), even if the traits class provides ``connect`` and ``disconnect`` methods. This is mainly intended for explicit arcs that should not allow user editing. (In this case, the resource might provide methods to use the underlying :smtk:`smtk::graph::ExplicitArcs` API in a way that enforces model consistency.) * - ``Ordered`` - ☐ - If present, this must be true (``std::true_type``), indicating that, when multiple arcs terminate at the same node, the order in which they are traversed is significant. This is used, for example, in CAD boundary-representation models to order the edges bounding a face loop. Assuming the arc's FromType is a ``Face`` and the ToType is an ``Edge``, then the order of edges reported by the outVisitor method (see below) is required to link the edges head-to-tail. Similarly, faces reported by the inVisitor method (see below), is frequently used to determine whether a given edge is oriented along the loop or opposing the loop direction. If present on explicit arcs, additional indexes are created in the arc container to preserve these orderings. Arcs may be explicit (meaning the resource holds pairs of node UUIDs representing each arc as part of its storage) or implicit (meaning that arcs are generated procedurally). An example use of implicit arcs is the OpenCascade session whose nodes form the boundary-representation (B-Rep) of a CAD model. The arcs are not stored by SMTK but instead are obtained by calling methods on the OpenCascade modeling kernel. Explicit arcs are the simplest to declare because SMTK provides a default implementation for you (using :smtk:`smtk::graph::ExplicitArcs`). For example: .. literalinclude:: ../../../smtk/graph/testing/cxx/TestArcs.h :language: c++ :start-after: ++ 2 ++ :end-before: -- 2 -- :linenos: is all that's required. SMTK will insert an instance of ExplicitArcs into the resource's ArcMap for you; when users create or remove ``ExplicitArc`` arcs between nodes, an instance of ``ExplicitArcs`` in the resource's arc map is edited. (NB: The ``ExplicitArcs`` instance is not stored directly; we will discuss that further in :ref:`smtk-graph-arc-implementation`). Beyond the type aliases above, several class-static member variables and methods may also be present in the arc-traits class if you wish to avoid explicitly storing arcs in the resource. .. list-table:: Constants and methods for graph-arc traits-type objects :widths: 25 25 :header-rows: 1 * - Member/method - Description * - ``std::size_t MaxOutDegree`` - The maximum number of arcs of this type that any ``FromType`` node may have (i.e., the maximum number of outgoing arcs of this type). A value of smtk::graph::unconstrained() allows any number of attached nodes. This value is used as a hard constraint by the ExplicitArcs class. * - ``std::size_t MaxInDegree`` - The maximum number of arcs of this type that any ``ToType`` node may have (i.e., the maximum number of incoming arcs of this type). A value of smtk::graph::unconstrained() allows any number of attached nodes. This value is used as a hard constraint by the ExplicitArcs class. * - ``std::size_t MinOutDegree`` - The minimum number of arcs of this type that any ``FromType`` node may have (i.e., the minimum number of outgoing arcs of this type). A value of 0 (the default) means there is no constraint. This is not currently enforced or validated. * - ``std::size_t MinInDegree`` - The minimum number of arcs of this type that any ``ToType`` node may have (i.e., the minimum number of incoming arcs of this type). A value of 0 (the default) means there is no constraint. This is not currently enforced or validated. * - ``smtk::graph::OwnershipSemantics Semantics`` - Whether one arc endpoint should prevent the other endpoint from removal. A value of None (the default) means neither endpoint owns the other. The Delete operation uses this to prevent deletions of nodes being "possesively referenced" by other nodes. * - ``template smtk::common::Visited outVisitor(const FromType* node, Functor ff) const`` - A method (usually templated on ``Functor`` type) that invokes the given functor with each destination (``ToType*``) connected to the given input node. The Functor is usually templated to allow (but not require) a return value to cause early termination. If this method is not provided, the arc is assumed to be explicit and an implementation will be provided for you. * - ``template smtk::common::Visited inVisitor(const ToType* node, Functor ff) const`` - A method (usually templated on ``Functor`` type) that invokes the given functor with each source (``FromType*``) connected to the given input node. The Functor is usually templated to allow (but not require) a return value to cause early termination. This method is only required on implicit arcs, and only if the ForwardIndexOnly trait is absent or false. * - ``template smtk::common::Visited visitAllOutgoingNodes(Functor ff) const`` - A method (usually templated on ``Functor`` type) that invokes the given functor on each node that has outgoing arcs. This, along with the ``outVisitor`` method above, can be used to iterate over all undirected arcs. When combined with visitAllIncomingNodes and inVisitor, then all directed arcs can be traversed efficiently. This method is optional and recommended only for implicit arcs. If you do not provide an implementation, then ArcImplementation will generate a slow version which traverses every node in the resource to identify those that may have outgoing arcs. * - ``template smtk::common::Visited visitAllIncomingNodes(Functor ff) const`` - A method (usually templated on ``Functor`` type) that invokes the given functor on each node that has incoming arcs. This method is optional and recommended only for implicit arcs. If you do not provide an implementation, then ArcImplementation will generate a slow version which traverses every node in the resource to identify those that may have incoming arcs. * - ``bool contains(const FromType* from, const ToType* to) const`` - A method that returns true if an arc of this type exists between the given from and to nodes. For undirected arcs whose FromType and ToType are identical, this method must return the same value given either (from, to) or (to, from). If this method is not provided, an implementation that uses outVisitor will be provided (but this is to be avoided if possible since it will not be efficient). * - ``bool connect(const FromType* from, const ToType* to, const FromType* beforeFrom = nullptr, const ToType* beforeTo = nullptr)`` - Insert an arc given its endpoint nodes and, optionally, a second pair of nodes specifying the the insertion location of each endpoint. The optional second set of (pre-existing) nodes is only used when the Ordered type-alias exists on this arc. If this method is not present on an implicit arc, insertion is impossible (i.e., the arcs are read-only). In this case, the decorated arc object will include an implementation of this method that always returns false so that users do not need to test for its existence. * - ``bool disconnect(const FromType* from, const ToType* to)`` - Remove an arc given its endpoint nodes. If this method is not present on an implicit arc, removal is impossible. In this case, the decorated arc object will include an implementation of this method that always returns false so that users do not need to test for its existence. A simple example of an arc out-node visitor from the ``TestArcs`` example is here: .. literalinclude:: ../../../smtk/graph/testing/cxx/TestArcs.h :language: c++ :start-after: // ++ 3 ++ :end-before: // -- 3 -- :linenos: Note that the example above is contrived for the purpose of testing. If only the ``outVisitor`` method is provided, then the resulting implicit arc will only be traversible in the forward direction (i.e., given a ``FromType`` node, visit its ``ToType`` nodes) and will be immutable – meaning that no arcs may be added or removed by users. (Generally, this means that the arcs are managed by a third party library that only allows arcs to be added or removed in patterns consistent with their modeling intent.) If you do not provide an ``outVisitor`` and (for bi-directionally indexed arcs) an ``inVisitor`` method, an explicit arc will be created. If the ``connect`` method is present for an *explicit* arc, then it will be called by the explicit arc's ``connect()`` method as a run-time check that an arc is allowed. No run-time checks are allowed for disconnection at this time. Arc-trait properties -------------------- SMTK provides an :smtk:`ArcProperties ` template that can be used to examine traits objects. It is used internally to decide how to decorate each arc's traits into a class that provides a complete implementation (described in the next section) of all the accessor and editor methods needed. You can and should use this class when writing logic to analyze arcs. It is important to understand that there are generally two different types you might pass as template parameters to the arc properties class: + the user-provided arc traits class (in which case the returned properties describe what the user has passed to the :smtk:`ArcImplementation `); or + the computed arc-storage object (i.e., ``detail::SelectArcContainer``), in which case the returned properties describe :smtk:`smtk::graph::ExplicitArcs` templated on the user-provided arc traits class. Generally, you will want to pass the user-provided traits but there are times you may wish to identify methods implemented by the arc-storage object. .. _smtk-graph-arc-implementation: Arc-trait decoration -------------------- Since arc classes are not required to implement all of the methods described above, SMTK provides the :smtk:`ArcImplementation ` class templated on your traits class. The arc implementation template is responsible for + providing a complete and consistent set of methods for examining and editing arcs of one type; + holding an instance of some object (either your ``ArcTraits`` class or :smtk:`ExplicitArcs\ `) that stores or fetches arcs on demand; and + providing interface objects (see :ref:`smtk-graph-endpoint-interface`) for graph components to expose. The storage that arc implementations use is selected by the :smtk:`SelectArcContainer ` template. This template selects either the arc traits-class itself for storage (in the case of implicit arcs where the traits-class implements methods as needed) or one of SMTK's explicit arc-storage classes. .. _smtk-graph-endpoint-interface: Arc endpoints ------------- You may have noticed that the arc-traits objects have an API that is functional but not necessarily easy to use. The arc implementation object also provides "endpoint interface" objects (:smtk:`ArcEndpointInterface `) that behave as containers for all the nodes attached at one endpoint by arcs of the given type. The endpoint interface classes hold a reference to a single component and provide access to nodes at the other end of arcs of the given type. When the arc is mutable and the component is not const-referenced, then methods are available to connect and disconnect nodes to the subject endpoint. Arc direction and indexing -------------------------- SMTK's implementation of an abstract graph involves adapting the mathematical description of a graph to an implementation in the C++ language. In order for the implementation to be consistent and efficient, there are some places where the theoretical and practical implementations differ. + Graph theory is not typically concerned with the computational complexity of queries, but our implementation must be. Indexing nodes in a large graph consumes memory, so SMTK allows arcs to be stored without data structures to traverse arcs in their "reverse" direction (i.e., from ``ToType`` nodes to ``FromType`` nodes). This indexing is **independent** of whether the arcs are considered directed or not. + When a graph is undirected and the nodes at each endpoint are of the same type (i.e., ``std::is_same`` is true), then visiting the incoming arcs is identical to visiting the outgoing arcs. If you visit both the outgoing and incoming arcs incident to a node, you will iterate over all the (undirected) arcs twice. In this case, it is also important to note that constraints on the in-degree and out-degree must be identical – ``MaxOutDegree`` must be equal to ``MaxInDegree`` – since the same arc between nodes A and B may be stored as (A, B) or (B, A). + When a graph is undirected but requires nodes of different types at each endpoint, traversing the graph will require you to call both the incoming and outgoing arc visitors. This is because the C++ callbacks for visiting nodes connected by arcs of these types must be passed a pointer to the proper node type.