I have a class Vertex defined as:
class Vertex {
private String s;
public Vertex(String s) {
this.s = s;
}
public String getName() {
return s;
}
public void setName(String s) {
this.s = s;
}
public boolean equals(Vertex o) {
return s.equals(o.getName());
}
@Override
public String toString() {
return s;
}
}
and a class DirectedGraph with the following methods:
private HashMap<Vertex, HashSet<Vertex>> adjacencyMap = new HashMap<>();
public boolean addVertex(Vertex v) {
if (!this.adjacencyMap.containsKey(v)) {
this.adjacencyMap.put(v, new HashSet<>());
return true;
}
return false;
}
public boolean addEdge(Vertex x, Vertex y) {
if (adjacencyMap.containsKey(x) && adjacencyMap.containsKey(y)) {
if (!adjacencyMap.get(x).contains(y)) {
adjacencyMap.get(x).add(y);
edgeCount++;
return true;
}
}
return false;
}
public DirectedGraph(File f) throws FileNotFoundException {
Scanner s = new Scanner(f);
while (s.hasNextLine()) {
String l = s.nextLine();
int i = 0;
Vertex parent = null;
for (String t : l.split(" ")) {
if (i == 0) {
parent = new Vertex(t);
if (root == null) {
root = parent;
}
addVertex(parent);
} else {
Vertex v = new Vertex(t);
addVertex(v);
if (addEdge(parent, v) != true) System.out.println(parent + ", " + v + "failed");
// System.out.println("adding edge: " + parent + ", " + v);
}
i++;
}
}
s.close();
for (Vertex v : adjacencyMap.keySet()) {
System.out.println(v + ": \n " + adjacencyMap.get(v));
}
}
as you can see, it takes a file and scans it line by line, assuming the first node is a "parent" node and the following depend on it. If I use the following input text file:
B D G
C A
E B F H
J B
I C
My issue is that my output is:
A:
[]
J:
[]
F:
[]
C:
[]
J:
[B]
B:
[]
C:
[]
G:
[]
E:
[F, B, H]
B:
[]
H:
[]
A:
[J, C, E]
I:
[C]
B:
[G, D]
D:
[]
E:
[]
C:
[A]
As you can see, my HashMap has multiple duplicate keys because I must not understand how containsKey works. I have two ideas to resolve my issue:
firstly, and more cave-manish, is to simply iterate over the keySet(), manually compare the Vertex's names, and combine the .get()s, or
update addVertex or addEdge, whichever is the primary offender, to recognize duplicate keys.
I'm not sure how to do either, so a shove in the right direction would be most helpful.
HashMap uses hashing function to calculate indices for objects used as key. For this functionality to work properly you need to provide both equals() AND hashCode() functions for class that instances of you plan to use as keys in your hash map.
That means you need to override public int hashCode() method that's now inherited straight from Object superclass, and put there some calculations that will return the same integer for objects that are considered 'equal'. Fortunately you compare Strings as this criteria so you can use String method hashCode resulting with:
@Override
public int hashCode() {
return s.hashCode();
}
Second problem that I previously missed is your implementation of equals() is wrong. You should override Object's equals() which has a signature public boolean equals( Object o ) and you implemented it with Vertex as an argument, which caused that while adding to hashmap Object's equals was used, as you didn't override by overload equals. That's one of the reasons that annotation @Overrideshould be used, compiler would tell you that you don't override anything and you would know that you're doing something wrong. Now, going back to how to implementequals` properly....
@Override
public boolean equals(Object o) {
if( o instanceof Vertex ) {
return s.equals((( Vertex)o).getName());
} else {
return false;
}
}
Now instances of Vertex will behave properly when used as key in hash map.
As a side note, putting all the logic, including opening, parsing file in constructor is a little too much to my taste, consider splitting it into some methods instead.