About path finding(in Graphs)..

This is a discussion on About path finding(in Graphs).. within the General Discussions forums, part of the Community Boards category; I studied Dijkstra's algorithm...but It seems a bit overkill (And if I'm not mistaken...somewhat inefficient) for what I have in ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    About path finding(in Graphs)..

    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 ?
    Last edited by manasij7479; 11-08-2011 at 06:02 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,468
    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.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    (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).
    Consider this post signed

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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!
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,554
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Elysia View Post
    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.
    Last edited by manasij7479; 11-09-2011 at 01:31 PM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,554
    Quote Originally Posted by manasij7479 View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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)
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,554
    Quote Originally Posted by manasij7479 View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,554
    Quote Originally Posted by manasij7479 View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Elysia View Post
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  14. #14
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,554
    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
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Elysia View Post
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding the path of a file
    By caduardo21 in forum C Programming
    Replies: 8
    Last Post: 08-09-2005, 11:00 AM
  2. Finding the path to your executable
    By jmd15 in forum Windows Programming
    Replies: 3
    Last Post: 07-19-2005, 09:32 AM
  3. path finding
    By X PaYnE X in forum Game Programming
    Replies: 27
    Last Post: 05-30-2005, 01:38 AM
  4. Finding current path
    By eam in forum Windows Programming
    Replies: 9
    Last Post: 12-19-2003, 09:15 PM
  5. Finding the path of an .exe file
    By Gonzo in forum C Programming
    Replies: 1
    Last Post: 09-15-2003, 05:19 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21