Graph Yapılar
Husamettin Elalmis
Last updated
Husamettin Elalmis
Last updated
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
husamettin.elalmis@arksoft.com.tr
