Permalink
Reply
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 gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]