Grafik (soyut veri türü) - Graph (abstract data type)

Bir Yönlendirilmiş grafik üç ile köşeler (mavi daireler) ve üç kenarlar (siyah oklar).

İçinde bilgisayar Bilimi, bir grafik bir soyut veri türü bu, uygulamak içindir yönsüz grafik ve Yönlendirilmiş grafik alanından kavramlar grafik teorisi içinde matematik.

Bir grafik veri yapısı, sonlu (ve muhtemelen değiştirilebilir) Ayarlamak nın-nin köşeler (olarak da adlandırılır düğümler veya puan), yönsüz bir grafik için bu köşelerin sırasız çiftleri veya yönlendirilmiş bir grafik için sıralı çiftler kümesi ile birlikte. Bu çiftler olarak bilinir kenarlar (olarak da adlandırılır bağlantılar veya çizgiler) ve yönlendirilmiş bir grafik için de bilinir oklar. Köşeler, grafik yapısının bir parçası olabilir veya tamsayı endeksleri ile temsil edilen harici öğeler olabilir veya Referanslar.

Bir grafik veri yapısı ayrıca her bir kenara bazılarını ilişkilendirebilir. kenar değerisembolik bir etiket veya sayısal bir öznitelik (maliyet, kapasite, uzunluk vb.) gibi.

Operasyonlar

Bir grafik veri yapısı tarafından sağlanan temel işlemler G genellikle şunları içerir:^[1]

• komşu(G, x, y): tepe noktasından bir kenar olup olmadığını test eder x tepe noktasına y;
• komşular(G, x): tüm köşeleri listeler y öyle ki tepe noktasından bir kenar var x tepe noktasına y;
• add_vertex(G, x): tepe noktasını ekler xorada değilse;
• remove_vertex(G, x): tepe noktasını kaldırır xeğer varsa;
• add_edge(G, x, y): tepe noktasından kenar ekler x tepe noktasına yorada değilse;
• remove_edge(G, x, y): kenarı tepe noktasından kaldırır x tepe noktasına yeğer varsa;
• get_vertex_value(G, x): köşe ile ilişkili değeri döndürür x;
• set_vertex_value(G, x, v): tepe noktasıyla ilişkili değeri ayarlar x -e v.

Değerleri kenarlarla ilişkilendiren yapılar genellikle şunları da sağlar:^[1]

• get_edge_value(G, x, y): kenarla ilişkili değeri döndürür (x, y);
• set_edge_value(G, x, y, v): kenarla ilişkili değeri ayarlar (x, y) için v.

Beyanlar

Pratikte grafiklerin gösterimi için farklı veri yapıları kullanılır:

Komşuluk listesi^[2]

Tepe noktaları kayıtlar veya nesneler olarak saklanır ve her köşe bir liste bitişik köşelerin. Bu veri yapısı, köşelerde ek verilerin depolanmasına izin verir. Kenarların nesneler olarak da saklanması durumunda ek veriler depolanabilir; bu durumda her köşe, gelen kenarlarını ve her kenar, olay köşelerini saklar.

Bitişiklik matrisi^[3]

Satırların kaynak köşeleri ve sütunların hedef köşeleri temsil ettiği iki boyutlu bir matris. Kenar ve köşelerdeki veriler harici olarak depolanmalıdır. Her köşe çifti arasında yalnızca bir kenarın maliyeti saklanabilir.

Sıklık matrisi^[4]

Satırların köşeleri ve sütunların kenarları temsil ettiği iki boyutlu bir Boole matrisi. Girişler, bir satırdaki tepe noktasının bir sütundaki kenara denk gelip gelmediğini gösterir.

Aşağıdaki tablo, zaman karmaşıklığı Bu gösterimlerin her biri için grafikler üzerinde çeşitli işlemler gerçekleştirmenin maliyeti |V | köşe sayısı ve |E | kenarların sayısı.^{[kaynak belirtilmeli ]} Matris gösterimlerinde, girişler bir kenarı takip etmenin maliyetini kodlar. Mevcut olmayan kenarların maliyetinin ∞ olduğu varsayılır.

	Komşuluk listesi	Bitişiklik matrisi	Sıklık matrisi
Mağaza grafiği	${ displaystyle O (| V | + | E |)}$	${ displaystyle O (| V | ^ {2})}$	${ displaystyle O (| V | cdot | E |)}$
Köşe ekle	${ displaystyle O (1)}$	${ displaystyle O (| V | ^ {2})}$	${ displaystyle O (| V | cdot | E |)}$
Kenar ekleyin	${ displaystyle O (1)}$	${ displaystyle O (1)}$	${ displaystyle O (| V | cdot | E |)}$
Köşeyi kaldır	${ displaystyle O (| E |)}$	${ displaystyle O (| V | ^ {2})}$	${ displaystyle O (| V | cdot | E |)}$
Kenarı kaldır	${ displaystyle O (| V |)}$	${ displaystyle O (1)}$	${ displaystyle O (| V | cdot | E |)}$
Köşeler x ve y bitişik mi (saklama konumlarının bilindiği varsayılarak)?	${ displaystyle O (| V |)}$	${ displaystyle O (1)}$	${ displaystyle O (| E |)}$
Uyarılar	Tüm köşeleri veya kenarları bulması gerektiğinden, köşeleri ve kenarları kaldırmak için yavaş	Köşelerin eklenmesi veya çıkarılması yavaş, çünkü matrisin yeniden boyutlandırılması / kopyalanması gerekir	Matrisin yeniden boyutlandırılması / kopyalanması gerektiğinden, köşeleri ve kenarları eklemek veya kaldırmak yavaş

