2

我正在写一个图表类，

我保留 aHashMap其中节点的 id（int 值）映射到关联的节点，并且我正在使用adjacency list方法来保持从节点开始的边（以 a 的形式保持它们HashSet）

请注意：该图是有向图且未加权的，

我想实现一个方法，该方法返回类对象的迭代器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;
    }
}
4

2 回答 2

1

I think something like this might work :

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

The EdgeIterator method creates an Iterator<Edge> and defines the methods of the Iterator interface (I left the implementation of these methods to you). The Iterator instance contains an instance of Iterator<GraphNode>, which it uses to iterate over the nodes.

You should add to the iterator some additional private members that keep track of the current node (the last node returned by the node iterator) and the current edge you are iterating on. Whenever you finish iterating over the edges of a node, you get the next node using itr.next() (after checking there is a next node available). next() of the edge iterator can construct the next Edge based on those private members.

于 2013-06-27T21:19:15.867 回答
0

正如 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;
}
于 2013-06-27T21:58:43.203 回答