iGraph Paketi


Bu yazımda sizlere R programlamanın kurallarını (syntax) anlatmayacağım. Çünkü R programlama için başlangıç seviyesindeki bilgilere internette kolaylıkla erişebilirsiniz. Ben yazılarımda sizlere paketleri tanıtmayı daha uygun görüyorum. Bu paketlerden ilki “igraph”, bizlere en kısa yolu bulmamızı sağlayan algoritmaları barındırmaktadır. Yani sonuç olarak graf teorisi üzerinde duracağız ve örneklerle konuyu pekiştireceğiz. Hadi başlayalım…

Öncelikle şunu belirtelim ki klasik R arayüzü biraz can sıkıcıdır. Bundan dolayı daha gelişmiş bir R arayüzü için biz RStudio kullanacağız. İndirmek için aşağıdaki linki kullanabilirsiniz.

https://www.rstudio.com/

Programın kurulumunu yaptıktan sonra arayüze bakacak olursak; değişkenler, veri tabloları, paketler…vb. hepsini bir arada barındırmaktadır. Yani R programlama için kolay bir kullanıcı dostu (user friendly) bir arayüz bizi karşılar.

Şimdi aşağıdaki komutla  “igraph” paketini indirelim. İndirdikten sonra kullanıma açmak için “library” komutuyla paketi çağıralım.

> install.packages("igraph")

> library("igraph")

Şimdi elimizde bir graf olduğunu varsayalım ve değişkenleri daha net görebilmek için bunu matrise aktardığımızı düşünelim.

                V1          V2          V3          V4          V5          V6

1             0             7             4             NA         2             NA

2             7             0             3             2             NA         6

3             4             3             0             8             1             NA

4             NA         2             8             0             10           3

5             2             NA         1             10           0             NA

6             NA         6             NA         3             NA         0

Şimdi igraph paketi vektörler üzerinde çalışmaktadır. Bundan dolayı yukarıdaki verileri bir dizi şeklinde program içerisinde tanımlayalım.

                > gr ß graph(edges=c(1,2,1,3,1,5,2,3,2,4,2,6,3,4,3,5,4,5,4,6),n=6,directed=F)

Yukarıdaki komutu inceleyelim. Bir graf oluşturmak için tahmin ettiğiniz gibi “graph” komutu kullanılmaktadır ve içerisine yukarıda görüldüğü üzere düğümlerin birbirleriyle olan bağlantıları girilmektedir. Argüman olarak tanımlanan “n” değeri düğüm sayısını “directed” ise grafın yönlü yada yünsüz olduğunu ifade eder. Aynı grafta değişkenleri yani düğümleri isimlendirmek istersek aşağıdaki komutu kullanırız.

> gr ß (c("A", "B", "B", "C", "C", "D"), directed = FALSE)

Renklendirmeler bize şunu ifade eder:

1.  ve 2. Düğüm arasında, 1 ile 3 arasında 1 ile 5 arasında….vb.  bağlantılıdır.

Şimdi kontrollerimizi yapalım. Ayrıtları görebilmek için E() komutu ve düğüm sayısını görebilmek için V() komutu kullanılır. Örneğin

> E(gr)

+ 10/10 edges:

 [1] 1--2 1--3 1--5 2--3 2--4 2--6 3--4 3--5 4--5 4--6

> V(gr)

+ 6/6 vertices:

[1] 1 2 3 4 5 6

Grafiğe ait ağırlıkları tanımlamak için yine vektör kullanacağız. Buradaki vektöre ait eleman sıralamasına dikkat edilmelidir.

> w=c(7,4,2,3,2,6,8,1,10,3)

> w

 [1]  7  4  2  3  2  6  8  1 10  3

Ağırlıkları tanımladık. Şimdi bunları graf içerisine atalım.

> E(gr)$weight = w

> E(gr)$weight

 [1]  7  4  2  3  2  6  8  1 10  3

Şimdi herşey hazır. Bakalım matrisimiz R içerisinde nasıl görünüyor.

