1400×1050 with Intel Mobile 915GM

I started off with a clean Suse 9.2 installation. After various dead ends, this is what I did so far:

  • Reinstall X.org (X11R6.8.2) from the sources. This seems necessary to compile the Intel drivers.
  • Install Intel’s linux driver. Without recompiling X first, this kind of fails, but still seems to do something to the system. After the above reinstallation, the installation succeeds without an error.
  • Run “modprobe intel-agp” before starting X. Obviously, this should be automated, once everything is working.
  • Set 1400×1050 as a legal resolution in the Video Bios using 855resolution. However, this doesn’t seem to work with my Bios.
  • I guess I’ll have to update 855resolution. That doesn’t seem so difficult after all. the trick seems to be to make the video bios writable by talking to the right ports. Fortunately, the Intel 915GM Specification is freely available. Thanks, Intel!
  • It turns out there is a tool that tweaks the 915GM!!! The tools is available on Steve Tomljenovic Geocities site (thank you, Steve!!!), and I got pointed there by Christian Zietz on the XFree86.Org Developers Mailing List (thank you, Christian!!!).
  • The tool 915resolution must run on every start – just put the following in /etc/rc.d/boot.local: “915resolution 5c 1400 1050” (on Suse)

Windows Refund for Laptops…?

The short answer is no.

The long story: I looked on the web, but there was suspiciously little information available. The best I found was this Linux Journal Article, and going to court sounded like too much trouble for me. I also Asked Slashdot, and while the discussion was interesting, there was little useful information there.

But here is the interesting twist: I went to Microsoft’s web site and checked out the Windows XP Professional License, which definitely sounded like I could return the software and keep the computer:

“This EULA is a legal agreement (…) for the Microsoft software product identified above (…) (“Product”). (…) IF YOU DO NOT AGREE, DO NOT INSTALL OR USE THE PRODUCT; YOU MAY RETURN IT TO YOUR PLACE OF PURCHASE FOR A FULL REFUND.”

However, when I actually looked at the license of the laptop I bought, it turned out that it had a different license! And it was very specific about not being able to return the software without returning the computer at the same time:

“This EULA is a legal agreement between you (…) and the manufacturer of the computer system or computer system (“HARDWARE”) with which you acquired the Microsoft software product(s) identified on the Certificate of Authenticity (“COA”) affixed to the HARDWARE. (…) IF YOU DO NOT AGREE TO THE TERMS OF THIS EULA (…) YOU SHOULD PROMPTLY CONTACT MANUFACTURER FOR INSTRUCTIONS ON RETURN OF THE UNUSED PRODUCT(S) FOR A REFUND. (…) The SOFTWARE is licensed with the COMPUTER as a single integrated product.

How twisted! Not only do they explicitly state that I cannot return the software, they also state that the software is “bound” to this computer. Well, on the other hand, by using a license like this, they probably only payed a fraction of the official XP price for the software. I’ll keep Windows around on a small partition, as a backup, but this license still bothers me.

Tricks mit Collections

Hash und Tree Implementierungen

Ich gehe mal davon aus, dass der Leser die Collection Interfaces List, Set und Map kennt. Reden wir doch mal ein bisschen über Sets:

Set fruit = new HashSet(); fruit.add("Apple"); fruit.add("Orange"); fruit.add("Banana"); fruit.add("Cherry"); System.out.println(fruit); 

[Apple, Orange, Banana, Cherry]

Soweit, so gut. Was aber, wenn wir die Früchte alphabetisch sotiert haben wollen? Das erreichen wir ganz einfach, indem wir statt einem HashSet ein TreeSet benutzen:

Set fruit = new TreeSet(); 

[Apple, Banana, Cherry, Orange]

Warum funktioniert das? Weil im zweiten Fall die Implementierung den Inhalt des Sets in einer Baumstruktur speichert, und damit garantiert, dass Einträge in log(n) gefunden werden können. Beim HashSet hingegen kann die Performanz an die Bedürfnisse gut angepaßt werden, indem beim Instantiieren die Anzahl der “Buckets” der Anwendung entsprechend gesetzt wird.

Im allgemeinen sind die Hash-Funktionen schneller, aber ein sortiertes Set zu haben, kann unbezahlbar sein. Ein paar Dinge sind zu beachten: Elemente im TreeSet müssen Comparable implementieren, sonst wird eine Exception geworfen. Außerdem kann ein HashSet null enthalten, TreeSet nicht.

