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 depthfirst or breadthfirst
>>>> 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 SANDBOX348
cool, go ahead :)
Throwing ideas:
As a zerocost 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
Email address: squarcel@dia.uniroma3.it
Phone: +390657333215
Fax: +390657333612
http://www.dia.uniroma3.it/~squarcel

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
