Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Check for fragmention in a graph

Subject: Check for fragmention in a graph

From: Mohammad Tabesh

Date: 23 Jun, 2010 20:47:04

Message: 1 of 5

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

Subject: Check for fragmention in a graph

From: Darren Rowland

Date: 25 Jun, 2010 02:14:04

Message: 2 of 5

Mohammad,

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

Darren

Subject: Check for fragmention in a graph

From: Mohammad Tabesh

Date: 25 Jun, 2010 06:07:23

Message: 3 of 5

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.

Subject: Check for fragmention in a graph

From: us

Date: 25 Jun, 2010 06:50:20

Message: 4 of 5

"Mohammad Tabesh" <osmikh@yahoo.com> wrote in message <i01h2r$t91$1@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

Subject: Check for fragmention in a graph

From: Darren Rowland

Date: 25 Jun, 2010 07:28:05

Message: 5 of 5

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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us