Can anyone help me with Kuskal and Dijkstra algorithms in C#? I have no idea where to start. Any tips?

3
Contributors
9
Replies
10
Views
9 Years
Discussion Span
Last Post by Ramy Mahrous

My team and I developed those two algorithms in C#, when I back home I'll attach you the source code. Please remind me after 8 hrs from now.

Thank you very much, I will remind you later.

P.S. If there's any mod available I would be thankful if he/she could rename Kuskal to Kruskal. Typo.

Never mind, I understood you :)

You're just going to give the code? What?

Kruskal code

``````void swap ( ref Node a, ref Node b )
{
///<Rizk>
Node c = a ;
a = b ;
b = c ;
///</Rizk>
}

/// <summary>
/// Calculate the Left Child node of a Parent
/// Used in Heap
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
int left ( int i )
{
///<Rizk>
return i * 2;
///</Rizk>
}

//Calculate the right Child node of a Parent
//Used in Heap

int right ( int i )
{
///<Rizk>
return i * 2 + 1;
///</Rizk>
}

// Arrange the Heap to Exatract the Minimum

void Min_Heapify ( Node [] a, int i, int Heap_Size )
{
///<Rizk>
int min;
int l = left ( i );
int r = right ( i );

if ( l <= Heap_Size &&  a[ l - 1 ].key < a [ i - 1 ].key )
min = l;
else
min = i;

if ( r <= Heap_Size && a[ r - 1 ].key < a [ min - 1 ].key )
min = r;

if ( min != i )
{
swap ( ref a [ i - 1 ], ref a [ min - 1 ] );
Min_Heapify ( a , min , Heap_Size );
}
///</Rizk>
}

// Bulid the Heap

void Build_Min_Heap ( Node [] a, int Heap_Size )
{
///<Rizk>
for ( int i = a.Length/2; i >= 1; i--)
Min_Heapify ( a , i , Heap_Size );
///</Rizk>
}

//Extract the Minimum Node

Node Extract_Min ( Node [] a, int Heap_Size )
{
///<Rizk>
Build_Min_Heap ( a , Heap_Size );
return a [ 0 ];
///</Rizk>
}

//Linear Search to Allow the Coder to Specify the subscriptor by Char
//rether than by int Value
// Used by Prim's Algorithm...

int searchForName ( char name , char [] array )
{
///<Rizk>
for ( int i = 0; i < array.Length; i++ )
if ( name == array[ i ] )
return i;
return -1;
///</Rizk>
}

int searchForName ( char name , Node [] array )
{
///<Rizk>
for ( int i = 0; i < array.Length; i++ )
if ( name == array[ i ].to )
return i;
return -1;
///</Rizk>
}

void intialize_nodes ( char [] alternatives, char r )
{
///<Rizk>
ArrayOfNodes = new Node [ alternatives.Length ];

for ( int i = 0; i < alternatives.Length; i++ )
{
ArrayOfNodes[ i ].to = alternatives [ i ];
ArrayOfNodes[ i ].from = Const_char;
ArrayOfNodes[ i ].key = Const;
}

ArrayOfNodes [ searchForName ( r , ArrayOfNodes ) ].key = 0;
ArrayOfNodes [ searchForName ( r , ArrayOfNodes ) ].from = '0';
///</Rizk>
}

void neighbour ( char a , int Heap_Size )
{
///<Rizk>
int size = 0 ;

for ( int i = 0; i < array_length ; i++ )
if ( Adjecency_Matrix[ searchForName ( a , alternatives ) , i ] > 0  &&  IsFoundInHeap ( a , Heap_Size ) )
size ++;

Array_Of_Related_Nodes = new char [ size ];

for ( int i = 0, z = 0; i < array_length; i++ )
if ( Adjecency_Matrix[ searchForName ( a , alternatives ) , i ] > 0 && IsFoundInHeap ( a , Heap_Size ) )
{
Array_Of_Related_Nodes [ z++ ] = alternatives [ i ] ;

if ( ArrayOfNodes [ searchForName ( alternatives [ i ] , ArrayOfNodes ) ].from == Const_char )
ArrayOfNodes [ searchForName ( alternatives [ i ] , ArrayOfNodes ) ].from = a ;
}
///</Rizk>
}

bool IsFoundInHeap ( char a , int Heap_Size )
{
///<Rizk>
for ( int i = 0; i < Heap_Size; i++ )
if ( ArrayOfNodes [ i ].to == a )
return true;
return false;
///</Rizk>
}

