Easy erase in list graphs

[Balazs Dezso]

The arcs and nodes might be able to erase during an iteration very easy way in the list and smart graph implementations. If an iterator points to an arc or a node, and the item is deleted, then the increment should be valid operation until other change occurred on the graph. Of course, accessing such iterator should be avoided.

[Alpar Juttner]

Replying to deba:

The arcs and nodes might be able to erase during an iteration very easy way in the list and smart graph implementations.

I can't understand how do you want to erase anything from a SmartGraph.

[Peter Kovacs]

Replying to alpar:

I can't understand how do you want to erase anything from a SmartGraph.

Neither nodes nor arcs can be removed from Smart(Di)graph structures. So let's consider List(Di)graph classes.

I think, "easy erase" can be used when arcs are removed from a digraph using ArcIt or OutArcIt iterators. However, arcs cannot be deleted using InArcIt and nodes cannot be deleted using NodeIt, since the next pointer of a removed node and the next_in pointer of a removed arc is used for storing a list of free items in the vectors. Thus we lose the original information which would be needed for the ++ operator of the iterator.

However, I could imagine such a List(Di)graph implementation in which the node/arc iteration would be performed by enumerating all elements of the corresponding vector and skipping the invalid ones (that are not used currently). I guess that it could be singificantly faster if most of the elements are used in the vectors, but it could be slower otherwise. Moreover, the easy erase would not be a problem using this method.

[Alpar Juttner]

Replying to kpeter:

However, I could imagine such a List(Di)graph implementation in which the node/arc iteration would be performed by enumerating all elements of the corresponding vector and skipping the invalid ones (that are not used currently). I guess that it could be singificantly faster if most of the elements are used in the vectors, but it could be slower otherwise. Moreover, the easy erase would not be a problem using this method.

This is a different story. I think Balazs meant one of the following solutions:

1. The iterator structure (probably not the default one) may contain pointer not only to the current item but also to the following one. Then operator++ could use this field instead of accessing the item's "next" pointer. This approach may suffer from running time penalties, but I have a feeling that the compiler will highly optimize it when using in simple for cycles.
2. The "deleted status" of an element could be indicated in one of the prev* fields instead of the next_? one. In this way the pointer to the following item is available even if the current one has been deleted. I can't see efficiency problems in this case. The drawback of this approach is that adding a new item will overwrite the deleted current item thus will destroy the linkage data, too.

[Peter Kovacs]

Replying to alpar:

This is a different story.

I know. It is just one of my old ideas which could be tested. I just rembered it while I was reading this ticket, that's why I proposed it here. :)

I think Balazs meant one of the following solutions:

1. The iterator structure (probably not the default one) may contain pointer not only to the current item but also to the following one. Then operator++ could use this field instead of accessing the item's "next" pointer. This approach may suffer from running time penalties, but I have a feeling that the compiler will highly optimize it when using in simple for cycles.

I find this soultion good, but the performance should be tested.

2. The "deleted status" of an element could be indicated in one of the prev* fields instead of the next_? one. In this way the pointer to the following item is available even if the current one has been deleted. I can't see efficiency problems in this case. The drawback of this approach is that adding a new item will overwrite the deleted current item thus will destroy the linkage data, too.

It is not so easy, since the prev pointer is also used for indicating the validity of a node or arc. I think, we should introduce a new value for each node and arc to implement this idea, e.g. a bool flag indicating validity. This seems to be the major drawback here.

[Balazs Dezso]

Replying to kpeter:

Replying to alpar:

This is a different story.

I know. It is just one of my old ideas which could be tested. I just rembered it while I was reading this ticket, that's why I proposed it here. :)

I think Balazs meant one of the following solutions:

1. The iterator structure (probably not the default one) may contain pointer not only to the current item but also to the following one. Then operator++ could use this field instead of accessing the item's "next" pointer. This approach may suffer from running time penalties, but I have a feeling that the compiler will highly optimize it when using in simple for cycles.

I find this soultion good, but the performance should be tested.

2. The "deleted status" of an element could be indicated in one of the prev* fields instead of the next_? one. In this way the pointer to the following item is available even if the current one has been deleted. I can't see efficiency problems in this case. The drawback of this approach is that adding a new item will overwrite the deleted current item thus will destroy the linkage data, too.

It is not so easy, since the prev pointer is also used for indicating the validity of a node or arc. I think, we should introduce a new value for each node and arc to implement this idea, e.g. a bool flag indicating validity. This seems to be the major drawback here.

In my point of view it is quite easy. For deleted nodes the following values must be set:

• next remains as the original
• prev set to -2
• first_out is the next free node (in the list of deleted nodes)

For deleted arcs the following values must be set:

• next_out remains original
• next_in remains original
• prev_out set to -2
• prev_in set to next free arc (in the list of deleted arcs)

For deleted arcs in undirected arcs:

• [n].next_out remains original
• [n|1].next_out remains original
• [n].prev_out is set to -2
• [n|1].prev_out is set to next free arc

[Peter Kovacs]

Replying to deba:

In my point of view it is quite easy.

You're right. Thank you for proposing the correct solution. Now, the only thing we have to do is to implement it. :)

[Alpar Juttner]

Replying to kpeter:

Replying to deba:

In my point of view it is quite easy.

You're right. Thank you for proposing the correct solution. Now, the only thing we have to do is to implement it. :)

As I mentioned, this solution suffer from the problem that you can't add new edges safely during the iteration. An example for this is like that

Node u, v;
for(OutArcIt a(g,u);a!=INVALID;++a)
  if(...) {
    t=g.target(a);
    ...
    g.delete(a);
    ....
    g.add(v,t);
  }

On the other hand, Solution 1 is the one that is routinely done by hand when elements have to be removed from a list. It might be somewhat slower (or not?) and needs more space, but is could be used in each and every situation. What about implementing it as an external tool like this?

for(SafeNodeIt<G> n(g);n!=INVALID;++n) {...}

Another advantage is that this can be a general tool that has to be written once but usable with any graph. Not to mention this:

for(Safe<NodeIt> n(g);n!=INVALID;++n) {...}