Databases
StackOverflow2013
Postsdbo
POGraph Algorithm To Find All Paths Between N Arbitrary Vertices
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGraph Algorithm To Find All Paths Between N Arbitrary Vertices
    text
    copied!<p>I have an graph with the following attributes:</p> <ul> <li>Undirected</li> <li>Not weighted </li> <li>Each vertex has a minimum of 2 and maximum of 6 edges connected to it. </li> <li>Vertex count will be &lt; 100</li> <li>Graph is static and no vertices/edges can be added/removed or edited.</li> </ul> <p>I'm looking for paths between a random subset of the vertices (at least 2). The paths should simple paths that only go through any vertex once.</p> <p>My end goal is to have a set of routes so that you can start at one of the subset vertices and reach any of the other subset vertices. Its not necessary to pass through all the subset nodes when following a route.</p> <p>All of the algorithms I've found (Dijkstra,Depth first search etc.) seem to be dealing with paths between two vertices and shortest paths.</p> <p>Is there a known algorithm that will give me all the paths (I suppose these are subgraphs) that connect these subset of vertices?</p> <p>edit:</p> <p>I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: <a href="https://imgur.com/mGVlX.gif" rel="nofollow noreferrer">http://imgur.com/mGVlX.gif</a></p> <p>There are two stages pre-process and runtime.</p> <h1>pre-process</h1> <ol> <li>I have a graph and a subset of the vertices (blue nodes)</li> <li>I generate all the possible routes that connect all the blue nodes</li> </ol> <h1>runtime</h1> <ol> <li>I can start at any blue node select any of the generated routes and travel along it to reach my destination blue node.</li> </ol> <hr> <p>So my task is more about creating all of the subgraphs (routes) that connect <strong>all</strong> blue nodes, rather than creating a path from A->B.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload