Ich möchte in Java zufällige, ungerichtete und verbundene Graphen erzeugen können. Außerdem möchte ich in der Lage sein, die maximale Anzahl von Scheitelpunkten in der Grafik zu steuern. Ich bin nicht sicher, was der beste Weg wäre, um dieses Problem anzugehen, aber hier sind ein paar, die ich mir vorstellen kann:
(1) Erzeuge eine Zahl zwischen 0 und n und sei die Anzahl der Scheitelpunkte. Verknüpfen Sie die Knoten dann willkürlich miteinander (erzeugen Sie vielleicht eine zufällige Zahl pro Knoten und die Anzahl der Kanten, die aus dem Knoten herauskommen). Durchsuche den Graphen ausgehend von einem beliebigen Eckpunkt (etwa bei der Breiten-Ersten-Suche) und lass unser zufälliges Diagramm G alle besuchten Knoten sein (auf diese Weise stellen wir sicher, dass G verbunden ist).
(2) Erzeuge eine zufällige quadratische Matrix (von 0 's und 1 ' s) mit Seitenlänge zwischen 0 und n (irgendwie). Dies wäre die Adjazenzmatrix für unser Diagramm (die Diagonale der Matrix sollte dann entweder alle 1 oder alle 0 sein). Erstellen Sie eine Datenstruktur aus dem Diagramm und durchlaufen Sie das Diagramm von einem beliebigen Knoten, um eine verbundene Liste von Knoten zu erhalten, und rufen Sie das Diagramm G auf.
Jede andere Möglichkeit, eine ausreichend zufällige Grafik zu erzeugen, ist willkommen. Hinweis : Ich brauche keinen rein zufälligen Graph, d. h. der Graph, den Sie erzeugen, muss keine speziellen mathematischen Eigenschaften haben (wie Gleichförmigkeit irgendeiner Art). Ich brauche einfach viele und viele Graphen für Testzwecke von etwas anderem.
Hier ist die Java Node Klasse, die ich verwende:
Hier ist die Graph -Klasse, die ich verwende (Sie können sagen, warum ich im Moment nur an verbundenen Graphen interessiert bin):
Als Beispiel, so mache ich jetzt Graphen für Testzwecke:
%Vor%Was auch immer Sie mit Ihrem Graphen machen wollen, ich schätze seine Dichte ist auch ein wichtiger Parameter. Andernfalls würden Sie nur eine Gruppe kleiner Cliquen (vollständige Graphen) mit zufälligen Größen generieren und diese dann zufällig verbinden.
Wenn ich richtig liege, würde ich Ihnen raten, das Erdős-Rényi-Modell : Es ist einfach, nicht weit von dem, was Sie ursprünglich vorgeschlagen, und ermöglicht es Ihnen, die Graph-Dichte zu steuern (also im Grunde: die Anzahl der Links).
Hier ist eine kurze Beschreibung dieses Modells:
Wenn bei diesem Modell Ihr p groß genug ist, ist es sehr wahrscheinlich, dass Ihr Graph verbunden ist (siehe die Wikipedia-Referenz für Details). In jedem Fall können Sie, wenn Sie mehrere Komponenten haben, deren Verbundenheit erzwingen, indem Sie Verbindungen zwischen Knoten verschiedener Komponenten erstellen. Zuerst müssen Sie jede Komponente identifizieren, indem Sie die erste Suche durchführen (eine für jede Komponente). Anschließend wählen Sie Knotenpaare in zwei verschiedenen Komponenten aus, erstellen eine Verknüpfung zwischen ihnen und betrachten beide Komponenten als zusammengeführt. Sie wiederholen diesen Vorgang, bis Sie eine einzelne Komponente übrig haben.
Der einzige knifflige Teil ist sicherzustellen, dass der letzte Graph verbunden ist. Um dies zu tun, können Sie eine disjunkte Set-Datenstruktur verwenden. Verfolgen Sie die Anzahl der Komponenten, zunächst n. Wählen Sie wiederholt Paare von zufälligen Scheitelpunkten u und v, fügen Sie dem Diagramm und der disjunkten Mengenstruktur die Kante (u, v) hinzu und dekrementieren Sie die Komponentenanzahl, wenn die Struktur besagt, dass u und v zu verschiedenen Komponenten gehören. Stoppen Sie, wenn die Komponentenanzahl 1 erreicht. (Beachten Sie, dass die Verwendung einer Adjazenzmatrix die Verwaltung des Falls vereinfacht, in dem die Kante (u, v) bereits in der Grafik vorhanden ist. In diesem Fall wird adj [u] [v] auf 1 gesetzt ein zweites Mal, das wie gewünscht keine Wirkung hat.)
Wenn Sie feststellen, dass Diagramme zu dicht (oder zu spärlich) erstellt werden, können Sie mit einer anderen Zufallszahl Kanten nur in k% der Zeit hinzufügen, wenn die Endpunkte bereits Teil der gleichen Komponente sind (oder wenn sie bereits vorhanden sind) Teil von verschiedenen Komponenten), für einige k.