jgrapht-users

[jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

The attached program throws a ConcurrentModificationException, and I  
don't know why. Even stranger, if outgoingEdgesOf is changed to  
edgesOf, the exception is not thrown. Doesn't make sense. Is this a bug?

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

[John V. S. <js...@gm...>]

Trevor Harmon wrote:
> The attached program throws a ConcurrentModificationException, and I 
> don't know why. Even stranger, if outgoingEdgesOf is changed to edgesOf, 
> the exception is not thrown. Doesn't make sense. Is this a bug?

Not a bug, unless you consider the program below to indicate a bug in 
the JDK :)

The outgoingEdgesOf vs edgesOf behavior is just a matter of getting 
lucky with one.

JVS

----

import java.util.*;

public class Goodbye
{
     public static void main(String [] args)
     {
         List<String> list = new ArrayList<String>();
         list.add("arm");
         list.add("leg");
         List<String> sublist = list.subList(0,1);
         list.removeAll(sublist);
     }
}

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 25, 2006, at 1:24 PM, John V. Sichi wrote:

> Trevor Harmon wrote:
>> The attached program throws a ConcurrentModificationException, and  
>> I don't know why. Even stranger, if outgoingEdgesOf is changed to  
>> edgesOf, the exception is not thrown. Doesn't make sense. Is this  
>> a bug?
>
> Not a bug, unless you consider the program below to indicate a bug  
> in the JDK :)

Let me rephrase my question then. The following JDK program works as  
expected:

List<String> list = new ArrayList<String>();
list.add("arm");
list.add("leg");
List<String> sublist = list.subList(0,1);
sublist.clear();

But the following JGraphT program throws a  
ConcurrentModificationException:

DirectedGraph<String, DefaultEdge> g =
	new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
String s1 = "s1";
String s2 = "s2";
g.addVertex(s1);
g.addVertex(s2);
g.addEdge(s1, s2);
g.edgesOf(s1).clear();

Regardless of this problem, how is one supposed to remove all  
outgoing edges from a vertex? That's all I'm trying to do. With the  
large number of methods available in JGraphT, I would have expected  
the API to provide a straightforward way of doing this (without  
having to iterate over the edges myself).

> The outgoingEdgesOf vs edgesOf behavior is just a matter of getting  
> lucky with one.

Well, that part I would still say is a bug. I could understand it if  
outgoingEdgesOf, incomingEdgesOf, and edgesOf all ended up causing  
the ConcurrentModificationException -- at least that would be  
consistent. But that's not the case here. The behavior of an API  
shouldn't be left to chance. :)

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

[John V. S. <js...@gm...>]

Trevor Harmon wrote:
> Well, that part I would still say is a bug. I could understand it if 
> outgoingEdgesOf, incomingEdgesOf, and edgesOf all ended up causing the 
> ConcurrentModificationException -- at least that would be consistent. 
> But that's not the case here. The behavior of an API shouldn't be left 
> to chance. :)

Go ahead and create a bug report for this inconsistency.  It may not get 
addressed for a while because the fix isn't trivial.

For a directed graph, edgesOf has to be computed on the fly by combining 
the incoming and outgoing edge sets of the vertex.  And that computation 
isn't something that's easy to express as a derived Set implementation, 
due to the requirement to filter out the duplicates for self-loops.  So 
the fix requires us to maintain a graph-level timestamp which can be 
used by ArrayUnenforcedSet to detect the ConcurrentModificationException.

One side-effect of the fix would be that any application code which is 
currently relying on the buffering behavior of edgesOf would break.  But 
in this case, a more consistent and less surprising API trumps 
backward-compatibility.

JVS

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 25, 2006, at 10:49 PM, Trevor Harmon wrote:

> But the following JGraphT program throws a
> ConcurrentModificationException:
>
> DirectedGraph<String, DefaultEdge> g =
> 	new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
> String s1 = "s1";
> String s2 = "s2";
> g.addVertex(s1);
> g.addVertex(s2);
> g.addEdge(s1, s2);
> g.edgesOf(s1).clear();

Oops, I don't think I tested this correctly. The above program  
doesn't throw an exception. In fact, it doesn't do anything. The  
graph remains unchanged!

Also, replacing the edgesOf call with outgoingEdgesOf causes an  
UnsupportedOperationException.

The latter may be acceptable behavior, but surely the former is not.  
And in any case, shouldn't there be some built-in way to remove all  
edges from a vertex?

> Regardless of this problem, how is one supposed to remove all
> outgoing edges from a vertex?

So far, the best I've come up with is this:

removeAllEdges( new Vector<Edge>(outgoingEdgesOf(node)) );

where "Edge" is the edge class and "node" is a vertex instance.

Unfortunately, this requires allocating a temporary vector and  
copying every edge into it. Is there a more efficient way?

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

[John V. S. <js...@gm...>]

Trevor Harmon wrote:
> On Nov 25, 2006, at 10:49 PM, Trevor Harmon wrote:
> 
>> But the following JGraphT program throws a
>> ConcurrentModificationException:
>>
>> DirectedGraph<String, DefaultEdge> g =
>>     new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
>> String s1 = "s1";
>> String s2 = "s2";
>> g.addVertex(s1);
>> g.addVertex(s2);
>> g.addEdge(s1, s2);
>> g.edgesOf(s1).clear();
> 
> Oops, I don't think I tested this correctly. The above program doesn't 
> throw an exception. In fact, it doesn't do anything. The graph remains 
> unchanged!
> 
> Also, replacing the edgesOf call with outgoingEdgesOf causes an 
> UnsupportedOperationException.
> 
> The latter may be acceptable behavior, but surely the former is not.

This one is easy to fix; we can just apply Collections.unmodifiableSet 
to the computed Set returned from edgesOf.  Then you'll get the 
UnsupportedOperationException in all cases (at the price of one extra 
object allocation, and possible breakage for existing apps).

>> Regardless of this problem, how is one supposed to remove all
>> outgoing edges from a vertex?
> 
> So far, the best I've come up with is this:
> 
> removeAllEdges( new Vector<Edge>(outgoingEdgesOf(node)) );
> 
> where "Edge" is the edge class and "node" is a vertex instance.
> 
> Unfortunately, this requires allocating a temporary vector and copying 
> every edge into it. Is there a more efficient way?

There is no more efficient way (although you should be using ArrayList 
instead of Vector).  This is a standard pattern for dealing with the 
same issue in the Java collection classes, and is used in the 
implementation for AbstractBaseGraph.removeVertex too.

If you want, log an enhancement request for convenience methods to be 
added to the Graphs utility class (removeEdgesOf, removeOutgoingEdgesOf, 
and removeIncomingEdgesOf).  If you were searching for them, others 
probably are too.

JVS

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 26, 2006, at 6:47 AM, John V. Sichi wrote:

> This one is easy to fix; we can just apply  
> Collections.unmodifiableSet to the computed Set returned from  
> edgesOf.  Then you'll get the UnsupportedOperationException in all  
> cases (at the price of one extra object allocation, and possible  
> breakage for existing apps).

Thanks; consistency is important.

> (although you should be using ArrayList instead of Vector).

Good point; I've changed it in my code.

> If you want, log an enhancement request for convenience methods to  
> be added to the Graphs utility class (removeEdgesOf,  
> removeOutgoingEdgesOf, and removeIncomingEdgesOf).  If you were  
> searching for them, others probably are too.

That's okay. The ArrayList idiom works well enough for now.

Trevor