Graphenalgorithmen

Klasse NeighbourIterator

In Graphenalgorithmen geht es oft darum, alle Nachbarn eines bestimmten Knotens zu durchlaufen. Ein NeighbourIterator ermöglicht es, von der konkreten Implementierung des Graphen zu abstrahieren, und die Nachbarknoten einen nach dem anderen zu liefern. Er leitet sich von dem Software-Entwurfsmuster Iterator ab.

Die Implementierung des Iterators NeighbourIterator berücksichtigt, dass ein Knoten möglicherweise gar keinen Nachbarknoten hat. Daher wird im Konstruktor zunächst die Methode tryNext aufgerufen. Die Methode tryNext sucht den ersten Nachbarknoten j; falls dieser nicht existiert, wird j bis zum Wert getSize() erhöht und die Methode getNext liefert gleich zu Beginn false.

public class NeighbourIterator implements Iterator<Integer>
{
    private Graph<?> g;
    private int i, j;

    public NeighbourIterator(Graph<?> g_, int i_)
    {
        g=g_;
        i=i_;
        j=0;
        tryNext();
    }

    public boolean hasNext()
    {
        return j<g.getSize();
    }

    public Integer next()
    {
        int k=j;
        j++;
        tryNext();
        return k;
    }

    private void tryNext()
    {
        while (j<g.getSize())
            if (g.isEdge(i, j))
                return;
            else
                j++;
    }

    public void remove()
    {
        // not implemented
    }

}

Weiter mit: [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 17.09.2012 Updated: 20.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden