Databases
StackOverflow2013
Postsdbo
POPaths in complete graph
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPaths in complete graph
    primarykey
    data
    text
    <p>I have a friend that needs to compute the following:</p> <p>In the complete graph Kn (k&lt;=13), there are k*(k-1)/2 edges. Each edge can be directed in 2 ways, hence 2^[(k*(k-1))/2] different cases.</p> <p>She needs to compute <code>P[A !-&gt; B &amp;&amp; C !-&gt; D] - P[A !-&gt; B]*P[C !-&gt; D]</code></p> <p>X !-> Y means "there is no path from X to Y", and P[ ] is the probability.</p> <p>So the bruteforce algorithm is to examine every one of the 2^[(k*(k-1))/2] different graphes, and since they are complete, in each graph one only needs to consider one set of A,B,C,D because of symmetry.</p> <p>P[A !-> B] is then computed as "number of graphs with no path between node 1 and 2" divided by total number of graphs, i.e 2^[(k*(k-1))/2].</p> <p>The bruteforce method works in mathematica up to K8, but she needs K9,K10... up to K13.</p> <p>We obviously don't need to find the shortest path in the cases, just want to find if there is one.</p> <p>Anyone have optimization suggestions? (This sound like a typical Project Euler problem).</p> <p><strong>Example:</strong></p> <p>The minimal graph K4 have 4 vertices, giving 6 edges. Hence there are 2^6 = 64 possible ways to assign directions to the edges, if we label the 4 vertices A,B,C and D.</p> <p>In some graphs, there is NOT a path from A to B, (lets say X of them) and in some others, there are no path from C to D (lets say Y). But in some graphs, there is no path from A to B, and at the same time no path from C to D. These are W.</p> <p>So <code>P[A !-&gt; B]=X/64</code>, <code>P[C !-&gt; D]=Y/64</code> and <code>P[A !-&gt; B &amp;&amp; C !-&gt; D] = W/64</code>.</p> <p><strong>Update:</strong></p> <ul> <li>A, B,C and D are 4 different vertives, hence we need at least K4.</li> <li>Observe that we are dealing with DIRECTED graphs, so normal representation with UT-matrices won't suffice.</li> <li>There is a function in mathematica that finds the distance between nodes in a directed graph, (if it returns infinity, there is no path), but this is a little bit overkill since we dont need the distance, just if there is a path or not.</li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPer Alexandersson
    1. USPer Alexandersson
    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
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POPaths in complete graph
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POPaths in complete graph
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POPaths in complete graph
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWould you please add small example to make problem clearer?
      singulars
      1. POPaths in complete graph
      1. USPratik Deoghare
    2. COAre A,B,C,D allowed to be equal?
      singulars
      1. POPaths in complete graph
      1. USCraig Gidney
 

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