Re: Shortest path algorithm in digraph with multiple goals?
From: Dr Chaos (mbNOSPAMkennel_at_yahoo.dot.com)
Date: 08/03/04
- Next message: Chris Menzel: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- Previous message: Peter Olcott: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Jym: "Re: Shortest path algorithm in digraph with multiple goals?"
- Next in thread: CBFalconer: "Re: Shortest path algorithm in digraph with multiple goals?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 02 Aug 2004 17:29:55 -0700
Jym wrote:
> On Mon, 2 Aug 2004, Arthur J. O'Dwyer wrote:
>
>
>>On Mon, 2 Aug 2004, Jym wrote:
>>
>>>On Mon, 2 Aug 2004, Dr Chaos wrote:
>>>
>>>>I am asking for recommendations on a "shortest path" or perhaps even
>>>>"elementary cycles" algorithm for a directed graph with a particular
>>>>structure:
>>
>>[...]
>>
>>>I recently got some kind of similar problem where I was looking for cycles
>>>and couldn't use the usual algorithms.
>>>Here's what I used, that may also be useful in your case:
>>
>>[snip automata, rational languages, ILP]
>>
>> Whoof! That's a lot heavier than my response! ;) (I hope the OP
>>finds it useful. I won't even pretend to understand it.)
>
>
> Yep, you're right. Your solution is much more easier... Graphs algorithms
> are obviously not my main domain :-)
>
> Note that my solution may be less space consuming if one wants to allow a
> lot of red edges (thus your solution will produce a huge graph).
>
>
>>But one small nitpick on your example...
>>
>>
>>>Suppose we have the following graph :
>>>
>>>+--------+
>>>v |
>>>A --> B |
>>>| | |
>>>| v |
>>>C --> D -+
>>>
>>>(that is a green (weighted) arc between A and B, C and D, B and D, D and A
>>>(so one green arc out of each node) an a red arc (unoriented) between A
>>>and C.)
>>
>>[...]
>>
>>>Clearly, cycles between A and A are either A-C-A (two red, cost 0) and
>>>A -> B -> D -> A (zero red, cost 3).
>>
>> /And/ there's a cycle A-C->D->A (one red, cost 2).
>
>
> Woops... looks like I totaly forgot this edge from C -> D in all my
> example...
> Doesn't change a lot of things anyway...
> The rationnal langugage will be something like
> ((abd)|(rcd)|(rs))*
> that is
> ((GGG)|(RGG)|(RR))*
> thus leading to the (still linear) expression :
> a(0,3)+b(1,2)+c(2,0) = (b+2c,3a+2b).
>
> And fixing the maximum value of the forst composant to 0, 1 or 2 will lead
> the minimization ILP procedure to find the three corrects answers.
>
> Thanks for noting this awfull mistake of mine.
>
> Hypocoristiquement,
> Jym.
Wow!
I certainly didn't think of it in terms of a linear programming problem;
I will save this message and come back to it if I need to but to stay
conservative I think I will start looking at modifications of known
graph traversal algorithms.
In particular, A.J. O'Dwyer in private mail suggested a good
transformation: suppose that you specify no more than K of the "special
arcs" can occur in any cycle. Then you can split the N vertices into
N*(K+1) of them, i.e. V -> (V,k) k \in 0, K. This is a vertex for
which there have been 'k' previous traversals of the "counted" arcs.
You can then define a distance function between these which is the
normal distance/weight for normal arcs, and then allows transitions from
(v_i,k) to (v_j,k+1) with a finite cost, and infinite otherwise.
So now, you look for the mininum shortest paths from outgoing(v_i) (all
immediate descendants of v_i) to any of (vi,k) for k=0..K, i.e. paths
which contain exactly 'k' of the counted nodes.
At this stage it appears that classical algorithms (Dijkstra's breadth
first search) will work, though peraps lowly.
it's not clear this is the most efficient algorithm, in particular for
my problem, or even what I want, but it's worth a start.
In particular, in my problem, consider the number of vertices will be
say N=1000 to 100000. There is a special structure I didn't previously
mention, namely that the
"regular" edge (which has no upper bound in the cycle) will always map
from vertex i to i+1, i.e. like a "forward iteration" for all points
except the last. The 'counted' arcs are rather arbitrary.
I then would be finding the shortest cycle (if it exists) containing
point v_i, for all v_i. So I would have to repeat the search for each
new v_i. It seems that would be lots of wasted effort.
My overall goal is to try to quantify approximate graph isomorphisms, or
lack thereof, somehow using the distribution of periods/costs of cycles.
Computational feasibility and actual quantitative implementation is key
and more important than proven results.
I.e. really it is a global question concerning differences between graph
toplogies. The N for each graph will be the same, and if necessary each
vertex has a reasonably sensible identity mapping from each graph---as
each vertex represents a point in vector spaces, different
representations of an underlying data set.
Note, I do not really want a statistic which just averages up local
quantities, (such as the number or existence of the bounded edges), as
that would really just a re-doing of a metric statistic in the original
space, which describe the current used algorithms for the problem.
That's why I'm considering "something" about elementary cycles too.
Any physicist-accessible guides to the known state of
mathematics/algorithms regarding this, or any off the wall suggestions?
- Next message: Chris Menzel: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- Previous message: Peter Olcott: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Jym: "Re: Shortest path algorithm in digraph with multiple goals?"
- Next in thread: CBFalconer: "Re: Shortest path algorithm in digraph with multiple goals?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
