commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
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>  dia.uniroma3.it>  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" (
>>>> http://en.wikipedia.org/wiki/Connected_component_(graph_theory).
>>> 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>  gmail.com>
>>>>
>>>> Flick photostream: http://www.flickr.com/photos/marcosperanza79/
>>>> Google Code: http://code.google.com/u/marco.speranza79/
>>>>
>
> 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,
Claudio

>
> Ciao
> Marco
>

-- 
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squarcel@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message