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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
