Erstellen Sie Ihre eigene Diagrammstrukturklasse und deren Zeichnung mit Python

Ich konnte das Problem des Diagramms, das in D von ABC160 von AtCoder gestellt wurde, nicht lösen. Nachdem ich Python studiert hatte, versuchte ich, die Diagrammstrukturklasse und sie mit maatplotlib zu zeichnen.

(Denken Sie über die Teilnahme an AtCoder nach) Code, an den ich mich gerne erinnert hätte, als ich zum ersten Mal an AtCoder teilgenommen habe (Reflection 1 zum nächsten Mal)

Es scheint *** NetworkX *** in der Bibliothek zu geben, das die Diagrammstruktur ausdrückt, aber ich werde es dieses Mal nicht verwenden. (Kann es nicht überhaupt mit AtCoder verwendet werden?)

Es gibt viele clevere Möglichkeiten, es auszudrücken: Da es sich um eine Implementierung innerhalb des Bereichs handelt, über den ein Amateur grob nachdenken kann, verzeihen Sie mir bitte, dass ich sie nicht erstellen kann.

Diagrammstrukturklasse

Konzept

Es wird angenommen, dass die Klasse ein Wörterbuch mit einem Knoten als Schlüssel und der Spitze der Kante als Wert als Elementvariable hat. Bereiten Sie die folgenden Methoden vor. ① Fügen Sie einen Knoten hinzu ② Fügen Sie eine Kante hinzu ③ Zeigen Sie den Knoten an ④ Geben Sie die Knoten als Liste zurück ⑤ Geben Sie den mit dem angegebenen Knoten verbundenen Knoten zurück

Klassendefinition

#Erstellen einer Diagrammstruktur
class cglaph():
  def __init__(self):
    #Knoteninitialisierung
    self.nodes={}

  def addnode(self,num):#① Fügen Sie einen Knoten hinzu
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Fügen Sie eine Kante hinzu
    node1=min(ag1,ag2)
    node2=max(ag1,ag2)
    addok=False

    for i in self.nodes.keys():
      if i==node1:
        for j in self.nodes.keys():
          if j==node2:
            addok=True

    if addok:
      self.nodes[node1].append(node2)
      self.nodes[node2].append(node1)

  def printnodes(self):    #③ Zeigen Sie den Knoten an
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Gibt eine Liste der Knoten zurück
    keylist=list()

    for i in self.nodes.keys():
      keylist.append(i)
    return keylist

  def getedge(self, node):#⑤ Gibt die Kante (verbundener Knoten) des angegebenen Knotens zurück.
    return self.nodes[node]

Lassen Sie uns tatsächlich ein ungerichtetes Diagramm erstellen, das 5 Knoten entsprechend verbindet

G=cglaph()
G.addnode(1)#Knoten hinzufügen
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Kante hinzufügen
G.addedge(1,4)
G.addedge(5,3)

G.printnodes()#Liste der Knoten

nodelist=G.getnodes()#Knotenliste abrufen
print ("NODE LIST:",nodelist)

G.getedge(1)#Knoten mit Knoten 1 verbunden

Visualisierung der erstellten Graphstruktur

Lassen Sie uns nach dem Studium von matplotlib das Diagramm visualisieren, das ich erstellt habe. Ich wusste also nicht, was ich mit der Zeichenposition des Knotens anfangen sollte Wir haben beschlossen, die Knoten an zufälligen Positionen zu platzieren. Ich würde mir gerne überlegen, wie ich es in Zukunft in eine schöne Position bringen kann.

Es scheint, dass Sie nichts tun müssen, wenn Sie NetworkX und matplotlib verwenden.

import matplotlib.pyplot as plt
import random
random.seed(0)

#Zufällig, weil ich nicht weiß, was ich mit der Knotenposition machen soll
N=len(nodelist)
x=[random.randint(0, 100) for i in range(N)]
y=[random.randint(0, 100) for i in range(N)]
print("x:",x)
print("y:",y)

#Diagrammerstellung
plt.figure(1)

#Knotenzeichnung
plt.scatter(x,y)

#Geben Sie der Knotenposition einen Knotennamen
ax=plt.axes()
for i in range(N):
  ax.annotate(nodelist[i],(x[i],y[i]),size=20)

#Eine Kante zeichnen Das ist nicht klug
for i in range(N):
  edges=G.getedge(i+1)
  for j in edges:
    plt.plot((x[i],x[j-1]),(y[i],y[j-1]), color='red')

plt.xlim(0, 100)
plt.ylim(0, 100)

Etwas *** MatplotlibDeprecationWarning *** wird erwähnt, aber jetzt ignorieren. Ich frage mich, ob die Verwendung von Achsen angemessen ist.

Schließlich

Ich werde endlich anfangen, die Suche nach Breitenprioritäten zu studieren!

Referenz

[Matplotlib] Anmerkungen und Pfeile

<Python, matplotlib> Fügen Sie jedem Element des Streudiagramms Zeichen hinzu.

Lassen Sie uns das Netzwerk mit Python analysieren und visualisieren! Erforderliche Verfahrenszusammenfassung

So rufen Sie Elemente mit der for-Schleife des Python-Wörterbuchs ab (dict)