Beispielprogramm - Berechnen einer unabhängigen Menge
(1. Version)



import gabl.export.*;
import gabl.graph.*;
import java.io.*;
import java.util.*;


// Sei G=(V,E) ein Graph. Eine Teilmenge I der Knoten ist unabhängig wenn
// die Knoten in I paarweise nicht durch Kanten verbunden sind.
// 
// Die Funktion "independent_set" berechnet eine unabhänige Menge auf die
// folgende Weise:
//
// Unter den noch nicht betrachteten Knoten wird einer zufällig ausgewählt.
// Falls dieser keine Kante zu den bereits ausgewählten hat wird er hinzugefügt.
// Dies wird solange wiederholt bis alle Knoten betrachtet wurden.
class IndependentSet
{
    // --------------------------------------
    // Überprüft ob die Kante {v,u} existiert
    static boolean isAdjacent ( AdjGraph G, Vertex v, Vertex u ) {
	AdjacencyIterator ait=G.createAdjacencyIterator(v);
	for (; ! ait.atEnd(); ait.increment()) 
	   if (ait.getVertex().equals(u))
	       return true;
	
	return false;
    }


    // ----------------------------------------------------------------
    // Üperprüft ob v eine Kante zu einem Knoten in der Liste L besitzt
    static boolean isAdjacent ( AdjGraph G, Vertex v, LinkedList L ) {
	ListIterator lit=L.listIterator(0);
	while (lit.hasNext())
	   if (isAdjacent(G, v, (Vertex)lit.next()))
	       return true;
	
	return false;
    }


    // ---------------------------------------------
    // Funktion die eine unabhaenige Menge berechnet:
    static LinkedList independentSet( AdjGraph G )
    {
	// Die Knoten in einer unabhängigen Menge werden in eine Liste gespeichert:
	LinkedList is=new LinkedList();

	int n = G.getNumberOfVertices();

	// Array zum speichern der noch nicht benutzten Knoten:
	Vertex[] vertices = new Vertex[n];
	VertexIterator vit = G.createVertexIterator();
	for (int i=0; !vit.atEnd() ; vit.increment(), ++i)
	    vertices[i] = vit.getVertex();
	
	for (; n > 0; --n) {
	   // Math.random() gibt ein "double" im Interval [0.0, 1.0) zurück
	   int index=(int)(Math.random() * n);   // Zufallszahl zwischen 0 und n-1
	   Vertex v= vertices[index];            // der ausgewählte Knoten
	   System.out.println("checking vertex " + G.toString(v));

	   if (!isAdjacent(G, v, is)) {
	      System.out.println("adding vertex " + G.toString(v));
	      is.add(v);
	   }
	   // swap
	   vertices[index] = vertices[n-1];
	}

	return is;
    }
    

    // ---------------------------------------------
    // Funktion die bei Programmstart ausgeführt wird
    public static void main ( String[] argv )
    {
	GraphFactory factory = new GraphFactory();   // Klasse um Graphen zu erzeugen
	File file = new File(argv[0]);               // Dateiname
	
	try
	{
	   // Nun lese den Graphen und extra Daten im GML Format ein
	   GraphBundle bundle = GraphFormatGML.readGraph(new FileInputStream(file), factory);	  
	   AdjGraph G = (AdjGraph)bundle.getGraph();   // extrahiere den Graphen
	   
	   LinkedList L = independentSet(G);

	   ListIterator lit=L.listIterator(0);
	   System.out.println("Have the following independent set: ");
	   while (lit.hasNext()) {
	      System.out.print(G.toString((Vertex)lit.next()) + " ");
	   }
	   System.out.println();
        }
	catch (NoSuchGraphImplementationException e) {
	    System.err.println(e.toString());
	}
	catch (ClassCastException e) {
	    System.err.println("Error: graph has wrong type '" + e.toString() + "'");
	    e.printStackTrace();
	}
	catch (IOException e) {
	    System.err.println("Error: reading file '" + file + "' failed.\n" + e);
	    e.printStackTrace();
	}
    }
}