Menu
▾
▴
Re: [Jung-support] sub graphs?
|
From: Harsch, T. J. (ARC-TI)[P. SYSTEMS] <tim...@na...> - 2010-02-25 23:26:11
|
Actually I think I misunderstood, it wasn't the latter case I was looking for it was the former. But I don't think WeakComponentClusterer would have helped because I need back the collection of disjoint graphs with their edges and directions preserved and not just vertex sets. In any case I implemented what I need and share on my blog: http://harschware.blogspot.com/2010/02/converting-disconnected-graphs-to.html Critique welcome. -----Original Message----- From: Joshua O'Madadhain [mailto:jos...@gm...] Sent: Thursday, February 25, 2010 12:34 PM To: Harsch, Timothy J. (ARC-TI)[PEROT SYSTEMS] Cc: jun...@li... Subject: Re: [Jung-support] sub graphs? On Thu, Feb 25, 2010 at 11:31 AM, Harsch, Timothy J. (ARC-TI)[PEROT SYSTEMS] <tim...@na...> wrote: > The latter is the one I was looking for... Thanks for the help. > > Would you have any tips for implementing something? Identifying strong components is a pretty standard algorithm, you can find descriptions of it in many algorithms texts and probably all over the web, too. You can use WeakComponentClusterer as a model for how we handle this kind of thing. > My use case would probably begin as a DirectedSparseGraph with N strongly connected subgraphs. I would want back, ideally a List, Set, Iterable, or some such of Graph views (once my graph is built it does not change so a view would be ideal for the memory savings) of the original graph. JUNG does not currently have good built-in support for constructing views; it's been on our to-do list but we haven't gotten around to it. Generally in these cases we construct new graphs corresponding to the components. > It probably has no impact but I will note that in my case I also have trivial graphs, ie vertices of 0 degree. That's easy enough to filter out ahead of time as a preprocessing step, but a reasonable strong component algorithm should have no problem handling this case. Joshua > > -----Original Message----- > From: Joshua O'Madadhain [mailto:jos...@gm...] > Sent: Thursday, February 25, 2010 10:22 AM > To: Harsch, Timothy J. (ARC-TI)[PEROT SYSTEMS] > Cc: jun...@li... > Subject: Re: [Jung-support] sub graphs? > > On Thu, Feb 25, 2010 at 9:41 AM, Harsch, Timothy J. (ARC-TI)[PEROT > SYSTEMS] <tim...@na...> wrote: >> Hi I am new to Jung so please bare with me. >> >> I'm wondering if Jung provides a mechanism to discover all connected >> subgraphs within a graph? > > Connected (meaning connected by edges considered as undirected); see > WeakComponentClusterer. > > Strongly connected (all vertices reachable by directed edges): no > current support. > > Joshua > >> >> >> >> ------------------------------------------------------------------------------ >> Download Intel® Parallel Studio Eval >> Try the new software tools for yourself. Speed compiling, find bugs >> proactively, and fine-tune applications for parallel performance. >> See why Intel Parallel Studio got high marks during beta. >> http://p.sf.net/sfu/intel-sw-dev >> _______________________________________________ >> Jung-support mailing list >> Jun...@li... >> https://lists.sourceforge.net/lists/listinfo/jung-support >> >> > > > > -- > jos...@gm......................www.ics.uci.edu/~jmadden > Joshua O'Madadhain: Information Scientist, Musician, Philosopher-At-Tall > It's that moment of dawning comprehension that I live for. -- Bill Watterson > My opinions are too rational and insightful to be those of any organization. > -- jos...@gm......................www.ics.uci.edu/~jmadden Joshua O'Madadhain: Information Scientist, Musician, Philosopher-At-Tall It's that moment of dawning comprehension that I live for. -- Bill Watterson My opinions are too rational and insightful to be those of any organization. |