|
From: Joris K. <de...@gm...> - 2015-08-10 03:43:46
|
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 <ste...@sa...>
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 <de...@gm...> 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 <ste...@sa...>
>> 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. <http://www.saama.com/disclaimer>
>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> 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. <http://www.saama.com/disclaimer>
>
>
>
|
