Python - Graphen

Ein Diagramm ist eine bildliche Darstellung einer Gruppe von Objekten, bei denen einige Objektpaare durch Verknüpfungen verbunden sind. Die miteinander verbundenen Objekte werden durch Punkte dargestellt, die als Scheitelpunkte bezeichnet werden, und die Verknüpfungen, die die Scheitelpunkte verbinden, werden als Kanten bezeichnet. Die verschiedenen Begriffe und Funktionen, die mit einem Diagramm verbunden sind, werden in unserem Tutorial hier ausführlich beschrieben. In diesem Kapitel erfahren Sie, wie Sie mit einem Python-Programm ein Diagramm erstellen und verschiedene Datenelemente hinzufügen. Im Folgenden sind die grundlegenden Operationen aufgeführt, die wir für Diagramme ausführen.

• Diagrammscheitelpunkte anzeigen
• Diagrammkanten anzeigen
• Fügen Sie einen Scheitelpunkt hinzu
• Fügen Sie eine Kante hinzu
• Diagramm erstellen

Mit den Datentypen des Python-Wörterbuchs kann ein Diagramm einfach dargestellt werden. Wir repräsentieren die Eckpunkte als Schlüssel des Wörterbuchs und die Verbindung zwischen den Eckpunkten, die auch als Kanten bezeichnet werden, als Werte im Wörterbuch.

Schauen Sie sich die folgende Grafik an -

In der obigen Grafik

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Wir können dieses Diagramm in einem Python-Programm wie folgt darstellen.

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
          "b" : ["a", "d"],
          "c" : ["a", "d"],
          "d" : ["e"],
          "e" : ["d"]
         }

# Print the graph 		 
print(graph)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}

Diagrammscheitelpunkte anzeigen

Um die Diagrammscheitelpunkte anzuzeigen, finden wir einfach die Schlüssel des Diagrammwörterbuchs. Wir verwenden die Methode keys ().

class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = []
        self.gdict = gdict

# Get the keys of the dictionary
    def getVertices(self):
        return list(self.gdict.keys())

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)

print(g.getVertices())

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

['d', 'b', 'e', 'c', 'a']

Diagrammkanten anzeigen

Das Finden der Diagrammkanten ist etwas schwieriger als die Scheitelpunkte, da wir jedes der Scheitelpunktpaare finden müssen, zwischen denen sich eine Kante befindet. Wir erstellen also eine leere Liste von Kanten und durchlaufen dann die Kantenwerte, die jedem der Scheitelpunkte zugeordnet sind. Es wird eine Liste gebildet, die die unterschiedliche Gruppe von Kanten enthält, die von den Eckpunkten gefunden wurden.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

    def edges(self):
        return self.findedges()
# Find the distinct list of edges

    def findedges(self):
        edgename = []
        for vrtx in self.gdict:
            for nxtvrtx in self.gdict[vrtx]:
                if {nxtvrtx, vrtx} not in edgename:
                    edgename.append({vrtx, nxtvrtx})
        return edgename

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)

print(g.edges())

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[{'b', 'a'}, {'b', 'd'}, {'e', 'd'}, {'a', 'c'}, {'c', 'd'}]

Hinzufügen eines Scheitelpunkts

Das Hinzufügen eines Scheitelpunkts ist unkompliziert, wenn wir dem Diagrammwörterbuch einen weiteren zusätzlichen Schlüssel hinzufügen.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

    def getVertices(self):
        return list(self.gdict.keys())

# Add the vertex as a key
    def addVertex(self, vrtx):
       if vrtx not in self.gdict:
            self.gdict[vrtx] = []

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)

g.addVertex("f")

print(g.getVertices())

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

['f', 'e', 'b', 'a', 'c','d']

Eine Kante hinzufügen

Das Hinzufügen einer Kante zu einem vorhandenen Diagramm umfasst das Behandeln des neuen Scheitelpunkts als Tupel und das Überprüfen, ob die Kante bereits vorhanden ist. Wenn nicht, wird die Kante hinzugefügt.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

    def edges(self):
        return self.findedges()
# Add the new edge

    def AddEdge(self, edge):
        edge = set(edge)
        (vrtx1, vrtx2) = tuple(edge)
        if vrtx1 in self.gdict:
            self.gdict[vrtx1].append(vrtx2)
        else:
            self.gdict[vrtx1] = [vrtx2]

# List the edge names
    def findedges(self):
        edgename = []
        for vrtx in self.gdict:
            for nxtvrtx in self.gdict[vrtx]:
                if {nxtvrtx, vrtx} not in edgename:
                    edgename.append({vrtx, nxtvrtx})
        return edgename

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)
g.AddEdge({'a','e'})
g.AddEdge({'a','c'})
print(g.edges())

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[{'e', 'd'}, {'b', 'a'}, {'b', 'd'}, {'a', 'c'}, {'a', 'e'}, {'c', 'd'}]