Forum: D Programlama Dili RSS
Çizit Veri Yapisi
kerdemdemir #1
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Çizit Veri Yapisi
Merhabalar,

Ali Abi ile azcık konuşmuştuk benim ihtiyacim oluyor şu yarışma soruları çözerken örneğin: http://codeforces.com/contest/839/problem/C.

Salih hocamda bazı açıklamaların eksik olduğunu söylemişti ve bazı tavsiyelerde bulunmuştu. Dediği gibi interface, fonksiyon şablonları filan biraz karışık fakat bunların amaçları benim ihtiyaç duyduğum esnekliği sağlayabilmeleri. Benim bu kodu kopyala-yapıştır yaparak değişik sorulara uyarlamam gerekiyor. Yarışmalar 3. kişilerin kütüphanelerini kabul etmiyor fakat direk kodu kopyala yapıştır yapmak mümkün.

Çok az düzeltmeler yaptım benim işimi gördü şimdilik daha gerektikce geliştireceğim. Sizin bir tavsiyeniz olursa lütfen belirtin sizde.

Şu main'e yazdığım şeyleri "unittest" yapmak istemiştim beceremedim. Şimdi ona uğraşacam biraz hem öğrenmek için hemde güzel gözüksün diye.  Kodlari unittest parentesinin içine koyduğumda hiç birşey olmadı sanki. 

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.array;
import std.range;
import std.math;
import std.container;
 
/**
  * Graph veri yapilari Node'lardan olusurlar . 
  * Bu Nodelar degisik veriler icerebilir. Fakat DFS ve BFS gibi algoritmaların bu degisik verilerden 
  * bagimsiz calisabilmesi icin asagidaki interface'i yarattim
 */
interface Node( NodeType)
{
    /** Bu node'un degerini doner ornegin A sehri icin 'A' olabilir veya 1. şehir için bir int olarak 1 olabilir 
        bu nedenle donus degeri bir sablondur */
    NodeType.Type GetValue();
    /** Bu node'a bagli diger nodelari doner  */
    NodeType[] GetConnectedElems();
    /** Bu node'a baska nodeları ekleyebilmemiz icindir. "..." kullanarak istediğimiz sayida Node'u ekleyebilmemiz 
    amaclanmistir. Ornegin ayni anda 2 veya 3 veya istenilen sayida Node eklenebilir   */
    void AddConnection( NodeType[] connections... );
}
 
/**
 *  Char veya Integer gibi basit verileri tutacak Nodelar icin tasarlanmistir. 
 */
class PrimitiveNode(T) : Node!(PrimitiveNode)
{
public:
    alias Type = T;
    this( Type val )
    {
        value = val; 
        isVisited = false;
        dist      = uint.max;
    }
 
    /** Interface methodlari */
    PrimitiveNode[] GetConnectedElems()
    {
        return connectedNodes;
    }
 
    void AddConnection( PrimitiveNode[] connections... )
    {
        foreach (connection; connections) {
            connectedNodes ~= connection;
        }    
    }
 
    int GetValue()
    {
        return value;
    }
 
    /** Bu Node turune ozel uzaklık ve daha once gezildi bilgisini tutan fonksiyonlar */
    uint GetDist()
    {
        return dist;
    }
 
    bool IsVisited()
    {
        return isVisited; 
    }
 
    void SetVisited()
    {
        isVisited = true;
    }
 
    void SetDist( uint newDist )
    {
        dist = newDist;
    }
 
    bool SetDistIfCloser ( uint newDist )
    {
        if ( newDist < dist )
        {
            dist = newDist;
            return true;
        }
        return false;
    } 
 
    PrimitiveNode[] connectedNodes;
    int value;
    uint dist;
    bool isVisited;
}
 
/**
 *  Nodelarin listesini tutan Graph veri yapisi. Simdilik sadece DFS ve BFS algoritmalarini iceriyor ilerde umarim buyur. Node tipini 
 *  Sablon seklinde aldigi icin degisik node turleri ile calisabilecek sekilde tasarlandi  
 */
struct Graph(NodeType)
{
    /** Node dizisi */
    NodeType[] adjMatrix;
 
    /**
     * Ornek BFS uygulamasi visitor diye bir fonksiyon aliyor disardan bu bulundugu node'un komsulari eger bu visitor fonksiyonu true 
       donuyorsa ziyaret ediyor. Visitor fonksiyonu degisebilir ornegin 
       1 - daha once ziyaret edilmis ise false donebilir veya (Klasik BFS)
       2 - daha once ziyaret edilmemisse node daha uzak ise false donebilir (Klasik en yakin yol bulma) 
       
       Bunlarin disinda bir cok degisik davranis eklenmesi amaclanmistir.  
     */
    void BFS( VisitBehaviour )( VisitBehaviour visitor, NodeType vertex)
    {
        import std.container : DList;
        DList!(NodeType) queue;
 
        queue.insertBack(vertex);
        while (!queue.empty())
        {
            auto current = queue.front();
            queue.removeFront();
            foreach ( elem ; current.GetConnectedElems() )
            {
                if ( visitor( elem, current ) )
                    queue.insertBack(elem);
            }
        }
    }
 
    /** Klasik DFS implementasyonu Visitor BFS deki gibi planlanmistir.  */
    void DFSHelper( VisitBehaviour )( VisitBehaviour visitor, NodeType element )
    {
        foreach ( elem; element.GetConnectedElems())
        {
            if ( !visitor() )
            {
                DFSHelper(visitor, elem);
            }
        }
    }
 
