Re: Question about graph theroy--Help!
- From: "Sable Basilisk" <sable_basilisk@xxxxxxxxxxx>
- Date: 28 Feb 2006 18:40:41 -0800
Bo wrote:
us wrote:
Thank you. But this is a Dijkstra's algorithm which only find the
shortest path. I want to find all the possible path from source to
destination. Could you give me some advices about this?
many thanks
BO
Assume : the source and destination may be the same node.
Path : described by a list of nodes visited in order.
Say you have N nodes. The longest path that never visits a node more
than once except possibly the destination node (no inner loops) will
have at most (N+1) nodes in the list (N links).
- Start with the source
- Generate all paths of length 1
- Run through the paths generated and generate all paths of length 2.
First, check if the new node is the destination. If so, mark it. If
not, check the most recently added node against previous nodes to see
if it has visited that node before (loop). Store any positive results
in the record variable for that path. Any paths that have a loop or
reach the destination will be ignored when generating more paths.
- Using only unmarked paths, generate all paths of length 3. Mark any
paths that visit a node twice or reach the destination.
- Continue until paths of length (N+) are generated and mark the ones
reach the destination or visit a node twice.
Look at all the paths generated that are marked as ending at the
destination in your complete list of paths structure.
Depending on how big N is and how many links there are, the size of the
data structures could get impossibly big, so culling the loops early
will help a lot to cut down on the size of the list of paths.
You could be very dynamic about resizing arrays depending on the
parameters, but any user will have to face a possible message that too
many paths were generated for the available memory. Once you accept
that, you can hard code some limits in from the start and take
advantage of that limit to avoid all the messy dynamic allocation and
checking to see if the space was available.
A path is stored by storing each node in the path, so it may contain
(N+1) nodes since all nodes must be unique except perhaps the start and
end node.
I am thinking that the code will be easier to write if you don't try to
do everything at once. Let each function do one simple thing like
generate all paths that are one unit longer from a given path. Let the
next function go through the paths and figure out if they reach the
destination. If you try to check paths as you generate them, the code
will be hard to read and more bug-prone.
Aiming for a data structure size of 256 bytes:
How about a maximum of N=253 nodes, so they could be numbered with a
byte from 1-253.
Store a path in an array of bytes of a fixed size of (N+1) = 254, with
a byte value of 0 meaning no more nodes.
To check if it reaches the destination, compare it to the first node.
To check for loops, XOR the most recently added node with previous
nodes (except the first) and if any result in 0, it has an inner loop.
A data structure for a path (call it PathInfo) would have:
- fixed array of 254 bytes
- byte variable, 1 = reaches destination, 2= has inner loop
- unsigned byte storing the length of the path (possibly useful to make
code easier and/or faster. not absolutely neccessary since the length
can be found by other slower methods or may be known from being inside
a for loop).
Now, if you hard allocate 1 million of PathInfo's, that's 256 MB which
most computers can handle. You could take a size parameter and
allocate based on that.
Also, have an index array from 1 to 254 of long integers to store where
the last path of that length is stored in the array of PathInfo's.
As you generate paths, they are all stored in the same array of
PathInfos's. You can grab each group of paths of length M using the
index array to generate the next group.
If you reach the maximum element of the array, stop and tell the user.
Maybe they want to try again with a bigger size and maybe tweak the
virtual memory settings. It would be a lot slower to have the overhead
of constantly growing the data structure and checking to see if the
memory was there.
To output the paths, run through the big array until the last path
stored and output the paths marked as ending at the destination.
If N is bigger than 255, you would need 16 bit integers for node names.
The number of possible paths also strongly depends on the maximum
number of links to any single node (call it M). If the links and nodes
are generated from real life, there is often a real life reason why
this is low (how many railroad tracks can leave a city?) and that will
keep the size of your list of paths from getting too big to store. If
M and N are both above 255, you'd have to be really lucky to have
enough memory to store all paths.
.
- Follow-Ups:
- Re: Question about graph theroy--Help!
- From: Chris M.
- Re: Question about graph theroy--Help!
- Prev by Date: Re: Mesh refinement in PDE Toolbox
- Next by Date: memory usage of mcr
- Previous by thread: Re: Mesh refinement in PDE Toolbox
- Next by thread: Re: Question about graph theroy--Help!
- Index(es):
Relevant Pages
|
