Блог

У меня есть структура данных орграфа, которая использует представление списка ( HashMap<Vertex, ArrayList<Vertex>> ); исходная вершина в качестве ключа и список вершин назначения в качестве значения. Поиск в глубину и цикл dfs используются для обхода графика, чтобы найти порядок выполнения вершин.

Порядок выполнения задается как метка вершинного объекта, setLabel(int i) и String name для генерации используется только поле hashcode .

Моя проблема в том, что после dfs завершения и когда я перебираю ключи HashMap [ graph.keySet() ] , остается еще несколько вершин, которые не помечены, но когда я перебираю исследуемый набор, который является a HashSet<Vertex> , все возможные вершины помечены (точно).

Что здесь может происходить? (Я могу использовать HashMap только для извлечения меток вершин)

Примечание: я считаю, что это имеет отношение к использованию изменяемых объектов в качестве ключей в хэш-картах. Если нет, пожалуйста, поправьте меня.

  /**
 * 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;
}}
  

Проблема почти наверняка связана с управлением secondPass переменной, поскольку именно это определяет, следует ли устанавливать метку:

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

Предоставленный вами код не показывает, где для этого будет установлено значение true.