Is the target vertex of an edge stored differently than the same vertex in the vertex set?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Is the target vertex of an edge stored differently than the same vertex in the vertex set?

Steven Barkin

I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget). I had thought they were identical - i.e. they point to the same object (a SteveVertex in this case) and have the same hash code - but they seem to be located in different places somehow, per symptom below.

When my code below comes across a loop, in which it encounters the original start vertex as the target of an edge, it does not show this vertex as having been visited, even though the hashCode (SteveVertex@vertex1) is identical to the first entry of the vertexSet which DOES show the vertex as having been visited.

Any help would be greatly appreciated in diagnosing this.

private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;

private static void SteveDepthFirstSearch(SteveVertex startVertex)
 {
     if (!startVertex.visited()) {
         startVertex.visit();
         for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));

         startVertex.setFinishOrder(counter);
         counter++;
     }

 }


public static void main(String[] args) {  

    ...

    for (SteveVertex v: graph.vertexSet())
        SteveDepthFirstSearch(v);

    ...

}

This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Is the target vertex of an edge stored differently than the same vertex in the vertex set?

Joris Kinable
The problem doesn't seem to be in the section of code you posted. Check whether your visited() method actually does something.

"I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget)." Also, check whether your isVisited() method returns the correct result.

I'm not sure where you get this idea from? This is not true. All methods use the same vertex or edge objects. Furthermore, none of the methods you've shown use equals/hashCode, so even if you had implemented them wrong, I don't see why this would effect your result. Btw, I would encourage you to have a look at the jgrapht graph source code. It is very clear and gives you a good understanding of how the graph package works.

It will not make a difference, but in your code I would find it cleaner to write:
for (SteveVertex neighborVertex : Graphs.outgoingNeighborsOf(graph,startVertex)   
             SteveDepthFirstSearch(neighborVertex);
instead of:
for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));


br,

Joris Kinable

On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <[hidden email]> wrote:

I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget). I had thought they were identical - i.e. they point to the same object (a SteveVertex in this case) and have the same hash code - but they seem to be located in different places somehow, per symptom below.

When my code below comes across a loop, in which it encounters the original start vertex as the target of an edge, it does not show this vertex as having been visited, even though the hashCode (SteveVertex@vertex1) is identical to the first entry of the vertexSet which DOES show the vertex as having been visited.

Any help would be greatly appreciated in diagnosing this.

private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;

private static void SteveDepthFirstSearch(SteveVertex startVertex)
 {
     if (!startVertex.visited()) {
         startVertex.visit();
         for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));

         startVertex.setFinishOrder(counter);
         counter++;
     }

 }


public static void main(String[] args) {  

    ...

    for (SteveVertex v: graph.vertexSet())
        SteveDepthFirstSearch(v);

    ...

}

This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Is the target vertex of an edge stored differently than the same vertex in the vertex set?

Joris Kinable
Your problem is in this part of your code:

String sourceToken = tokenizer.nextToken();
int sourceNum = Integer.parseInt(sourceToken);
SteveVertex sourceVertex = new SteveVertex(sourceNum);
boolean success = graph.addVertex(sourceVertex);
System.out.println("added "+sourceVertex.ID()+" success: "+success);

String destToken = tokenizer.nextToken();
int destNum = Integer.parseInt(destToken);
SteveVertex destVertex = new SteveVertex(destNum);
success = graph.addVertex(destVertex); /* may already exist */
System.out.println("added "+destVertex.ID()+" success: "+success);


if (sourceNum != destNum) {
graph.addEdge(sourceVertex, destVertex);
numEdges++;
if (numEdges % 1000 == 0)
StdOut.printf("Edge count: %d\n", numEdges);
}

You create 2 new objects, source and target vertices, and add them to the graph. Jgrapht won't add them if they are already present. Next you add a new edge using graph.addEdge(sourceVertex, destVertex). Jgrapht will first check whether source and the target vertices are already present. Lets assume that your code does the following:
SteveVertex object1=new SteveVertex(1);
SteveVertex object2=new SteveVertex(2);
graph.addVertex(object1); //success
graph.addVertex(object2); //success

SteveVertex object3=new SteveVertex(1);
SteveVertex object4=new SteveVertex(2);
graph.addVertex(object3); //fail
graph.addVertex(object4); //fail
graph.addEdge(object3,object4); //Incorrect

