Havuz Problemi

Dinamik Graf Yapısı Projesi

Şeyma Nur MUTLU ve Melike OĞUZ

Kocaeli Üniversitesi Bilgisayar Mühendisliği

ÖZET

“Havuz Problemi" adlı programda kullanıcı tarafından girilen musluk sayısı adedince node oluşturulur. Daha sonra kullanıcı, başlangıç ve bitiş düğümleri seçimi yapar. Tüm bu işlemlerden sonra program, havuz hangi yol ile en kısa sürede dolar ve boşaltılır hesabı yaptıktan sonra sonuçları çıktı olarak verir.

1- Giriş

Havuz Problemi programımız graf mantığı ile çalışmaktadır. Bu yüzden musluklar ve boru hattı graf yapısındaki node ve edgelere karşılık gelmektedir.Şimdi programımızı anlatmaya başlayalım.

Program çalıştırıldıktan sonra öncelikle ekrana kaç adet musluk sayısı olacağı kullanıcıya sorulur. Daha sonra musluk adedince nodelar ekrana bastırılır. Bu işlemler yapılırken her şey dinamik olması gerektiği için dinamic graph yapısı kullanılmıştır.

Kullanıcının kullanımı için gayet kullanışlı olan bir arayüz ile başlangıç ve bitiş düğümleri sorulur. Düğümler belirlendikten sonra bu düğümler renklendirilir. Daha sonra akış sisteminin devamının yapılabilmesi için arayüz üzerinden hangi musluk ile hangi musluk arasında bağlantı olsun ve bu hattın kapasite miktarı ne kadar olmalı gibi sorular sorulur.

Sorular cevaplandırıldıkça TableView üzerinden kontrol edilmesi kolay olsun diye her defasında bu kutucuğa veriler bastırılır. Girilen bilgiler doğrultusunda havuzu dolduracak suyun geçeceği tesisatın görüntüsü ortaya çıkar.

Daha sonra yine arayüz üzerinden kullanıcı Maksimum Akış veya Mimimum Akış butonlarına tıklayarak hangi boru hattı ve musluklar açılırsa havuz en kısa sürede dolar ve boşaltılır diye görür. Görsel açıdan bu bilgiler kullanıcıya gösterildikten sonra program sona erer.

2- Temel Bilgiler

• Program, Java dilinde geliştirilmiş olup debug ve release işlemleri Eclipse ID kullanılarak yapılmıştır ile yapılmıştır.

• Arayüz için JavaFx kullanılıp gerekli jarlar projeye entegre edilmiştir. JavaFx'in tasarımı Scene Builder kullanılarak geliştirilmiştir.

3- Tasarım

Proje aşağıdaki başlıklar altında geliştirilmiştir.

3.1 Yazılım Tasarımı

Main (class): Projenin başlatıldığı classtır. Burada bir adet Scene oluşturulur. Bu ekran üzerinden kullanıcıdan musluk sayısı verisi alınır. Cizdir adlı butonuna basılarak graf yeni pencerede açılır. Layered eklenerek daha önce hazırlanmış olan arayüzler arasında geçiş yapabilmek için bir adet Anchor Pane oluşturulmuştur. Daha sonra Grid Paneler bu Anchor Pane'in çocukları olarak eklenmiştir. Sırası ile arayüzler arasında geçişler yapılır.

MainControlller (class): Main classındaki kullanıcı tarafından alınan musluk sayısı bilgisi, bu classta bulunan TakeMuslukSayisi adlı metoda gönderilir ve düğümler oluşturulur. Diğer fxml formatındaki arayüzler arasında geçiş yapılır.

Anchor (fxml): İçerisinde sadece Anchor Pane bulunur ve Grid Paneler arasında geçiş yapılabilmek için oluşturulmuştur.

Application (css): Arayüz üzerindeki tasarımların görüntüleri için css dosyası oluşturulmuştur.

Main (fxml): Program başlatıldığında ilk olarak kullanıcının gördüğü ekrandır. txtMuslukSayisi adlı textField'a musluk sayısı girilir. Daha sonra Cizdir adlı butona tıklanarak diğer arayüze geçiş sağlanır.

First (fxml): Kullanıcıdan başlangıç, bitiş düğümünün, hangi musluk ile hangi musluk arasında bağlantı kurulmasının istendiğinin, kapasite miktarının ve hangi akış türünün seçilmek istendiğinin sorulduğu arayüzdür.

FirstPageController (class): First adlı arayüzün arkaplanında yapılan fonksiyonları barındıran sınıftır.

EdgeInfo (class): Klavye üzerinden kullanıcıdan alınan musluk bağlantı bilgilerinin yani birinci düğümün, ikinci düğümün ve kapasitenin tutulduğu sınıftır.

4- Karşılaşılan Sorunlar ve Çözümleri

4.1- Javafx.scene.layout.AnchorPane Can Not Be Cast o javafx.scene.layout.GirdPane Hatasının Alınması