Bitişiklik listeleri genellikle tercih edilir çünkü bunlar seyrek grafikler. Grafik yoğunsa, yani kenar sayısı ise bitişik matris tercih edilir |E | kare köşelerin sayısına yakın, |V |²veya iki köşeyi birbirine bağlayan bir kenar varsa, hızlı bir şekilde bakılabilmesi gerekiyorsa.^[5][6]

Paralel Grafik Gösterimleri

Grafik problemlerinin paralelleştirilmesi önemli zorluklarla karşı karşıyadır: Veriye dayalı hesaplamalar, yapılandırılmamış problemler, zayıf konum ve hesaplama oranına yüksek veri erişimi.^[7][8] Paralel mimariler için kullanılan grafik gösterimi, bu zorlukların üstesinden gelmede önemli bir rol oynar. Kötü seçilmiş temsiller, algoritmanın iletişim maliyetini gereksiz şekilde artırabilir ve ölçeklenebilirlik. Aşağıda, paylaşılan ve dağıtılmış bellek mimarileri ele alınmıştır.

Paylaşılan hafıza

Bir durumunda paylaşılan hafıza model, paralel işlem için kullanılan grafik gösterimleri sıralı durumdakiyle aynıdır,^[9] çünkü grafik gösterimine paralel salt okunur erişim (ör. bitişiklik listesi ) paylaşılan bellekte etkilidir.

Dağıtılmış Bellek

İçinde dağıtılmış bellek model, olağan yaklaşım, bölüm köşe kümesi ${ displaystyle V}$ grafiğin içine ${ displaystyle p}$ setleri ${ displaystyle V_ {0}, noktalar, V_ {p-1}}$. Buraya, ${ displaystyle p}$ mevcut işleme elemanlarının (PE) miktarıdır. Köşe seti bölümleri daha sonra eşleşen endeksli PE'lere ve ayrıca karşılık gelen kenarlara dağıtılır. Her PE'nin kendine ait alt grafik başka bir bölümdeki bir uç noktaya sahip kenarların özel dikkat gerektirdiği temsil. Standart iletişim arayüzleri için MPI, diğer uç noktaya sahip olan PE'nin kimliği tanımlanabilir olmalıdır. Dağıtık bir grafik algoritmalarında hesaplama sırasında, bilgilerin bu kenarlardan geçirilmesi iletişim anlamına gelir.^[9]

Grafiği bölümlere ayırma dikkatlice yapılması gerekiyor - düşük iletişim ve hatta boyut bölümleme arasında bir denge var^[10] Ancak bir grafiği bölmek NP açısından zor bir sorundur, bu yüzden onları hesaplamak mümkün değildir. Bunun yerine, aşağıdaki buluşsal yöntemler kullanılır.

1D bölümleme: Her işlemci ${ displaystyle n / p}$ köşeler ve karşılık gelen giden kenarlar. Bu, bitişik matrisin satır bazlı veya sütun bazlı ayrışması olarak anlaşılabilir. Bu gösterimde çalışan algoritmalar için bu, Hepsi Bir Arada iletişim adımının yanı sıra ${ displaystyle { mathcal {O}} (m)}$ her bir PE potansiyel olarak diğer her bir PE'ye giden kenarlara sahip olduğundan ileti arabellek boyutları.^[11]

2D bölümleme: Her işlemci bitişik matrisin bir alt matrisini alır. İşlemcilerin dikdörtgen şeklinde hizalandığını varsayın ${ displaystyle p = p_ {r} kere p_ {c}}$, nerede ${ displaystyle p_ {r}}$ ve ${ displaystyle p_ {c}}$ sırasıyla her satır ve sütundaki işleme öğelerinin miktarıdır. Ardından her işlemci bir alt matris bitişik boyut matrisinin ${ displaystyle (n / p_ {r}) kere (n / p_ {c})}$. Bu bir dama tahtası bir matristeki desen.^[11] Bu nedenle, her işleme birimi, aynı satır ve sütunda yalnızca PE'lere giden kenarlara sahip olabilir. Bu, her PE için iletişim ortağı sayısını sınırlandırır. ${ displaystyle p_ {r} + p_ {c} -1}$ dışında ${ displaystyle p = p_ {r} kere p_ {c}}$ olası olanlar.

Ayrıca bakınız

• Grafik geçişi grafik yürüyüş stratejileri için
• Grafik veritabanı grafik (veri yapısı) kalıcılığı için
• Grafik yeniden yazma grafiklerin kural tabanlı dönüşümleri için (grafik veri yapıları)
• Grafik çizim yazılımı grafik çizmek için yazılım, sistem ve sistem sağlayıcıları için

Referanslar

Dış bağlantılar

• Boost Grafik Kitaplığı: güçlü bir C ++ grafik kitaplığı s.a. Boost (C ++ kitaplıkları)
• Networkx: bir Python grafik kitaplığı
• GraphMatcher Yönlü / yönsüz grafikleri hizalamak için bir java programı.
• GraphBLAS Özellikle seyrek grafiklere odaklanarak, grafikler üzerindeki işlemler için bir kütüphane arayüzü spesifikasyonu.