mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) (04/06/91)
Hi,
Here's another one of those perennial graph-theory questions, on
finding paths through directed graphs. It applies to a peculiar
variant of the problem that my (untrained) intuition tells me should be
possible in quite "reasonable" time and space (perhaps O(N log N) space
in total, and perhaps L*O((log N)) time, where N is the number of nodes
in the graph, and L is the length of the generated path; the number of
links is bounded to a small multiple of N). This problem arose in
connection with adding intelligent movement to computer controlled
pieces in a large, realtime game system.
I have a (small) set of directed graphs, each graph initially being
one node in size. Over time, the graphs expand; each new node that is
added to a graph has outdegree (typically) below five. Almost every
link has a corresponding back-link from its target node to its source
node (but this cannot be guaranteed). Links all have the same weight.
Occasionally, as the graphs expand, two graphs may touch, and
coalesce into one, larger graph. Individual graphs can grow reasonably
large - several hundred nodes is common, and after all the nodes have
been added, and all the graphs coalesced, we end up with well over two
thousand nodes in the graph.
I am looking for an algorithm, or pointers to an algorithm, which
will allow me to compute a "reasonably short" path between two
arbitrary nodes (given the restrictions and simplifications listed
below). Failing that, an authoritative reason why it isn't possible
would be appreciated. In the following, all time and space
complexities given are intended as indications of what is reasonable
given the problem domain:
The algorithm need not compute the shortest path (it can even
contain cycles); it would be nice if it (usually) did better than
following a spanning tree of the graph (what's the spanning tree
for a directed graph? :-).
The algorithm need not work for *all* start/destination pairs, but
it should work for most. That is, it is permissible for the algorithm
to 'give up' if it decides that it's taking too long, or that there is
no such path. If the start and destination are in different graphs, or
there is no path, of course, the algorithm should give up.
Any external structures which help the computation must be able to
be built incrementally, and should be cheap in terms of time and space
- O(N log N) is not unreasonable for the space, and O(log N) time for
the (usual) case of adding a single node to a graph. Coalescing graphs
could take longer.
The path can be generated incrementally (that is, given a source
and a destination, we have a certain amount of time to generate each
move - the whole path need not be computed in one hit). For instance,
one could keep a list of intermediate nodes to visit, with the first
node in the list guaranteed to be adjacent to the start node; then,
after each move is taken, we could re-apply the algorithm to compute a
path to the next node on the list, possibly generating more
intermediate nodes.
I've pondered this problem, but haven't found a solution; since
it's not relevant to my work, I thought I'd see if anyone else has seen
anything similar. Any suggestions?
Thanks,
Mike.
--
Mike McGaughey ACSNET: mmcg@bruce.cs.monash.oz
"His state is kingly; thousands at his bidding speed,
And post o'er land and ocean without rest." - Milton.