override the equals and hashcode

[Gil Shoam]

Hi,
I'm writing a program that represents a graph.
I have 3 classes.
1. a Node class (which takes an object)
2. a Edge class (which build an edge from a source Node to destination Node)
3. A graph class. Here it is:

public class Graph {

    private HashSet<Node> _nodes;
    private HashSet<Edge> _edges;


    public Graph() {
        _nodes = new HashSet<Node>();
        _edges = new HashSet<Edge>();
    }


    public Graph(ArrayList<Node> nodeList, ArrayList<Edge> edgeList) {
        _nodes = new HashSet<Node>(nodeList);
        _edges = new HashSet<Edge>(edgeList);
    }

I'm trying to override the equals and hashcode methods to check if two graphs are similar.
meantime I wrote it just to check the nodes but with no luck:

 public boolean equals(Graph graph) {
        if (this._nodes.equals(graph._nodes)) //&& _edges.equals(graph._edges))
            return true;
        return false;
    }

when I tried

 System.out.println(graph.equals(graph1));
        System.out.println(graph._nodes.contains(nodeA));

I got:
false
true

in other words I wasn't able to implement the method for the actual Node which contains a char, but only for it's wrapping. for the same reason I am able to add two similar char to the _nodes hashset (which should in theory not be possible). I did so and the did toString and got
Nodes: [A,B,D,A,C]
So it sees is as two different object although I want it to see the two A's as the same (and then it won't add another A right?)
I understand what the problem is, I just don't know how to solve it.

