Créez votre propre classe de structure graphique et son dessin avec python

Je ne pouvais pas résoudre le problème du graphe qui était posé dans D de ABC160 d'AtCoder, donc après avoir étudié python, j'ai essayé de dessiner la classe de structure de graphe et cela avec maatplotlib.

(Réfléchissez à votre participation à AtCoder) Code dont j'aurais aimé me souvenir lors de ma première participation à AtCoder (Réflexion 1 pour la prochaine fois)

Il semble y avoir *** NetworkX *** dans la bibliothèque qui exprime la structure du graphe, mais je ne l'utiliserai pas cette fois. (Ne peut-il pas être utilisé avec AtCoder en premier lieu?)

Il existe de nombreuses façons intelligentes de l'exprimer, Puisqu'il s'agit d'une implémentation dans la gamme à laquelle un amateur peut penser grossièrement, veuillez pardonner qu'elle n'a pas été créée.

Classe de structure graphique

Concept

On suppose que la classe a un dictionnaire avec un nœud comme clé et la pointe du bord comme valeur comme variable membre. Préparez les méthodes suivantes. ① Ajouter un nœud ② Ajouter un bord ③ Afficher le nœud ④ Renvoie les nœuds sous forme de liste ⑤ Renvoie le nœud connecté au nœud spécifié

Définition de classe

#Créer une structure graphique
class cglaph():
  def __init__(self):
    #Initialisation du nœud
    self.nodes={}

  def addnode(self,num):#① Ajouter un nœud
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Ajouter un bord
    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):    #③ Afficher le nœud
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Renvoie une liste de nœuds
    keylist=list()

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

  def getedge(self, node):#⑤ Renvoie l'arête (nœud connecté) du nœud spécifié.
    return self.nodes[node]

Créons en fait un graphe non orienté qui connecte 5 nœuds de manière appropriée

G=cglaph()
G.addnode(1)#Ajouter un nœud
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Ajouter un bord
G.addedge(1,4)
G.addedge(5,3)

G.printnodes()#Liste des nœuds

nodelist=G.getnodes()#Obtenir la liste des nœuds
print ("NODE LIST:",nodelist)

G.getedge(1)#Nœud connecté au nœud 1

Visualisation de la structure graphique créée

Après avoir étudié matplotlib, visualisons le graphique que j'ai fait. Je ne savais pas quoi faire avec la position de dessin du nœud, donc Nous avons décidé de placer les nœuds à des positions aléatoires. Je voudrais penser à un moyen de le placer dans une bonne position à l'avenir.

En premier lieu, si vous utilisez NetworkX et matplotlib, vous n'avez rien à faire.

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

#Aléatoire car je ne sais pas quoi faire avec la position du nœud
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)

#Création de graphes
plt.figure(1)

#Dessin de nœud
plt.scatter(x,y)

#Donnez un nom de nœud à la position du nœud
ax=plt.axes()
for i in range(N):
  ax.annotate(nodelist[i],(x[i],y[i]),size=20)

#Dessiner un bord Ce n'est pas intelligent
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)

Quelque chose *** MatplotlibDeprecationWarning *** est mentionné, mais ignorez-le maintenant. Je me demande si l'utilisation des axes est appropriée.

finalement

Je vais enfin commencer à étudier la recherche de priorité de largeur!

référence

[Matplotlib] Annotations et flèches

<Python, matplotlib> Ajoutez des caractères à chaque élément du diagramme de dispersion.

Analysons et visualisons le réseau avec Python! Résumé de la procédure requise

Comment récupérer des éléments avec la boucle for du dictionnaire Python (dict)