    /** Klasik DFS implementasyonu Visitor BFS deki gibi planlanmistir.  */    
    void DFS ( VisitBehaviour )( VisitBehaviour visitor )
    {
        for (uint i = 0; i < adjMatrix.length; i++)
        {
            if ( !visitor() )
                DFSHelper(visitor, adjMatrix[i]);
        }
    }
};
 
 
 
int main(string[] argv)
{
    /** Bunlari unittest icinde yapmak isterdim beceremedim  */    
 
     /** 4 tane node olusturdum degerleri 0,1,2,3  */
    auto first = new PrimitiveNode!int(0);
    auto second = new  PrimitiveNode!int(1);
    auto third = new  PrimitiveNode!int(2);
    auto fourth = new  PrimitiveNode!int(3);
 
     /**  2. ve 3. sehirler 1. sehirin komsusu */
    first.AddConnection(second, third);
     /**  4 sehir 2. sehirin komsusu */
    second.AddConnection(fourth);
 
     /** Nodelari graph veri yapisinin icine yerlestiriyorum.  Burda bir fonksiyon ve ... kullanabilirdim hos olurdu */
    Graph!(PrimitiveNode!int) cities;
    cities.adjMatrix ~= first;
    cities.adjMatrix ~= second;
    cities.adjMatrix ~= third;
    cities.adjMatrix ~= fourth;
 
    /** 1. gezme stratejisi bagli nodelarin belirli bir sehirden en yakin mesafesini bulur */
    bool visitStrategy1( PrimitiveNode!int current, PrimitiveNode!int parent )
    {
        uint newDist = parent.GetDist() + 1;
        if ( newDist < current.GetDist() )
        {
            current.SetDist(newDist);
            return true;
        }
        return false;        
    }
 
    /** 2. gezme stratejisi daha once gezilmis yerleri gezmez */
    bool visitStrategy2( PrimitiveNode!int current, PrimitiveNode!int parent )
    {
        if ( current.IsVisited() )
            return true;
        else 
        {
            current.SetVisited();
            return false; 
        }
    }
 
    first.SetDist(0);
    cities.BFS( &visitStrategy1, first);
    writeln( "4. sehrin 1. sehre uzakligi: ", fourth.GetDist()); // 2 Olmasini bekliyorum 
    writeln( "2. sehrin 1. sehre uzakligi: ", second.GetDist()); // 1 Olmasini bekliyorum 
    return 0;
}
Bu mesaj kerdemdemir tarafından değiştirildi; zaman: 2017-08-30, 14:46.
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Unittest bloğunun çalışabilmesi için derlerken -unittest parametresini vermek gerekiyor. Benzetme yerindeyse bu sanki 2. bir main fonksiyonu gibi düşünebiliriz.

Bir de yanlış hatırlamıyorsam, tek satırlık assertler var ki normal bir derleme anında bunlar koda dahil edilmiyordu.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #3
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Graph'ın Türkçesi grafik olmasa gerek... :)

assert'lerin (ve sözleşmeli programlama kodlarının) koddan çıkartılmaları için -release seçeneği kullanılıyor ama assert(false) hiçbir zaman koddan çıkartılmıyor.

Ali
erdem (Moderatör) #4
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Graph'ın türkçesi çizit.

Çizit (Giriş giriş)
int Kö() --> köşe sayısı
int Ke() --> kenar sayısı
void kenarEkle(int v, int w) --> v-->w'ye kenar ekle.
Tur komşular (int v) --> v düğümüne komşu olan düğümler

Sonra veri yapıları ile algoritmaların ayrılması kanatindeyim  :-)
kerdemdemir #5
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Erdem& Ali Abi teşekkür ederim başlığın ismini değiştirdim.Gerçekten kötü olmuş affola.

İş yerinde geçenlerde çok rezil oldum benden bir Json formatında disk'e birşey kaydetmemi istediler. Bende işte bir kaç veri yapısını sarmalayan adaptör sınıfları filan yazdım. Yanlışlıkla sınıfımın adını  "JsonWrapper" yerine "JasonWrapper",diye bırakmışım ve tatile çıkmışım. Biriside benim git branch'imden görmüş bunu utandım valla.
kerdemdemir #6
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #4
erdem:
Graph'ın türkçesi çizit.

Çizit (Giriş giriş)
int Kö() --> köşe sayısı
int Ke() --> kenar sayısı
void kenarEkle(int v, int w) --> v-->w'ye kenar ekle.
Tur komşular (int v) --> v düğümüne komşu olan düğümler


Eger bunu ilerde kullanırken büyür ve güzel hale gelirse veya başka birinden talep gelirse tavsiye ettiğin kelimelerle çevirebilirim. Acaba köşe yerine düğüm daha mı uygun?

erdem:
Sonra veri yapıları ile algoritmaların ayrılması kanatindeyim  :-)

Sanıyorsam Düğümlere(Node'lara) ait bir sınıf yaparken amacım buydu böylece Graph sınıfının içinde sadece algoritmalar kaldı.
erdem (Moderatör) #7
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
kerdemdemir:
Acaba köşe yerine düğüm daha mı uygun?

Herhalde vertice yerine köşe, node yerine de düğüm kullanılıyor. Ama ben ikisinin arasındaki farkı bilemiyorum.

Aslında bunları da şuradan bakmıştım: (Undirected graph data type)

http://algs4.cs.princeton.edu/41graph/
acehreli (Moderatör) #8
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Aslında vertice ve node aynı şey. Düğüm bağlantılarına edge deniyor.

Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-17, 16:52:56 (UTC -08:00)