
Comments and Discussions



many thanks it's a grate example






You might want to correct Euclidean distance in the Point3D class. Currently it does not take the zvalue into account. I kept on wondering why the algorithm was giving me a suboptimal path. Other than that, great job.





The rendering of power of two in the expression for norm is not rendered correctly. Please either use HTML character entity or the "sup" tag.
—SA
Sergey A Kryukov






is there any way to have my own H values for each and every node  means that i will provide the values manualy.






i need an euclidean distance c# code that gets the distance between two 1 dimension signals





Hi,
I was looking for a library that allows me to draw easily graps and this one seems really great! However, I could not find, so far, a way using this code to set and display labels for arcs and nodes. Any hint on that?
Thanks!





I find the article to be somewhat naive. Do not want to sound adversarial, but I am not sure what the goal of the article was meant to be. Was the goal was to introduce a family of informed offline searches A* algorithm belongs to? The subject of informed offline search is rather well studied, there are plenty of resources, why post an article to demonstrate the solvability of searching a graph of 4 nodes is somewhat perplexing. IMHO the optimal path search being an NPhard problem would have been better demonstrated by using very large state spaces because this would have demonstrated the challenges dealing with nondeterministically polynomial problems.
modified on Wednesday, July 22, 2009 6:14 PM





2
Write the program ETofSentences that performs the Transposition Encryption/Decryption of sentences
I. Entering Inputs
· The program will:
1 Prompt yo to enter the “length of perm tation” yo want to perform which means
the length of the key yo want to se
e g , P351624 is of length 6
2 Read and store the length of the key into a variable
· The program will:
3 Prompt yo to enter a text to code
4 Read and store the text into a variable
II. Building the Coding key
· The program will b ild the coding key by:
3 Creating an array of size eq al to the key ( = length of perm tation)
The key is b ilt by concatenating s ccessive random integers Î [ 1, key length ]
(considered by their seq ence of apparition)
Hint: Use Math random(), Math floor(), and type cast to generate s ccessive random
integers
e g to generate the key P351624, yo r program will s ccessively create:
1
st
random integer = 3
2
nd
random integer = 5
3
rd
random integer = 1
4
th
random integer = 6
5
th
random integer = 2
6
th
random integer = 4
These integers are transferred into the array previo sly created in q estion (II 3)
as soon as they are validated based on the following constraints :
Within a key, an integer is not allowed to appear twice (the 2
nd
occ rrence of
the same integer is discarded, and seek another random integer)
A s ite of three seq ential integers (forward or backward) is not allowed in
the same key (the last integer is discarded)
e g , 123 or 765 are not allowed
III. Building the Decoding key (reverse key)
The program will b ild the decoding key by:
4 Deriving that from the coding one
I wrote this, but not correct. I need help