Initialisierung

In dem Beispiel weiter oben wollen wir vier Früchte in unserem Set haben. leider können wir diese nicht dem Konstruktor mitgeben. Aber mit einem Trick wir können eine Klasse ableiten, die diese Werte in das Set einträgt:

Set fruit = new TreeSet() {{ add("Apple"); add("Orange"); add("Banana"); add("Cherry"); }}; 

Collections Klasse

die Collections Klasse wird oft übersehen, enthält aber einen Haufen unglaublich pratischer statischer Methoden. Diese fallen in die folgenden Kategorien:

Such- und Sortierfunktionen: Kleinstes und größtes Element, oder gleich die ganze Liste sortieren, und mit bestimmten Suchalgorithmen ein Element finden. Es können auch gezielt nur bestimmte Teile einer Liste durchsucht werden.

Kopieren, ersetzen, verdrehen: Collections können per Zufall vermischt werden, Kopien erstellt werden, oder mit einem bestimmten Objekt viele Male gefüllt werden.

Wrapping: Eine unmodifizierbare oder synchronisierte Version einer Collection können erzeugt werden. Besonders das Wrapping ist extrem nützlich. Wenn eine Funktion ein Set zurückgibt, das nicht verändert werden darf, kann das entweder dokumentiert werden (kann ignoriert werden), oder ein neues Set kann erzeugt werden:

return new TreeSet(fruit); 

Oder, die beste Lösung, wir geben ein nicht modifizierbares Set zurück:

return Collections.unmodifiableSet(fruit); 

Anfragen an das zurückgegebene Set werden an das interne Set weitergegeben – aber jeder Versuch, das Set zu ändern, wirft eine UnsupportedOperationException. Das war’s für heute! Zum Abschluß möchte ich noch herzlich den Collections Framework Overview empfehlen, der noch weiter auf die Philosophie der Architektur eingeht. Viel Spaß beim Lesen!

Larry Summers und Diskriminierung gegen Frauen

Was ist der eigentliche Skandal? Das Thema “Akademische Karrieren für Frauen” anzusprechen ist grundsätzlich legitim. Die Frage ist, ob Summers, in der Rolle des Präsidenten von Harvard, dieses Thema ansprechen darf. Vom Economist:

    “And the firestorm is not about one judgment, but about his right to raise the issue of innate differences at all.”

Jetzt, wo die Katze aus dem Sack ist, stellen sich zwei ganz wichtige Fragen: (1) Hat Summers recht oder nicht mit seinen drei Thesen:

  • Discrimination and social pressure might hold women back
  • 80-hour-a-week science careers might be harder for women to take on
  • the outcome might be related to findings that men tend to be over-represented at the top of science-aptitude tests

Und (2), was man deswegen unternehmen sollte.

In Anbetracht der Tatsache, dass Summer gebeten wurde, eine provokative Rede zu halten, und zwar nicht in der Rolle des Harvardpräsidenten, kann ich schon nachvollziehen, wie es zu dieser Rede kam.

    “Note first that this was given in a private capacity to an economics conference, and that he had been briefed to ask provocative questions”

Meine persönliche Meinung: Ich glaube nicht, dass Summers sexistisch ist, oder rücksichtslos. Aber ich glaube auch nicht, dass er diese Rede “aus versehen” gehalten hat, und sich nicht über die Implikationen im Klaren war. Summers hat noch nie etwas davon gehalten, sich auf Zehenspitzen zu bewegen (ich war in Boston, als er das Thema “Grade Inflation” ansprach – das gab auch einen ganz schönen Aufruhr). Ich glaube, dass er das Thema bewusst angesprochen hat, um die Situation zu verbessern. Von seiner Rede:

    “What should we all do? I think the case is overwhelming for employers trying to be the [unintelligible] employer who responds to everybody else’s discrimination by competing effectively to locate people who others are discriminating against, or to provide different compensation packages that will attract the people who would otherwise have enormous difficulty with child care. (…) But I think it’s something that has to be done with very great care because it slides easily into pressure to achieve given fractions in given years, which runs the enormous risk of people who were hired because (…) being seen by others as having been hired for some other reason. And I think that’s something we all need to be enormously careful of as we approach these issues, and it’s something we need to do, but I think it’s something that we need to do with great care. ”

