Kuskal and Dijkstra

[bsdpowa]

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

[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.

[bsdpowa]

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.

[Ramy Mahrous]

Never mind, I understood you :)

[thoughtcoder]

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

[Ramy Mahrous]

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 )
				{
					Thread.Sleep(1000);
					this.DrawAnswerPrim( q.to, q.from, q.key );
					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 ];
				///
				this.DrawAnswerKrusk( alternatives [ a ], alternatives [ b ], Adjecency_Matrix[a,b] );
				///
				MessageBox.Show ( " Next " ,"Solution",MessageBoxButtons.OK,MessageBoxIcon.Information);
				Adjecency_Matrix_Temp[a,b]= 10000;
				Adjecency_Matrix_Temp[b,a]= 10000;
				Adjecency_Matrix_Temp[a,a]= 1;
				Adjecency_Matrix_Temp[b,b]= 1;
				
			}
			else 
			{
				Adjecency_Matrix_Temp[a,b]= 0;
				Adjecency_Matrix_Temp[b,a]= 0;
			}
			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.

[bsdpowa]

Thank you very much Ramy!

[Ramy Mahrous]

Please mark this thread as solved :)

[thoughtcoder]

Agh why is there priority queue code mixed in? Kill me now.

[Ramy Mahrous]

It's not the best, it's what we wrote when I was student, and I didn't work in this algorithm I was in GUI Layer.