Python - Grafik

Grafik adalah representasi bergambar dari sekumpulan objek di mana beberapa pasang objek dihubungkan oleh tautan. Objek yang saling berhubungan diwakili oleh titik yang disebut sebagai simpul, dan tautan yang menghubungkan simpul disebut tepi. Berbagai istilah dan fungsi yang terkait dengan grafik dijelaskan dengan sangat rinci dalam tutorial kami di sini. Pada bab ini kita akan melihat cara membuat grafik dan menambahkan berbagai elemen data ke dalamnya menggunakan program python. Berikut adalah operasi dasar yang kami lakukan pada grafik.

  • Menampilkan simpul grafik
  • Tampilan tepi grafik
  • Tambahkan simpul
  • Tambahkan tepi
  • Membuat grafik

Grafik dapat dengan mudah disajikan menggunakan tipe data kamus python. Kami mewakili simpul sebagai kunci kamus dan hubungan antara simpul juga disebut tepi sebagai nilai dalam kamus.

Perhatikan grafik berikut -

Pada grafik di atas

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

Grafik ini dapat kita sajikan dalam program python seperti di bawah ini.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Menampilkan simpul grafik

Untuk menampilkan simpul-simpul grafik kita secara sederhana menemukan kunci-kunci dari kamus grafik. Kami menggunakan metode 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())

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Tampilan tepi grafik

Menemukan tepi grafik sedikit lebih sulit daripada simpul karena kita harus mencari setiap pasang simpul yang memiliki tepi di antara keduanya. Jadi kita membuat daftar tepi yang kosong kemudian mengulangi nilai tepi yang terkait dengan masing-masing simpul. Sebuah daftar dibentuk yang berisi kelompok tepi yang berbeda yang ditemukan dari simpul.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Menambahkan titik sudut

Menambahkan titik sudut langsung ke depan di mana kami menambahkan kunci tambahan lain ke kamus grafik.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Menambahkan tepi

Menambahkan tepi ke grafik yang ada melibatkan perlakukan simpul baru sebagai tupel dan memvalidasi jika tepi sudah ada. Jika tidak maka tepi ditambahkan.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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