GUI should support directed graphs and multigraphs

[cardinot]

Currently, the graph widget draws all graphs as a simple and undirected graph.

It would be nice to have a way to distinguish simple graphs, digraphs and multigraphs.

For instance, a digraph should show the arrows to indicate the direction of the links as in the example below:

However, we should keep in mind that any change in the way how we draw things can drastically affect the performance of the GUI.

For instance, in the case of a multigraph, in order to change the style of a second edge, we'd have to keep track of the first edge, or "predict" that two or more edges will have to be drawn etc. So, we need to ensure that those operations do not add an extra and unnecessary cost to the simplest and most common scenario, i.e., simple undirected graph. On the contrary case, we could extend the base classes and implement an optimized version for multigraphs. Then, in the GUI, the user could choose which widget they wish to open, i.e., undirected graph style, directed style or multigraph style 😃

Thanks @Sedictious for raising this issue.

[Sedictious]

Supporting multigraphs is tricky, because the most widely used approach is to draw every edge separately . This could be implemented in evoplex in the following way:

• Add an edge
• Find out how many edges connect the selected nodes
• Calculate the "control points" of the new edges based on the edge count.
• Draw the bezier curves using the aforementioned control points

This obviously doesn't scale well since:

• You need to re-draw the edges each time you add a new one.
• Allowing curved paths will make the graphs more cluttered and messy.
• Drawing curves is slower than drawing lines.

If multigraphs are supported, we could colour-code the edges to indicate whenever more than one edge is present. We could use virtually any convergent series, to calculate the gradient of a given edge.

For example, let's say we have two nodes connected by three edges. We then calculate then gradient of the green channel using any convergent series (here we'll use the reciprocals of Triangular numbers). Here the resulting colour will be (0, 225/3 + 225/6, 0) = (0, 112.5, 0)

[cardinot]

This obviously doesn't scale well

Yes, you're right.
However, it would be interesting to allow a proper representation of this type of graph in Evoplex. Then, we could leave for the users to choose the option that better suits their needs, i.e., simpler representation with straight-lines (cheaper) and more advanced representation with curved lines (expensive).

If multigraphs are supported, we could colour-code the edges to indicate whenever more than one edge is present. We could use virtually any convergent series, to calculate the gradient of a given edge.

That's a good solution indeed. However, the problem is that we already use colours to distinguish the edge attributes (just as we do for the nodes). Another potential solution may be to set the thickness 🤔

[Sedictious]

I got this as a proof of concept for possible directed graph representation. Any thoughts?

[cardinot]

That's great @Sedictious

Any thoughts?

Yes, make sure the size of the arrow is proportional to the edge thickness; in this way, we "ensure" that things will work well when zooming in/out, or when the user manually sets the edge thickness in the graph settings.

[Sedictious]

@cardinot That sounds good! I can't push yet since the implementation is a bit hack-y, but I initially made the arrow size proportional to the edgeScale.

I don't know whether my solution is optimal, but I did get this by calculating the normal direction vector connecting the two nodes (u0, u1). I then calculated the "tip" of the arrow

float x1 = ep.second.x2() - nodeRadius * u0;
float y1 = ep.second.y2() - nodeRadius * u1;

and then a temporary point somewhere on the edge

float x2 = (x1 - m_edgeScale * u0 * c);
float y2 = (y1 - m_edgeScale * u1 * c);

All that remains for calculating the other 2 points that make up the arrow, is to rotate (x2, y2) around (x1, y1) by an angle θ. So as you can see, the arrows themselves are all defined by (x2, y2) and θ (since (x1, y1) is static) and thus are easily modifiable. I take it you want to change m_edgeScale to edge thickness (forgot the name of the variable). Also, I'm not completely sure, but I think it might be a good idea to clamp the values.

[cardinot]

The strategy looks good. However, it might be easier to give some thoughts on optimization after being able to check the whole thing.