BTW, I wrote equal methods in the Node and Edge classes, both work fine. (in both cases i based the methods on the toString result)
Here:

  public boolean equals(Node node){
     if(this._object.toString().equals(node.toString()))
            return true;
        return false;

    }
    public static void main(String[] args) {
         //Character character = new Character('A');
        Node node = new Node('A');
        Node node1= new Node('A');
        System.out.println(node.toString());
        System.out.println(node1.toString());
        System.out.println(node.equals(node1));

prints:
A
A
true

and in Edge:

 public boolean equals(Edge edge) {
        if (this.toString().equals(edge.toString()))
            return true;
        return false;
    }

    public static void main(String[] args) {
        Node nodeS = new Node('C');
        Node nodeD = new Node('D');
        Node nodeS1= new Node('C');
        Node nodeD1= new Node('D');

        Edge edge = new Edge(nodeS, nodeD);
       Edge edge1 = new Edge(nodeS1,nodeD1);
        System.out.println(edge.toString());
        System.out.println(edge1.toString());
        System.out.println(edge.equals(edge1));

returns:
(C,D)
(C,D)
true


Please Help, and sorry for the long post

Thanks

Gil

[Ralph Cook]

This is where I get lost:

Gil Shoam wrote:

 public boolean equals(Graph graph) {
        if (this._nodes.equals(graph._nodes)) //&& _edges.equals(graph._edges))
            return true;
        return false;
    }

when I tried

 System.out.println(graph.equals(graph1));
        System.out.println(graph._nodes.contains(nodeA));

I got:
false
true

in other words I wasn't able to implement the method for the actual Node which contains a char, but only for it's wrapping. for the same reason I am able to add two similar char to the _nodes hashset (which should in theory not be possible). I did so and the did toString and got
Nodes: [A,B,D,A,C]
So it sees is as two different object although I want it to see the two A's as the same (and then it won't add another A right?)
I understand what the problem is, I just don't know how to solve it.

I don't know which one 'the method' is. This is the first mention made in your post of a char, which doesn't seem to fit into your class anywhere. Characters, perhaps, but not chars. And I have to assume that this 'nodeA' was added to one (both?) of your instances at some point, you don't say that it is. Anyway, I have now read through this several times and I'm not sure I understand the question. I think it might be clear if you made a series of steps -- instantiate A, add B to its list, add C to its list, instantiate D, etc., and then call equals and show that it exhibits the behavior you don't want.

Gil Shoam wrote:

BTW, I wrote equal methods in the Node and Edge classes, both work fine.

Did you also write hashCode methods for them? Two 'equal' objects are supposed to return the same hashCode; if they don't, things like HashSets could behave unpredictably...

[Gil Shoam]

I'll clarify: (the Object identifies and translates 'A' into new Character('A'), so that is not the problem)

this is the Node class:

public class Node {

    private Object _object;


    public Node(Object obj) {
        _object= obj;
    }

    public String toString() {
        return _object.toString();

    }

    public boolean equals(Node node){
     if(this._object.toString().equals(node.toString()))
            return true;
        return false;

    }
    public static void main(String[] args) {
         //Character character = new Character('A');
        Node node = new Node('A');
        Node node1= new Node('A');
        System.out.println(node.toString());
        System.out.println(node1.toString());
        System.out.println(node.equals(node1));

it prints :
A
A
true

meaning it compares two different nodes and 'equals' checks if they have the same name.

this is the Edge Class:

public class Edge {
    private Node _source;
    private Node _dest;

    public Edge(Node source, Node dest) {
        _source = source;
        _dest = dest;

    }


    public String toString() {
        return "(" + _source.toString() + "," + _dest.toString() + ")";
    }

    public boolean equals(Edge edge) {
        if (this.toString().equals(edge.toString()))
            return true;
        return false;
    }

    public static void main(String[] args) {
        Node nodeS = new Node('C');
        Node nodeD = new Node('D');
        Node nodeS1= new Node('C');
        Node nodeD1= new Node('D');

        Edge edge = new Edge(nodeS, nodeD);
       Edge edge1 = new Edge(nodeS1,nodeD1);
        System.out.println(edge.toString());
        System.out.println(edge1.toString());
        System.out.println(edge.equals(edge1));

prints
(C,D)
(C,D)
true

so here the equals also works.

in the graph class i did this:

public class Graph {

    private HashSet<Node> _nodes;
    private HashSet<Edge> _edges;


    public Graph() {
        _nodes = new HashSet<Node>();
        _edges = new HashSet<Edge>();
    }


    public Graph(ArrayList<Node> nodeList, ArrayList<Edge> edgeList) {
        _nodes = new HashSet<Node>(nodeList);
        _edges = new HashSet<Edge>(edgeList);
    }


    public void addNode(Node node) {
        _nodes.add(node);
    }

    public void removeNode(Node node) {
        _nodes.remove(node);
    }

    public void addEdge(Edge edge) {
        _edges.add(edge);
    }

    public void removeEdge(Edge edge) {
        _edges.remove(edge);
    }

    public boolean isNode(Node node) {
        return _nodes.contains(node);
    }

    public boolean isEdge(Edge edge) {
        return _edges.contains(edge);
    }


    public boolean equals(Graph graph) {
        if (this._nodes.equals(graph._nodes)) //&& _edges.equals(graph._edges))
            return true;
        return false;
    }

    public String toString() {
        String nodes = "Nodes:" + _nodes.toString();
        String edges = "Edges" + _edges.toString();
        return nodes + "\n" + edges;
        /*
        String nodes = "";

        Iterator iterator = _nodes.iterator();
        while (iterator.hasNext())
            nodes = iterator.next() + ", ";
        return nodes;
        */
    }


    public static void main(String[] args) {
        //new list of nodes
        ArrayList<Node> nodes = new ArrayList<Node>();

        //creates new nodes
        Node nodeA = new Node('A');
        Node nodeB = new Node('B');
        Node nodeC = new Node('C');
        Node nodeD = new Node('D');
        Node nodeA2= new Node('A');

        //add nodes to the list

        nodes.add(nodeA);
        nodes.add(nodeB);
        nodes.add(nodeC);
        nodes.add(nodeD);
        nodes.add(nodeA2);

        //new list of edges
        ArrayList<Edge> edges = new ArrayList<Edge>();

        //creates new edges
        Edge edge1 = new Edge(nodeA, nodeB);
        Edge edge2 = new Edge(nodeA, nodeC);
        Edge edge3 = new Edge(nodeB, nodeC);

        //add edges to the list
        edges.add(edge1);
        edges.add(edge2);
        edges.add(edge3);

        Graph graph = new Graph(nodes, edges);

        //create another similar graph
        ArrayList<Node> nodes1 = new ArrayList<Node>();

        Node nodeE = new Node('A');
        Node nodeF = new Node('B');
        Node nodeG = new Node('C');
        Node nodeH = new Node('D');


        nodes1.add(nodeE);
        nodes1.add(nodeF);
        nodes1.add(nodeG);
        nodes1.add(nodeH);

        ArrayList<Edge> edges1 = new ArrayList<Edge>();
        Edge edge4 = new Edge(nodeA, nodeB);
        Edge edge5 = new Edge(nodeA, nodeC);
        Edge edge6 = new Edge(nodeB, nodeC);

        edges1.add(edge4);
        edges1.add(edge5);
        edges1.add(edge6);
        Graph graph1 = new Graph(nodes1, edges1);


        System.out.println(graph.toString());
        System.out.println(graph1.toString());
        System.out.println(graph.equals(graph1));
        System.out.println(graph._nodes.contains(nodeA));

    }

}

it prints:
Nodes: [A,D,B,A,C]
Edges: [(A,B),(B,C)(A,C)]
nodes1: [A,C,B,D]
Edges 1:[(A,B),(B,C)(A,C)]
false
true

so there are two problems here.
1) How can I add another 'A' to Nodes? a hashset isn't supposed to allow it. i.e it has two similar elements. I know it sees them as different because it is looking at the 'Node' wrapping.
2) If I erase the extra 'A' from Nodes, and to the equals method again (which currently only checks the _nodes)
it still returns false even though they have the same elements in the set.
the last line gives 'true' because the set has wrapped the Characters with the nodes, so I guess the equals method is comparing that. (So these 2 problems are actually the same I think..?)
That is where I am stuck..
Hope this helps...

[Ralph Cook]

From the javadoc for Object.hashCode() (SE 5.0):

"If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. "

You have not shown that you've overridden hashCode, but you have overridden equals to produce true on two different objects. By default, the Object implementation of hashCode would return different values for your two different objects. I don't know that that's your only problem, but it looks likely, and is certainly not what's recommended for equals and hashCode.

rc