In the last step, the addEdge method will check whether object3 and object4 are already in the graph. Because you incorrectly overrode the hashCode and equals methods, it will think that these vertices are already in the graph, and the method will modify the internal edge structure using the objects you provided. Even though object1.hashCode()==object3.hashCode() and object1.equals(object3), object1==object3 fails. By doing so, you violate the equals contract between two objects:

"The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true)."

see: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-

An easy fix to your problem would be to use a map:

Map<Integer, SteveVertex> vertexMap=new HashMap<>(); ... int sourceToken = Integer.parseInt(tokenizer.nextToken()); SteveVertex sourceVertex; if(vertexMap.containsKey(sourceToken){ sourceVertex=vertexMap.get(sourceToken); }else{ sourceVertex = new SteveVertex(sourceToken); vertexMap.put(sourceToken, sourceVertex); graph.addVertex(sourceVertex); } int targetToken = Integer.parseInt(tokenizer.nextToken()); SteveVertex targetVertex; if(vertexMap.containsKey(targetToken){ targetVertex=vertexMap.get(targetToken); }else{ targetVertex = new SteveVertex(targetToken); vertexMap.put(targetToken, targetVertex); graph.addVertex(targetVertex); } graph.addEdge(sourceVertex, destVertex);

br,


Joris Kinable
Ps. Please don't set messages directly to me, instead, use the mailing list.

On Sun, Aug 9, 2015 at 5:38 PM, Steven Barkin <[hidden email]> wrote:
Thanks Joris.  Would you be open to reviewing my two Java source files plus the input text file with the graph info?  They are fairly simple.  I'm attaching them here if you be willing to take a look.  These are related to a Coursera class I am taking (Stanford Algorithms Design and Analysis).

On Sun, Aug 9, 2015 at 2:22 PM, Joris Kinable <[hidden email]> wrote:
The problem doesn't seem to be in the section of code you posted. Check whether your visited() method actually does something.

"I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget)." Also, check whether your isVisited() method returns the correct result.

I'm not sure where you get this idea from? This is not true. All methods use the same vertex or edge objects. Furthermore, none of the methods you've shown use equals/hashCode, so even if you had implemented them wrong, I don't see why this would effect your result. Btw, I would encourage you to have a look at the jgrapht graph source code. It is very clear and gives you a good understanding of how the graph package works.

It will not make a difference, but in your code I would find it cleaner to write:
for (SteveVertex neighborVertex : Graphs.outgoingNeighborsOf(graph,startVertex)   
             SteveDepthFirstSearch(neighborVertex);
instead of:
for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));


br,

Joris Kinable

On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <[hidden email]> wrote:

I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget). I had thought they were identical - i.e. they point to the same object (a SteveVertex in this case) and have the same hash code - but they seem to be located in different places somehow, per symptom below.

When my code below comes across a loop, in which it encounters the original start vertex as the target of an edge, it does not show this vertex as having been visited, even though the hashCode (SteveVertex@vertex1) is identical to the first entry of the vertexSet which DOES show the vertex as having been visited.

Any help would be greatly appreciated in diagnosing this.

private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;

private static void SteveDepthFirstSearch(SteveVertex startVertex)
 {
     if (!startVertex.visited()) {
         startVertex.visit();
         for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));

         startVertex.setFinishOrder(counter);
         counter++;
     }

 }


public static void main(String[] args) {  

    ...

    for (SteveVertex v: graph.vertexSet())
        SteveDepthFirstSearch(v);

    ...

}

This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users




This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Is the target vertex of an edge stored differently than the same vertex in the vertex set?

Steven Barkin
In reply to this post by Steven Barkin
Thanks - the HashMap solved my problem.   I really appreciate your taking the time to look at my program.

On Sun, Aug 9, 2015 at 8:43 PM, Joris Kinable <[hidden email]> wrote:
Your problem is in this part of your code:

String sourceToken = tokenizer.nextToken();
int sourceNum = Integer.parseInt(sourceToken);
SteveVertex sourceVertex = new SteveVertex(sourceNum);
boolean success = graph.addVertex(sourceVertex);
System.out.println("added "+sourceVertex.ID()+" success: "+success);

String destToken = tokenizer.nextToken();
int destNum = Integer.parseInt(destToken);
SteveVertex destVertex = new SteveVertex(destNum);
success = graph.addVertex(destVertex); /* may already exist */
System.out.println("added "+destVertex.ID()+" success: "+success);


if (sourceNum != destNum) {
graph.addEdge(sourceVertex, destVertex);
numEdges++;
if (numEdges % 1000 == 0)
StdOut.printf("Edge count: %d\n", numEdges);
}

