Re: [jgrapht-users] setting edge weights

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

Hi Joris,

Note that this is also true for edge adjacency (even for unweighted
edges) due to the IntrusiveEdge implementation; i.e. if you add a
DefaultEdge e1 to g1 between (v1,v2), and then add e1 to g2 between
(v3,v4), e1 gets updated in both graphs (corrupting g1).

This imperfect situation came about due to JGraphT's emphasis on
performance:  it avoids the need for map lookups for traversing graphs
and accessing weights, and in the common case of no sharing (or
something like subgraph sharing where there's no discrepancy between
the two graphs), all is well.

In other cases where edge sharability is required, it's necessary to
use your own edge class (avoiding inheritance from the Default*Edge
classes), and override the graph's get/setEdgeWeight.

Where do you think is a good place to document this?  I'm thinking
maybe a wiki page explaining the pitfalls, and then links to it from
various classes (although no matter how much documentation we do, it's
still likely that developers will overlook this).

On Tue, Apr 22, 2014 at 8:47 PM, Joris Kinable <de...@gm...> wrote:
> Hi,
>
> I've encountered some issues with edge weights which potentially could cause
> bugs. I was wondering whether some corrections in the code are required.
>
> Take the following simple code snippet:
>
> //Define graph4, consisting of a single edge (0,1) with edge weight 10
> WeightedGraph<Integer, DefaultWeightedEdge> graph4=new
> SimpleWeightedGraph<Integer,
> DefaultWeightedEdge>(DefaultWeightedEdge.class);
> graph4.addVertex(0);
> graph4.addVertex(1);
> DefaultWeightedEdge e1= graph4.addEdge(0, 1);
> graph4.setEdgeWeight(e1, 10);
> //Define graph5 without edges or vertices
> SimpleWeightedGraph<Integer, DefaultWeightedEdge> graph5=new
> SimpleWeightedGraph<Integer,
> DefaultWeightedEdge>(DefaultWeightedEdge.class);
> graph5.setEdgeWeight(e1, 5);
>
> System.out.println("Edge weight graph 4: "+graph4.getEdgeWeight(e1));
> //OUTPUT: Edge weight graph 4: 5.0
>
> Notice that jgrapht allowed me to change the weight of edge e1 in graph4
> through graph5 which does not even contain this edge. This seems pretty
> awkward?
>
> 1. the setEdgeWeight should only work if the graph contains the edge.
> 2. I think that it would be a good idea to update the documentation of the
> DefaultWeightedEdge, thereby emphasizing that edge weights are stored on the
> edges, and not in the graph. Lets say you have 2 graphs, g1 and g2 both
> containing the same edge e (same object). Invoking g1.setEdgeWeight(e, 10)
> will also change the weight of this edge in graph g2.
>
> I'm not sure how to accomplish the following:
> Given a weighted graph g1, create a subgraph g2 containing a subset of the
> edges of g1 with *different* weights. Then for a given edge e which is
> contained in both g1 and g2, I would like to invoke:
> "Weight of e in g1: "+ g1.getEdgeWeight(e);
> "Weight of e in g2: "+ g2.getEdgeWeight(e);
> I could do something ugly by creating a mapping from edges in graph g1 to
> different edges in graph g2. Then for a given edge e in g1 I could invoke:
> Map<DefaultWeightedEdge, DefaultWeightedEdge> edgeMapping=...;
> "Weight of e in g1: "+ g1.getEdgeWeight(e);
> "Weight of e in g2: "+ g2.getEdgeWeight(edgeMapping.get(e));
> I would be happy to learn about cleaner methods.
>
>
> br,
>
> Joris
>
> ------------------------------------------------------------------------------
> Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software
> Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> Get Started Now And Turn Your Intranet Into A Collaboration Platform
> http://p.sf.net/sfu/ExoPlatform
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>