You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Marco Speranza <ma...@gmail.com> on 2012/01/27 12:35:26 UTC
[Graph] Graph connectivity algo
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.
Moreover the algorithm could count the number of che "connected componet" (
http://en.wikipedia.org/wiki/Connected_component_(graph_theory).
what do you think about that?
Ciao
--
Marco Speranza <ma...@gmail.com>
Flick photostream: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
Re: [Graph] Graph connectivity algo
Posted by Simone Tripodi <si...@apache.org>.
Hi Marco!
go for it!!! Just fill an issue and provide a patch ;)
thanks for your effort,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Fri, Jan 27, 2012 at 12:35 PM, Marco Speranza
<ma...@gmail.com> 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.
>
> Moreover the algorithm could count the number of che "connected componet" (
> http://en.wikipedia.org/wiki/Connected_component_(graph_theory).
>
> what do you think about that?
>
> Ciao
>
> --
> Marco Speranza <ma...@gmail.com>
>
> Flick photostream: http://www.flickr.com/photos/marcosperanza79/
> Google Code: http://code.google.com/u/marco.speranza79/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] Graph connectivity algo
Posted by Marco Speranza <ma...@gmail.com>.
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 <ma...@gmail.com>
Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
Re: [Graph] Graph connectivity algo
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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
Re: [Graph] Graph connectivity algo
Posted by Marco Speranza <ma...@gmail.com>.
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
Ciao
Marco
--
Marco Speranza<marco.speranza79 <at> gmail.com>
Flick photostream: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] Graph connectivity algo
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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<ma...@gmail.com>
>>
>> Flick photostream: http://www.flickr.com/photos/marcosperanza79/
>> Google Code: http://code.google.com/u/marco.speranza79/
>>
>
--
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
Re: [Graph] Graph connectivity algo
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
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.
Ciao
Claudio
>
> what do you think about that?
>
> Ciao
>
> --
> Marco Speranza<ma...@gmail.com>
>
> Flick photostream: http://www.flickr.com/photos/marcosperanza79/
> Google Code: http://code.google.com/u/marco.speranza79/
>
--
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