Add your own alternative version
Stats
460.9K views 7.2K downloads 359 bookmarked
Posted
23 Jun 2003

Comments and Discussions



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.
<br />
#include<iostream.h><br />
#include<math.h><br />
#include<stdio.h><br />
#include<conio.h><br />
#include<stdlib.h><br />
<br />
// these constants save calculation time<br />
const unsigned long power10[10] = {1,10,100,1000,10000,100000,1000000,<br />
10000000,100000000,1000000000};<br />
<br />
// define a Boolean type<br />
typedef enum BOOL {TRUE, FALSE};<br />
<br />
typedef struct _NETWORK<br />
{<br />
unsigned char nodes; // the 2 connected nodes<br />
unsigned long arcFlow;<br />
unsigned long arcFloworiginal;<br />
} NETWORK;<br />
<br />
// function prototypes<br />
double permutation(int,int);<br />
double numPossiblePaths(char);<br />
unsigned long padPath(unsigned long,char);<br />
unsigned long convertBase(unsigned long, unsigned char);<br />
<br />
/*<br />
* This function returns the number of possible paths using<br />
* permmutation, not including restrictions posed on arcs and nodes<br />
*<br />
**/<br />
double numPossiblePaths(char nodes)<br />
{<br />
double sum=0;<br />
char i;<br />
<br />
for (i=2; i<=(nodes2); i++)<br />
sum += permutation(nodes2,i);<br />
<br />
// nP0 and nP1 are always 1 and n, so save time by doing this<br />
return (sum+nodes1); // or 1+(nodes2), whatever<br />
}<br />
<br />
/*<br />
* This function returns nPk (permmutation)<br />
*<br />
**/<br />
double permutation(int n, int k)<br />
{<br />
double sum=0;<br />
int i;<br />
<br />
if (k>n  n<2)<br />
return 1; // return with error if k>n<br />
else<br />
{<br />
// do n!<br />
for (i=n; i>1; i)<br />
sum += log(i);<br />
// do (nk)!<br />
for (i=(nk); i>1; i)<br />
sum = log(i);<br />
}<br />
// return nPk<br />
return exp(sum);<br />
}<br />
<br />
/*<br />
* This function pads a path with the start and end nodes<br />
*<br />
**/<br />
unsigned long padPath(unsigned long num, char nodes)<br />
{<br />
unsigned char ctr=10;<br />
<br />
while ((num / power10[ctr]) == 0);<br />
<br />
num = num + nodes * power10[ctr+1];<br />
num = (num*10)+1;<br />
<br />
return num;<br />
}<br />
<br />
/*<br />
* This function takes in a decimal number and a base to convert it to<br />
*<br />
**/<br />
unsigned long convertBase(unsigned long num, unsigned char numBase)<br />
{<br />
int ctr=0;<br />
unsigned long convertedNum=0;<br />
<br />
while (num!=0) // dont bother converting when quotient is 0<br />
{<br />
convertedNum = convertedNum+((num % numBase) * power10[ctr]);<br />
num /= numBase; // go down 1 digit in old base<br />
ctr++; // go up 1 digit in new base<br />
}<br />
<br />
return convertedNum;<br />
}<br />
<br />
/*==========================================================*/<br />
int main(void)<br />
{<br />
char nodes=6; // number of nodes in network<br />
unsigned long countTo=0, // number to count in decimal<br />
ctr,ctr2,ctr3,n,n2,n3, // general counters and holders<br />
path, // a path<br />
networkFlow=0, // initlally network flow is 0<br />
smallestArcCapacity; // Duh.<br />
NETWORK network[34] = {1}; // holds network information<br />
<br />
// this value changes along the process<br />
BOOL nodePath,validPath=TRUE; // of path selection, and determines whether<br />
<br />
// a path makes it into the path array.<br />
network[0].nodes = 21;<br />
network[0].arcFlow = 2;<br />
network[1].nodes = 31;<br />
network[1].arcFlow = 6;<br />
network[2].nodes = 41;<br />
network[2].arcFlow = 3;<br />
network[3].nodes = 12;<br />
network[3].arcFlow = 0;<br />
network[4].nodes = 42;<br />
network[4].arcFlow = 1;<br />
network[5].nodes = 52;<br />
network[5].arcFlow = 4;<br />
network[6].nodes = 13;<br />
network[6].arcFlow = 0;<br />
network[7].nodes = 43;<br />
network[7].arcFlow = 3;<br />
network[8].nodes = 63;<br />
network[8].arcFlow = 2;<br />
network[9].nodes = 14;<br />
network[9].arcFlow = 0;<br />
network[10].nodes = 24;<br />
network[10].arcFlow = 1;<br />
network[11].nodes = 34;<br />
network[11].arcFlow = 3;<br />
network[12].nodes = 54;<br />
network[12].arcFlow = 1;<br />
network[13].nodes = 64;<br />
network[13].arcFlow = 3;<br />
network[14].nodes = 25;<br />
network[14].arcFlow = 4;<br />
network[15].nodes = 45;<br />
network[15].arcFlow = 1;<br />
network[16].nodes = 65;<br />
network[16].arcFlow = 6;<br />
network[17].nodes = 36;<br />
network[17].arcFlow = 0;<br />
network[18].nodes = 46;<br />
network[18].arcFlow = 0;<br />
network[19].nodes = 56;<br />
network[19].arcFlow = 0;<br />
<br />
<br />
<br />
// get the number to count to<br />
countTo = (unsigned long) pow(nodes,nodes2);<br />
<br />
// start the path building<br />
for (ctr=1; ctr<countto; ctr++)<br="" mode="hold" /> {<br />
validPath = TRUE; // path is valid so far<br />
// convert number to path by converting to base NODES number<br />
n = path = convertBase(ctr, nodes); // n is temp var<br />
<br />
do<br />
{<br />
n3 = n % 10; // number that is checked for doubles<br />
n2 = path; // whole path is checked each time<br />
ctr2 = 0; // used to count doubles, none yet<br />
<br />
do<br />
{<br />
if ((n2%10)==n3) // if digit = number we're looking for,<br />
ctr2++; // found double, so increment<br />
n2 /= 10; // go down 1 digit<br />
} while (n2!=0);<br />
<br />
// check if there were doubles and if number is less then 2<br />
if (ctr2>1  (n%10)<=1)<br />
validPath = FALSE;<br />
n /= 10; // go down 1 digit<br />
} while (n!=0 && validPath!=FALSE); // stop converting when quotient is 0<br />
<br />
// add the start and end nodes to path. e.g. if path is 423 and<br />
// there are 6 nodes, the path becomes 64231<br />
path = padPath(path,nodes);<br />
<br />
// check if path is proper by checking the restrictions given<br />
// by the user<br />
if (validPath==TRUE)<br />
{<br />
ctr2 = 0;<br />
smallestArcCapacity = 255;<br />
nodePath = TRUE; // variable used to check path at each node<br />
<br />
while ((n=(path % power10[ctr2+2] / power10[ctr2]))>9 && (nodePath!=FALSE))<br />
{<br />
nodePath = FALSE; // check each path with the information<br />
<br />
for (ctr3=0; ctr3<20; ctr3++) // given by user<br />
<br />
// check if nodes correct and arc flow capacity>0<br />
if ((n == network[ctr3].nodes) && (network[ctr3].arcFlow != 0))<br />
{<br />
nodePath = TRUE; // in the noetwork array, path is bad<br />
<br />
if (network[ctr3].arcFlow < smallestArcCapacity)<br />
smallestArcCapacity = network[ctr3].arcFlow;<br />
}<br />
ctr2++; // as soon as path is know to be bad, loop quits<br />
}<br />
validPath = nodePath; // result of path , bad or good<br />
}<br />
<br />
// if path is valid, decrease all flows on path by smallestArcFlow<br />
// and increase in oppositte direction<br />
if (validPath==TRUE)<br />
{<br />
ctr2 = 0;<br />
<br />
while ((n=(path % power10[ctr2+2]) / power10[ctr2])>9)<br />
{<br />
ctr3 = 0;<br />
<br />
while (n != network[ctr3++].nodes);<br />
network[ctr31].arcFlow = smallestArcCapacity;<br />
<br />
ctr3 = 0;<br />
<br />
while ((((n%10)*10)+(n/10)) != network[ctr3++].nodes);<br />
network[ctr31].arcFlow += smallestArcCapacity;<br />
ctr2++; // as soon as path is know to be bad, loop quits<br />
}<br />
networkFlow += smallestArcCapacity; // Duh.<br />
}<br />
<br />
if (validPath==TRUE)<br />
cout << path << " " << smallestArcCapacity << endl;<br />
}<br />
cout << networkFlow;<br />
return 0;<br />
}</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 :
<br />
Graph G = new Graph();<br />
Node N1 = G.AddNode(0,0,0);<br />
Node N2 = G.AddNode(5,0,0);<br />
Node N3 = G.AddNode(5,5,0);<br />
Node N4 = G.AddNode(5,5,5);<br />
G.AddArc(N1,N2,1);<br />
G.AddArc(N2,N3,1);<br />
G.AddArc(N3,N4,1);<br />
G.AddArc(N1,N3,1);<br />
eg of this :
<br />
Graph G = new Graph();<br />
Node Start = G.AddNode(0,0,0);<br />
G.AddNode(5,0,0);<br />
G.AddNode(5,5,0);<br />
Node Ziel = G.AddNode(5,5,5);<br />
<br />
G.AddArc(new Node(0,0,0),new Node(5,0,0),1);<br />
G.AddArc(new Node(5,0,0),new Node(5,5,0),1);<br />
.<br />
.<br />
.<br />
G.AddArc(new Node(5,5,0),new Node(5,5,5),1);<br />
G.AddArc(new Node(0,0,0),new Node(5,5,0),1);<br />
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







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.

