Introduction: what is it supposed to do ?
I dedicated myself to creating a .NET component that allows the building of graphs and the performance of some operations on these structures. In particular A*, the famous path finding algorithm, can be run to find the best path between two places.
First and foremost it should be kept in mind that a graph is defined with :
- A list of nodes
- A list of arcs
Each node is defined with the following data :
- A geographical position in space (co-ordinates X,Y,Z)
- The collection of the outgoing arcs
- The collection of the incoming arcs
Each arc is simply defined with its two extremity nodes. So an arc is oriented from StartNode to EndNode. It is also characterized by a crossing factor named 'Weight'. This value represents the difficulty to reach the ending node from the starting one. Thus, getting through an arc has a cost, which can be basically calculated like this :
Cost = Distance(StartNode, EndNode) * Weight
You may be asking "What is the use of this structure ?...". Well, the applications can be various, ranging from road maps and circulation models to a character's mobility in a video game. Now the question is: "How one would move across this graph ?".
What is A* ?
Imagine that you are on a node and that you want to reach another position somewhere else on the graph. Then ask : "Which way will I follow, and why ?". The main factor to take into account here is the cost of moving. It must be minimal. The cost criterion is basically a function of the distance (sum of arcs' lengths). However, it can also be adjusted and varied with other data, which describe for example the slope, the harshness/practicability of the ground. You can even model a traffic jam.
To achieve the best path, there are many algorithms which are more or less effective, depending on the particular case. Efficiency depends not only on the time needed for calculation, but also on the reliability of the result. A* is able to return the best path (if it exists) between two nodes, according to accessibility/orientation and, of course, cost of arcs.
Among the variety of existing algorithms, some do not always actually return the best path, but they can give precedence to speed over accuracy. Efficiency depends on the number of nodes and on their geographical distribution. However in most cases A* turns out to be the most effective, because it combines optimized search with the use of a heuristic.
A heuristic is a function that associates a value with a node to gauge it. One node is considered better than another, if the final point is reached with less effort (e.g. shorter distance).
A* will always return the shortest path if, and only if, the heuristic is admissible; that is to say, if it never overestimates. On the other hand, if the heuristic is not admissible, A* will find a path in less time and with less memory usage, but without the absolute guaranty that it is the best one. Here are three admissible heuristics which correspond to a particular distance between the node of evaluation and the target node :
- Euclidean distance > Sqrt(Dx�+Dy�+Dz�)
- Manhattan distance > |Dx|+|Dy|+|Dz|
- Maximum distance > Max(|Dx|, |Dy|, |Dz|)
These functions give an estimation of the remaining distance for each node that can be explored. Thus the search can be oriented toward the 'best' nodes. For a given node, the sum [Current cost + Heuristic value] is an estimation of the cost of reaching the ending node from the starting node, passing by the current one. This value is used to continuously choose the most promising path.
In practice, the algorithm maintains 2 lists of nodes that are filled and modified during the search :
- The first one, called
Open, contains the tracks leading to nodes that can be explored. Initially, there is only the starting node. At each step, the best node of Open is taken out. Then, the best successor of this node (according to the heuristic) is added to the list as a new track. One doesn't know where the nodes that are in Open lead, because they have not been propagated yet. However, the best one is examined at each new step.
- The second one, called
Closed, stores the tracks leading to nodes that have already been explored.
The program is based on a recursive model. The loop is performed as long as Open still contains some elements. See the code for details (written with C#, it is sufficient enough to be self explainable).
public bool SearchPath(Node StartNode, Node EndNode)
{
lock (_Graph)
{
Initialize(StartNode, EndNode);
while ( NextStep() ) {}
return PathFound;
}
}
Using the code: public interfaces of the component
The Graph class gathers a set of methods to manage its data, such as :
- Add/Suppress a node/arc
- Get the nearest/farthest node/arc from a point
- Activate/Inactivate the entire graph
- Empty the graph
From a more practical point of view, here are the methods and properties you can use for the main classes and objects :
public class Graph
{
public Graph()
public IList Nodes { get }
public IList Arcs { get }
public void Clear()
public bool AddNode(Node NewNode)
public Node AddNode(float x, float y, float z)
public bool AddArc(Arc NewArc)
public Arc AddArc(Node StartNode, Node EndNode, float Weight)
public void Add2Arcs(Node Node1, Node Node2, float Weight)
public bool RemoveNode(Node NodeToRemove)
public bool RemoveArc(Arc ArcToRemove)
public void BoundingBox(out double[] MinPt, out double[] MaxPt)
public Node ClosestNode(double X, double Y, double Z, out double Dist,
bool IgnoreFreeWay)
public Arc ClosestArc(double X, double Y, double Z, out double Dist,
bool IgnoreFreeWay)
}
public class Node
{
public Node(double PositionX, double PositionY, double PositionZ)
public IList IncomingArcs { get }
public IList OutgoingArcs { get }
public double X { get }
public double Y { get }
public double Z { get }
public void ChangeXYZ(double PositionX, double PositionY,
double PositionZ)
public bool Passable { get/set }
public Node[] AccessibleNodes { get }
public Node[] AccessingNodes { get }
public void UntieIncomingArcs()
public void UntieOutgoingArcs()
public void Isolate()
public Arc ArcGoingTo(Node N)
public Arc ArcComingFrom(Node N)
public object Clone()
public static void BoundingBox(IList NodesGroup, out double[] MinPt,
out double[] MaxPt)
public static double EuclidianDistance(Node N1, Node N2)
public static double SquareEuclidianDistance(Node N1, Node N2)
public static double ManhattanDistance(Node N1, Node N2)
public static double MaxDistanceAlongAxis(Node N1, Node N2)
public override string ToString()
public override bool Equals(object O)
public override int GetHashCode()
}
public class Arc
{
public Arc(Node Start, Node End)
public Node StartNode { get/set }
public Node EndNode { get/set }
public double Weight { get/set }
public bool Passable { get/set }
virtual public double Cost { get }
public double Length { get }
virtual protected double CalculateLength()
public override string ToString()
public override bool Equals(object O)
public override int GetHashCode()
}
public class AStar
{
public AStar(Graph G)
public bool SearchPath(Node StartNode, Node EndNode)
public void Initialize(Node StartNode, Node EndNode)
public bool NextStep()
public bool Initialized { get }
public int StepCounter { get }
public bool SearchStarted { get }
public bool SearchEnded { get }
public bool PathFound { get }
public Node[] PathByNodes { get }
public Arc[] PathByArcs { get }
public bool ResultInformation(out int NbArcsOfPath, out double CostOfPath)
public double DijkstraHeuristicBalance { get/set }
public Heuristic ChoosenHeuristic { get/set }
public static Heuristic EuclidianHeuristic { get }
public static Heuristic MaxAlongAxisHeuristic { get }
public static Heuristic ManhattanHeuristic { get }
}
Nodes and arcs can be Passable or not. Selecting one of these two states for a node, propagates the same state to outgoing and incoming arcs. Likewise, destroying a node implies the destruction of all the directly linked arcs. In addition, an arc must always be linked to two nodes, whereas a node can be isolated.
Note that these data override Object.ToString() as well as Object.Equals(Object O). Moreover they can be serialized.
Simple example of the usage with the console application
using System;
using System.Collections;
using System.Text;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using EMK.Cartography;
namespace EMK.Tests
{
public class TestAStar
{
public static void Main()
{
try
{
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);
Console.WriteLine( ListNodesAndArcs(G) );
Console.WriteLine("Best path to reach "+N4+" from "+N1+" :");
AStar AS = new AStar(G);
if ( AS.SearchPath(N1, N4) )
foreach (Arc A in AS.PathByArcs)
Console.WriteLine( A.ToString() );
else Console.WriteLine( "No result !" );
Console.Write("Serialize and Deserialize. ");
Stream StreamWrite = File.Create("GraphSaved.bin");
BinaryFormatter BinaryWrite = new BinaryFormatter();
BinaryWrite.Serialize(StreamWrite, G);
StreamWrite.Close();
Stream StreamRead = File.OpenRead("GraphSaved.bin");
BinaryFormatter BinaryRead = new BinaryFormatter();
Graph G2 = (Graph) BinaryRead.Deserialize(StreamRead);
StreamRead.Close();
Console.WriteLine( ListNodesAndArcs(G2) );
}
catch(Exception e)
{
Console.Write( "Error :\n\n"+e.ToString() );
}
}
static private string ListNodesAndArcs(Graph GraphToDescribe)
{
StringBuilder SB = new
StringBuilder("Description of the Graph:\n\tNodes> ");
foreach (Node N in GraphToDescribe.Nodes)
SB.Append( N.ToString()+"; " );
SB.Append("\n\tArcs> ");
foreach (Arc A in GraphToDescribe.Arcs)
SB.Append( A.ToString()+"; " );
return SB.ToString();
}
}
}Description of the Graph:
Nodes> {0;0;0}; {5;0;0}; {5;5;0}; {5;5;5}
Arcs> {0;0;0}-->{5;0;0}; {5;0;0}-->{5;5;0};
{5;5;0}-->{5;5;5}; {0;0;0}-->{5;5;0}
Best path to reach {5;5;5} from {0;0;0} :
{0;0;0}-->{5;5;0}
{5;5;0}-->{5;5;5}
Serialize and Deserialize. Description of the Graph:
Nodes> {0;0;0}; {5;0;0}; {5;5;0}; {5;5;5}
Arcs> {0;0;0}-->{5;0;0}; {5;0;0}-->{5;5;0};
{5;5;0}-->{5;5;5}; {0;0;0}-->{5;5;0}
Example of use in a graphical environment
The graphical interface aims at bringing the component into play so as to reflect, fairly and simply, what it can do. The application lets you draw, move, erase or inactivate several nodes and arcs. When your graph is complete you just have to click on the 'A*' icon and select the starting and ending nodes with the respective left and right mouse buttons. Then you will automatically see the best way. If you modify the graph, this path will be updated.
If you want to visualize the algorithm's logic, then select the 'Step by Step' mode in the sub-menu of the 'A*' icon. The idea is to give the user a clear view of what happens.
In the option panel ('?' icon), you can change the heuristic and set its influence. 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.
Remarks
The program has been validated with a series of adapted tests, gathering various scenarios and interactions. Nevertheless it does not aim to be a perfect application, but an unassuming program that modestly claims to be simple and ergonomic. For information, I had already done this work with C++ for the DLL as well as MFC for the 2D graphical interface. I had also tested it in a 3D context with an OpenGL graphical interface. The next step will be to implement the 3D interface with Direct3D 9.0 for .NET or with one of the OpenGL solutions for this framework.
The source code contains a light but interesting implementation of geometrical tools such as Point3D and Vector3D. They were needed for graphical interactions in the GraphFormer example application (projections on lines, vectors' operations, etc...).
For convenience and performance I used the SortableList type for Closed and Open lists. The advantage is that, the best track will always be the first element, since the list remains sorted (cf the article I have written formerly about Automatic Sorted List). Nonetheless it would be very easy to replace it with another list type, such as ArrayList, provided you look for the 'best' element (that is to say the lower) at each step.
History
- June the 22nd, 2003 : Translation of the library code and comments from French to English.
- June the 24th, 2003 : Article submission.
- June the 26th, 2003 : No more Flickering thanks to DoubleBuffer Panel style.
|
|
 |
 | How to set and display labels for nodes and arcs?
pluto.plutone | 4:30 23 Jul '09 |
|
|
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!
|
|
|
|
|
| Somewhat naive...
petervn | 13:07 22 Jul '09 |
|
|
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 off-line searches A* algorithm belongs to? The subject of informed off-line 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 NP-hard problem would have been better demonstrated by using very large state spaces because this would have demonstrated the challenges dealing with non-deterministically polynomial problems.
modified on Wednesday, July 22, 2009 6:14 PM
|
|
|
|
|
 | Need help on C# Programming,
nosa oko | 22:26 21 Nov '08 |
|
|
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);
}
}
}
|
|
|
|
|
| Faster
Kilpo | 20:14 21 Oct '08 |
|
|
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
|
|
|
|
|
| Well done
Fco. Javier Marin | 16:13 20 Oct '08 |
|
|
You know what algorithm uses Google in Google Map? May be similar to this...
|
|
|
|
|
| how to input edges pair??
farhancrazy | 8:14 5 Sep '08 |
|
|
how to input edges pair??
|
|
|
|
|
| 2D Cut optimization software
Member 3693033 | 12:12 9 May '08 |
|
|
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
|
|
|
|
|
| license type
Rul | 1:46 5 Mar '08 |
|
|
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)
|
|
|
|
|
| eric marchesin, are you dead???
murathankocan | 8:06 2 Mar '08 |
|
|
hi eric,
how can we contact you???
|
|
|
|
|
| is it possible, for OCR?
reymond | 15:51 18 Jan '08 |
|
|
is it possible to find out the features of Character Recognition Task, using method this Method ?
any idea ?
|
|
|
|
|
| Another method...
cplas | 20:56 7 Jan '08 |
|
|
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.
|
|
|
|
|
| Re: Another method...
murathankocan | 23:00 11 Jan '08 |
|
|
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^2-n)/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
#include
#include
#include
#include
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<=(nodes-2); i++)
sum += permutation(nodes-2,i);
return (sum+nodes-1); }
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=(n-k); 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,nodes-2);
for (ctr=1; ctr"" 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[ctr3-1].arcFlow -= smallestArcCapacity;
ctr3 = 0;
while ((((n%10)*10)+(n/10)) != network[ctr3++].nodes);
network[ctr3-1].arcFlow += smallestArcCapacity;
ctr2++; }
networkFlow += smallestArcCapacity; }
if (validPath==TRUE)
cout << path << " " << smallestArcCapacity << endl;
}
cout << networkFlow;
return 0;
}
|
|
|
|
|
|
|
this thingie
//n>k
for (i=n; i>1; i--)
sum += log(i); //n!
for (i=(n-k); i>1; i--)
sum -= log(i); //(n-k)!
equals
//n>k
for(i=n; i>n-k; --i)
sum+=log(i); 
|
|
|
|
|
| Please help me for Senoir Project
SalmaAlnajim | 9:04 7 Jan '08 |
|
|
Please can I ask you questions?
How I can out put a 3D-graph 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
|
|
|
|
|
| grabbing data from sql table
murathankocan | 22:59 4 Jan '08 |
|
|
hi there,
is it possible that this application grabbs data (lat/lon/distance) from ms-sql 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
|
|
|
|
|
| Adding more then 4 Nodes ?
STF-DIR | 19:54 26 Dec '07 |
|
|
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
|
|
|
|
|
| Great code!
eduardosl | 13:56 11 Dec '07 |
|
|
Eric,
Thanks for a very useful, well-written, well-documented chunk of code!
-Eduardo S.
|
|
|
|
|
| question
cacu | 8:10 20 Aug '07 |
|
|
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
|
|
|
|
|
| Bravo
Jay Gatsby | 14:24 18 Aug '07 |
|
|
I can't belive it took me this long to run across this. Wow, bravo!
-Gatsby
|
|
|
|
|
|
|
Last Updated 24 Jun 2003 |
Advertise |
Privacy |
Terms of Use |
Copyright ©
CodeProject, 1999-2010
