On 07/11/2011 11:44 AM, Jan Torben Heuer wrote: > > I have a graph (org.geotools.graph.structure.basic.BasicGraph) and I > want to find alls its subgraphs (that is, all componenents that are not > connected with each other).
The definition of subgraph they taught me at the University is different: a subgraph is a graph whose edges and nodes are subsets of the edges and nodes of the graph; hence, being disjoint is not necessary for being a subgraph. What are you trying to enumerate are the different "vertex-disjoint subgraphs" (or maybe the "edge-disjoint subgraphs"). Try Googling around with these search strings, or maybe just "disjoint subgraphs" > Do you know if there is an Algorithm in n log(n) which is not > recursive? My graph has a max depth of ~ 200Mio so I *think* recursion > matters (I might be wrong) and a simple depth-first traversal is not > efficient. I browsed my book about graphs theory and found nothing on this issue; however, from this (just http://arxiv.org/abs/0709.1227) and this (www.cs.elte.hu/egres/qp/egresqp-10-04.ps) I infer this problem is not trivial. Regards, Luca Morandini http://www.lucamorandini.it ------------------------------------------------------------------------------ All of the data generated in your IT infrastructure is seriously valuable. Why? It contains a definitive record of application performance, security threats, fraudulent activity, and more. Splunk takes this data and makes sense of it. IT sense. And common sense. http://p.sf.net/sfu/splunk-d2d-c2 _______________________________________________ Geotools-gt2-users mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