using System;
using System.Text;
using System.Collections;
namespace ETofSentences
{
class ETofSentences
{
static void Main(string[] args)
{
//Part I: Entering inputs
//***************************
int lengthPermutation;
string encodedText;
Console.Write("Please enter the length of permutation(P): ");
lengthPermutation = Convert.ToInt32(Console.ReadLine());
Console.Write("Please enter the text to encode: ");
encodedText = Console.ReadLine();
//Part II: Building the Coding key
//***********************************
ArrayList encodeKey = new ArrayList();
Random random = new Random();
string permutation = null;
//int n = 0;
for (int i = 0; i < lengthPermutation; i++)
{
encodeKey.Add(Convert.ToString(Math.Floor(Convert.ToDouble(random.Next(1, lengthPermutation)))));
permutation += string.Concat(encodeKey[i]);
}
//testing
Console.WriteLine("permutation: " + permutation);
Console.ReadLine();
//Part III: Derive the decoding/reverse key
//*******************************************
string decodeKey = Reverse(permutation);
Console.WriteLine("Decode Key: " + decodeKey);
//Part IV: Encryption – Decryption of a simple sentence
//*****************************************************
char [] chartext = encodedText.ToCharArray();
string subtext = null;
// Console.WriteLine("First subtext part: " +
// encodedText.Substring(encodedText.IndexOf(chartext[0]), lengthPermutation));
int h = encodedText.Length % lengthPermutation;
int k = lengthPermutation  h;
while (k > 0)
{
encodedText = encodedText + " ";
k;
}
int z=0;
//Console.WriteLine("h: " + h);
//Console.WriteLine("text: " + encodedText);
// subtext = string.Concat(encodedText.Substring(0, lengthPermutation), " "
// , encodedText.Substring(lengthPermutation *1, lengthPermutation) , " " ,
// encodedText.Substring(lengthPermutation *2,lengthPermutation), " ");
while( z< encodedText.Length)
{
subtext += string.Concat(encodedText.Substring(z, lengthPermutation) , " ");
z= z+ lengthPermutation;
}
Console.WriteLine("subtext: " + subtext);
Console.ReadLine();
}
//Reverse the permutation/encoding key
static string Reverse(string permutation)
{
int length = permutation.Length;
char[] array = new char[length];
for (int i = 0; i < length; i++)
{
array[i] = permutation[length  1  i];
}
return new string(array);
}
//swap two array positions
static void Swap(char a, char b)
{
char temp = a;
a = b;
b = temp;
}
static int unique(ArrayList a, int n)
{
int i, k;
k = 0;
for (i = 1; i < n; i++)
{
if (a[k] != a[i])
{
a[k + 1] = a[i];
k++;
}
}
return (k + 1);
}
}
}





Hello
I have actual got this to work on Shape files, but now the speed is a problem
Do you have any ide how to speed up things?
I have an Intel Duo E7300 2.66GB computer. still is to slow.
arcs is about 150 000pcs
best regards
Krister





The mapping building process is slow for large maps.
It is because every time you add a node (an arc) into the graph, it will check whether it is already contained in the array list or not. This process is very timeconsuming.
As I am sure there is no redundant nodes (arcs) in my map data, I cut out the check processes. The improvement is as follows.
(1) In Graph.cs, add the following method.
public Node AddNodeWithNoChk(float x, float y, float z)
{
Node NewNode = new Node(x, y, z);
LN.Add(NewNode);
return NewNode;
}
public Arc AddArcWithNoChk(Node StartNode, Node EndNode, float Weight)
{
Arc NewArc = new Arc(StartNode, EndNode);
NewArc.Weight = Weight;
LA.Add(NewArc);
return AddArc(NewArc);
}
(2) In TestAStar, replace all AddNode() with AddNodeWithNoChk().
Node N1 = G.AddNodeWithNoChk(0,0,0);
Node N2 = G.AddNodeWithNoChk(5,0,0);
...
G.AddArcWithNoChk(N1,N2,1);
G.AddArcWithNoChk(N2,N3,1);
...
It will be faster at least four orders of magnitude for a map with 150000 nodes and arcs.
On my Core i3 2.13GHz computer, the time of mapping building is about 2 seconds and path planning is about 6 seconds. It is not fast enough.
modified on Sunday, July 10, 2011 11:30 AM





You know what algorithm uses Google in Google Map? May be similar to this...





how to input edges pair??





Hi,
Has anyone got a fast algorithm on optimizing a sheet(s) cut into pieces with miniumum wastage.
Something like the Cut2dx automation object in www.optimalprograms.com but I would like it for dot net in C# with code.
Thanks,
Bond Ridhoo





Somebody knows the type of license of A+??





It is listed in the source files:
What this means is:
 You can use the code in any projects you create, but must be provided free of charge
 The license itself is incompatible with the GPL, meaning that you cannot import the code into a GPL project
 The library itself is useable in GPL projects, provided it is linked verbatim (see above)





hi eric,
how can we contact you???





is it possible to find out the features of Character Recognition Task, using method this Method ?
any idea ?





