setting edge weights

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

setting edge weights

Joris Kinable
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: setting edge weights

John Sichi
Administrator
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 <[hidden email]> 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
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: setting edge weights

Joris Kinable
Hi John,

Thanks for the follow up. You are right about the performance impact which occurs if additional checks are performed such as edge ownership, or edge occurrence in a graph. Perhaps we could add some assert statements to check for these issues. Doing this would not affect production code as java ignores the assert statements, whereas it would make debugging easier. This way at least some trivial cases can be verified, such as whether the edge is contained in the graph when invoking setEdgeWeight. However, this would not resolve your tricky example wrt the edge adjacency problem as graph g2 has no notion of the existence of graph g1. 

Wrt the documentation: depending on the quantity I would prefer to keep as much documentation in the javadoc as this is simply more convenient. However linking to an external wiki page would also be fine, especially if the amount of documentation is large. 

br,

Joris


On Wed, Apr 23, 2014 at 1:27 AM, John Sichi <[hidden email]> wrote:
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 <[hidden email]> 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
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...