About path finding(in Graphs)..

**manasij7479** · 11-08-2011

I studied Dijkstra's algorithm...but It seems a bit overkill (And if I'm not mistaken...somewhat inefficient) for what I have in mind.

I'm trying(well..tried a long time ago...and revisiting it now) to do a sort of network simulation and this is for the routing part.

If I can have the different 'devices' in the network running concurrently...but being able to send messages to only those to which it is connected by a wire...thus an edge; would the following simple algorithm be a good idea?

(Say...I have a structure 'path' that notes the address of the machine it is passed to into an array....and has a record of the destination(so that it knows when to stop))
The sender send out(broadcasts) such structures, and when the destination node gets it, it returns the traveler to the sender through the path recorded in it.
Whoever returns to the sender first is the winner. (A few other paths are noted ...so they can be used if the best one fails.)

The only problem I see with this is the wastage of bandwidth...
But that may not be a problem because breaking up the IP into 4(or 6) parts reduces the no. of unused broadcasts.
Also...This should be able to return a winner as fast as it takes to traverse the shortest path (x2 ). (...which, to my knowledge is better than the small no. of algorithms I read about)

Any suggestions ? advice ? or debunking ?

**anduril462** · 11-08-2011

It sounds like you're after something similar to traceroute. The Wikipedia page explains the concept fairly simply, and the utility is open source. Note that such techniques are not used in general for routing purposes on the internet. Some serious oversimplification of graph algorithms and how the internet works follows:

You wont find anything that runs in, say O(V) time or anything (where V is the number of vertexes). All optimal path algorithms are fairly inefficient due to the nature of graphs. For a graph G with V vertexes, the number of potential edges E is on the order of V^V, so even if you tweak Dijkstra's algorithm to run in O(|E| log |V|), you're still looking at a fairly costly algorithm.

I think the problem is with your general approach of trying to establish the fastest link(s) from point A to point B. The internet generally don't keep route statistics for individual routes from point A to point Z. Instead, each router/gateway keeps a list of which subnets exist on which ports, effectively only caring about routes for groups of IP addresses and only to it's immediate neighbors. It leaves it up to those neighbors to worry about the fastest way to all of their neighbors, etc. There are complex mechanisms for establishing and learning routes, and adapting to when nodes fall off line. Reading the Wikipedia articles on Border Gateway Protocol and Interior Gateway Protocol, and some of the pages they link to may shed some light on the subject.

Perhaps a clearer explanation of what exactly you're trying to achieve here will help me help you find a good solution.

**manasij7479** · 11-08-2011

It sounds like you're after something similar to traceroute.

Possibly yes.
I though that (response) time is a better indication of a good path than keeping edge values..(thus network stats..as you said).

