Change the Edge ID about evoplex HOT 4 CLOSED

It is only true if you do not have the edge object. That is, the scenario where you have two nodes and you don't know whether they are connected or not. However, this scenario might be a bit unusual... that's why I asked if you have a specific use case (I might be missing something).

I guess I should've specified how I tried to approach the problem; I found selecting the edges to be too computationally demanding and -since I assumed the graph to be simple- you simply needed drag the nodes and if there is an edge connecting them it is deleted, otherwise a new one is created. We still only need to traverse the specified node's edges, so you're probably right in that the change is unnecessary.

As this discussion goes out of the scope of the original request, I moved it to a dedicated place

Great! I'll make sure to join the discussion if I have any ideas.

from evoplex.

Hi @Sedictious, thanks for raising this issue.

Currently node IDs are added incrementally, which while not a problem for generating one-time graphs with non-variable attributes, could prove to be problematic in the long run.

Could you provide an example where it would be problematic?

The main problem is you can't easily infer the specific edge given it's ID.

Given an Edge, you can easily access their nodes. Given a Node, you can easily acess its edges and neighbours.

// a node is aware of its in/out edges
Node a;
Edges in = a->inEdges();
Edges out = a->outEdges();

// an edge is aware of its source/target nodes
Node src = edge.origin();
Node tgt = edge.neighbour();

However, if you have two arbitrary nodes, the only way to know if they are connected is by checking the edges, e.g.,

Node a, b;
// checking if a->b
for (Node neighbour : a.outEdges())
    if (neighbour == b)
        // yes, a and b are connected

Of course, this solution runs in linear time, which can be an issue if the node a has a huge number of neighbours or if the model needs to perform this type of operation very often. However, in the latter case, the modeller could consider implementing their own data structures to improve the performance of their algorithm.

Moreover, you could theoretically have the same edge with distinct IDs.

Exactly, we do that to support any kind of graph, including the ones with multiple edges.

I propose to change the way an edge's ID is generated, by providing some meaningful information about the nodes it connects, thus achieving constant-time random access. We could replace all IDs with a simple string (node1, node2), or some range-encoded integer.

In fact, it is hard to have a solution which tackles all issues. By the end, every decision will have pros and cons and the key point here is that we should (try to) ensure that the backbones of EvoplexCore will always use the simplest/lightest/fastest solution for the general case. Then, if the modeller needs to improve the performance of a specific use case, he/she is always free to use another container on top of it to map the ids etc. Does it make sense?

A few cons in your solution:

• it would drop support for multiple edges
• replacing the keys from int to string would affect drastically the performance. Strings need much more memory and are much more expensive to build and compare.

from evoplex.

Could you provide an example where it would be problematic?

I was mainly thinking about deleting edges, since the current solution requires to iterate through all the node's neighbours.

You're right though, this would drop multigraph support and complicate everything rather than simplify it. That being said, wouldn't it make sense to have some kind of visual indication for multiple edges (curved paths would probably be too computationally expensive, so maybe some sort of colour/size change)?

from evoplex.

I was mainly thinking about deleting edges, since the current solution requires to iterate through all the node's neighbours.

It is only true if you do not have the edge object. That is, the scenario where you have two nodes and you don't know whether they are connected or not. However, this scenario might be a bit unusual... that's why I asked if you have a specific use case (I might be missing something).

In any case, it worth mentioning that in Evoplex, edges and nodes will belong to a graph. The graph is aware of all nodes and edges, then operations to edit the graph are performed at a top level, i.e., in the graph class. You can check the available functions here, e.g., AbstractGraph::removeEdge.

You're right though, this would drop multigraph support and complicate everything rather than simplify it. That being said, wouldn't it make sense to have some kind of visual indication for multiple edges (curved paths would probably be too computationally expensive, so maybe some sort of colour/size change)?

Yes, that would be very interesting. 👍
As this discussion goes out of the scope of the original request, I moved it to a dedicated place: #31 Feel free to add your thoughts there. 😄

from evoplex.