Graph Yapılar

Husamettin Elalmis

Graph Yapılar

Merhaba arkadaşlar, bu yazıda sizlere Graph yapılardan bahsedeceğim.

Graph Nedir?

Graph, birbirleri ile ilişiği olan düğümler kümesidir. Düğümler arası bağlantılar vardır.

Dijkstra Algoritması

• Alman bilim adamı Dijkstra tarafından 1959 yılında geliştirilmiştir

• En kısa yolu bulma algoritması olarak bilinir

• Tek yönlü ve negatif olmayan kenarlar için kullanılabilir

• Bellman-Ford algoritmasına göre nispeten daha hızlı tepki verir.

Dijkstra Algoritmasının Dezavantajları

• Negatif kenarlı durumlarda yanlış çıktı üretir

• 

• Negatif döngü durumlarında yanlış çıktı üretir veya sonsuz loopa girebilir

• 

Bellman-Ford Algoritması

• Dijkstra algoritmasının üzerine geliştirilmiştir

• Tüm düğümleri gezme prensbine dayanır

• Negatif kenarları barındırabilir

Bellman-Ford Algoritmasının Dezavantajları

• Dijkstraya göre daha yavaş çalışır

• Negatif döngü yapılarında hatalı tepki verebilir veya sonsuz döngüye girebilir

Peki Ne Yapacağız?

• Kendi algoritmamızı yazacağız

• Graph modellemesini kullanacağız

• Düğümleri esnek olması açısından çok yönlü (gidiş-dönüş) tasarlayacağız, bu bizim tasarımımızdır. (A'dan B'ye gidiş 25 km iken, B'den A'ya gidiş(veya dönüş diyebiliriz) 10 km olabilir senaryomuz olsun, ve bu tüm düğümler için çift yönlü olsun.)

• Başlangıç noktası seçeceğiz, bitiş noktası seçeceğiz. Tüm düğümleri dolaşacağız

• Tüm düğümleri dolaşırken maliyet hesaplaması yapacağız, maliyeti en ucuz olanı en geçerli path olarak bileceğiz. Ancak diğer pathleri de biliyor olacağız.

• Olası Pathlerin tamamının listesini çıkarabiliyor olacağız

• Bu pathler elimizde olacağı için, "Şu şehirden geçmemiz lazım", "Bu şehirden geçmememiz lazım" tarzı senaryolar için filter yapabiliyor olacağız

• Kendi kodumuzu kendimiz yazıp bunları tatbik edeceğiz.

Temsili Bir Harita Belirleyelim

• Temsili bir harita belirleyelim

• Tüm şehirlere gidiş-dönüş çift yönlü olsun, hepsine değer matrisi tanımlayacağız.

• Graph algoritması (modellemesi) kullanacağız, tüm düğümleri maliyet hesabı ile dolaşacağız

• Senaryomuz şu problem çözsün,

  • Başlangıç noktası Bolu olsun

  • Varış noktası Antalya olsun

  • Trabzon şehrine mutlaka uğrasın

  • Konya yolundan asla geçmesin

  • En az maliyetli rota kullanılsın

• Şekil 1 – Başlangıç Haritamız

• Şekil 2 – Çözüm Haritamız

Program Kodu

using System.Collections.Generic;

using System.Drawing;

namespace GraphArge

{

// Graph nodu olarak modelleyeceğiz. Her node, bir şehire denk gelecek. public class GNode

{

public string Name { get; set; } // Şehrin adı public Point Point { get; set; } // Ekrandaki koordinatı, gösterim çizim amaçlı kullanacağız public GNode(string name)

{

this.Name = name;

}

public override string ToString()

{

return $"{this.Name}";

}

}

// Düğümün kenarı amacı ile kullanacağız. Bir düğümün diğer düğüme olan uzaklığını barındıracağız. // Bunu bilinçli olarak GNode'dan farklı olarak tasarlamak istedim public class VertexItem

{

public GNode Target { get; set; } public int Distance { get; set; } public VertexItem(GNode target, int distance)

{

this.Target = target; this.Distance = distance;

}

public override string ToString()

{

return $"{this.Target} ({this.Distance} km)";

}

}

// Bir node'un diğer notlara olan ilişiğini barındıracağız public class GraphItem

{

public GNode Source { get; set; } // Kaynak düğüm public bool IsVisited { get; set; } // Ziyaret edilip edilmediği public List<VertexItem> Vertexs { get; set; } // Diğer düğümlere olan ilişki matrisi public GraphItem(GNode gnode) // Kaynak düğümü setleyerek başla

{

this.Source = gnode; this.Vertexs = new List<VertexItem>(); // İlişki matrisi tanımla

}

public override string ToString()

{

return $"{this.Source} {this.Vertexs.Count}";

}

}

// Tüm haritamızı oluşturan objemiz. Tüm şehirleri biliyoruz, birbirine olan ilişki ve uzaklık (gidiş-dönüş) matrisini biliyor olacağız public class Graph

{

public List<GraphItem> Nodes { get; set; } // Tüm şehirler (nodes) public Graph()

{

this.Nodes = new List<GraphItem>();

}

}

}

