Databases
StackOverflow2013
Postsdbo
PODiscover All Paths in Single Source, Multi-Terminal (possibly cyclic) Directed Graph
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODiscover All Paths in Single Source, Multi-Terminal (possibly cyclic) Directed Graph
    primarykey
    data
    text
    <p>I have a graph <code>G = (V,E)</code>, where </p> <ul> <li><code>V</code> is a subset of <code>{0, 1, 2, 3, …}</code> </li> <li><code>E</code> is a subset of <code>VxV</code></li> <li>There are no unconnected components in <code>G</code> </li> <li>The graph may contain cycles</li> <li>There is a known node <code>v</code> in <code>V</code>, which is the source; i.e. there is no <code>u</code> in <code>V</code> such that <code>(u,v)</code> is an edge</li> <li>There is at least one sink/terminal node <code>v</code> in <code>V</code>; i.e. there is no <code>u</code> in <code>V</code> such that <code>(v,u)</code> is an edge. The identities of the terminal nodes are not known - they must be discovered through traversal</li> </ul> <p>What I need to do is to compute a set of paths <code>P</code> such that every possible path from the source node to any terminal node is in <code>P</code>. Now, if the graph contains cycles, it is possible that by this definition, <code>P becomes an infinite set. This is not what I need. Rather, what I need is for</code>P<code>to contain a path that doesn't explore the loop and at least one path that does explore the loop.<br> I say "at least one path that does explore the loop", as the loop may contain branches internally, in which case, all of those branches will need to be explored as well. Thus, if the loop contains two internal branches, each with a branching factor of 2, then I need a total of four paths in</code>P` that explore the loop.</p> <p>For example, an algorithm run on the following graph:</p> <pre><code> +-------+ | | v | 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6 | | | | | v | v | 9 +-&gt;7-+ | v 8 </code></pre> <p>which can be represented as:</p> <pre><code>1:{2} 2:{3} 3:{4} 4:{5,9} 5:{6,7} 6:{7} 7:{4,8} 8:{} 9:{} </code></pre> <p>Should produce the set of paths:</p> <pre><code>1,2,3,4,9 1,2,3,4,5,6,7,8 1,2,3,4,5,6,7,4,9 1,2,3,4,5,7,8 1,2,3,4,5,7,4,9 1,2,3,4,5,7,4,5,6,7,8 1,2,3,4,5,7,4,5,7,8 </code></pre> <p>Thus far, I have the following algorithm (in python) that works in some simple cases:</p> <pre><code>def extractPaths(G, s=None, explored=None, path=None): _V,E = G if s is None: s = 0 if explored is None: explored = set() if path is None: path = [s] explored.add(s) if not len(set(E[s]) - explored): print path for v in set(E[s]) - explored: if len(E[v]) &gt; 1: path.append(v) for vv in set(E[v]) - explored: extractPaths(G, vv, explored-set(n for n in path if len(E[n])&gt;1), path+[vv]) else: extractPaths(G, v, explored, path+[v]) </code></pre> <p>but it fails horribly in the more complex cases. </p> <p>I'd appreciate any help as this is a tool to validate an algorithm that I have developed for my Master's thesis.<br> Thank you in advance</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USinspectorG4dget
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COIt is totally unclear what does it mean to explore each loop once. Can you define it rigorously?
      singulars
      1. PODiscover All Paths in Single Source, Multi-Terminal (possibly cyclic) Directed Graph
      1. USn.m.
    2. CO`4,5,7` is a loop, and thus a valid path may contain several repetitions of `4,5,6` (e.g. `1,2,3,4,5,7,4,5,7,4,5,7,4,5,7,4,5,7,8`). However, I am not interested in generating such a path. I am only interested in the path that (a) ignores this loop and (b) explores the loop once. Thus, I am interested in `1,2,3,4,5,7,8` and `1,2,3,4,5,7,4,5,7,8`. If there are branching nodes within a loop, I will need to generate paths that explore each of them as well. Does this make things clearer?
      singulars
      1. PODiscover All Paths in Single Source, Multi-Terminal (possibly cyclic) Directed Graph
      1. USinspectorG4dget
    3. CONo, not really. I asked what does it mean to explore a loop once. An example does not make a rigorous definition. Let's try again. What makes two paths "essentially the same"? Is there a procedure one can run and say "we have done this path before"? Can you answer this in a general way, without invoking an example?
      singulars
      1. PODiscover All Paths in Single Source, Multi-Terminal (possibly cyclic) Directed Graph
      1. USn.m.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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