You create 2 new objects, source and target vertices, and add them to the graph. Jgrapht won't add them if they are already present. Next you add a new edge using graph.addEdge(sourceVertex, destVertex). Jgrapht will first check whether source and the target vertices are already present. Lets assume that your code does the following:
SteveVertex object1=new SteveVertex(1);
SteveVertex object2=new SteveVertex(2);
graph.addVertex(object1); //success
graph.addVertex(object2); //success

SteveVertex object3=new SteveVertex(1);
SteveVertex object4=new SteveVertex(2);
graph.addVertex(object3); //fail
graph.addVertex(object4); //fail
graph.addEdge(object3,object4); //Incorrect

In the last step, the addEdge method will check whether object3 and object4 are already in the graph. Because you incorrectly overrode the hashCode and equals methods, it will think that these vertices are already in the graph, and the method will modify the internal edge structure using the objects you provided. Even though object1.hashCode()==object3.hashCode() and object1.equals(object3), object1==object3 fails. By doing so, you violate the equals contract between two objects:

"The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true)."

see: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-

An easy fix to your problem would be to use a map:

Map<Integer, SteveVertex> vertexMap=new HashMap<>(); ... int sourceToken = Integer.parseInt(tokenizer.nextToken()); SteveVertex sourceVertex; if(vertexMap.containsKey(sourceToken){ sourceVertex=vertexMap.get(sourceToken); }else{ sourceVertex = new SteveVertex(sourceToken); vertexMap.put(sourceToken, sourceVertex); graph.addVertex(sourceVertex); } int targetToken = Integer.parseInt(tokenizer.nextToken()); SteveVertex targetVertex; if(vertexMap.containsKey(targetToken){ targetVertex=vertexMap.get(targetToken); }else{ targetVertex = new SteveVertex(targetToken); vertexMap.put(targetToken, targetVertex); graph.addVertex(targetVertex); } graph.addEdge(sourceVertex, destVertex);

br,


Joris Kinable
Ps. Please don't set messages directly to me, instead, use the mailing list.

On Sun, Aug 9, 2015 at 5:38 PM, Steven Barkin <[hidden email]> wrote:
Thanks Joris.  Would you be open to reviewing my two Java source files plus the input text file with the graph info?  They are fairly simple.  I'm attaching them here if you be willing to take a look.  These are related to a Coursera class I am taking (Stanford Algorithms Design and Analysis).

On Sun, Aug 9, 2015 at 2:22 PM, Joris Kinable <[hidden email]> wrote:
The problem doesn't seem to be in the section of code you posted. Check whether your visited() method actually does something.

"I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget)." Also, check whether your isVisited() method returns the correct result.

I'm not sure where you get this idea from? This is not true. All methods use the same vertex or edge objects. Furthermore, none of the methods you've shown use equals/hashCode, so even if you had implemented them wrong, I don't see why this would effect your result. Btw, I would encourage you to have a look at the jgrapht graph source code. It is very clear and gives you a good understanding of how the graph package works.

It will not make a difference, but in your code I would find it cleaner to write:
for (SteveVertex neighborVertex : Graphs.outgoingNeighborsOf(graph,startVertex)   
             SteveDepthFirstSearch(neighborVertex);
instead of:
for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));


br,

Joris Kinable

On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <[hidden email]> wrote:

I seem to have come across a non-intuitive discrepancy between how vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the vertexSet, vs. how they are stored as the target of an edge (see below for my usage of getEdgeTarget). I had thought they were identical - i.e. they point to the same object (a SteveVertex in this case) and have the same hash code - but they seem to be located in different places somehow, per symptom below.

When my code below comes across a loop, in which it encounters the original start vertex as the target of an edge, it does not show this vertex as having been visited, even though the hashCode (SteveVertex@vertex1) is identical to the first entry of the vertexSet which DOES show the vertex as having been visited.

Any help would be greatly appreciated in diagnosing this.

private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;

private static void SteveDepthFirstSearch(SteveVertex startVertex)
 {
     if (!startVertex.visited()) {
         startVertex.visit();
         for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))   
             SteveDepthFirstSearch(graph.getEdgeTarget(e));

         startVertex.setFinishOrder(counter);
         counter++;
     }

 }


public static void main(String[] args) {  

    ...

    for (SteveVertex v: graph.vertexSet())
        SteveDepthFirstSearch(v);

    ...

}

This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users




This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 




This communication is confidential and subject to and governed by the confidentiality and use restrictions contained in Saama’s Electronic Communications Disclaimer.

 


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users