# Efficient compile-time directed graph

During my research in Rigid Body Dynamics, (where Contact Graphs are used to solve the contact problem) I came across the question if it is possible to define at compile time a directed graph (class) where each Node has a NodaDataType and each Edge has an EdgeDataType.

The graph should have the following properties:

• Heterogenous Node Data Types should be allowed, e.g. {NodeDataA, NodeDataB, NodeDataC} should result in 3 node types, node data types are unique.
• There should be a compile time map which maps each node data type to a corresponding edge data type: Something like this:

Table 1:

The edge data types do not generally need to be distinct, meaning the following symmetric table would also be feasible:

Table 2:

• Each Edge type has a pointer to a start/end node and possible to a twin edge

• Each Node type has a list of IN/OUT edges
• The graph class contains a list of all edges and nodes (possible multiple storages for each type)
• The graph should be good to handle visitors to iterate over all edges or nodes. How to achieve this is not yet clear, as depending on the implementation it might be easier or not?
• Polymorphic design for the nodes and edges by means of using virtual should be avoided, because the graph needs to be ultra fast!, no virtual table look up during runtime!

The graph should be defined completely at compile time by using templates and meta programming.

DESIGN 1

Without mentioning to much detail already about meta programming and all this madness: I started off by defining the following two classes:

template<typename TStartNodeData, typename TEndNodeData, typename TTraits  >
class Edge{
public:

using Traits = TTraits;

using EdgeData = /* get this trough the Traits class (look up in type map)*/

using StartNodeType = Node<TStartNodeData,Traits>;
using EndNodeType   = Node<TEndNodeData,Traits>;
using TwinEdge      = /* not important*/;

StartNodeType * m_startNode;
EndNodeType   * m_endNode;
TwinEdge      * m_twinEdge;

EdgeData m_data;
};

template<typename TNodeData, typename TTraits>
class Node{
public:
using Traits = TTraits;
using NodeData = TNodeData;

using OutEdgeStorageType =  /* define a std::tuple with the storages for each possible edge for this node type!*/

using InEdgeStorageType =  /* define a std::tuple with the storages for each possible edge for this node type!*/
};


The Traits class is a special class which handles all the meta programming madness, specially the compile time map mentioned above.

The problem which is inherently given by the implementation are the following:

• First if we have Table 1 or 2, the graph class needs to contain 3 different storages (e.g. std::tuple< NodeStorage< Node<NodeDataA, Traits> > .... > ), that is normal and totally fine I think. The problem come with the edges, the graph class needs 9 different storages for all edge types. This is cumbersome since with table 2 only 3 different storage types should be needed basically ...)

• Second if we have Table 1 or 2, and use the above Edge class, each Node has 3 possible storages for IN edges, and 3 possible storages for OUT edges. This is cumbersome but unavoidable if we template the Edge class for the start and end NodeDataType. But for example table 2, Node<NodaDataA,Traits> should only need one single edge storage for OUT and for IN edges, but has for example storages for OUT edges:

EdgeStorage<Edge<NodeDataA,NodeDataA,Traits>>
EdgeStorage<Edge<NodeDataA,NodeDataB,Traits>>
EdgeStorage<Edge<NodeDataA,NodeDataC,Traits>>


Note: we cannot solely have a template parameter for the EdgeDataType since is is not unique to determine at compile time the start and end node types in the Edge class, see table 2: Edge<EdgeData1,Traits> might correspond to an edge from NodeDataA -> NodeDataA or NodeDataA -> NodaDataC, thats why we templated for both start and end node data types).

DESIGN 2

We could somehow avoid the template parameter in the edge class by using a EdgeBase and also a NodeBase class like:

template<typename Traits>
class EdgeBase{
std::size_t m_type /*  type with which we can cast to the corresponding Edge<...> by the help of the Traits parameter */
}

template<typename Traits>
class NodeBase{
std::size_t m_type /*  type with which we can cast to the corresponding Node<...> by the help of the Traits parameter */
}


The Node and Edge classes would look like the following:

template<typename TEdgeData, typename TTraits  >
class Edge : public EdgeBase<Traits> {
public:
using Traits = TTraits;

using EdgeData = TEdgeData;

using StartNodeType = NodeBase<Traits>;
using EndNodeType   = NodeBase<Traits>;
using TwinEdge      = /* not important*/;

StartNodeType * m_startNode;
EndNodeType   * m_endNode;
TwinEdge      * m_twinEdge;

EdgeData m_data;
};

template<typename TNodeData, typename TTraits>
class Node : public NodeBase<Traits> {
public:
using Traits = TTraits;
using NodeData = TNodeData;

using OutEdgeStorageType =  EdgeStorage< EdgeBase<Traits> >

using InEdgeStorageType  =  EdgeStorage< EdgeBase<Traits> >;
};


The desing 2 has the following issues:

• By using base classes EdgeBase<Traits> and NodeBase<Traits>, the design simplifies a lot, because we do not determine the full type at compile time, but have then the problems during run time, since if we do some computations and also apply visitors on the graph we always need to cast the base classes to the corresponding type, (which might be fast since its a static_cast but anyway a branch on the m_type which might be done for each edge if we applied an node visitor to the graph which needs to do some work on the in and out edges, this seems stupid.

Question:

I would be interested if somebody has some deeper knowledge and some inputs where to look for such a fancy compile time graph and also which design makes more sense and also if there are better approaches to obtain the criterion mentioned at the beginning.

• I'm looking at the same problem. Did you ever make progress on this, find an existing implementation? – Catskul May 6 '17 at 17:27
• I implemented a compile time graph like the one above in GRSFramework ( I dont know anymore which design...) github.com/gabyx/GRSFramework/blob/master/common/include/GRSF/… I have not found so far any other thing like this before, and I am guessing it is probably also overkill, and the performance of it is still left to be judged by tests... – Gabriel May 13 '17 at 16:43