If I handle each part...subnet of the address separately, then I'd have to worry about fairly simple networks at a time...and once the required node (at a level) is found, it can handle a search among those under it in the same way(...or better if cached.).
(Why isn't that O(V) ? ... It only goes through the optimal path once(twice if the returning is counted)...or is concurrency not accountable when calculating the efficiency ?)

Perhaps a clearer explanation of what exactly you're trying to achieve here will help me help you find a good solution.

I have a graph data structure, which stores the address nodes( and edges as an adjacency list.)
There is a global map which can be used to use that address to get a pointer..or reference to the actual node object.
Keeping the node objects out of the abstraction now, I'm looking for the simplest way to find a good path between two nodes in the graph, keeping a semblance to how the networks actually operate.

**bernt** · 11-08-2011

(Say...I have a structure 'path' that notes the address of the machine it is passed to into an array....and has a record of the destination(so that it knows when to stop))
The sender send out(broadcasts) such structures, and when the destination node gets it, it returns the traveler to the sender through the path recorded in it.
Whoever returns to the sender first is the winner. (A few other paths are noted ...so they can be used if the best one fails.)

How would loops in the graph be handled?
I think that one would have to keep track of each node's "distance" a la Dijkstra's Algorithm. I can see how the algorithm might terminate once a winner is found, but I can also see this getting into an infinite loop, especially if the start and end aren't actually connected (eg, a server is down).

**manasij7479** · 11-08-2011

but I can also see this getting into an infinite loop, especially if the start and end aren't actually connected (eg, a server is down).

Didn't think of that before...
The tracers can be made to expire after they have a certain maximum no. of addresses.
And.. if none of them returns within a certain time... it will be a timeout error!

**Elysia** · 11-09-2011

I can see two scenarios:
- You will try to find the optimal path, which will involve Dijkstra & co. Obviously, if a more efficient algorithm existed, we'd use it. But since we're stuck with Dijkstra & co, I am assuming none exists. Clearly, if you have a multi-core cpu, you could use your algorithm, which would only differ from Dijkstra in that it visits multiple nodes at once. Note that this has its drawbacks since the different threads cannot know of the progress of the others. This will mean they might just traverse down nodes already searched by another thread.
- You will settle for a path (not necessarily the optimal one). You'd probably have to go with a depth-first algorithm for this one to be feasible. It might find a path faster, and it would require some other algorithm than dijkstra.

I fail to see why you think Dijkstra seems like overkill and inefficient. If you have a graph with nodes and edges, it is one of the best searching algorithms.
Although, if you know the layout of your network, you may be able to use an A* algorithm to cut down the search time.

**manasij7479** · 11-09-2011

Originally Posted by Elysia

I fail to see why you think Dijkstra seems like overkill and inefficient. If you have a graph with nodes and edges, it is one of the best searching algorithms.

Overkill because it can't (to my knowledge) be simplified by making some nice assumptions, and I do not always need the absolute best, any good path will do.
Inefficient because I can't think way to have it scale with parallel stuff going on. Is it possible ?
Also.. with it.. I'd need to set cost values for each edge..(Avoiding that makes the graph class much simpler..! and the simulation more realistic(probably))

Note that this has its drawbacks since the different threads cannot know of the progress of the others.

Why would they need to ?
The sender will catch.. say.. the first 10 of the tracers having the path data, that manage to return. The rest will self destruct after a certain time.

**Elysia** · 11-09-2011

Originally Posted by manasij7479

Overkill because it can't (to my knowledge) be simplified by making some nice assumptions...

Look up A*.

...and I do not always need the absolute best, any good path will do.

True, then you may not be interested in Dijkstra. Unfortunately, I'm not aware of any other good algorithms, but surely there are some greedy ones that might fit you.

Inefficient because I can't think way to have it scale with parallel stuff going on. Is it possible ?

Yes, it's possible. Dijkstra is scalable with the number of nodes. Since it examines all the neighboring nodes before continuing, one should be able to spawn different threads to tackle them.
The only bottleneck is that it will need to return to a single point to examine which node it will proceed with.
I suppose any depth-first algorithm would be highly scalable too, since each branch could be offloaded into a new thread.

Why would they need to ?
The sender will catch.. say.. the first 10 of the tracers having the path data, that manage to return. The rest will self destruct after a certain time.

Well, draw a tree with a lot of circular paths. The threads would all have to go around searching the same nodes before finally reaching the destination node.

**manasij7479** · 11-09-2011

Since it examines all the neighboring nodes before continuing, one should be able to spawn different threads to tackle them.

Good idea. My approach on this was wrong because I tried to do much more at once...and jumbled up data on what was visited and what wasn't.

The threads would all have to go around searching the same nodes

What if each spawns new ones each time the path is branched ?
The wastage won't be too significant because I could have those extra ones end at dead ends, at nodes visited too many times and also self destruct after a certain time.

A*

How would the nodes have a sense of direction about which way it is to the destination ?(..even if the topology is known)

**Elysia** · 11-09-2011

Originally Posted by manasij7479

What if each spawns new ones each time the path is branched ?
The wastage won't be too significant because I could have those extra ones end at dead ends, at nodes visited too many times and also self destruct after a certain time.

How does this solve the fact that thread A has examined node B that is connected to node A that is connected to node C and now thread B examines node B?
If thread A gets nowhere, then thread B will also have to search that and get nowhere (unless you synchronize them, but that will probably slow everything to a crawl).
Also remember to not spawn too many threads, as it will slow down the algorithm and eat much more memory. Be considerate, so to speak.

How would the nodes have a sense of direction about which way it is to the destination ?(..even if the topology is known)

In a way, it can be compared to pathfinding, I guess. The straight line to the node might be a good guess.

**manasij7479** · 11-09-2011

If thread A gets nowhere, then thread B will also have to search that and get nowhere

I'd just let them go nowhere and die.
But very soon, the main thread traversing circular path that was sending these threads to wrong 'tangents', would come to a gruesome end because of visiting a node too many times.

The straight line to the node

What is a straight line when all I know is the address of a node and who it can immediately communicate to ?

**Elysia** · 11-09-2011

Originally Posted by manasij7479

I'd just let them go nowhere and die.
But very soon, the main thread traversing circular path that was sending these threads to wrong 'tangents', would come to a gruesome end because of visiting a node too many times.

Yeah, it'll work. Just pointing out that it is a drawback that results in wastage.

What is a straight line when all I know is the address of a node and who it can immediately communicate to ?

You could model your IP addresses as coordinates. You obviously know the destination node and the source node.

**manasij7479** · 11-09-2011

Originally Posted by Elysia

You could model your IP addresses as coordinates. You obviously know the destination node and the source node.

Like .. the best path between 117.x.x.x and 125.x.x.x is more probably through 120.x.x.x than 110.x.x.x ?

**Elysia** · 11-09-2011

I don't know about that.
I am just saying that you could model your IPs as a 4-dimensional coordinate system, so if a.b.c.d, then the straight line would be sqrt(a^2+b^2+c^2+d^2).
I am not going to bother even trying to model subnets because routing through subnets is so incredibly complicated O_O

**manasij7479** · 11-09-2011

Originally Posted by Elysia

I don't know about that.
I am just saying that you could model your IPs as a 4-dimensional coordinate system, so if a.b.c.d, then the straight line would be sqrt(a^2+b^2+c^2+d^2).
I am not going to bother even trying to model subnets because routing through subnets is so incredibly complicated O_O

:Too much Calculation:
Though this can become ineffective if I try to manage subnets recursively....

Thanks for the help
..now it actually seems that I can make something substantial from the haphazard idea it was initially.

Thread: About path finding(in Graphs)..

Thread Tools

Search Thread

Display

About path finding(in Graphs)..

Similar Threads

Finding the path of a file

Finding the path to your executable

path finding

Finding current path

Finding the path of an .exe file