How to build up a directed graph at compile time?

Question

I want to build a directed graph in C++11 at compile time.

Example: I have some threads and queues and want to build up:

+-------+            +---------+            +-------+
| f_gen | -> QGen -> | f_check | -> QOut -> | f_out |
+-------+            +---------+    ^       +-------+
                          |         |
                         \|/        |
                          |         |
                        QProc       |
                          |         |
                         \|/        |
                          |         |
                     +-----------+  |
                     | f_process | /
                     +-----------+

Please note that this is only an example: the solution should handle directed graphs of every node / edge type.

I want to write it maybe like:

make_directed_graph<Queue, Thread>(
// Queues
{
   // ID, Type of Queue, queue size
   { 0, std::string, 100 }, // QGen
   { 1, int, 250 },         // QProc
   { 2, std::string, 500 }  // QOut
},
// Threads
{ 
   // Fn, thread cnt, in queues, out queues
   { f_gen, 5, {}, { qref(0) } }, // ID 1: QGen 
   { f_check, 30, { qref(0) }, { qref(1), qref(2) }}, // IDs of queues
   { f_process, 75, { qref(1) }, { qref(2) }},
   { f_out, 12, { qref(2) }, {} }
});

Please note that this is just an idea - any other possibility of writing this down is fine for me.

I managed to implement a make_tree function. It can be used like

make_tree< arexp, int >(
     { '+', { 1, 2, { '*', { 3, 4, 5 } } } } )

There is one big difference here: nodes and edges can be created 'on the fly' - there is no need to reference any existing one.

The biggest problem for the directed graph is how to reference an object / structure / part which was defined earlier. Like: how to reference a queue when defining the threads (or vice verse).

My questions:

Is it possible to define a directed graph at compile time?
If so, can you please give me a hint how to implement it?

Somehow it reminds me of http://stackoverflow.com/a/2024573/396583 :) — vines, Apr 14 '14 at 11:33
You really want bigraphs and trigraphs? Beware they are an actual *feature* of C and C++. — Deduplicator, Apr 14 '14 at 11:33
Hmmmm: looks that the word 'digraph' has more than one usage: reformulated using 'directed graphs'. — Andreas Florath, Apr 14 '14 at 11:49
"Having" an arbitrary graph representation isn't the same as being able to use it for something. For metaprocessing, I would usually recommend forming the structure from function overload sets rather than pointers. But we really need to know the problem at hand. — Potatoswatter, Apr 14 '14 at 12:18
Why not just have a list of queues, and then create a number of threads that use those queues ? Why the extra effort to model it as a compile time directed graph ? — Sander De Dycker, Apr 14 '14 at 12:35
Note that a pointer is no more than the ID of a memory cell; since you cannot manipulate memory at compile-time (or at least, you are severely restricted), the simplest solution it seems would be to just use IDs. — Matthieu M., Apr 14 '14 at 13:30
@MatthieuM. : Pointers do work as non-type template arguments. — MSalters, Apr 14 '14 at 13:53
@MSalters: only pointers to global objects, which is *severely restricted*. — Matthieu M., Apr 14 '14 at 15:37
@MatthieuM. : That's rather obvious: there's no reasonable way to talk about the address of a stack variable before the stack even exists, and for a reentrant function there may even be multiple instances of that same stack variable (so no single address). — MSalters, Apr 14 '14 at 15:46
@MSalters: The reason is of course obvious, but it does not make it less restrictive :) — Matthieu M., Apr 14 '14 at 16:48
I'd really suggest looking at Boost.MSM and Boost.Statechart. While not full directed graphs, they do implement a subset of graphs. IIRC, Statechart has to go out of its way to enforce statechart-type structure and those checks can be omitted to allow you to ignore the "level" you're jumping to. To do it at compile time is going to take a lot of MPL muscle, far more than I feel like using for an SO question. — KitsuneYMG, Apr 15 '14 at 00:20
@Potatoswatter: I have only a rough idea what you are saying: can you formulate it as an answer? — Andreas Florath, Apr 16 '14 at 13:06
@MatthieuM. MSalters: Sorry I can not follow your discussion. How is this related to a possible solution? — Andreas Florath, Apr 16 '14 at 13:08
@KitsuneYMG: I'm not sure about the length of a solution. I'm dreaming of one which can be written down in some lines. — Andreas Florath, Apr 16 '14 at 13:10
@AndreasFlorath You want compile-time data structures, you have to deal with MPL. MPL is messy and long a probably takes a lot of support classes. The user would have something easy, but the plumbing is almost always exceptionally messy. — KitsuneYMG, Apr 16 '14 at 13:50

score 1 · Answer 1 · answered Apr 14 '14 at 14:01

1

It's generally possible, because you identify objects with pointers, and those pointers are valid non-type template arguments.

Queue<std::string> QGen(100); // No need for an ID, we have &QGen.
// We  *do* need to pass the Queue type to figure out the type of &QGen.
Thread<void, nullptr, std::string, &QGen> f_gen(5);

Of course, you can't define a cyclic graph this way.

answered Apr 14 '14 at 14:01

MSalters

173,980
10
155
350

Use extern to forward declare for cyclic graphs. – brian beuning Apr 16 '14 at 02:30
@brianbeuning: Won't work. Even with `extern` you need to specify the types. In this case, the types themselves would have a circular dependency. – MSalters Apr 16 '14 at 06:51
This does not answer the question: I need one directed graph (object) (as returned by 'make_directed_graph') and not a series of queues and threads. Nevertheless the answer addresses the problem of type handling / specification. – Andreas Florath Apr 16 '14 at 13:17

score 0 · Answer 2 · answered Apr 16 '14 at 12:45

I think I'm one step further to a solution (but not yet complete):

My mistake was that there is no need to directly write down the graph itself, but some kind of representation. The following source code at least compiles:

directed_graph const dg(
  make_directed_graph<Node, Edge>(
     {
        { 1, "qgen" },
        { 2, "qproc" },
        { 3, "qout" },
        { "fgen", {}, { 1 } },
        { "fcheck", { 1 }, { 2, 3 } },
        { "fproc", { 2 }, { 3 } },
        { "fout", { 3 }, {} }
     }));

Given the following definitions for make_directed_graph and the appropriate initializer_list:

class NodeRef {
public:
   NodeRef(int nid);
};

class digraph_initializer {
public:
   digraph_initializer(int id, std::string const & s);
   digraph_initializer(
      std::string const & s,
      std::initializer_list< NodeRef > const nr_in,
      std::initializer_list< NodeRef > const nr_out);
};

class directed_graph {
};

template< typename TNode, typename TEdge >
directed_graph make_directed_graph(
   std::initializer_list<digraph_initializer> const & dgi);

Still some open points:

How to ensure that edges can only be referenced when they are defined?
Build up the 'real' graph from the initializer_list at compile time.
Add template (parameters) for handling / initializing arbitrary nodes / edges.

How to build up a directed graph at compile time?

2 Answers2