Und damit spricht Summer selbst an, was die Sorge des Authors des Emails war, weswegen ich dies alles schreibe:

    Ein befreundeter Theologe und Unternehmensberater macht mich auf eine Kontroverse bei Harvard aufmerksam, deren Bedeutung weit über diese und andere Universitäten hinausreicht. Es geht um die Frage, wie der möglicherweise unterschiedliche “Erfolg” von Frauen und Männern in der Wissenschaftskarriere zu beurteilen ist, und welche Konsequenzen sich daraus für die Anstellungspraxis ergeben.

Aber hier ist noch ein weiterer, wichtiger Aspekt: Diese Diskussion hat unterschiedliche Implikationen auf den amerikanischen und den deutschen Markt.

Zunächst der Amerikanische: Ich würde behaupten, dass es in dem diskutieren Arbeitsmarkt (Professuren fuer die Ivy League) keine Diskriminierungen gegen Frauen gibt, und gerade in der Einkommensklasse wird penibel auf “Political Correctness” geachtet (uebrigens ist MITs Praesident seit kurzem eine Frau, Susan Hockfield). Als vor kurzem Carly Fiorina, CEO von HP, gefeuert wurde, war sich die Presse einig, dass sie wegen Inkompetenz, und nicht Diskriminierung gehen musste. Dennoch werden lediglich 7 von den Fortune 500 Firmen von Frauen geleitet – warum? Diese Frage versuchte Summers zu beantworten.

Meiner (subjektiven) Meinung nach ist der Deutsche Arbeitsmarkt wesentlich diskriminierender, und nicht nur gegen Frauen, sondern auch ältere Menschen. Hier ist eine Geschichte von einer Freundin (das war Anfang der 90er). Sie bewarb sich um eine Stelle, die sie nicht bekam. Die Personalchefin sagte ihr “unter der Hand”, dass sie zwar kompetent sei, aber sich die Firma es sich nicht leisten kann, eine Frau in den Mitte 20ern einzustellen. Ich weiss nicht, wie sich Deutschland in den letzten 15 Jahren gewandelt hat, aber die Geschichte hat mir doch einen ganz schönen Schrecken eingejagt.

Zum Absschluss noch ein weiteres Zitat aus dem Economist:

    “In the end, the debate about Mr Summers comes down to a simple choice. On one side sit short-term expediency and censorship; on the other, freedom of speech and long-term effectiveness. If Mr Summers’s foes manage to sack or gag him, they may have a happier university in the short term. But they will have snuffed out an invigorating source of criticism in a cosy world. And they will also have endangered the fundamental right of an academic to ask questions. This should be enough to make liberal opinion everywhere start gasping for air.”

“The Gates”

I was lucky enough to see the Exibit, on the second day. It was a beautiful day with blue sky. Conciously, we entered the park on 86th Street (West Side), as we correctly assumed it would be less crowded there than on 59th Street. The first impression was… anticlamactic. After having seen pictures of the German Reichstag, initially, the installation felt small. But after strolling through the park for only a few minutes, everything started to sink in, and it was a beautiful, meditative experience. There was so much to discover, everybody had time and it felt like learning to see all over again. Did you ever have the experience of visiting a new city, looking at every building and going “wow”? Did it ever occur to you that you’d do the same in your home town, if it wouldn’t be your home town?

We strolled through the park for three hours, and it was worth it every minute of it. As a highlight, we saw Christo and Jeanne-Claude drive by in a limo with their entourage. I didn’t feel the need to come back – still today, they day the installation is taken down, I feel a little melancoly and still happy that I was lucky enough to experience this.

Unit Tests: Und private Methoden…?

Es ist eine gute Sache, daß ich mehr Unit Tests schreibe! Das hat zum einen damit zu tun, daß ich eine Menge gelernt habe; aber auch damit, daß ich viel GUI Code schreibe, und die GUI zum Testen zu starten ist extrem ineffizient.

Aber zum Thema private Methoden: Das Thema wurde für mich wieder aktuell, als ich vorgestern einen Vortrag von Andrew Glover zum Thema “Code Metrics for Targeted Code Refactoring” gehört habe (Organisiert von der Philadelphia JUG). Das Thema Unit Testing von privaten Methoden kam zur Sprache, und er erwähnte das JunitX Projekt, das dies ermöglicht.

Aber bevor wir ins Detail gehen, sollten wir uns die Frage stellen: Ist es überhaupt richtig, private Methoden zu testen, und was sind bessere Lösungen oder Alternativen?

