Using mutable objects as keys in HashMaps

I have a digraph data structure which uses list representation(HashMap<Vertex, ArrayList<Vertex>> ); source vertex as the key and an ArrayList of destination vertices as the value. A depth first search and dfs loop are used to traverse the graph to find the execution order of the vertices.

The execution order is set as a label of a Vertex object by setLabel(int i) and only the String name field is used to generate hashcode.

My problem is that after dfs is completed and when I iterate through the keys of the HashMap [graph.keySet()] , there are still few Vertices which are not labeled, But when I iterate though the explored set which is aHashSet<Vertex>, all the possible vertices are labeled(Accurately).

What could possibly be happening here? (I can only use the HashMap to retrieve the labels of the vertices)

Note: I believe this is relevant to using mutable objects as keys in HashMaps. If not please correct me.

 /**
 * Recursive depth-first search     
 * @param graph HashMap<Vertex,ArrayList> (list representation)
 * @param start starting Vertex
 */
public void dfsR(HashMap<Vertex, ArrayList<Vertex>> graph, Vertex start) {
    this.explored.add(start); //a HashSet<Vertex>        

    ArrayList<Vertex> list = graph.get(start);
    if (list != null) {
        for (Vertex v : list) {
            if (!this.explored.contains(v)) {
                this.dfsR(graph, v);
            }
        }
    }
    /* First pass-Execution order */
    if (!this.secondPass) {
        start.setLabel(++this.label);
    }
}

 /**
 * Run DFS on every vertex of the Graph      
 * @param graph HashMap<Vertex,ArrayList<Vertex>> (list representation)
 */
private void dfsLoop(HashMap<Vertex, ArrayList> graph) {
    this.secondPass = false;
    this.explored.clear();        
    this.label = 0;
    for (Vertex vertex : graph.keySet()) {
        if (!this.explored.contains(vertex)) {
            this.dfsR(graph, vertex); /* Recursive dfs */                                
        }
    }
}

public class Vertex {

private final String name;
private int label;    

public Vertex(String name) {
    this.name = name;
    this.label = -1;
}

public Vertex(Integer name) {
    this.name = String.valueOf(name);
    this.label = -1;
}

public String getName() {
    return name;
}

/**
 * Value(Label) obtained from Topological Ordering  
 * @param label integer value of the relevant position
 */
public void setLabel(int label){
    this.label = label;
}

/** 
 * @return the Label obtained from the Topological ordering
 */
public int getLabel(){
    return this.label ;
}    

@Override
public String toString() {
    return name;
}

@Override
public boolean equals(Object o) {
    if(o == null){
        return false;
    }
    if (o instanceof Vertex) {
        Vertex v = (Vertex) o;
        return this.name.equals(v.getName());
    }
    return false;
}

@Override
public int hashCode() {
    int hash = 3;       
    hash = 89 * hash + this.name.hashCode();
    return hash;
}}

Answers


The problem is almost certainly related to the management of the secondPass variable, as that is what controls whether or not to set the label:

if (!this.secondPass) {
    start.setLabel(++this.label);
}

The code you provided does not show where this would be set to true.


Need Your Help

Commerce Server 2009 API - Get All Profiles

e-commerce microsoft-commerce-server

Is there a way, using the CS2009 API, to get all profiles? I have trying to migrate to the CS2009 API, and I need to be able to get all profiles from a custom profile.

can't display ¥ with TCPDF, but other kanji are okay

php tcpdf true-type-fonts

I'm using TCPDF to create PDFs that include Japanese characters. Using the TrueType font ArialUni, most characters are displayed correctly, except the yen symbol shows up as a square box instead o...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.