Re: Finding simple cycles approximating target distance


Keith A. Lewis wrote:
> "KoenM" <rockinfewl@xxxxxxxxx> writes in article <1136885432.085264.66410@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> dated 10 Jan 2006 01:30:32 -0800:
> >Thinking about developing a bicycle route finder, I'm not sure how to
> >best solve the following problem relating graph theory.
> >
> >Given a directed weighted graph, and a specific vertex as starting
> >point, how do I find simple cycles approximating some target distance,
> >most efficiently?
> >>From the graph at hand, I expect result cycles will consist of about 10
> >to 100 edges.
> >
> >I guess I'm after 'simple' cycles here, to make sure I get
> >'interesting' cycles to bike, and not heavily zigzagging ones that pass
> >the same point multiple times?
>
> Some thoughts and suggestions:
>
> Once you discover a cycle, it applies equally well using any point it
> contains as a starting point. Depending on the total number of edges in
> your database, you might want to consider cataloging simple cycles for quick
> lookup.
>
> Possibly only the simplest cycles should be in the catalog, two for each
> edge in most cases -- one going left at every opportunity for a
> counterclockwise cycle and the other going right for a clockwise cycle. You
> could build up a cycle by adding in adjacent cycles and subtracting the
> common edge. For directed edges, you'd also need a list of cycles with that
> edge reversed (again, just the two simplest) to make the edge subtraction
> work. Call these "alternative paths".
>
> HTH.
>
> --Keith Lewis klewis {at} mitre.org
> The above may not (yet) represent the opinions of my employer.


Thank you for the suggestion Keith.
I will look into this.

Koen.

.

Relevant Pages

  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Elecsol batteries (again)
    ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
    (uk.rec.waterways)
  • Re: Algorithm for breaking cycles in directed graph by edge removal
    ... It is clear to me that a DFS (depth first search) can find all cycles in a directed graph. ... DFS will label some edges as "BACK" edges; these back edges connect a node U to an ancestor node V in the traversal tree. ...
    (comp.theory)
  • Re: Algorithm for breaking cycles in directed graph by edge removal
    ... DFS will label some edges as "BACK" edges; ... Obviously, by removing the back edges, all cycles in the graph will be ... Maybe try constructing a dynamic programming algorithm to solve the ...
    (comp.theory)
  • Re: Graph to regions algorithm
    ... > My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... To find cycles in a graph, you compute the "minimum spanning tree". ...
    (comp.graphics.algorithms)