It's not quite on topic, but let me ask you smart guys;
This is the data:
A -> B
B -> C
C -> D
E -> C
A -> E
B -> A
C -> B
C -> A
A -> C
You see, if you wish to go from A to D you can go:
(1) A->B->C->D
(2) A->C->D
(3) many others involving cycles like A->C->B->A->C->D and so forth...
In any case, I have this system in MySQL:
{PrimKey, X, Y} where PrimKey is an integer, X and Y are the node values. For example A->B is {1, A, B}, then B->C becomes {2, B, C} and so forth.
This is graph theory, traversal of graphs but considering there are cycles this makes it a bit tricky.
I have to make a class i.e. "Map" to help me keep order of who comes and goes to who. This way if I want to go from A to D I can return a list where I get various paths leading to D without the backtracking (A->C->B->A->C->D e.g.) and it shouldn't stuck looping indefinitely.
Do you have some ideas how I should structure this class?
I was thinking something along the lines of:
class Map {
nodes = array();
addNode(node) {
addChild(getParent(node::letter), node) // find A in nodes then add this node as that parents child, if not then add the child as a new root-node with node::letter as index key
}
getRoutes(start, end) {
// traverse the nodes, find any paths starting at start and ending at end, paths not leading to the end are ignored, this I reckon will be a recursive function
}
}
Very rough, maybe someone has a better idea or a tip like example code they know of on the net. :P
|