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