Ich höre oft: “Wenn Du glaubst, private Methoden testen zu müssen, ist das ein Warnsignal.” Private Methoden sollten durch die nicht-privaten Methoden getestet werden, die sie benutzen. Sollte das nicht möglich sein, sollte die Architektur überdacht werden.

Ich stimme dem zu, daß diese Situationen mit Skepsis betrachtet werden sollten. Allerdings liegt meiner Meinung nach die Betonung von “Unit Test” auf “Unit”, und je kleiner die getestete Einheit, umso besser. Wenn ein Methode zu unübersichtlich wird (z.B. > 600 Zeilen), dann macht es Sinn, Teile in private Methoden auszulagern (und die Architektur zu überdenken, aber manchmal geht es eben nicht anders). Und meiner Meinung nach macht es viel Sinn, diese Teile einzeln zu prüfen. Und wenn wir diese kleinen Hilfsmethoden schreiben bevor die sie nutzende Methode geschrieben ist, dann macht es erst recht Sinn, diese zu testen. Bill Venners hat einen exellenten Aufsatz zu dem Thema geschrieben.

package private

Was können wir also tun? Das einfachste ist, die zu testenden Methoden package private zu machen. Eine package private Methode hat keine Qualifizierer (also weder private, protected oder public), und kann lediglich von Klassen in der selben Package gesehen werden. Vorteil: Extrem leicht zu implementieren; Refactoring (z.B. umbenennen) funktioniert problemlos, weil das Refactoringwerkzeug alle Referenzen finden kann. Nachteil: Wir verletzen Encapsulation. Das muß jeder für sich entscheiden, wie wichtig das ist. Aber ich finde es sehr wichtig. Zum einen gibt der Qualifizierer dem Entwickler ein starkes Signal und erlaubt, mit einem Blick die Bedeutung einer Methode einzuschätzen. Hinzu kommt, daß Eclipse mich warnt, wenn eine private Methode nicht benutzt wird. Das geht leider nicht mit package private Methoden.

Reflektion

JunitX benutzt Reflektion, um auf private Methoden zuzugreifen, und dieser Ansatz gefällt mir. Allerdings habe ich es nicht geschafft JunitX zum Laufen zu bringen (Version 5.1 schien noch nicht einmal richtig gejart worden zu sein, und 5.0 schien Bugs im Code zu haben). Aber es gibt ja genug Alternativen, und Junit Addons erfüllt diese Rolle – die Klasse junitx.util.PrivateAccessor, um genau zu sein. Diese Klasse ist sehr leicht zu nutzen. Nehmen wir mal an, wir wollen die folgende Methode testen:

 class RocketScience { private static boolean isPrime(int number) { ... } } 

Und hier ist der Test Code, der diese Methode testet:

 public void testIsPrimeExpectFalse() throws Throwable { Object isPrime = PrivateAccessor.invoke( RocketScience.class, "isPrime", new Class[] { Integer.TYPE }, new Object[] { new Integer(8) }); assertEquals(isPrime, Boolean.FALSE); } 

Diese Beispiel zeigt auch sehr schön, wie wir die Konvertierung von Primitives (int, boolean, etc.) zu Objekten durchführen, denn Reflektion funktioniert nur für Objekte. Natürlich würde man eine Methode wie diese in der Praxis nie Privat machen, sondern in einer Werkzeugklasse verfügbar machen – aber das ist ja nicht der Punkt von diesem Beispiel.

Die Sache hat einen einzigen Haken: Der Compiler (und die IDE) kann keine Korrelation zwischen diesem Test under der getesteten Methode erkennen, und wenn die Methode umbenannt wird, wird dieser Test nicht erkannt. Aber das ist in Ordnung – denn der Test wird versagen, und kann schnell und einfach repariert werden.

Using procmail with the Courier MTA and virtual mailboxes

It was tricky, as it wasn’t clear on how to tell procmail where to get its configuration and the processed files. First, the Courier Documentation clearly says how to do this with non-virtual mailboxes. In the /etc/courier/courierd configuration file, change the line

 DEFAULTDELIVERY=./Maildir 

to

 DEFAULTDELIVERY="| /usr/bin/preline /usr/bin/procmail" 

