Graphenalgorithmen

Graphen mit Knotenmarkierungen

Viele Probleme lassen sich mithilfe von Graphen modellieren, deren Knoten z.B. mit Zahlenwerten markiert sind.

Definition:  Sei G = (V, E) ein Graph und A eine Menge. Eine Abbildung

m : V → A,

die jedem Knoten v ∈ V ein Element m(v) ∈ A zuordnet, heißt Knoten­markierung.

Wir leiten Implementierungen von Graphen mit Knoten­markierungen von der Klasse DirectedGraph bzw. von der Klasse UndirectedGraph ab.

Marker

In vielen Graphen­algorithmen werden im Verlauf der Berechnungen gewisse Knoten markiert, z.B. um sie als schon besucht zu kennzeichnen. Um derartige temporäre Markierungen anzubringen, verwenden wir die Klasse Marker.

Wir verwenden die Klasse Marker ebenfalls, um Graphen mit Knoten­markierungen darzustellen.

Es folgt eine entsprechende Implementierung in der Klasse NodeWeightedGraph, die hier von der Klasse DirectedGraph abgeleitet ist. Hierbei wird ein Marker mit Typ-Parameter Double eingesetzt.

// modelliert einen Graphen mit Knotenmarkierungen vom Typ Double
public class NodeWeightedGraph extends DirectedGraph
{
    private Marker<Double> a;    // Knotenmarkierungen

    public NodeWeightedGraph(int n)
    {
        super(n);
        a=new Marker<Double>(n, 0.0);
    }

    public void setEdge(int i, int j)
    {
        setWeight(i, j, true);
    }

    public void setNodeWeight(int i, double x)
    {
        a.setMark(i, x);
    }

    // addiert x zum aktuellen Knotengewicht
    public void addNodeWeight(int i, double x)
    {
        a.setMark(i, a.getMark(i)+x);
    }

    public double getNodeWeight(int i)
    {
        return a.getMark(i);
    }

    // bildet die Summe aller Knoten, die in einer Liste p angegeben werden
    public double sumNodeWeight(ArrayList<Integer> p)
    {
        double sum=0;
        Iterator<Integer> it=p.iterator();
        while (it.hasNext())
            sum+=getNodeWeight(it.next());
        return sum;
    }

    @Override
    public String toString()
    {
        int i;
        String s="";
        for (i=0; i<n; i++)
            s+=i+" "+a.getMark(i)+"\n";
        return s+super.toString();
    }

}

 

 

 

Weiter mit:   [Gerichteter Baum mit Kantenmarkierung]   oder   [up]

 

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