Great article.
I implemented this same problem for an assignment in school years ago by calculating all the possible paths (based on whatever conditions and restricted by other conditions for speed) which I generated by going through all possible values generated by using various base x numbers, based on the number nodes. This was definitely fun programming.





is your solution able to grab node and acr information from any table???





It's been 10 years, would have to take a look. The project was for an assignment. Limited to 10 nodes (base 10, but could be any base) as it was just an assignment, but it could find every possible path, where (n^2n)/2 gives the number of possible interconnections between all nodes. The project was in MFC but below is some CRT code. This was a year out of high school so don't expect anything professional =) Though the instructor (Concorde engineer) definitely liked it. I think it was the maximum flow problem.
Not sure why this piece of crap editor takes out formatting.
#include<iostream.h>
#include<math.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
const unsigned long power10[10] = {1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000};
typedef enum BOOL {TRUE, FALSE};
typedef struct _NETWORK
{
unsigned char nodes; unsigned long arcFlow;
unsigned long arcFloworiginal;
} NETWORK;
double permutation(int,int);
double numPossiblePaths(char);
unsigned long padPath(unsigned long,char);
unsigned long convertBase(unsigned long, unsigned char);
double numPossiblePaths(char nodes)
{
double sum=0;
char i;
for (i=2; i<=(nodes2); i++)
sum += permutation(nodes2,i);
return (sum+nodes1); }
double permutation(int n, int k)
{
double sum=0;
int i;
if (k>n  n<2)
return 1; else
{
for (i=n; i>1; i)
sum += log(i);
for (i=(nk); i>1; i)
sum = log(i);
}
return exp(sum);
}
unsigned long padPath(unsigned long num, char nodes)
{
unsigned char ctr=10;
while ((num / power10[ctr]) == 0);
num = num + nodes * power10[ctr+1];
num = (num*10)+1;
return num;
}
unsigned long convertBase(unsigned long num, unsigned char numBase)
{
int ctr=0;
unsigned long convertedNum=0;
while (num!=0) {
convertedNum = convertedNum+((num % numBase) * power10[ctr]);
num /= numBase; ctr++; }
return convertedNum;
}
int main(void)
{
char nodes=6; unsigned long countTo=0, ctr,ctr2,ctr3,n,n2,n3, path, networkFlow=0, smallestArcCapacity; NETWORK network[34] = {1};
BOOL nodePath,validPath=TRUE;
network[0].nodes = 21;
network[0].arcFlow = 2;
network[1].nodes = 31;
network[1].arcFlow = 6;
network[2].nodes = 41;
network[2].arcFlow = 3;
network[3].nodes = 12;
network[3].arcFlow = 0;
network[4].nodes = 42;
network[4].arcFlow = 1;
network[5].nodes = 52;
network[5].arcFlow = 4;
network[6].nodes = 13;
network[6].arcFlow = 0;
network[7].nodes = 43;
network[7].arcFlow = 3;
network[8].nodes = 63;
network[8].arcFlow = 2;
network[9].nodes = 14;
network[9].arcFlow = 0;
network[10].nodes = 24;
network[10].arcFlow = 1;
network[11].nodes = 34;
network[11].arcFlow = 3;
network[12].nodes = 54;
network[12].arcFlow = 1;
network[13].nodes = 64;
network[13].arcFlow = 3;
network[14].nodes = 25;
network[14].arcFlow = 4;
network[15].nodes = 45;
network[15].arcFlow = 1;
network[16].nodes = 65;
network[16].arcFlow = 6;
network[17].nodes = 36;
network[17].arcFlow = 0;
network[18].nodes = 46;
network[18].arcFlow = 0;
network[19].nodes = 56;
network[19].arcFlow = 0;
countTo = (unsigned long) pow(nodes,nodes2);
for (ctr=1; ctr<countto; ctr++)
{
validPath = TRUE; n = path = convertBase(ctr, nodes);
do
{
n3 = n % 10; n2 = path; ctr2 = 0;
do
{
if ((n2%10)==n3) ctr2++; n2 /= 10; } while (n2!=0);
if (ctr2>1  (n%10)<=1)
validPath = FALSE;
n /= 10; } while (n!=0 && validPath!=FALSE);
path = padPath(path,nodes);
if (validPath==TRUE)
{
ctr2 = 0;
smallestArcCapacity = 255;
nodePath = TRUE;
while ((n=(path % power10[ctr2+2] / power10[ctr2]))>9 && (nodePath!=FALSE))
{
nodePath = FALSE;
for (ctr3=0; ctr3<20; ctr3++)
if ((n == network[ctr3].nodes) && (network[ctr3].arcFlow != 0))
{
nodePath = TRUE;
if (network[ctr3].arcFlow < smallestArcCapacity)
smallestArcCapacity = network[ctr3].arcFlow;
}
ctr2++; }
validPath = nodePath; }
if (validPath==TRUE)
{
ctr2 = 0;
while ((n=(path % power10[ctr2+2]) / power10[ctr2])>9)
{
ctr3 = 0;
while (n != network[ctr3++].nodes);
network[ctr31].arcFlow = smallestArcCapacity;
ctr3 = 0;
while ((((n%10)*10)+(n/10)) != network[ctr3++].nodes);
network[ctr31].arcFlow += smallestArcCapacity;
ctr2++; }
networkFlow += smallestArcCapacity; }
if (validPath==TRUE)
cout << path << " " << smallestArcCapacity << endl;
}
cout << networkFlow;
return 0;
}</stdlib.h></conio.h></stdio.h></math.h></iostream.h>





