Working with HiddenEdgeSet

[Arman Mohseni Kabir]

I want to randomly choose a node from the graph and restore all the hidden edges of that node form the HiddenEdgeSet. I would be grateful if you could help me. 

Also, how can I randomly choose an edge from the HiddenEdgeSet and restore it in the original graph?

Thank You,

Arman

[Stephan Beyer]

Hi,

On 05/02/2018 04:44 PM, Arman Mohseni Kabir wrote:
> I want to randomly choose a node from the graph

You can use graph.chooseNode(); but it is not suited for every
use-case (because it needs linear time).

> and restore all the
> hidden edges of that node form the HiddenEdgeSet. I would be
> grateful if you could help me.

I am not sure if there is builtin functionality for that.

However, you can maintain a

NodeArray<List<edge>> hiddenIncidentEdges{graph};

that contains a list of incident hidden edges for each node.
So always when you hide an edge e, you also have to do add it to the
lists:

hiddenIncidentEdges[e->source()].pushBack(e);
hiddenIncidentEdges[e->target()].pushBack(e);

Then when you want to restore all incident edges of v, simply do

for (edge e : hiddenIncidentEdges[v]) {
hiddenEdges.restore(e);
hiddenIncidentEdges[e->source()].removeFirst(e);
hiddenIncidentEdges[e->target()].removeFirst(e);
}

Note again that List::removeFirst() needs linear time.

> Also, how can I randomly choose an edge from the HiddenEdgeSet and
> restore it in the original graph?

Again I am not sure if there is builtin functionality for that
but you can manually maintain a list of all hidden edges and choose
a random member.

Note that the original purpose of the hidden edges is to temporarily
hide edges and let an auxiliary algorithm run on the graph without
these edges. Afterwards all hidden edges are restored.

Your need to restore edges selectively sounds to me like
HiddenEdgeSet is not the right tool. Instead, you probably want to
use a GraphCopy of a graph that you createEmpty() and then
selectively add edges from the original graph. I hope the reference
documentation for GraphCopy will help you.

Best
Stephan

[Arman Mohseni Kabir]

I appreciate your elaborate response. 

Here is what I want to do, I would really appreciate if you could direct me to the most efficient way of doing this.

I want to hide/delete all the edges/nodes in the graph while keeping a copy of all of them.  Then I want to randomly select these deleted/hidden nodes/edges, add them to the original graph and compute the respective bicomponents and tricomponents (using dynamic algorithms in ogdf) of the resulting graph. I want to do it until the original graph is restored. 

I would really appreciate your help.

Also, this part of your code gives me a segmentation fault. Maybe it is because we are removing things from the list in a for loop.