|
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace DataStructTest
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private int totalNodes=100000;
private float[,] cost;
private DijkstraFast dijkstra;
private Random rv;
private void Form1_Load(object sender, EventArgs e)
{
cost = new float[totalNodes, 4];
// initialize the cost matrix
rv= new Random();
for (int i = 0; i < totalNodes; i++)
{
cost[i, 0] = (float)rv.Next(1000)*0.01f;
cost[i, 1] = (float)rv.Next(1000) * 0.01f;
cost[i, 2] = (float)rv.Next(1000) * 0.01f;
cost[i, 3] = (float)rv.Next(1000) * 0.01f;
}
dijkstra = new DijkstraFast(totalNodes,
new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost),
new DijkstraFast.NearbyNodesHint(GetNearbyNodes));
}
// a function to get relative position from one node to another
private int GetRelativePosition(int start, int finish)
{
if (start - 1 == finish)
return 0;
else if (start +1 == finish)
return 1;
else if (start +5 == finish)
return 2;
else if (start -5 == finish)
return 3;
return -1;
}
// get costs. If there is no connection, then cost is maximum.
private float getInternodeTraversalCost(int start, int finish)
{
int relativePosition = GetRelativePosition(start, finish);
if (relativePosition < 0) return float.MaxValue;
return cost[start, relativePosition];
}
private IEnumerable<int> GetNearbyNodes(int startingNode)
{
List<int> nearbyNodes = new List<int>(4);
if (startingNode >= totalNodes-5) startingNode = -1;
if (startingNode <=5) startingNode = -1;
// in the order as defined in GetRelativePosition
nearbyNodes.Add(startingNode-1);
nearbyNodes.Add(startingNode+1);
nearbyNodes.Add(startingNode+5);
nearbyNodes.Add(startingNode-5);
return nearbyNodes;
}
// compute
private void button1_Click(object sender, EventArgs e)
{
int t1 = Environment.TickCount;
int[] minPath = dijkstra.GetMinimumPath(int.Parse(textBox2.Text), int.Parse(textBox3.Text));
int t2 = Environment.TickCount;
listBox1.Items.Clear();
for (int i = 0; i != minPath.Length; i++)
listBox1.Items.Add(minPath[i]);
int diff = (t2 - t1);
MessageBox.Show("Path finding took "+diff.ToString()+" ms, Minimum item in list box: "+ minPath[minPath.Length-1].ToString());
}
// initialize
private void button2_Click(object sender, EventArgs e)
{
totalNodes=int.Parse(textBox1.Text);
cost = new float[totalNodes, 4];
// initialize the cost matrix
rv = new Random();
for (int i = 0; i < totalNodes; i++)
{
cost[i, 0] = (float)rv.Next(1000) * 0.01f;
cost[i, 1] = (float)rv.Next(1000) * 0.01f;
cost[i, 2] = (float)rv.Next(1000) * 0.01f;
cost[i, 3] = (float)rv.Next(1000) * 0.01f;
}
dijkstra = new DijkstraFast(totalNodes,
new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost),
new DijkstraFast.NearbyNodesHint(GetNearbyNodes));
}
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
Currently, also an MSc. student in Technical University of Munich, I develop practical application in computer vision for more than 5 years. I design real-time solutions to industrial and practical vision problems, both 3D and 2D. Very interested in developing algorithms in C relating math and vision.
Please visit Gravi's web page (http://www.gravi.com.tr) and my page (http://www.tbirdal.me) to learn more about what we develop.
I admire performance in algorithms.
"Great minds never die, they just tend to infinity..."