0

Basically, I am trying to read in a text file using the following code in order to build a graph using the adjacency lists representation. However, I ran into 2 problems.

The first and the major problem is that: I do not understand when I check graph.contains(v_l), it always return false. I have been stuck in this problem for ages now. Really need some help here.

The second problem: I do not understand why is that within the if statement, I cannot do the following:

if(graph.containsKey(v_l) == false){
                // this always fail               
                graph.put(v_l, edges_of_this_vertex.add(v_r));
                // the following works though 
                ArrayList<Vertex> edges_of_this_vertex = new ArrayList<Vertex>();
                edges_of_this_vertex.add(v_r);
                graph.put(v_l, edges_of_this_vertex);
 }

I have no idea why this is happening ? 

 class Vertex{
            int node;
            ....
            public Vertex(int node){
                 this.node = node;
            }

            public String toString(){
                 return Integer.toString(node);
            }
    }
class dgraph{
 // constructor ...

 // instance method
 public HashMap<Vertex, ArrayList<Vertex>> read_file_and_populate(String file_loc, boolean reverse) throws IOException{

        HashMap<Vertex, ArrayList<Vertex>> graph = new HashMap<Vertex, ArrayList<Vertex>>();
        int l = 0;
        int r = 0;
        if(reverse == false){
            r = 1;
        } else{
            l = 1;
        }

        FileInputStream fil = new FileInputStream(file_loc);
        BufferedReader br = new BufferedReader( new InputStreamReader(fil));
        String element = null;

        while( (element = br.readLine()) != null){
            String[] line = element.split("\\s");
            Vertex v_l = new Vertex( Integer.parseInt(line[l]) );
            Vertex v_r = new Vertex( Integer.parseInt(line[r]) );
            System.out.println("l = " + l + " r = " + r );
            if(graph.containsKey(v_l) == false){
                ArrayList<Vertex> edges_of_this_vertex = new ArrayList<Vertex>();
                edges_of_this_vertex.add(v_r);
                graph.put(v_l, edges_of_this_vertex);
                //graph.put(v_l, edges_of_this_vertex.add(v_r));
            } else{
                graph.get(v_l).add(v_r);

            }
        }
        return graph;
    }
}

Below is some example data :

1 1 
1 2 
1 5 
1 6 
1 7 
1 3 
1 8 
1 4 
2 47646 
2 47647 
2 13019 
2 47648 
2 47649 
2 47650 
2 7700 
2 47651 
2 47652 
3 511596 
5 1 
5 9
mynameisJEFF
  • 4,073
  • 9
  • 50
  • 96

2 Answers2

1

Your value class (Vertex) needs to implement hashCode & equals(), otherwise all the operations will be done by checking to see if its the same instance (which it'll never be in this case). assuming the int is the only state in Vertex, the hashCode & equals functions should be based on those e.g.

public int hashCode() {
   return node *31;
}

public boolean equals(Object o) {
    if (o == this) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Vertex r = (Vertex)o;
    return node == r.node;
}
superfell
  • 18,780
  • 4
  • 59
  • 81
  • `int node` is not the only instance variable in Vertex class but it is the only variable I would use to compare different Vertex objects. Would your solution still work in this case ? And what exactly is the hashCode() method doing ? I mean why do we need to do `node * 31` ? Can't we just return `node` ? – mynameisJEFF Dec 16 '14 at 04:12
  • There's a detailed discussion of hashCode in this question http://stackoverflow.com/questions/113511/hash-code-implementation – superfell Dec 16 '14 at 04:25
0

In

// this always fail               
            graph.put(v_l, edges_of_this_vertex.add(v_r));

you are trying to add the result of edges_of_this_vertex.add(v_r) to the graph. The add() function to a arraylist returns a boolean (always true). So, when you do a graph.get(v_l), you will always get a boolean true.

user2533521
  • 236
  • 1
  • 4