Re: [Jung-support] graphs that share vertices

[Danyel F. <da...@ac...>]

Unfortunately, Joshua's "combined graph" will still need to be 
filterered (which creates a new instance) in order for any meaningful 
algorithms to be run on it, or for the graph to be visualizes.

I'm not sure this method would get you very far...

-Danyel

Joshua O'Madadhain wrote:

> On 25 May 2004, at 9:20, oxc...@st... wrote:
> 
>> Hello,
>> I want to have two graphs that have the same set of vertices and differ
>> only in the connections. However, I got a predicate error (vertex not in
>> graph):
>>
>> java.lang.IllegalArgumentException: Predicate
>> edu.uci.ics.jung.graph.predicates.NotInGraphVertexPredicate rejected V50:
>> NotInGraphVertexPredicate: G10272075[]
>>
>> when trying to add one of the vertices to the other graph. Is it possible
>> to have those nodes shared? ... I can not afford to have duplicate
>> vertices because my network is to big, what can be done if not using the
>> same object for both?
> 
> 
> The current version of the JUNG architecture does not allow for shared 
> nodes; that vertex is being rejected on attempted addition to the second 
> graph because it's already in an existing graph.  (The "not in graph 
> vertex predicate" must evaluate to "true" in order for the vertex to be 
> added.)  This was a conscious decision on our part; shared vertices can 
> cause some conceptual problems.
> 
> I see that Danyel has already described the JUNG-canonical solution; 
> I'll just add that a copy of a vertex compares as equal with the 
> original, so you can (for example) fetch, using v.getEqualVertex(), the 
> vertex in another graph (if any) that is "equal to" v, which allows you 
> to treat the two vertices as if they were shared.
> 
> I don't know that the overhead from having a second node set would be as 
> high as you suspect.  Have you actually been running into memory 
> problems, or are you anticipating them?
> 
> Also, unless the graph is very sparse, you are likely to have many more 
> edges than nodes in either case: that is, the edges are more likely to 
> cause memory problems than the vertices.
> 
> In any case, there is another way to address this, if you really don't 
> want to create two graphs:
> 
> (1) create a graph which allows parallel edges.
> (2) create a tag for your edges that allows you to distinguish between 
> your two edge sets (e.g., a flag in the UserData)
> (3) create two Predicates which each pass one value for that tag.
> (4) use these predicates as criteria for edge subsets
> (5) create a OnePredicate that operates on these two Predicates
> (6) add this OnePredicate as an edge constraint to the graph
> 
> At this point, effectively you have a single graph which can be treated, 
> with a little bit of effort, as two separate graphs which share a vertex 
> set.  ("A little bit of effort": for example, when you call 
> v.getPredecessors(), you would need to run the resulting set through a 
> Predicate-based filter if you wanted only edges from one edge set.  So 
> you'd probably want to write a utility method to do this, which would 
> look like a simpler version of PredicateUtils.getEdges().  On 
> reflection, I may actually add such a method to PredicateUtils in a 
> future release.)
> 
> The code for this is pretty straightforward (and in fact is a slightly 
> simpler version of the code for defining a k-partite graph, as seen in 
> the constructor for KPartiteSparseGraph).  Let us know if you need help, 
> either with the code or with understanding my proposed solution, or if 
> you have another possible solution that you'd like to discuss.
> 
> Regards,
> 
> Joshua
> 
>  jm...@ic......Obscurium Per Obscurius...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.
> 
> 
> 
> -------------------------------------------------------
> This SF.Net email is sponsored by: Oracle 10g
> Get certified on the hottest thing ever to hit the market... Oracle 10g. 
> Take an Oracle 10g class now, and we'll give you the exam FREE.
> http://ads.osdn.com/?ad_id=3149&alloc_id=8166&op=click
> _______________________________________________
> Jung-support mailing list
> Jun...@li...
> https://lists.sourceforge.net/lists/listinfo/jung-support