Opened 11 years ago

# Easy erase in list graphs

Reported by: Owned by: Balazs Dezso Alpar Juttner major core

### Description

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.

### comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

### comment:2 in reply to:  description ; follow-up:  3 Changed 10 years ago by Alpar Juttner

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`.

### comment:3 in reply to:  2 ; follow-up:  4 Changed 10 years ago by Peter Kovacs

Summary: Easy erase in list and smart graphs → Easy erase in list graphs

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.

### comment:4 in reply to:  3 ; follow-up:  5 Changed 10 years ago by Alpar Juttner

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.

### comment:5 in reply to:  4 ; follow-up:  6 Changed 10 years ago by Peter Kovacs

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.

1. 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.

### comment:6 in reply to:  5 ; follow-up:  7 Changed 10 years ago by Balazs Dezso

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.

1. 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

### comment:7 in reply to:  6 ; follow-up:  8 Changed 10 years ago by Peter Kovacs

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. :)

### comment:8 in reply to:  7 Changed 10 years ago by Alpar Juttner

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);
....
```for(SafeNodeIt<G> n(g);n!=INVALID;++n) {...}
```for(Safe<NodeIt> n(g);n!=INVALID;++n) {...}