迭代器多套

Question

我寫一個Graph類，

我保持HashMap在哪些節點（INT值）的ID都會被映射到相關的節點，我使用adjacency list方法來保持從邊緣開始一個節點（使它們保持在一個HashSet的形式）

注意的是：該圖是針對和未加權，

我想要實現其超過Edge類對象返回一個迭代的方法：

當獲得下一個迭代器時，會得到一個類Edge的對象，該對象在被遍歷時被創建，並且如果沒有更多的節點鄰居，它會轉到下一個節點（順序不重要），如果沒有更多的起始節點（全部遍歷），它完成。

有關如何在Edge上實現此迭代器而不事先保留Edge類對象中的邊緣的任何想法？

class Graph{ 
    HashMap<Integer , GraphNode> nodes; 
    public Graph(){ 
     nodes = new HashMap<Integer ,GraphNode>(); 
    } 
    public boolean addEdge(GraphNode n1 , GraphNode n2){ 
     if (!nodes.containsKey(n1) || !nodes.containsKey(n2)) 
      return false; 
     return n1.addNeighbor(n2); 
    } 
    public boolean addNode(int id){ 
     if (nodes.containsKey(id)) 
      return false; 
     nodes.put(id , new GraphNode(id)); 
     return true; 
    } 
    public boolean removeNode(GraphNode n1){ 
     if (!nodes.containsKey(n1.content)) 
      return false; 
     for (GraphNode m : n1.neighbors) 
      m.removeNeighbor(n1); 
     nodes.remove(n1); 
     return false; 
    } 
    public boolean removeEdge(GraphNode n1 , GraphNode n2){ 
     if (!nodes.containsKey(n1) || !nodes.containsKey(n2)) 
      return false; 
     return n1.removeNeighbor(n2); 
    } 
    public Iterator<GraphNode> NodeIterator(){ 
     return nodes.values().iterator(); 
    } 


    public Iterator<Edge> EdgeIterator(){ 
     Iterator<GraphNode> itr = this.NodeIterator(); 
     while (itr.hasNext){ 
      GraphNode n = itr.next(); 
      //...... 

     } 
    } 

} 
class GraphNode{ 
    HashSet<GraphNode> neighbors; 
    int content; 
    public GraphNode(int content){ 
     this.content = content; 
     neighbors = new HashSet<GraphNode>(); 
    } 
    boolean addNeighbor(GraphNode n){ 
     if (neighbors.contains(n)) 
      return false; 
     neighbors.add(n); 
     return true; 
    } 
    boolean removeNeighbor(GraphNode n){ 
     if (!neighbors.contains(n)) 
      return false; 
     neighbors.remove(n); 
     return true; 
    } 


    } 

class Edge{ 
    Node start , end; 
    public Edge(Node start , Node end){ 
     this.start = start; 
     this.end = end; 
    } 
} 

Answer 1

我覺得這樣的事情可能工作：

public Iterator<Edge> EdgeIterator(){ 
    Iterator <Edge> edgeIter = new Iterator<Edge>() { 

     private Iterator<GraphNode> itr = this.NodeIterator(); 
     private GraphNode currentNode; 
     ... // additional private members as required 

     public void remove() 
     { 
      // you don't have to implement this method if you don't need to support 
      // this operation 
     } 

     public Edge next() 
     { 
      if (!hasNext()) 
      throw new NoSuchElementException(); 

      return new Edge (x , y); // where you find x & y based on the current state 
            // of the iterator (kept in the private members of 
            // this instance) 
     } 

     public boolean hasNext() 
     { 
      return ?; // you return a boolean value based on the current state 
         // of the iterator (kept in the private members of 
         // this instance) 
     } 
    }; 

    return edgeIter; 
} 

的EdgeIterator方法創建一個Iterator<Edge>並定義Iterator接口（我離開了這些方法的實施給你）的方法。 Iterator實例包含一個Iterator<GraphNode>的實例，它用於遍歷節點。

您應該向迭代器添加一些跟蹤當前節點（節點迭代器返回的最後一個節點）和當前正在迭代的邊的其他私有成員。無論何時您完成迭代節點的邊緣，都會使用itr.next()（在檢查是否存在下一個節點之後）獲得下一個節點。邊緣迭代器的next()可以構建基於這些私有成員的下一個Edge。

Answer 2

正如Eran所說，我完成了迭代器方法的代碼， 您認爲這個方法有效嗎？

public Iterator<Edge> EdgeIterator(){ 
    Iterator<Edge> edgeIter = new Iterator<Edge>() { 

     private Iterator<GraphNode> node_itr = NodeIterator(); 
     private Iterator<GraphNode> neighbor_itr; 
     private GraphNode current_node; 
     private GraphNode current_neighbor; 
     public void remove() 
     { 
      if (current_node == null || current_neighbor == null) 
       return; 
      current_node.removeNeighbor(current_neighbor); 
     } 
     public Edge next() 
     { 
      if (neighbor_itr == null || !neighbor_itr.hasNext()) 
       if (node_itr.hasNext()){ 
        current_node = node_itr.next(); 
        neighbor_itr = current_node.neighbors.iterator(); 
       }else 
        return null; 
      current_neighbor = neighbor_itr.next(); 
      return new Edge(current_node , current_neighbor); 
     } 
     public boolean hasNext() 
     { 
      if (neighbor_itr == null || !neighbor_itr.hasNext()) 
       if (node_itr.hasNext()) 
        return node_itr.next().neighbors.iterator().hasNext(); 
       else 
        return false; 
      return true; 
     } 
    }; 

    return edgeIter; 
} 

更新：編輯好的/工作版本：

public Iterator<Edge> EdgeIterator(){ 
    Iterator<Edge> edgeIter = new Iterator<Edge>() { 
     private Iterator<GraphNode> node_itr = NodeIterator(); 
     private Iterator<GraphNode> neighbor_itr; 
     private GraphNode current_node; 
     private GraphNode current_neighbor; 
     public void remove() 
     { 
      if (current_node == null || current_neighbor == null) 
       return; 
      current_node.removeNeighbor(current_neighbor); 
     } 
     private void moveNext(){ 
      if (neighbor_itr == null || !neighbor_itr.hasNext()){ 
       while (node_itr.hasNext()){ 
        current_node = node_itr.next(); 
        neighbor_itr = current_node.neighbors.iterator(); 
        if (neighbor_itr.hasNext()){ 
         break; 
        } 
       } 
      } 
     } 
     public Edge next() 
     { 
      moveNext(); 
      current_neighbor = neighbor_itr.next(); 
      return new Edge(current_node , current_neighbor); 
     } 
     public boolean hasNext() 
     { 
      moveNext(); 
      return neighbor_itr.hasNext(); 
     } 
    }; 

    return edgeIter; 
}