>gr[]

        6 x 6 sparse Matrix of class "dgCMatrix"

                 

        [1,] . 7 4  .  2 .

        [2,] 7 . 3  2  . 6

        [3,] 4 3 .  8  1 .

        [4,] . 2 8  . 10 3

        [5,] 2 . 1 10  . .

        [6,] . 6 .  3  . .

 

Şimdi en kısa yol hesaplamasına geçebiliriz. Bunun için “shortest.paths” komutunu kullanacağız.

 

 

        > shortest.paths(gr)

                [,1] [,2] [,3] [,4] [,5] [,6]

        [1,]    0    6    3    8    2   11

        [2,]    6    0    3    2    4    5

        [3,]    3    3    0    5    1    8

        [4,]    8    2    5    0    6    3

        [5,]    2    4    1    6    0    9

        [6,]   11    5    8    3    9    0

 

“shortest.paths” komutu tek başına kullanılabileceği gibi birden fazla argümanıda mevcuttur. Kullanım şekli aşağıdaki gibidir.

shortest.paths(graph, v=V(graph), to=V(graph), mode = c("all", "out", "in"),      weights = NULL , algorithm = c("automatic","unweighted”,"dijkstra","bellman-ford","johnson"))

Argümanlar;

Graph: Üzerinde çalışılan grafı temsil etmektedir.

V: Başlangıç düğümünü belirlemek için kullanılır.

To: Bitiş düğümünü belirlemek için kullanılır.

mode: Eğer bu argüman “out” olarak belirlenmişse başlangıç düğümünden itibaren, “in” ise bitiş düğümünden sonra, “all” ise varsayılan olarak belirlenmiştir. Fakat bu argüman yönsüz graflar için kullanılmamaktadır.

Weight: Graf içerisinde ağırlık barındırıyorsa “NULL” barındırmıyorsa “NA” olarak ayarlanmalıdır.

Algorithm: Bu argüman ile grafikte kullanılacak en kısa yolu belirleyen algoritma seçilmektedir. Varsayılan olarak uygulandığında bu argüman en hızlı ve uygun algoritmayı kendisi seçmektedir. Eğer graf içerisinde negatif ağırlık varsa ve 100 düğümden fazlaysa Jhonson algoritması kullanılmaktadır. E Düğümler arasındaki en kısa yolları görebilmek için “all_shortest_paths” komutu kullanılmaktadır. Buradaki amaç seçilen iki düğüm arasındaki minimum çözümü görebilmektir.

> all_shortest_paths(gr, from=V(gr), to = V(gr), mode = c("out", "all", "in"))

$res

$res[[1]]

+ 1/6 vertex:

[1] 1

$res[[2]]

+ 4/6 vertices:

[1] 1 5 3 2

$res[[3]]

+ 3/6 vertices:

[1] 1 5 3

$res[[4]]

+ 5/6 vertices:

[1] 1 5 3 2 4

$res[[5]]

+ 2/6 vertices:

[1] 1 5

$res[[6]]

+ 6/6 vertices:

[1] 1 5 3 2 4 6

$nrgeo

[1] 1 1 1 1 1 1

Diğer bütün düğümler pozitif ise Dijkstra algoritması seçilmelidir.

Umarım sizler için faydalı olmuştur. R’lı günlere…

İlgili linkler

http://en.wikipedia.org/wiki/Igraph

http://igraph.wikidot.com/

http://github.com/szhorvat/IGraphM

http://igraph.org/r/

 

Yazar Kimdir?

Sıtkı Cansu, 19 Ekim 1985 yilinda Konya-Beyşehir'de dogmustur.İlk, orta ve liseyi Beyşehir'de bitirmis olup Konya-Ereğli Selçuk MYO Bilgisayar programcılığı ve Mugla Sıtkı Koçman Üniversitesi İstatistik bölümünden mezun olmustur. Çesitli yerlerde web tasarımcı ve veri tabani yöneticisi olarak çalışan yazar, son üç senedir ingilizce öğretmenliği yapmaktadir. Şu anda yüksek lisansını tamamlamak üzere Mugla Üniversitesinde öğrenim görmektedir.