this thingie
//n>k
for (i=n; i>1; i)
sum += log(i); //n!
for (i=(nk); i>1; i)
sum = log(i); //(nk)!
equals
//n>k
for(i=n; i>nk; i)
sum+=log(i);





Please can I ask you questions?
How I can out put a 3Dgraph according to equation calcalations(Fitness function in Genetic Algorithm? I have already the equation and the program in C#? Can you please help me with C# language?? see "simpler genetic algorithm" in this web site.
Regards,
Salma Alnajim





hi there,
is it possible that this application grabbs data (lat/lon/distance) from mssql table WITHOUT pushing all map data at once to the graphformer???
(in this case the app needs to decide which nodes/paths (from table) needs to be grabbed...)
regards,
Murat KOCAN





Hello,
i`m trying to add more then 4 Nodes :
Graph G = new Graph();
Node N1 = G.AddNode(0,0,0);
Node N2 = G.AddNode(5,0,0);
Node N3 = G.AddNode(5,5,0);
Node N4 = G.AddNode(5,5,5);
G.AddArc(N1,N2,1);
G.AddArc(N2,N3,1);
G.AddArc(N3,N4,1);
G.AddArc(N1,N3,1);
eg of this :
Graph G = new Graph();
Node Start = G.AddNode(0,0,0);
G.AddNode(5,0,0);
G.AddNode(5,5,0);
Node Ziel = G.AddNode(5,5,5);
G.AddArc(new Node(0,0,0),new Node(5,0,0),1);
G.AddArc(new Node(5,0,0),new Node(5,5,0),1);
.
.
.
G.AddArc(new Node(5,5,0),new Node(5,5,5),1);
G.AddArc(new Node(0,0,0),new Node(5,5,0),1);
But it will not work.
The result is "no result found"
Can anyone help ?





Hi there,
I think I had the same problem. The application doesn't seem to realize that your nodes Start and Ziel are the same as those you added to the graph as start or end nodes of your arcs. It doesn't care that they have the same coordinates as they don't have the same designation.
As a consequence Start and Ziel are not seen as nodes which are connected by arcs, but as unconnected nodes. As you can only find a way between connected nodes you get the "no result found".
Try replacing the coordinates in the arc with your start and ziel nodes and always check the direction of the arcs.
G.AddArc(Start,new Node(5,0,0),1);
G.AddArc(new Node(5,0,0),new Node(5,5,0),1);
.
.
.
G.AddArc(new Node(5,5,0),Ziel,1);
G.AddArc(Start,new Node(5,5,0),1);
It was a longer time ago, when I worked with this algorithm so the syntax might not be the best, but I think this should work.
good luck and greetinx from Osnabrück
Maddix





Hello,
i understand what you mean, but i think it will not work.
This :
G.AddArc(new Node(5,0,0),new Node(5,5,0),1);
Adds 2 Nodes, but the nodes are not connected to any other Nodes !!
The only one way is
Node N1 = G.AddNode(0,0,0)
Node N2 = G.AddNode(0,0,1)
.
.
and then it is possible to add Arcs between the Nodes """INSIDE THE GRAPH """
G.AddArc(N1, N2,0);
.
.
then you can find a way from N1 to Nx
Matthias





Eric,
Thanks for a very useful, wellwritten, welldocumented chunk of code!
Eduardo S.





How can I run the graphformer.exe because when I unzip it to C drive I try to run it and give me en error.
Do I have to have C# installed





Dear "cacu" to run that .exe application You shold download from www.microsoft.com .Net Framework 2.0 from Here[^]





hi ZenyukIV,
thanks for your reply
how can i use this code in visual C++ ?
regards,
Carl





I can't belive it took me this long to run across this. Wow, bravo!
Gatsby





Hello Erwin:
Your application is very useful and powerful, but I think that something is required: I don't known if it is possible to draw the graph given a table. In other words, if he user inputs a table with the start and end nodes with the specified weigth, so:
start\end 1 km 2 km 3 km
n0 n1 n2 n3
n1 n2 n4 n5
well, etc.
and the aplication could draw a nice graph?
Think about this.
Andrés A





i have VC# Express and i cant compile it.
It tries to convert it and well basically. I doesnt work.
Is there anything i can add/change?
thanks





mr. Eric Marchesin,
i personally feels that u r the man who help me out from my final submission project which r help this month on 30th october, so could u please let me know or arranged some project with sourcecoding in c# or vb.net (for compiler construction & artificial intelligence related projects) , i'll very pleased to get from u ...thnks
i am student of mcs. from pakistan, and my name is AHMED ASIF UDDIN;)





Hi Asif
what the hell are you asking about.
being a mcs student you are not suppose to eat ready stuff's.
it was just Ridiculous
azam's





hi Eric,
do u have A* algorithm implementation in C or C++?
its really urgent for me.
kindly help...
looking forward 2 ur reply.
rupalini





Yeah i have converted this article in c++.





Hi. It's a nice work.
Is it possible to use this algorithm for following task:
I have an array of Points(x,y) and I need to go through EACH Point in the shortest path. I can't skip any point.
Thank's a lot.





That's exactly what my "solution" does, posted under cplas. Though it's limited to 10 nodes, it was just an assignment. I've got a MFC project too if you like.





I am trying to change the code in your TestAStar.cs file of your implementation of the A* alogrithm. I am having trouble, so I thought i would ask if you could help. The following code is what I replaced your code with.
Node TempN1, TempN2;
for (int i = 0; i < locList.Count; i++)
{
TempN1 = G.AddNode(i,i,0);
}
for (int i = 0; i < heurLoc1.Count; i++)
{
N1 = locList.IndexOf(heurLoc1[i]);
N2 = locList.IndexOf(heurLoc2[i]);
TempN1 = new Node(N1, N1, 0);
G.AddNode(TempN1);
TempN2 = new Node(N2, N2, 0);
G.AddNode(TempN2);
G.Add2Arcs(TempN1, TempN2, i);
}
NDepart = new Node(0,0,0);
NArrivee = new Node(5, 5, 0);
Console.WriteLine(ListNodesAndArcs(G));
//Console.WriteLine(" Best path to reach "+N4.ToString()+" from "+N1.ToString()+" :");
Console.WriteLine();
AStar AS = new AStar(G);
if (AS.SearchPath(NDepart, NArrivee))
foreach (Arc A in AS.PathByArcs) Console.WriteLine(A.ToString());
else Console.WriteLine("No result !");
The following is the results I get.
Description of the Graph:
Nodes> {0;0;0}; {1;1;0}; {2;2;0}; {3;3;0}; {4;4;0}; {5;5;0};
Arcs> {1;1;0}>{0;0;0}; {0;0;0}>{1;1;0}; {1;1;0}>{5;5;0}; {5;5;0}
>{1;1;0}; {2;2;0}>{0;0;0}; {0;0;0}>{2;2;0}; {2;2;0}>{1;1;0}; {1;1;0}>{2;
2;0}; {2;2;0}>{5;5;0}; {5;5;0}>{2;2;0}; {3;3;0}>{0;0;0}; {0;0;0}>{3;3;0}
; {3;3;0}>{1;1;0}; {1;1;0}>{3;3;0}; {3;3;0}>{2;2;0}; {2;2;0}>{3;3;0}; {3
;3;0}>{5;5;0}; {5;5;0}>{3;3;0}; {4;4;0}>{0;0;0}; {0;0;0}>{4;4;0}; {4;4;0
}>{1;1;0}; {1;1;0}>{4;4;0}; {4;4;0}>{2;2;0}; {2;2;0}>{4;4;0}; {4;4;0}>
{3;3;0}; {3;3;0}>{4;4;0}; {4;4;0}>{5;5;0}; {5;5;0}>{4;4;0}; {0;0;0}>{5;5
;0}; {5;5;0}>{0;0;0};
No result !
I don't understand why I am getting "No result!"
The last line of the Arcs shows that there is a path between:
NDepart(0,0,0) and NArrivee(5, 5, 0)
Thanks,
Dusty





Hi,
I think you must use the Nodes from the graph to search for path. Because the new nodes that you are passing to the search do not have any arcs associated.
< RickSP >
Join to the best... Join to C++ developers





Dear Mr Eric,
In your article, you've mentioned that:
"The min value (in fact 0) means that only the heuristic will be used. On the contrary, the max value (in fact 1) means that the search will behave in accordance with the Dijkstra algorithm."
However, in the comments of your code (Astar.cs), you wrote:
This value must belong to [0; 1] and it determines the influence of the heuristic on the algorithm.
/// If this influence value is set to 0, then the search will behave in accordance with the Dijkstra algorithm.
/// If this value is set to 1, then the cost to come to the current node will not be used whereas only the heuristic will be taken into account.
Moreover, another explanation is found in track.cs:
> 0 will minimize the number of nodes explored but will not take the real cost into account.
> 0.5 will minimize the cost without developing more nodes than necessary.
> 1 will only consider the real cost without estimating the remaining cost.");
They made me confused. Therefore, can you please clarify whether 0 indicates a Dijkstra or a pure Heuristics? Thanks.





Good work done Eric! Lovely piece of code.
You developed for presentation but did you include any interface or class afterwards for data binding as a ADO.NET connection for using any data set to represent as graph?
Thanks,
Fatih





You don't need the closed list. And even if you keep it you should never update elements in the closed list. Unless ...
You accept negative costs in witch case none of this algorithms works
Juan Uribe
jcuglo@hotmail.com





Nice way of depicting the 'classic' shortestpath algorithm
Cheers,
Rohit Wason





hi
i want to know about graphical algorithm (arcs)
and how can i draw it by c#
thanks





Hi!
I have a problem. Can anyone help me?
In C# programming I understand any code in part "Class" but I can't write a program with "Class".
Thanks!







General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

First Posted  23 Jun 2003 
Views  411,912 
Bookmarked  345 times 

