AnleitungIn diesem Abschnitt wird ein Beispielprojekt erzeugt, um die wichtigsten Funktionen von Rocs zu zeigen. Als Ziel soll ein Graph und ein Skript erstellt werden, um damit einen einfachen Approximationsalgorithmus für das Minimum-Knotenüberdeckungproblem zu zeigen, der eine Knotenüberdeckung mit Güte 2 berechnet. Mit dem Minimum-Knotenüberdeckungsproblem wird eine Untermenge von Graphenknoten C mit minimaler Größe gesucht, so dass jede Graphenkante mit mindestens einem Knoten in C verbunden ist. Dies Problem ist NP-vollständig. Es soll gezeigt werden, wie eine Approximation mit dem Faktor 2 durch Suchen nach Matching in den angegebenen Graphen berechnet wird.
Ziel ist die Visualisierung der Beziehung von Matching-Knotenüberdeckungen und Minimum-Knotenüberdeckungen. Dazu werden zwei Kantentypen definiert, einer für die Matching-Kanten und einer zur Darstellung normaler Kanten, außerdem noch zwei Datentypen, die zur Unterscheidung von in C enthaltenen bzw. nicht enthaltenen Knoten verwendet werden.
Zum Erstellen eines Graphen verwenden Sie in der Voreinstellung den Graphen-Generator von Rocs. Wählen Sie dazu im Menü → → . Wählen Sie einen Zufälligen Graph mit 30 Knoten, 90 Kanten und mit Seed = 1. Seed ist der Startwert für den Generator des zufälligen Graphen. Wird der gleiche Seed verwendet, ergibt das auch reproduzierbar den gleichen Graphen.
Öffnen Sie die Seitenleiste Elementtypen und erstellen Sie einen zweiten Knotentyp und auch einen zweiten Kantentyp. Klicken Sie bei beiden neuen Typen auf den Knopf , um einen Dialog zu öffnen. Setzen Sie die Kennung der neuen Typen auf 2 und geben Sie ihnen eine andere Farbe, um si von den Standardtypen zu unterscheiden. Dann setzen Sie alle Kantentypen auf Bidirektional und stellen die Kennung der Standardtypen auf 1.
Dann muss der Algorithmus der Approximation wie im folgenden implementiert werden:
for (var i=0; i < Document.nodes.length; i++) {
Document.nodes[i].type = 1;
}
for (var i=0; i < Document.edges.length; i++) {
Document.edges[i].type = 1;
}
var E = Document.edges(); // Menge der nicht bearbeiteten Kanten
var C = new Array(); // Matching-Kanten
while (E.length
> 0) {
var e = E[0]; // die erste Kante e={u,v}
var u = e.from();
var v = e.to();
e.type = 2; // als Matching-Kanten setzen
E.shift(); // e (i.e., E[0]) aus der Liste der Kanten entfernen
C.push(u); // u zu C hinzufügen
C.push(v); // v zu C hinzufügen
// u,v als Knoten von C markieren C
u.type = 2;
v.type = 2;
// von E alle Kanten entfernen, die inzident zu u oder v sind
var adjacent = u.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // Index suchen
if (index != -1) {
E.splice(index, 1); // Löschen, wenn gefunden
}
}
var adjacent = v.adj_edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // Index suchen
if (index!=-1) {
E.splice(index, 1); // Löschen, wenn gefunden
}
}
}
Console.log("Knotenüberdeckung enthält " + C.length + " Knoten.");