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: squar...@dia.uniroma3.it > Phone: +39-06-57333215 > Fax: +39-06-57333612 > http://www.dia.uniroma3.it/~squarcel > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@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.speranz...@gmail.com> Flickr: http://www.flickr.com/photos/marcosperanza79/ Google Code: http://code.google.com/u/marco.speranza79/
smime.p7s
Description: S/MIME cryptographic signature
