Graphenalgorithmen

Klasse NeighbourIterator

 aufwärts

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.

Implementierung

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.

Eine andere Möglichkeit besteht darin, den NeighbourIterator als FilterIterator zu implementieren.

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 17.09.2012   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik