Überprüfen, ob alle Scheitelpunkte in einer Schleife verbunden sind

Question

Ich schreibe ein Projekt, wo Sie ein Polygon mit Scheitelpunkten und Linien verbinden können und dann in eine Physik-Engine wie pymunk laufen lassen.

Ich möchte sicherstellen, dass alle Knoten in einer Schleife wie diese

verbunden sind, und wenn es nicht ganz wie so

verbunden ist Jeder Knoten ist ein Vertex-Objekt, das unter

class Vertex(): 
    def __init__(self, id, position, pointsTo = [], rectSize = [10, 10]): 
     self.id = int(id) 
     self.position = tuple(position) 
     self.rect = tuple((position[0], position[1], rectSize[0], rectSize[1])) 
     self.pointsTo = list(pointsTo) 

    def setPosition(self, position): 
     self.position = tuple((position[0] - (self.rect[2]/2), position[1] - (self.rect[3]/2))) 
     self.rect = tuple((self.position[0], self.position[1], self.rect[2], self.rect[3])) 

    def getRect(self): 
     return self.rect 

Wo pointsTo eine Liste der Scheitelpunkte ist, die an diesem Eckpunkt verbunden sind .Wie würde ich herausfinden, ob eine Liste von Scheitelpunkten in einer Schleife miteinander verbunden ist

Answer 1

Wenn wir es als Graphen betrachten, haben wir den Scheitelpunkt, und pointsTo ist eine Adjazenzliste von Kanten. Ich nehme auch eine ungerichtete Graphik an, basierend auf der Illustration in der Frage, also wenn A-> B, dann B-> A. Wir können uns ein Polygon als einen N-Zyklus vorstellen. Ich ignoriere die Möglichkeit von Kanten, die sich auf dem Bildschirm ohne tatsächlichen Scheitelpunkt im Diagramm kreuzen.

Angenommen, es ist ein N-Zyklus. Dann hat jeder Eckpunkt genau zwei Kanten und alle Eckpunkte sind verbunden. Beides ist einfach zu testen.

(Hinweis: Wenn jeder Scheitelpunkt genau zwei Kanten hat, dann haben Sie sich verbunden. Der verbundene Test ist nur um zu sehen, ob es mehrere Polygone gibt, und um den Beweis zu erleichtern. Siehe für eine ähnliche Wie dieses berühmte Problem zeigt, könnten Sie sogar testen, ob Sie mehrere Polygone zulassen, aber nur nach zusätzlichen Linien suchen möchten, die nicht zu einem Polygon verbunden sind.

hypothetisch, beginnen Sie an einem beliebigen Punkt und beginnen Sie, die Punkte zu Vertices zu besuchen, die dem Graphen folgen, und niemals eine zuvor besuchte Kante/Vertex zu verwenden. Jedes Mal, wenn Sie einen neuen Scheitelpunkt besuchen, ist es das erste Mal, dass Sie dort waren. Daher können Sie die anderen Punkte nicht an diesem Scheitelpunkt verwenden, sodass Sie fortfahren können, bis Ihnen die Scheitelpunkte ausgehen. Zu diesem Zeitpunkt haben Sie zwei unbenutzte pointsTo - one im Startknoten und einen außerhalb des Endvertex. Entweder zeigen sie auf einen Knoten, der nicht existiert, oder sie zeigen aufeinander, was bedeutet, dass es sich um einen N-Zyklus handelt.

Somit ist der obige Test bewiesen.

Ich sagte, es ist leicht, Dinge zu testen, so muss ich tun, so: Um zu testen, dass die Kurve, siehe https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

verbunden ist

eine Begegnungsflag hinzufügen (auf false initialisiert) mit allen Ecken. Wählen Sie einen beliebigen Eckpunkt aus und beginnen Sie, Nachbarn zu besuchen. Wenn Sie ausgehen, sehen Sie, ob ein Vertex nicht besucht wurde.

oder machen Sie eine Reihe von vertex.id's, fügen Sie sie beim Besuch hinzu. Am Ende prüfen len (das Set) ist die Anzahl der Ecken in der Grafik

Answer 2

Sie müssen bei der Definition eines Strongly Connected Component suchen und dann testen, ob Ihr Diagramm als stark von Ihrem Vertex und Edges dh Vertex.pointsTo Formen dargestellt Verbundene Komponente mit allen Vertices in Ihrer Liste.