Il giorno 30/gen/2012, alle ore 15:33, Claudio Squarcella ha scritto:
>
>
> 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
>
Ciao Claudio,
I attached a patch into jira (SANDBOX348) with my work.
that a lot for your tips ;)
ciao

Marco Speranza <marco.speranza79@gmail.com>
Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
