Python - Graphiques

Un graphique est une représentation picturale d'un ensemble d'objets où certaines paires d'objets sont reliées par des liens. Les objets interconnectés sont représentés par des points appelés sommets et les liens qui relient les sommets sont appelés arêtes. Les différents termes et fonctionnalités associés à un graphe sont décrits en détail dans notre tutoriel ici. Dans ce chapitre, nous allons voir comment créer un graphique et y ajouter divers éléments de données à l'aide d'un programme python. Voici les opérations de base que nous effectuons sur les graphiques.

• Afficher les sommets du graphe
• Afficher les bords du graphique
• Ajouter un sommet
• Ajouter un bord
• Créer un graphique

Un graphique peut être facilement présenté à l'aide des types de données du dictionnaire python. Nous représentons les sommets comme les clés du dictionnaire et la connexion entre les sommets également appelés arêtes comme les valeurs du dictionnaire.

Jetez un œil au graphique suivant -

Dans le graphique ci-dessus

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

Nous pouvons présenter ce graphique dans un programme python comme ci-dessous.

# 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)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

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

Afficher les sommets du graphe

Pour afficher les sommets du graphe, nous trouvons simplement les clés du dictionnaire des graphes. Nous utilisons la méthode 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())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

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

Afficher les bords du graphique

Trouver les arêtes du graphe est un peu plus compliqué que les sommets car nous devons trouver chacune des paires de sommets qui ont une arête entre eux. Nous créons donc une liste vide d'arêtes puis itérons les valeurs d'arêtes associées à chacun des sommets. Une liste est formée contenant le groupe distinct d'arêtes trouvé à partir des sommets.

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())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

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

Ajouter un sommet

L'ajout d'un sommet est simple où nous ajoutons une autre clé supplémentaire au dictionnaire graphique.

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())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

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

Ajout d'un bord

Ajouter une arête à un graphe existant implique de traiter le nouveau sommet comme un tuple et de valider si l'arête est déjà présente. Sinon, le bord est ajouté.

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())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

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