[Just another graph-related algorithm] Kruskal`s algorithm

[KraHen]

(Scroll down for the code if you aren`t interested in my wall of text.)

Okay, my previous post on Dijkstra`s algorithm didn`t really get the attention it was supposed to get, but I`m still starting a trend out of this. What exactly? I will be posting general purpose algorithms from time to time, as I truly believe that this is one of the most fundamental and important aspect of being a good coder : knowing the basic algorithms (lol?). If anyone can provide a way of implementing this in a CO environment, let me know, I have a few ideas but I want to see yours as well. (Hint : AI)

If anyone is interested in graph theory, here you get another algorithm from me (again don`t mind the implementation, I did this when I was starting out with C++, also did this as a school exercise, so it`s not even OOP. It`s purpose is just to demonstrate a basic implementation of the algorithm). IF you aren`t familiar with graph theory, don`t worry, if you don`t want to read up on it, I will be composing a simple, but pretty long description/guide of it which I will be posting here.

So here it goes, what is Kruskal`s algorithm? If you ever worked with graphs, you are probably aware of what trees are, also what a minimum spanning tree is. Kruskal`s algorithm computes just that, the minimum spanning tree of a more complex (connected and weighted!) graph, and does this with a greedy approach. I store the graph with an incidence list in a std::vector, opposed to the distance matrix used in my Dijkstra code released @ epvp.

Here`s a wikipedia link which can explain better : Kruskal's algorithm - Wikipedia, the free encyclopedia

Also a youtube video :

CODE :

 Spoiler

PHP Code:

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int N; int M;
priority_queue< pair<int, pair<int, int> > > q; // our queue
vector< pair<int, pair<int,int > > > tmp; // auxiliary container
vector< pair<int, pair<int,int > > > ffa; // minimum spanning tree
bool jartam[1000]; // "jartam" means "visited" in hungarian :) 

void getData()
{
    ifstream fin("kruskal.txt");
    fin >> N; fin >> M;
    pair<int, pair<int,int> > temp;
    int a, b, d; // from A to B, with a length of D
    for(int i=0; i<N; ++i)
    {
        fin >> a; fin >> b; fin >> d;
        temp.first = -d; temp.second.first = a; temp.second.second = b;
        // NOTE : we add the distance with a - prefix to ensure that the priority queue orders it in the right way
        q.push(temp);
    }
    fin.close();
}

void Kruskal()
{
    pair<int, pair<int,int> > temp;
    temp = q.top(); q.pop();
    ffa.push_back(temp);
    jartam[temp.second.first] = true;
    jartam[temp.second.second] = true;
    while(!q.empty())
    {
        temp = q.top(); q.pop();
        if(jartam[temp.second.first]==true && jartam[temp.second.second]==false)
        {
            // add to the m. spanning tree
            ffa.push_back(temp);
            // cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
            jartam[temp.second.second] = true;
            // push tmp`s values
            while(!tmp.empty())
            {
                q.push(tmp.back());
                tmp.pop_back();
            }
        }
        if(jartam[temp.second.first]==false && jartam[temp.second.second]==true)
        {
            // add to the minimum spanning tree
            ffa.push_back(temp);
            //  cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
            jartam[temp.second.first] = true;
            // pushing tmp`s values
            while(!tmp.empty())
            {
                q.push(tmp.back());
                tmp.pop_back();
            }
        }
        if(jartam[temp.second.first]==true && jartam[temp.second.second]==true)
        {
            tmp.push_back(temp); // we put it aside
        }
        // else do nothing
    }
}

int main()
{
    getData();
    Kruskal();
    cout << "Minimum spanning tree : " << endl;
    for(unsigned int i=0; i<ffa.size(); ++i)
    {
        cout << ffa.at(i).second.first << " -> " << ffa.at(i).second.second << " = " << -ffa.at(i).first << endl;
    }
    cin.get();
    return 0;
} 


That`s all folks!

[Zeroxelli]

This looks real interesting, going to read up on it in a bit here. Thanks

[InfamousNoone]

cool video, enjoyed watching

[KraHen]

Here`s one way of using it : you construct a tree for a bot, where the nodes are different behaviors for the AI. Based on how the player acts, you can eliminate some of these behaviors, then out of the remaining nodes, you construct a minimum spanning tree, and randomly (based on player behavior) move between the nodes of your new tree. It constructs a pretty believable bot IMO.

[Zeroxelli]

Yeah, from the bits of information I've had the time to read so far, it really does seem like a feasible option for a good AI system.

[MeGaMaX]

Interesting ^^

rewritten c# code maybe useful for some one

using System.Collections.Generic;
using System;

private int N;
private int M;
private priority_queue< pair<int, pair<int, int>> > q = new priority_queue< pair<int, pair<int, int>> >(); // our queue
private List< pair<int, pair<int,int >> > tmp = new List< pair<int, pair<int,int >> >(); // auxiliary container
private List< pair<int, pair<int,int >> > ffa = new List< pair<int, pair<int,int >> >(); // minimum spanning tree
private bool[] jartam = new bool[1000]; // "jartam" means "visited" in hungarian :)

private void getData()
{
	ifstream fin = new ifstream( "kruskal.txt" );
	fin >> N;
	fin >> M;
	pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>();
	int a; // from A to B, with a length of D
	int b;
	int d;
	for ( int i = 0; i < N; ++ i )
	{
		fin >> a;
		fin >> b;
		fin >> d;
		temp.first = -d;
		temp.second.first = a;
		temp.second.second = b;
		// NOTE : we add the distance with a - prefix to ensure that the priority queue orders it in the right way
		q.push( temp );
	}
	fin.close();
}

