commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <>
Subject Re: [Graph] Graph connectivity algo
Date Mon, 30 Jan 2012 14:33:03 GMT

On 30/01/2012 09:51, Marco Speranza wrote:
> Claudio Squarcella<squarcel<at>>  writes:
>> On 27/01/2012 12:47, Claudio Squarcella wrote:
>>> Hello,
>>> On 27/01/2012 12:35, Marco Speranza wrote:
>>>> Hi all,
>>>> I'm trying to implement the Boruvka's algorithm and I need to know is a
>>>> grah is connected or not.
>>>> So I'd like to propose a simple algorithm to do that.
>>>> A simple way to implement that is run a depth-first or breadth-first
>>>> search
>>>> starting from an arbitrary vertex. If the number of the vertices touched
>>>> are the same of the origina graph, the graph is connected.
>>> cool, go for it
>>>> Moreover the algorithm could count the number of che "connected
>>>> componet" (
>>> well you get that number if you actually map each vertex to a
>>> connected component, which means you could need to run the search
>>> algorithm more than once.
>>> As a unified solution maybe we could go for an algorithm that returns
>>> the connected components as a collection of graphs, and then in your
>>> case you just check that there is only one connected component.
>> ...and of course also the simplified version "give me the connected
>> component containing the input vertex", which suits your case better and
>> does not waste resources.
>> Claudio
>>> Ciao
>>> Claudio
>>>> what do you think about that?
>>>> Ciao
>>>> -- 
>>>> Marco Speranza<marco.speranza79<at>>
>>>> Flick photostream:
>>>> Google Code:
> hi Claudio,
> thanks for your tips. This week I implemented a simple algo that uses the Depth
> First Search to find the connected component.
> The algo finds the connected components for all vertices or only for an provided
> set of vertices (in order to find only the connected components that contain
> these vertices).
> I created the patch, if you agree I can attach that into the issue SANDBOX-348

cool, go ahead :)

Throwing ideas:
As a zero-cost improvement you could add one more "shortcut" allowing 
for a single Vertex to be specified as input, since that sounds like a 
reasonable use case. Also, the same code could be used to provide 
another utility method that checks whether there is at least a path 
between two input vertices.

Ciao and thanks,

> Ciao
> Marco

Claudio Squarcella
PhD student at Roma Tre University
E-mail address:
Phone: +39-06-57333215
Fax: +39-06-57333612

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message