• Daha önce Anchor Pane kullanarak oluşturduğumuz arayüzlerimizi Grid Pane olarak bir nesne listesinde tutmak isteidiğimizde karşımıza çıkan hata türüdür. Çözümü için "First.fxml" adlı dosyanın kodlarını inceledik ve < AnchorPane> < /AnchorPane > tagleri < GridPane > < /GridPane > olarak değiştirilmiştir.
  
  

5- Kullanılan Algoritmalar

5.1.1- Ford- Fulkerson Algoritmasının Açıklaması (Max Flow)

• Ford Fulkerson (Çizge Teoremi) algoritması tarihi, 1736 yılında ilk kez Leonhard Euler tarafından çözümlenen, Königsberg’in 7 köprüsü (graf teorisi nedir) problemi ile başlamaktadır. Birçok problem Euler tarafından bulunan bu teorem üzerinden çözümlenmektedir.

• Bu problemlerden birisi de azami akış (max flow) problemidir.Herhangi bir başlangıç noktasından hedef noktasına olan azami akışı belirlemek için kullanılan Ford Fulkerson Algoritması 1956 yılında L.R Ford ve D.R Fulkerson tarafından bulunmuştur.

• Günlük hayattaki önemi çok büyük olan bu algoritma kullanıldığı bazı yerler; elektrik devreleri, bilgisayar ağ sistemlerinin optimizasyonu, trafik akışını yönlendirme, elektrik, su ve atık su akışını yönlendirmede kullanılmaktadır.

5.1.2- Ford- Fulkerson Algoritmasının Karmaşıklık Analizi

• Maksimum akışı bulmak için kullandığımız algoritmanın karmaşıklık analizi, O(VE^{2})t'dır.

5.1.3- Ford-Fulkerson Algoritmasının Pseudo Kodu

• Başlangıç olarak seçilen düğümden başla.

• Başlangıç düğümünden bitiş düğümüne bir artırım yolu varsa, akışa bu yol akışını ekle.

• Akışı sonuç olarak döndür.

5.2.1 Karger’s Algoritmasının Açıklaması (Min Cut)

• Bilgisayar bilimi ve graf teorisinde Karger'in algoritması, bağlı bir grafın minimum kesimini hesaplamak için rastgele bir algoritmadır. David Karger tarafından icat edildi ve ilk olarak 1993 yılında yayınlandı.

• Yönlendirilmemiş ve ağırlıksız bir graf verildiğinde, en küçük kesimi (grafiği iki bileşene ayıran en az kenar sayısı) bulur.

5.2.2- Karger’s Algoritmasının Karmaşıklık Analizi (Min Cut)

• Minimum akışı bulmak için kullandığımız algoritmanın karmaşıklık analizi, E=O(V2)'dir.

5.2.3- Karger’s Algoritmasının Pseudo Kodu

• Orijinal grafın kopyası olarak contracted graf CG'yi başlat.

• 2'den fazla köşe varken.

  • Kasılmış grafikte rastgele bir kenar (u,v) seçin.

  • u ve v'yi tek bir tepe noktasında birleştirin (veya contract) (contracted grafı güncelle).

  • Self-loopları sil

• İki köşe ile temsil edilen kesimi sonuç

olarak döndür.

6. Havuz Problemi Pseudo Kod

1- Kullanıcıdan musluk sayısını al.

2- Cizdir butonuna basıldıktan sonra girilen musluk sayısı adedince node oluştur. First.fxml dosyasını çalıştır.

3- Oluşturulan nodeları GraphStream penceresine bas.

4- Kullanıcıdan başlangıç düğümünü ve bitiş düğüm bilgilerini al.

5- Başlangıç ve bitiş düğümlerini mavi renkle belirtip ekrana bas.

6- Kullanıcıdan hangi musluklar arasında bağlantılı kurulacağı bilgisini ve kapasite miktarını al.

7- Düğümler arası geçiş bilgilerini ve kapasite miktarı bilgilerini TableView'de göster.

8- Düğümler arasındaki geçiş bilgilerini kullanarak son grafı ekrana bas.

9- Maksimum Akış butonuna basıldığında maxFlow metodunu çalıştır.

10- Minimum Akış butonuna basıldığında minFlow metodunu çalıştır.

11- Programı sonlandır.

7- Kazanımlar

1- Dinamik graf yapısının kullanılması

2- JavaFx ile arayüz tasarımı, TableView gibi birçok nesnenin kullanımının öğrenilmesi

3- Min Cut ve Max Flow algoritmalarının çalışma mantığı

4- GitHub kullanımı

5- Scene Builder kullanımı

6- Karmaşıklık analizinin nasıl yapılacağını öğrenmek

8- Projenin Videosu

9- Kaynakça

[1] http://graphstream-project.org/

[2] https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/

[3] https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

[4] https://stackoverflow.com/questions/35956527/javafx-javafx-scene-layout-anchorpane-cannot-be-cast-to-javafx-scene-layout-bo

[5] https://code.makery.ch/tr/library/javafx-tutorial/part1/

[6] https://www.youtube.com/watch?v=5GsdaZWDcdY

[7] https://www.youtube.com/watch?v=zWTzZ4sNAFw

[8] https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

[9] https://www.muhendisbeyinler.net/ford-fulkerson-algoritmasi/

[10] https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

[11] https://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/