commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marco.speranz...@gmail.com>
Subject Re: [Graph] Graph connectivity algo
Date Mon, 30 Jan 2012 22:42:14 GMT
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 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
> 


Ciao Claudio,

I attached a patch into jira (SANDBOX-348) 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/





Mime
View raw message