using System;

using System.Collections.Generic;

using System.Data;

using System.Drawing;

using System.Drawing.Drawing2D;

using System.Linq;

using System.Windows.Forms;

namespace GraphArge

{

public partial class frmMain : Form

{

// variables private Graph graph; // haritamız public frmMain()

{

InitializeComponent();

}

private void frmMain_Load(object sender, EventArgs e)

{

// şehirler arası mesafeleri tanımla, örn: Edirne'de İstanbul'a gidiş mesafesi 120 kmdir." // veriler rastgele tahmini girilmiştir, temsilidir

// şehirler arası gidiş-dönüş mesafeleri aynı değildir, bilinçli olarak bu şekilde yaptım. Gidiş dönüş aynı mesafe olsa kod çok daha kısalır zaten

// bunlar veritabanından vs okunabilir

List<string> list = new List<string>();

list.Add("Edirne İstanbul 120");

list.Add("Edirne İzmir 250");

list.Add("İstanbul Bolu 350");

list.Add("İstanbul Bursa 150");

list.Add("İstanbul İzmir 225");

list.Add("İstanbul Edirne 120");

list.Add("Bursa Bolu 180");

list.Add("Bursa Ankara 225");

list.Add("Bursa Antalya 670");

list.Add("Bursa İzmir 170");

list.Add("Bursa İstanbul 160");

list.Add("İzmir Edirne 250");

list.Add("İzmir İstanbul 225");

list.Add("İzmir Bursa 170");

list.Add("İzmir Antalya 350");

list.Add("İzmir Ankara 450");

list.Add("Antalya İzmir 325");

list.Add("Antalya Bursa 300");

list.Add("Antalya Ankara 560");

list.Add("Bolu Bartın 120");

list.Add("Bolu Yozgat 400");

list.Add("Bolu Ankara 190");

list.Add("Bolu Bursa 180");

list.Add("Bolu İstanbul 350");

list.Add("Ankara Bolu 200");

list.Add("Ankara Bartın 325");

list.Add("Ankara Yozgat 240");

list.Add("Ankara Konya 260");

list.Add("Ankara Antalya 600");

list.Add("Ankara Bursa 265");

list.Add("Ankara İzmir 475");

list.Add("Bartın Trabzon 275");

list.Add("Bartın Yozgat 180");

list.Add("Bartın Ankara 400");

list.Add("Bartın Bolu 120");

list.Add("Yozgat Bartın 180");

list.Add("Yozgat Trabzon 210");

list.Add("Yozgat Hakkari 700");

list.Add("Yozgat Konya 400");

list.Add("Yozgat Ankara 240");

list.Add("Yozgat Bolu 325");

list.Add("Trabzon Bartın 300");

list.Add("Trabzon Erzurum 230");

list.Add("Trabzon Hakkari 650");

list.Add("Trabzon Yozgat 210");

list.Add("Konya Ankara 260");

list.Add("Konya Yozgat 370");

list.Add("Konya Erzurum 750");

list.Add("Konya Mardin 350");

list.Add("Konya Antalya 550");

list.Add("Erzurum Trabzon 250");

list.Add("Erzurum Hakkari 350");

list.Add("Erzurum Mardin 450");

list.Add("Erzurum Konya 700");

list.Add("Hakkari Erzurum 350");

list.Add("Hakkari Mardin 260");

list.Add("Hakkari Yozgat 750");

list.Add("Hakkari Trabzon 650");

list.Add("Mardin Erzurum 450");

list.Add("Mardin Hakkari 260");

list.Add("Mardin Konya 400");

list.Add("Mardin Antalya 675");

// haritamız

graph = new Graph();

foreach (var item in list)

{

var arr = item.Split(' ');

GNode gSource = new GNode(arr[0].Trim());

GNode gTarget = new GNode(arr[1].Trim());

var distance = Convert.ToInt32(arr[2]); var oNode = graph.Nodes.FirstOrDefault(x => x.Source.Name == gSource.Name); // Ekranda şehirlerin koordinatlarını göstermek için X,Y point ayarı yapıyorum

// Koordinatları yaklaşık olarka hardcoded setlemek istedim, normal şartlarda dbden okunabilir

if (oNode == null)

{

graph.Nodes.Add(new GraphItem(gSource));

oNode = graph.Nodes.Last();

switch (oNode.Source.Name)

{

case "Ankara":

{

oNode.Source.Point = new Point(400, 230);

break;

}

case "İstanbul":

{

oNode.Source.Point = new Point(140, 90);

break;

}

case "Edirne":

{

oNode.Source.Point = new Point(40, 40);

break;

}

case "İzmir":

{

oNode.Source.Point = new Point(85, 265);

break;

}

case "Bursa":

{

oNode.Source.Point = new Point(225, 180);

break;

}

case "Antalya":

{

oNode.Source.Point = new Point(250, 400);

break;

}

case "Bolu":

{

oNode.Source.Point = new Point(360, 115);

break;

}

case "Bartın":

{

oNode.Source.Point = new Point(465, 55);

break;

}

case "Yozgat":

{

oNode.Source.Point = new Point(565, 180);

break;

}

case "Konya":

{

oNode.Source.Point = new Point(560, 315);

break;

}

case "Mardin":

{

oNode.Source.Point = new Point(665, 385);

break;

}

case "Trabzon":

{

oNode.Source.Point = new Point(665, 105);

break;

}

case "Erzurum":

{

oNode.Source.Point = new Point(800, 185);

break;

}

case "Hakkari":

{

oNode.Source.Point = new Point(820, 415);

break;

}

default: break;

}

}

// Bu düğümün ilişki matrisini giriyorum

oNode.Vertexs.Add(new VertexItem(gTarget, distance));

}

// Ekranda şehirler arası çizgileri çizmek için point noktalarını setliyorum foreach (var item in graph.Nodes)

{

foreach (var item2 in item.Vertexs)

{

item2.Target.Point = graph.Nodes.First(x => x.Source.Name == item2.Target.Name).Source.Point;

}

}

// Form boyutu değiştiğinde harita refresh olsun this.ClientSizeChanged += (ss, ee) => { this.Invalidate(); }; // Haritayı çiz this.Paint += (ss, ee) =>

{

// daire yarıçapı var radius = 50; // tüm nodları gez foreach (var item in graph.Nodes)

{

var xx = item.Source.Point.X; var yy = item.Source.Point.Y;

ee.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

ee.Graphics.FillEllipse(Brushes.Red, xx, yy, radius, radius);

ee.Graphics.DrawString(item.Source.Name, new Font("Tahoma", 8), Brushes.Black, xx + 5, yy + 10);

// ilişik matrisine bakarak bu noddan ilişik matrisine çizgiler çiz foreach (var item2 in item.Vertexs)

{

var xxFrom = item.Source.Point.X + radius / 2; var yyFrom = item.Source.Point.Y + radius / 2; var xxTo = item2.Target.Point.X + radius / 2; var yyTo = item2.Target.Point.Y + radius / 2;

ee.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

ee.Graphics.DrawLine(new Pen(Color.Blue, 2), xxFrom, yyFrom, xxTo, yyTo);

}

}

};

}

private void btnBul_Click(object sender, EventArgs e)

{

rtb1.Text = string.Empty;

// Kaynak Bolu // Hedef Antalya // Zorunlu güzergah Trabzom // Yasaklı güzergah Konya

Find("Bolu", "Antalya", new string[] { "Trabzon" }, new string[] { "Konya" });

}

// tüm graphi gezeceğiz private void Find(string start, string end, string[] musts, string[] denieds)

{

// başlangıç nodunu bul var gStart = graph.Nodes.FirstOrDefault(x => x.Source.Name == start); // bitiş nodunu bul var gEnd = graph.Nodes.FirstOrDefault(x => x.Source.Name == end); // dolaşımda kullanılan path bilgisini nodelist olacak şekilde Stack yapısında tutacağız, recursive kullanacağız

Stack<GraphItem> path = new Stack<GraphItem>();

// En pahalı mesafe 2milyar küsür kmdir, bunu maliyet düşürme işleminde kullanacağız int maxDistance = int.MaxValue; // bu şehre uğradım biti

gStart.IsVisited = true;

// şehri pathe ekle

path.Push(gStart);

// nodun ilişkilerini dolaş foreach (var item in gStart.Vertexs)

{

// şimdiki ilişki nodunu al var gCur = graph.Nodes.FirstOrDefault(x => x.Source.Name == item.Target.Name); // ilişki nodunu ziyaret ettim biti

gCur.IsVisited = true;

// pathe ekle

path.Push(gCur);

// Recursive olarak taramaya başla, bu loopdan sonra tüm şehirler gezinmiş olacak

FindRecursive(ref gCur, gStart, gEnd, musts, denieds, ref path, ref maxDistance);

// ziyaret ettim bitini geri çek

gCur.IsVisited = false;

// pathden kaldır

path.Pop();

}

gStart.IsVisited = false;

path.Pop();

}

// Bir noddan diğer bir noda gez private void FindRecursive(ref GraphItem gCur, GraphItem start, GraphItem gEnd, string[] musts, string[] denieds, ref Stack<GraphItem> path, ref int maxDistance)

{

// vardığın nod hedef mi? if (gCur.Source == gEnd.Source)

{

// zorunlu güzergah var mı? bool hasMatchMusts = path.Select(x => x.Source.Name).ToArray().Any(x => musts.Any(y => y == x)); if (!hasMatchMusts)

{

return;

}

// maliyet hesapla var distance = 0;

List<GraphItem> list = new List<GraphItem>();

foreach (var item in path)

{

list.Insert(0, item);

}

for (int i = 0; i < list.Count - 1; i++)

{

var oDistance = list[i].Vertexs.First(x => x.Target.Name == list[i + 1].Source.Name).Distance;

distance += oDistance;

}

if (distance < maxDistance)

{

// maliyeti düşür

maxDistance = distance;

}

else return; // pathimiz budur var res = string.Join("-->", path.Select(x => x.Source.Name).Reverse()); this.Refresh(); // bulduğun pathi ekrana çiz

ShowPath(path);

rtb1.AppendText($"{res} ({maxDistance} km)\n");

// aramaya devam et return;

}

// ilişki nodunu gez foreach (var item in gCur.Vertexs)

{

var gCur2 = graph.Nodes.FirstOrDefault(x => x.Source.Name == item.Target.Name); // daha önce ziyaret ettiysen pas geç (sonsuz loopu engelliyoruz) if (gCur2.IsVisited) continue; // yasaklı güzergaha girdiysen pas geç if (denieds.Any(x => x.Contains(gCur2.Source.Name))) continue; // pathe ekle

path.Push(gCur2);

// ziyaret bitini setle

gCur2.IsVisited = true;

// aramaya devam et

FindRecursive(ref gCur2, start, gEnd, musts, denieds, ref path, ref maxDistance);

// ziyaret bitini kaldır

gCur2.IsVisited = false;

// pathden kaldır

path.Pop();

}

}

// path listesini ekranda çiz göster private void ShowPath(Stack<GraphItem> path)

{

List<GraphItem> list = new List<GraphItem>();

foreach (var item in path)

{

list.Insert(0, item);

}

Graphics g = this.CreateGraphics();

var radius = 50; for (int i = 0; i < list.Count; i++)

{

var item = list[i]; var xx = item.Source.Point.X; var yy = item.Source.Point.Y;

g.SmoothingMode = SmoothingMode.AntiAlias;

g.FillEllipse(Brushes.Green, xx, yy, radius, radius);

g.DrawString($"{item.Source.Name}({i + 1})", new Font("Tahoma", 8), Brushes.Black, xx + 5, yy + 10);

if (i + 1 < list.Count)

{

var item2 = list[i + 1]; var xxFrom = item.Source.Point.X + radius / 2; var yyFrom = item.Source.Point.Y + radius / 2; var xxTo = item2.Source.Point.X + radius / 2; var yyTo = item2.Source.Point.Y + radius / 2;

g.SmoothingMode = SmoothingMode.AntiAlias;

g.DrawLine(new Pen(Color.Orange, 2), xxFrom, yyFrom, xxTo, yyTo);

}

}

}

}

}

Sonuç

• Graph yapısını kullanarak kendi algoritmamızı işletmiş olduk

• Her şehri bir node olarak kurguladık, node'lar arası ilişki listesini Vertex olarak barındırdık

• Graph adlı classımız, tüm haritayı temsil etti.

• İstediğimiz senaryoya göre en kısa yolu bulmuş olduk ve pathini de göstermiş olduk.

Notlar:

• Recursive algoritmaların yazılması, bu tarz konulara yeni başlayanlar için karmaşık ve anlaşılması çok zor gelebilir.

• Graph tarzı modellemelerde kod yazarken, konuya tam focuslanılmalıdır, dikkat dağınıklığında lojik hakimeyetinizi kaybedebilirsiniz. Bu tarz kodları yazmak genellikle zorlayıcıdır.

Saygılarımla,

Hüsamettin ELALMIŞ – 05.06.2022

[e-mail]