void MST_Prime_Algorithm ( char r, int [ , ] Adjacency_Matrix, char [] alternatives, Node [] arrayOfNodes )
{
///<Rizk>
intialize_nodes ( alternatives , r );
string ramrom="Ramy.wav";
int Heap_Size = array_length;
Node q;
int z = 0;
while ( Heap_Size > 0 )
{
q = Extract_Min ( ArrayOfNodes , Heap_Size );
neighbour ( q.to , Heap_Size );

for ( int ii = 0; ii < Array_Of_Related_Nodes.Length; ii++ )
{
//check if the weight between the two vertex is less that or larger than the weight at the heap
if ( Adjacency_Matrix [ searchForName ( q.to, alternatives ) , searchForName ( Array_Of_Related_Nodes [ ii ] , alternatives ) ] < ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ], ArrayOfNodes ) ].key )
{
//replace with the minimum weight
ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ] , ArrayOfNodes ) ].key =  Adjacency_Matrix [ searchForName ( q.to, alternatives ) , searchForName ( Array_Of_Related_Nodes [ ii ] , alternatives ) ];
ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ] , ArrayOfNodes ) ].from = q.to;
}
}

array_final [ z ].to = q.to ;
array_final [ z ].from = q.from;
array_final [ z ].key = q.key;
z++ ;
if ( flagfirst == 0 )
{
MessageBox.Show ( " Next " ,"Solution",MessageBoxButtons.OK,MessageBoxIcon.Information);
}
swap ( ref ArrayOfNodes[ searchForName( q.to , ArrayOfNodes ) ] , ref ArrayOfNodes [ Heap_Size - 1 ] );
Heap_Size -- ;
flagfirst = 0;
}
///</Rizk>
}
int Get_smallest_other_Algorithm ( int [ , ] Adjecency_Matrix_Temp, ref int x, ref int y, ref int small )
{
///<Rizk>
int flg = 0 ;
int col, row;
for ( col = 0; col < array_length; col++ )
{
for ( row=0;row< array_length ; row++ )
if ( ( Adjecency_Matrix_Temp [ col, row ] != 0 ) && ( col != row ) && ( Adjecency_Matrix_Temp [ col, row ] != 10000 ) )
{
small = Adjecency_Matrix_Temp [ col, row ];
x = col;
y = row;
flg = 1;
break;
}
if ( flg == 1 )
break ;
}

for ( col = 0; col < array_length; col++ )
{
for ( row = 0; row < array_length; row++ )
if ( ( Adjecency_Matrix_Temp [ col, row ] < small ) && ( Adjecency_Matrix_Temp [ col, row ] != 0 )
&& ( col != row ) && ( Adjecency_Matrix_Temp [ col, row ] != 10000 ) )
{
small = Adjecency_Matrix_Temp [ col, row ];
x = col;
y = row;
}
}
return 0 ;
///</Rizk>
}

int  MST_other_Algorithm ( int small,int [ , ] Adjecency_Matrix_Temp, ref int  a, ref int  b)
{
///<Rizk>
int check = 0;
if ( ( Adjecency_Matrix_Temp [ a , a ] == 0 ) && ( Adjecency_Matrix_Temp [ b , b ] != 0 ) )
check = 1;
if ( ( Adjecency_Matrix_Temp [ a , a ] != 0 ) && ( Adjecency_Matrix_Temp [ b , b ] == 0 ) )
check = 1;
if ( ( Adjecency_Matrix_Temp [ a , a ] == 0 ) && ( Adjecency_Matrix_Temp [ b , b ] == 0 ) )
check = 1;
if ( check == 1 )
{

len++;
array_final [ len ].to = alternatives [ a ];
array_final [ len ].from = alternatives [ b ];
array_final [ len ].key= Adjecency_Matrix [ a, b ];
///
///
MessageBox.Show ( " Next " ,"Solution",MessageBoxButtons.OK,MessageBoxIcon.Information);

}
else
{
}
return 0;
///</Rizk>
}

int  check_end_other_Algorithm ( int [ , ] Adjecency_Matrix_Temp )
{
///<Rizk>
int x ,y ;

for ( x = 0; x < array_length; x ++ )
{
for ( y = 0; y < array_length ; y ++ )
{
if ( ( Adjecency_Matrix_Temp [ x , y ] == 0 ) && ( x == y ) )
return 0;
}
}

return 1 ;
///</Rizk>
}``````

This code we developed 4 years ago, I don't expect any beneficial unless you know the algorithm well.

Thank you very much Ramy!