private void Kruskal()
{
	pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>();
	temp = q.top();
	q.pop();
	ffa.Add( temp );
	jartam[ temp.second.first ] = true;
	jartam[ temp.second.second ] = true;
	while ( ! q.empty() )
	{
		temp = q.top();
		q.pop();
		if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == false )
		{
			// add to the m. spanning tree
			ffa.Add( temp );
			// cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
			jartam[ temp.second.second ] = true;
			// push tmp`s values
			while ( tmp.Count > 0 )
			{
				q.push( tmp[ tmp.Count - 1 ] );
				tmp.RemoveAt( tmp.Count - 1 );
			}
		}
		if ( jartam[ temp.second.first ] == false && jartam[ temp.second.second ] == true )
		{
			// add to the minimum spanning tree
			ffa.Add( temp );
			//  cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
			jartam[ temp.second.first ] = true;
			// pushing tmp`s values
			while ( tmp.Count > 0 )
			{
				q.push( tmp[ tmp.Count - 1 ] );
				tmp.RemoveAt( tmp.Count - 1 );
			}
		}
		if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == true )
		{
			tmp.Add( temp ); // we put it aside
		}
		// else do nothing
	}
}

static int Main()
{
	getData();
	Kruskal();
	Console.Write( "Minimum spanning tree : " );
	Console.Write( "\n" );
	for ( uint i = 0; i < ffa.Count; ++ i )
	{
		Console.Write( ffa[ i ].second.first );
		Console.Write( " -> " );
		Console.Write( ffa[ i ].second.second );
		Console.Write( " = " );
		Console.Write( -ffa[ i ].first );
		Console.Write( "\n" );
	}
	Console.Read();
	return 0;
}

[I don't have a username]

Not a full rewriting, but almost :P

[Zeroxelli]

Originally Posted by androw3349

Interesting ^^

rewritten c# code maybe useful for some one

using System.Collections.Generic;
using System;

private int N;
private int M;
private priority_queue< pair<int, pair<int, int>> > q = new priority_queue< pair<int, pair<int, int>> >(); // our queue
private List< pair<int, pair<int,int >> > tmp = new List< pair<int, pair<int,int >> >(); // auxiliary container
private List< pair<int, pair<int,int >> > ffa = new List< pair<int, pair<int,int >> >(); // minimum spanning tree
private bool[] jartam = new bool[1000]; // "jartam" means "visited" in hungarian :)

private void getData()
{
	ifstream fin = new ifstream( "kruskal.txt" );
	fin >> N;
	fin >> M;
	pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>();
	int a; // from A to B, with a length of D
	int b;
	int d;
	for ( int i = 0; i < N; ++ i )
	{
		fin >> a;
		fin >> b;
		fin >> d;
		temp.first = -d;
		temp.second.first = a;
		temp.second.second = b;
		// NOTE : we add the distance with a - prefix to ensure that the priority queue orders it in the right way
		q.push( temp );
	}
	fin.close();
}

private void Kruskal()
{
	pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>();
	temp = q.top();
	q.pop();
	ffa.Add( temp );
	jartam[ temp.second.first ] = true;
	jartam[ temp.second.second ] = true;
	while ( ! q.empty() )
	{
		temp = q.top();
		q.pop();
		if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == false )
		{
			// add to the m. spanning tree
			ffa.Add( temp );
			// cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
			jartam[ temp.second.second ] = true;
			// push tmp`s values
			while ( tmp.Count > 0 )
			{
				q.push( tmp[ tmp.Count - 1 ] );
				tmp.RemoveAt( tmp.Count - 1 );
			}
		}
		if ( jartam[ temp.second.first ] == false && jartam[ temp.second.second ] == true )
		{
			// add to the minimum spanning tree
			ffa.Add( temp );
			//  cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl;
			jartam[ temp.second.first ] = true;
			// pushing tmp`s values
			while ( tmp.Count > 0 )
			{
				q.push( tmp[ tmp.Count - 1 ] );
				tmp.RemoveAt( tmp.Count - 1 );
			}
		}
		if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == true )
		{
			tmp.Add( temp ); // we put it aside
		}
		// else do nothing
	}
}

static int Main()
{
	getData();
	Kruskal();
	Console.Write( "Minimum spanning tree : " );
	Console.Write( "\n" );
	for ( uint i = 0; i < ffa.Count; ++ i )
	{
		Console.Write( ffa[ i ].second.first );
		Console.Write( " -> " );
		Console.Write( ffa[ i ].second.second );
		Console.Write( " = " );
		Console.Write( -ffa[ i ].first );
		Console.Write( "\n" );
	}
	Console.Read();
	return 0;
}

Could use having the variables named after the paper on the algorithm, or at least naming the variables something more appropriate, and possibly some formatting. But that's just me.

[MeGaMaX]

sorry if it not rewritten good but in fact i'm not good at C# as C++

[shitboi]

most graph traversal algorithms are not exactly great within map coordinate to coordinate travel, especially maps with rivers. Even after revising them to account for rivers, one may face a limited stack problem, unless you change it to use loop instead of recursion

[KraHen]

This isn`t a graph traversal algorithm. And if you face stack limitation problems you clearly don`t know anything about graphs.

[shitboi]

lol.. i was thinking about tree when i replied.