Python NetworkX ile Graf Teorisi

Thanks — Photo by Alina Grubnyak on Unsplash

Merhaba, bu yazıda graf teorisi ile ilgili çalışmalarınızda işinizi oldukça hızlandıracak ve kolaylaştıracak bir python paketinden bahsedeceğim. Giriş seviyesinde olacak olan bu yazıda NetworkX paketinin yüklenmesine, basit ve karmaşık yapıdaki grafların nasıl oluşturulduğuna ve son olarak bu grafların nasıl görselleştirildiğine değineceğim.

Not : Bahsedilen konuyla ilgili NetworkX dokümanına yönlendiren linkleri sözcüklere bağladım. Altı çizili olanlar ilgili sayfaya yönlendirmektedir.

1. NetworkX Kurulumu

NetworkX kullanabilmek için python sürümünüzün en az 3.5 olması gerekiyor. Eğer anaconda gibi bir dağıtım kullanıyorsanız benim aşağıdaki örnekte yaptığım gibi yeni bir environment oluşturup kurulumu oraya yapabilirsiniz. Veya mevcut dağıtımınızda devam edebilirsiniz.

graph isimli bir environment oluşturulması ve pip ile paketin yüklenmesi için :

> conda create graph python=3.6
> pip install networkx
> activate graph

2. İlk Basit Grafımızı Oluşturalım

NetworkX paketimizi yükledikten sonra artık ilk grafımızı oluşturabiliriz. Hiçbir node ve edge sahibi olmayan boş bir graf oluşturmak için :

import networkx as nx
G = nx.Graph()

Böylece artık G isminde bir boş grafımız oldu. Bu graf nesnesi ile kendinde tanımlanmış bir sürü methodu kullanabiliriz. Grafımızı oluşturmaya devam edelim. Öncelikle düğümlerimizi ekleyelim. Bu örnekte düğümlerimizi birer sayı ile ifade edeceğim. Kodun bütününü tekrar görecek olursak :

import networkx as nx
G = nx.Graph()
G.add_node(1)              # düğümleri tek tek ekleyebiliriz.
G.add_nodes_from([2,3])    # düğümleri bir diziden de alabiliriz.

Bu seviyede elimizde 1,2 ve 3 isimlerini verdiğimiz üç düğüm var fakat aralarında henüz bir bağlantı yok. Şimdi bağlantılarımızı ekleyelim.

import networkx as nx
G = nx.Graph()
G.add_node(1)              
G.add_nodes_from([2,3])    
G.add_edge(1,2)                     # kenarlar da tek tek veya bir
G.add_edges_from([(1,3),(2,3)])     # listeden eklenebilir. 

Örnekten de anlayacağınız gibi add_edge(1,2) ifadesi 1 ve 2 isimli düğümler arası bir bağlantı oluşturur. Bağlantılarımıza baktığımızda bir üçgen oluşmasını bekliyoruz. Şimdi bu grafımızı bir de alıştığımız şekilde görüntüleyelim.

3. Grafları Görselleştirme / Çizdirme

NetworkX çok basit bir seviyede görselleştirme sunsa da kendi dokümantasyonlarında da dedikleri gibi asıl işi grafların analizidir. Gelecekte görselleştirme özelliğini tamamen paketten çıkarmayı düşündüklerini de belirtmişler ve bazı görselleştirme kütüphaneleri önermişler. Bunlardan en çok öne çıkanları meşhur matplotlib ve graphviz. Devam eden örneklerimizde matplotlib kullanacağız.

Matplotlib paketini kurmak için aşağıdaki komut yeterlidir :

pip install matplotlib

Şimdi matplotlib’i de import ederek yukarıda oluşturmuş olduğumuz grafı çizdirelim.

import networkx as nx
import matplotlib.pyplot as plt     #paketi import ediyoruz
G = nx.Graph()
G.add_node(1)              
G.add_nodes_from([2,3])
G.add_edge(1,2)                    
G.add_edges_from([(1,3),(2,3)])     
nx.draw(G, with_labels=True)
plt.show()

Çizim 1

Eğer bu örnekte olduğu gibi düğüm adlarını görüntülemek istemiyorsanız draw methodundaki with_labels=True parametresini False yapabilirsiniz.

İlk örneğimiz yönsüz (undirected) bir graf örneğiydi. Aynı örneğimizde yönlü (directed) bir graf kullanacak olursak kod ve çıktı şu şekilde olacaktır :

import networkx as nx
import matplotlib.pyplot as plt     
G = nx.DiGraph()  # Yönlü grafları DiGraph sınıfı ile tanımlıyoruz.
G.add_node(1)              
G.add_nodes_from([2,3])
G.add_edge(1,2)                    
G.add_edges_from([(1,3),(2,3)])
nx.draw(G, with_labels=True)
plt.show()

Çizim 2 ( Yönlü Graf / Directed Graph )

Çizimde de göreceğiniz gibi bağlantıları tanımlamada kullandığımız sıra (1,3) bağlantının yönünü de belirledi. Bu örneğe bir de aynı düğümler arasında ters yönden (3,1) bir bağlantı eklersek çıktı şu şekilde olacaktır :

Çizim 3

4. Toparlarken

Tahmin edeceğiniz gibi NetworkX’in kabiliyeti yukarıda anlatılanların çok daha üzerinde. NetworkX, çalışılması çok zor olan büyük ölçekli grafların oluşturulması, yönetilmesi, analiz edilmesi ve birçok algoritmanın bu graflar üzerinde çalıştırılabilmesi için muazzam bir paket.

Oldukça esnek yapısı sayesinde büyük veri setlerini graf modellerine dönüştürmenize olanak sağlarken içinde hazır bulundurduğu algoritmalar ile de bu veri setlerini anlamlandırmanızı kolaylaştırıyor ve hızlandırıyor.

Bunların yanında bünyesinde barındırdığı hazır graf şablonları ile de birçok karakteristik grafı hızlıca oluşturabilirsiniz. Yazıyı NetworkX paketinde hazır bulunan graf türleri ile oluşturulmuş çıktılarla tamamlıyorum. Bir diğer yazımızda NetworkX paketine daha detaylı bakacağız ve algoritmaları inceleyeceğiz.

İyi çalışmalar dilerim, Ersin.

5. Bazı Özel Graflar ve Çıktıları

Tûran Graph >> G = nx.turan_graph(5,5)

Star Graph >> G = nx.star_graph(35)

Petersen Graph