But this in itself doesn’t work – because procmail tries to process mail for the virtual mailman account (vmailman). The home directory for vmailmain is /var/mail, so it looks for /var/mail/.procmailrc. But procmail complains because of the permissions on that directory, and I really don’t want to change them anyway. And even if I change them, I won’t be able to distinguish the various virtual users (which each have directories under /var/mail).

In the end things were simple, because courier conveniently calls procmail in the virtual user’s home directory (e.g. /var/mail/user1. procmail takes a configuration file as an argument, so the following line in /etc/courier/courierd does the trick:

 DEFAULTDELIVERY="| /usr/bin/preline /usr/bin/procmail ./.procmailrc" 

I still need a custom .procmailrc file in each virtual user directory (because procmail needs absolute paths), but that’s something I can live with.

Don’t worry – it’s getting better after Monday

The components of the formular are weather, debt, money due on January’s pay day, the time since Christmas, the period since the failure to quit a bad habit, general motivational levels and the need to take action and do something about it.

As I said, it can only get better…

Ringe in Molekülen

Graf Propagations-Applet
Weiter Unten >>

Disclaimer: Den hier beschriebenen Algorithmus benutzen wir zur Zeit nicht bei meinem Arbeitgeber, und ich habe ihn in meiner Freizeit entwickelt. Die Aufgabe wurde lediglich durch meine Arbeit inspiriert.

Übrigens, Sie können per Email benachrichtigt werden, wenn ein neuer Newsletter veröffentlicht wird. Einfach ein Profil einrichten – keine Sorge, ich verspreche, nicht zu Spammen!

Was ist überhaupt das Problem? Rechts ist ein Molekül abgebildet. Falls Sie sich wundern, daß viele Verbindungen kein Atomzeichen haben: Es ist üblich, Kohlenstoff (C) implizit durch die Ecken darzustellen, und Wasserstoff (H) wird nie gezeichnet. Aber das berührt unser Problem nicht.

Wieviele Ringe hat dieses Molekül? Auf den ersten Blick wissen wir, daß es vier sind. Allerdings würde ein Algorithmus wahrscheinlich fünf sehen. Warum? Der Doppelring links oben enthält zwei kleine Ringe, und einen beide kleinen Ringe umspannenden größeren Ring. Wie ich weiter unten beschreiben werde, müssen wir diese Ringe später wieder entfernen.

Wie sollen wir Ringe repräsentieren? Dazu zog ich Robert Sedgewick’s “Algorithms in C++” zu Rate (eine uralte Edition – inzwischen gibt’s auch eine Java Ausgabe). Denn ein Molekül kann als Graf dargestellt werden. Ein Graf besteht aus Punkten (Atomen), und Kanten zwischen diesen Punkten (Bindungen). Sedgewick schlägt zwei Datenstrukturen vor, um Grafen intern zu speichern. Für dieses Problem bietet sich die “adjacency-structure” Representation an. Bei dieser Representation haben wir eine Liste mit allen Punkten, die wiederum mit einer Liste von verbundenen Punkten assoziiert sind. Zum Beispiel würden wir die folgende Datenstruktur für Wasser (H1-O-H2) bekommen:

 H1 -> [ O ] H2 -> [ O ] O  -> [ H1 H2 ] 

Beachten Sie, daß jede Bindung zweimal auftaucht. Den “verschwendeten” Speicherplatz nehmen wir gerne in Kauf. In einem Molekül sind nicht alle Bindungen gleich (einfach, doppelt, etc.). Das könnten wir speichern, indem die Einträge in der Liste Datenstrukturen sind, die diese Information auch noch aufnehmen. Um unsere Ringe zu finden, ist der Bindungstyp allerdings unwichtig.

Unser erstes Ziel ist es, den gesamten Graf abzugrasen, und zwar immer entlang der Kanten. Dabei gibt es natürlich viele, viele Wege. Sedgewick bietet zwei Algorithmen an mögliche Wege zu finden: der eine geht in die Tiefe, der andere in die Breite. Hier ist ein Diagram aus seinem Buch das den Unterschied visualisiert:

Die roten Linien zeigen die ersten Schritte eines tiefen bzw. breiten Wanderalgorithmusses. Der tiefe springt so schnell wie möglich von Punkt zu Punkt, und kehrt nur dann zu Abzweigungen zurück, wenn es nicht weiter geht. Der breite folgt allen möglichen Abzweigungen, und geht erst dann weiter vorwärts, wenn alle Abzweigungen besucht wurden. Ich denke, es ist intuitiv klar, daß der breite Algorithmus kleine, geschlossene Ringe findet. Mit dem folgenden Applet können Sie selbst Grafen erstellen, und sie mit dem gleich beschriebenen Algorithmus propagieren lassen:

Ihr Browser unterstützt nicht das <APPLET> tag!
Klicken erzeugt einen Punkt. Ziehen von einem Punkt zum anderen erzeugt eine Kante. Zum Propagieren, einen Punkt anklicken.

Weiß: Noch nicht besucht
Rot: Punkt wird besucht
Gelb: Punkt wird untersucht
Grau: Punkt wurde besucht

Aber wie funktionieren die Algorithmen, und wie benutzen wir sie? Ich werde hier nur den breiten beschreiben, weil wir den benutzen. Hier soll nur bemerkt werden, daß die Algorithmen sich ähneln, und daß der tiefe Algorithmus leicht rekursiv zu programmieren ist, während der breite sich gut als Schleife schreiben läßt. Und hier ist der Algorithmus:

Map graf; // Object -> Set von verbundenen Objekten Set visited; // Set von besuchten Objekten void visit(Object head) { List queue = new ArrayList(); queue.add(head); while (! queue.isEmpty()) { Object entry = queue.remove(0); visited.add(entry); // hier entry verarbeiten Set neighbors = (Set)graf.get(entry); for (Iterator i = neighbors.iterator(); i.hasNext();) { Object neighbor = i.next(); boolean wasVisited = visited.contains(neighbor); if (! wasVisited) queue.add(neighbor); } } } 

Ein paar Kommentare:

  • Der Graf ist in der Variablen graf in der form einer Map gespeichert. Die keys sind die Knoten, die mit einem Set assoziiert sind, welches die verbundenen Knoten enthält.
  • Das Set visited enthält die Knoten, die bereits besucht wurden, und muss vor jeder neuen iteration zurückgesetzt werden.
  • Wenn die Funktion “visit” aufgerufen wird, werden alle verbundenen Punkte entlang ihrer Kanten berührt. Sollte der Graf nicht verbunden sein, so kann man einfach für alle Punkte im Graf (also über graf.getkeys() iterieren) visit aufrufen.

Ich hoffe, daß dieser Algorithmus, im Zusammenhang mit dem Applet die Zusammenhänge verständlich macht. der gesamte Code für das Applet ist verfügbar. Falls Sie mit dem Code experimentieren möchten, können Sie weitere Implementierungen des Interfaces Crawler erstellen.

  • Crawler – ein Interface für die Implementierung von Algorithmen.
  • WidthCrawler – Implementierung eines Crawlers, der in der Breite sucht.
  • Visitor – Das Visitor Interface ist ein Argument für den Crawler, um beim Besuch eines Knoten Code ausführen zu können.
  • DrawingCanvas – Die Benutzeroberfläche: Swing Canvas der es dem Benutzer ermöglicht, Grafen zu zeichnen und die Propagation visuell auszuführen.
  • GrafDemo – Die Klasse stellt den Einstiegspunkt ins Programm zur Verfügung, das als Applet oder als Java Anwendung ausgeführt werden kann.

Wir haben zwar eine Menge geschafft heute, aber es gibt noch einiges zu tun, bis wir die Ringe haben. Vielleicht werde ich das Thema in der Zukunft noch einmal ansprechen. Falls nicht, hier sind die Schritte, die wir durchführen müssen, um die Ringe zu finden:

  • Den Propagator anhalten, sobald der Anfangspunkt wiedergefunden wurde, ohne Ecken zweimal zu benutzen (einmal vor und zurück gilt nicht!). Dann haben wir nämlich einen Ring gefunden.
  • Den Propagator für jedes Atom einmal ausführen. Damit finden wir alle Ringe, denn jeder Ring hat mindestens ein Atom, daß mit keinem anderen Ring geteilt wird.
  • Ringduplikate ausfiltern!
  • Doppelringe wie oben beschrieben rausfiltern. Das machen wir, indem wir Ringe suchen, die zwei oder mehr Kanten gemeinsam haben. Den größeren von den zweien entfernen wir.

Bleibt nur noch die Frage, ob wir mit diesem Algorithmus wirklich alle Ringe finden. Außerdem könnten wir noch die Performance des Algorithmus untersuchen. Ich überlasse dies gerne dem Leser.