Python - Gráficos

Un gráfico es una representación pictórica de un conjunto de objetos donde algunos pares de objetos están conectados por enlaces. Los objetos interconectados se representan mediante puntos denominados vértices y los vínculos que conectan los vértices se denominan aristas. Los diversos términos y funcionalidades asociados con un gráfico se describen con gran detalle en nuestro tutorial aquí. En este capítulo, veremos cómo crear un gráfico y agregarle varios elementos de datos usando un programa de Python. A continuación se muestran las operaciones básicas que realizamos en gráficos.

• Mostrar vértices de gráficos
• Mostrar bordes de gráfico
• Agregar un vértice
• Agrega una ventaja
• Creando una gráfica

Un gráfico se puede presentar fácilmente utilizando los tipos de datos del diccionario de Python. Representamos los vértices como las claves del diccionario y la conexión entre los vértices también llamados aristas como los valores en el diccionario.

Eche un vistazo al siguiente gráfico:

En el gráfico anterior

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

Podemos presentar este gráfico en un programa de Python como se muestra a continuación.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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

Mostrar vértices de gráficos

Para mostrar los vértices del gráfico, simplemente busquemos las claves del diccionario de gráficos. Usamos el método 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())

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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

Mostrar bordes de gráfico

Encontrar los bordes del gráfico es un poco más complicado que los vértices, ya que tenemos que encontrar cada uno de los pares de vértices que tienen un borde entre ellos. Entonces creamos una lista vacía de aristas y luego iteramos a través de los valores de aristas asociados con cada uno de los vértices. Se forma una lista que contiene el grupo distinto de aristas que se encuentran a partir de los vértices.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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

Agregar un vértice

Agregar un vértice es sencillo, donde agregamos otra clave adicional al diccionario de gráficos.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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

Agregar una ventaja

Agregar un borde a un gráfico existente implica tratar el nuevo vértice como una tupla y validar si el borde ya está presente. Si no, se agrega el borde.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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