#83 Context implementation is nasty
The Context implementation using a single cached instance of Context (see http://jung.cvs.sourceforge.net/jung/jung2/jung-algorithms/src/main/java/edu/uci/ics/jung/algorithms/util/Context.java?view=markup ) is incredibly unpleasant. This seems to only be used within the rendering thread, so in principle access is restricted to a single thread, so as long as it's only used non-persistently this should not break anything. However at the very least this should have great big warning labels on it instead of being completely uncommented.
However, quickly running through the codebase, I note that this is only used as part of a Predicate<Context<K, E>>. Presumably you're trying to avoid the allocation of a large number of garbage objects. So wouldn't it be clearly better to simply create a BinaryPredicate<K, E> interface to use where you would previously have used Predicate<Context<K, E>>? This is cleaner, less evil and eliminates a class of potential bugs.
Logged In: YES
user_id=1211988
Originator: NO
Are you saying that our internal use of Context is causing breakage in your code?
Could you describe how?
Or are you saying that when you attempt to use our Context for another
purpose, it is not working as you need it to?
Thanks for clarifying,
Tom Nelson
Logged In: YES
user_id=1681313
Originator: YES
No, it works for now, and now that I'm aware of the potential problem it will probably remain working in my code. This is more in the category of "Bug just waiting to happen". Unless I'm vastly misunderstanding the intended usage of the API (which is, I admit, possible), it isn't possible to keep the Context use "internal only" - defining your own custom rendering conditions requires the use of Context (specifically Predicate<Context>).
Given this, the fact that it is completely and utterly unsafe to use Context in a manner which allows two to exist at the same time[1] is extremely scary! It probably wouldn't break anything in expected normal usages but has the potential to introduce some really weird bugs where two usages are unexpectedly sharing the same instance of Context and overwriting eachother's data as a result, especially in multi-threaded situations.
This is why I'm suggesting the refactoring of using a BinaryPredicate interface as a replacement. It also has the advantage of more cleanly expressing the intent (and producing more readable type signatures).
[1] Without explicitly invoking the constructor anyway, which is contrary to how it's used anywhere one might look for example usages and has performance problems which is presumably the reason for this design in the first place.
Logged In: YES
user_id=1211988
Originator: NO
I agree that Singletons can create surprises in code.
As to the need for this particular optimization, Joshua will probably
jump in later when the US west coast wakes up....
How would you write the BinaryPredicate class? I'm a little confused, as
Predicates have only 2 states anyway....
Logged In: YES
user_id=1681313
Originator: YES
The BinaryPredicate interface would be something like the following:
public interface BinaryPredicate<S, T>{
public boolean evaluate(S first, T second);
}
So a Predicate<Context<S, T>> becomes a BinaryPredicate<S, T> by replacing evaluate(arg); with evaluate(arg.graph, arg.element);
The optimisation in question is definitely understandable, as otherwise it result in allocating one object per graph node inside the render loop (again, as far as I understand it. My exposure to Jung is, so far, limited). This would be unfortunate to say the least! I'm objecting to the implementation of the optimisation, not the need for it. :-)
Logged In: YES
user_id=709417
Originator: NO
David:
Lots of things are not commented very well at the moment. JUNG 2.0 is currently in alpha, and none of us gets paid in any way to work on it.
In any case, while I understand the theoretical problem that you're describing, I think that it's unlikely that this design will cause any problems in practice.
That said, creating a two-argument predicate (a less confusing term than 'binary predicate', IMO) might be a reasonable solution here. We'll look into it.
(Side note: as I have said elsewhere, there are more tactful ways to suggest modifications to free software.)
Joshua
Logged In: YES
user_id=1211988
Originator: NO
we wanted to use the commons collections Predicate, which takes only one arg
in its evaluate method, That led to the 'context' object, to temporarily
(for example) put a vertex in the context of its graph. This is because
there is no v.getIncidentEdges() method in our graph, you need to call
graph.getIncidentEdges(v) instead.
If the context objects were stateful, then you could have a lot of tedious
clean-up to do if, for example, you remove a vertex from the graph. You'd
need to hunt down any context objects referencing the vertex and get
rid of them.
Tom Nelson
Logged In: YES
user_id=1681313
Originator: YES
You're right. I've not been very tactful. I have a tendency to overreact, and I apologise for it. I still stand by my points though, if not the phrasing of them.
"Binary predicate" is a relatively standard term (used for things like <, ==, etc.), but I don't really care what you call it. :-)
Also, fair point about the lack of comments in the alpha. It hadn't occurred to me that Context was a new thing, but it should have. Sorry.
I question the value of using the commons collections predicate. There are essentially two benefits to reusing the existing interface:
a) It allows you to do various filtering operations on collections. As we've established, the implementation strongly discourages the existence of multiple Context implementations, so this is has no real benefit.
b) Commons collections provides various predicate combinators. These are admittedly vaguely useful in certain cases. I question how much utility they really have (I find that doing such things in Java seems to be sufficiently awful from a syntax and semantics point of view that it's rarely worth the bother), but I can see the point of view.
So, let's assume you want to use the predicate class. How about, instead of making it a Predicate<Context<Graph<K, T>, K> you make it a Predicate<K>, with the Predicate being scoped to a particular Graph instance where it needs to be?
Example:
public class SelfLoopEdgePredicate<V,E> implements Predicate<Context<Graph<V,E>,E>> {
public boolean evaluate(Context<Graph<V,E>,E> context) {
Pair<V> endpoints = context.graph.getEndpoints(context.element);
return endpoints.getFirst().equals(endpoints.getSecond());
}
}
becomes:
public class SelfLoopEdgePredicate<E> implements Predicate<E> {
private final Graph graph;
public SelfLoopEdgePredicate<E>(Graph<?, E> graph){
this.graph = graph;
}
public boolean evaluate(E edge ) {
Pair<V> endpoints = graph.getEndpoints(edge);
return endpoints.getFirst().equals(endpoints.getSecond());
}
}
The implementation of the predicate becomes slightly longer here, but in the common use case where these are anonymous inner classes it actually becomes shorter! (As an amusing side point, it might be useful to add a .equals() utility method to Pair which compares its arguments for equality. The implementation could then become "return graph.getEndpoints(edge).equals();". I'm perhaps overly fond of adding cute helper instance methods though)
I have some more general comments to make about the API design if you care to hear them (including my proposed change to the code snippet which I initially complained about on my blog). What would be an appropriate medium to send them to you via? Email? A mailing list? Post them on my blog? :-)
Logged In: YES
user_id=1211988
Originator: NO
David,
The support forum is a good place to discuss features of the library. It
is fairly active, and Joshua and I are pretty responsive there.
One reason I would resist having a Predicate hold the graph state
is that, with a library that supports a lot of dynamic changes to
graphs (and changes from one graph to another), any stateful
objects require that you hunt them down
and kill them after you make changes somewhere else. I realize that
if substituted for our current Predicate, your stateful Predicate would
not create a problem. Our Context singleton, however pretty much
enforces that it cannot be used to persist state. We use Context internally
as a means to simplify our Graph API (must look at graph elements
in the context of a graph). We also try hard to not invent classes we don't
really need, leveraging commons-collections as much as possible.
Also, any user wishing to persist state someplace is free to use another
Collection class, or anything else they like to do so.
In any event, Joshua and I often beat on things like this in great detail,
and it is refreshing to have other voices introduce ideas into the fray.
Tom
Logged In: YES
user_id=1681313
Originator: YES
I think leveraging commons collections as much as possible is a Really Bad Idea, personally. It has some useful implementations, but the overall approach to manipulating collections is unutterably clumsy in Java. This is a common sore point of mine. I often get accused of "reinventing the wheel", but when the wheels you're trying to use are triangular it's not a bad idea to knock up your own circular implementation of the Wheel interface in five minutes. :-)
I'm also very suspicious of the infinite micropluggability style of design. It's a good idea in languages which actually support it well, but Java isn't an instance of those. It may be good practice to prefer delegation to inheritance, but for single method plugins it's just painful. (For clarification: I'm not objecting to large scale pluggability. Composable objects are *good*. It's specifically this style of trying to fake functions with objects that I find really painful, having been bitten by it in the past).
On to the specific issues you raise:
As you say, the Predicate implementation I suggest doesn't cause a problem. It isn't, in itself, stateful - it merely closes over an existing chunk of state without contributing its own state to it. Consequently no matter what you do it doesn't need updating, because there's nothing to update. This is something to strive for. I agree that having widespread state is to be avoided, but creating objects which refer to an existing self-contained piece of state is fine and useful.
Also, I'd argue that your Context object doesn't enforce that it can't be used to persist state. It merely breaks in easily missable ways if you try. That's not quite the same thing. :-)
I mentioned briefly in my blog comments, but an example of a potential problem (which is not threading related) is as follows:
I have a Graph<Foo, Bar> and a Graph<Baz, Bif>. I want to form the product graph Graph<Tuple<Foo, Baz>, Tuple<Bar, Bif>>. I now want to create the product filter based on two filters on my original graph. Unfortunately when I try to do this I discover that I'm trying to create a Context<Graph<Foo, Bar>, Foo> out of my Context<<Tuple<Foo, Baz>, Tuple<Bar, Bif>>, Tupe<Foo, Bar>> (god I hate Java's type signatures), and discover that I'm accidentally overwriting the original context, so when I try to look at it again to create the Context<Baz, Bif> it all breaks.
It's a somewhat contrived example admittedly, but I can see it as potentially useful.
Logged In: YES
user_id=1211988
Originator: NO
David,
I guess I would say that our Context enforces that it can't be used
to persist state by failing when you attempt to do so. Not unlike
any other Singleton.
In your example, is there any reason to use Context over creating
your own (non-commons collections, i presume) class?
Its like if I tell you that your Porsche is not useful because my
family would not fit in it....
Tom
Logged In: YES
user_id=1681313
Originator: YES
The reason to use Context in the second example is that your API demands it, which brings up another point: You've mentioned that the Context class is "internal", but it really isn't. There are a lot of public facing APIs which need to use it in order to function. All the filtering for display, etc. is based on Context.
Granted, you don't have to reuse the context based predicates you've already created for the existing graph implementations, but unless you want to copy and paste the code between the implementations you need to create some way of reusing the existing code. Projecting contexts is the natural way to do it given the way the API is exposed, which is currently ruled out by your implementation.