Prev: replacing loops to improve performance
Next: Simhydraulics modelling
From: Mohammad Tabesh on 23 Jun 2010 16:47
Hi all,

I need to check if removing a node causes fragmentation in an undirected graph?

I now remove the node temporarily and calculate the shortest paths between all adjacent nodes. If any of the paths does not exist, it means the node causes fragmentation.

This check is done in every step of my algorithm and the speed and resources consumed is of importance to me. Does anyone know a better way to do the job?

Tnx
From: Darren Rowland on 24 Jun 2010 22:14
Mohammad,

Can you post some of your code so that we can see exactly what you are trying to do.

Darren
From: Mohammad Tabesh on 25 Jun 2010 02:07
Dear Darren,

The code is fairly large.
I have n nodes and an n-by-n adjacency zero-one matrix which indicates whether two nodes are connected with an arc or not (this is a common representation of an undirected graph). The graph is not fragmented (i.e. there is a path between any two arbitrary nodes).

I need to check if removing a node (setting the column and row to zero) will cause fragmentation (i.e. the graph is divided into two sub-graphs in a way that there is no path connecting the sub-graphs).

I can check all the pairs to see if there is still at least one path connecting them or not. However, this is resource consuming. Therefore, I have decided to perform this check only on the nodes adjacent to the one I removed, because the only arcs removed were connected to them. I am still looking for a more efficient method of doing the job.

Thanks for your attention.
From: us on 25 Jun 2010 02:50
"Mohammad Tabesh" <osmikh(a)yahoo.com> wrote in message <i01h2r$t91$1(a)fred.mathworks.com>...
> Dear Darren,
>
> The code is fairly large.
> I have n nodes and an n-by-n adjacency zero-one matrix which indicates whether two nodes are connected with an arc or not (this is a common representation of an undirected graph). The graph is not fragmented (i.e. there is a path between any two arbitrary nodes).
>
> I need to check if removing a node (setting the column and row to zero) will cause fragmentation (i.e. the graph is divided into two sub-graphs in a way that there is no path connecting the sub-graphs).
>
> I can check all the pairs to see if there is still at least one path connecting them or not. However, this is resource consuming. Therefore, I have decided to perform this check only on the nodes adjacent to the one I removed, because the only arcs removed were connected to them. I am still looking for a more efficient method of doing the job.
>
> Thanks for your attention.

show some code and data...

us
From: Darren Rowland on 25 Jun 2010 03:28
Mohammad,

I have found the following algorithm reference.

An algorithm for the blocks and cutnodes of a graph, K. Paton
http://portal.acm.org/citation.cfm?id=362628

A Java library featuring this algorithm is detailed in (pdf ~1.5Mb download), pg 64

gen.lib.rus.ec/get?md5=5405176d3cbc42164f3fa1645fc5a828

Basically this algorithm allows you to find the cutnodes (the nodes which will cause graph fragmentation) in one pass by conducting a Depth-First-Search.

Hth
Darren
 | 
Pages: 1
Prev: replacing loops to improve performance
Next: Simhydraulics modelling