Add your own alternative version
Stats
452.7K views 6.9K downloads 355 bookmarked
Posted
23 Jun 2003

Comments and Discussions



My personal thoughts are as follows. The license seems to cover the sourcecode form only (as it states), but not the resulting binaryform product. In other words, you can't sell the sources without the permission from the author, but you can sell the compiled endproduct. I'm going to try contacting the author to clarify the terms for commercial usage.





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++)<br="" mode="hold" /> {
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>





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.







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

