Python — Графики

Граф представляет собой графическое представление набора объектов, где некоторые пары объектов связаны ссылками. Взаимосвязанные объекты представлены точками, называемыми вершинами, а связи, соединяющие вершины, называются ребрами. Различные термины и функции, связанные с графиком, подробно описаны в нашем уроке здесь. В этой главе мы увидим, как создать граф и добавить в него различные элементы данных с помощью программы на Python. Ниже приведены основные операции, которые мы выполняем на графиках.

• Показать вершины графа
• Отображение ребер графа
• Добавить вершину
• Добавить ребро
• Создание графика

График может быть легко представлен с использованием типов данных словаря Python. Мы представляем вершины в качестве ключей словаря, а связь между вершинами также называется ребрами в качестве значений в словаре.

Посмотрите на следующий график —

На приведенном выше графике

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

Мы можем представить этот граф в программе на Python, как показано ниже.

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

Когда приведенный выше код выполняется, он дает следующий результат —

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

Показать вершины графа

Чтобы отобразить вершины графа, мы просто находим ключи словаря графа. Мы используем метод 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())

Когда приведенный выше код выполняется, он дает следующий результат —

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

Отображение ребер графа

Поиск ребер графа немного сложнее, чем вершин, так как мы должны найти каждую из пар вершин, у которых есть ребро между ними. Таким образом, мы создаем пустой список ребер, затем перебираем значения ребер, связанные с каждой из вершин. Формируется список, содержащий отличную группу ребер, найденных по вершинам.

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

Когда приведенный выше код выполняется, он дает следующий результат —

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

Добавление вершины

Добавление вершины является прямым, где мы добавляем еще один дополнительный ключ к графическому словарю.

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

Когда приведенный выше код выполняется, он дает следующий результат —

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

Добавление ребра

Добавление ребра в существующий граф включает обработку новой вершины как кортежа и проверку, если ребро уже присутствует. Если нет, то край добавляется.

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

Когда приведенный выше код выполняется, он дает следующий результат —