<html><body><div style="color:#000; background-color:#fff; font-family:times new roman, new york, times, serif;font-size:10pt">Hi experts!<br><div><span><br></span></div><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent; font-style: normal;">If I do:</div><pre class="prettyprint"><code><span class="pln">G </span><span class="pun">=</span><span class="pln"> </span><span class="typ">Graph</span><span class="pun">(</span><span class="pln">M</span><span class="pun">)<br><br></span></code></pre><div>That is: to use the associated <a href="https://en.wikipedia.org/wiki/Intersection_graph">intersection graph</a>,
where the vertices are the sticks and there is an edge between the two
vertices if they intersect. Two sticks are "connected by a
'intersected-stick' path" if they are in the same connected component of
this graph.</div><div>It turns out that the matrix I consider (M) is the <a href="https://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a> of this graph.</div><div><br></div><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent; font-style: normal;">Then, I can do:</div><pre class="prettyprint"><code><span class="pln">first_stick </span><span class="kwd">in</span><span class="pln"> G</span><span class="pun">.</span><span class="pln">connected_component_containing_vertex</span><span class="pun">(</span><span class="pln">second_stick</span><span class="pun">)</span></code></pre><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent; font-style: normal;">This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with
'second_stick'.</div><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent; font-style: normal;"><br></div><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent; font-style: normal;">The problem is that <br></div><pre class="prettyprint"><code><span class="pln">G</span><span class="pun">.</span><span class="pln">connected_component_containing_vertex()<br><br></span></code></pre>explore <span style="font-weight: bold;"><span style="text-decoration: underline;">all </span></span>the sub-graph.<br><br>How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'? <br><br>Waiting for your answers.<br><br>Thanks a lot!!<br><div style="color: rgb(0, 0, 0); font-size: 13.3333px; font-family: times new roman,new york,times,serif; background-color: transparent;
font-style: normal;"><br><span></span></div><br><div style="font-family: times new roman, new york, times, serif; font-size: 10pt;"> <div style="font-family: times new roman, new york, times, serif; font-size: 12pt;"> <div dir="ltr"> <hr size="1"> <font face="Arial" size="2"> <b><span style="font-weight:bold;">De:</span></b> Robert Kern <robert.kern@gmail.com><br> <b><span style="font-weight: bold;">Para:</span></b> Discussion of Numerical Python <numpy-discussion@scipy.org> <br> <b><span style="font-weight: bold;">Enviado:</span></b> lunes, 2 de septiembre de 2013 10:40<br> <b><span style="font-weight: bold;">Asunto:</span></b> Re: [Numpy-discussion] Stick intersection path algorithm<br> </font> </div> <div class="y_msg_container"><br><div id="yiv8971658870"><div dir="ltr">On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta <<a rel="nofollow" ymailto="mailto:joseluismietta@yahoo.com.ar" target="_blank"
href="mailto:joseluismietta@yahoo.com.ar">joseluismietta@yahoo.com.ar</a>> wrote:<br>><br>> Hi experts!<br>><br>> I wanna study the intersection between line segments (sticks).<br>
> I wrote a algorithm that generate a matrix, M, with N rows and N columns. The M-element Mij is 1 if stick number 'i' intersect stick number 'j' (obviously M is symmetric).<br>><br>> Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-sticks' path.<br>
<br>You may find it helpful to reword your problem using standard terminology. If I hadn't read your previous question, I would not have been able to understand what you meant by intersected sticks (or, as Chris thought at first, that you needed help determining the intersections). This will also help in searching Google for background and pre-existing software to solve your problem.<br>
<br>You have an "undirected graph" (the sticks are "nodes", and the intersections are "edges") and you want to find if two given nodes are "reachable" from each other. You are currently representing your graph as an "adjacency matrix" `M` where `M[i,j]` is 1 iff nodes `i` and `j` have an edge between them and 0 otherwise. The "transitive closure" of your graph `M` is the graph that connects two nodes with an edge iff the two nodes are reachable from each other in the original graph `M`. There are several graph theory packages out there, like NetworkX, that will do this for you. Depending on the kinds of queries you would like to do, as David points out, want to compute the "connected components" of your graph; a connected component is a subgraph of your original graph such that all of the nodes are reachable from each other.<div>
<br></div><div>You can also look up Python code for computing the transitive closure of a graph; it's not a complicated algorithm. However, this algorithm is usually implemented using a different representation of a graph than an adjacency matrix, so you may need to do a conversion.</div>
<div><br><div>--<br>Robert Kern<br></div></div></div></div><br>_______________________________________________<br>NumPy-Discussion mailing list<br><a ymailto="mailto:NumPy-Discussion@scipy.org" href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br><a href="http://mail.scipy.org/mailman/listinfo/numpy-discussion" target="_blank">http://mail.scipy.org/mailman/listinfo/numpy-discussion</a><br><br><br></div> </div> </div> </div></body></html>