On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta < joseluismie...@yahoo.com.ar> wrote: > > Hi experts! > > If I do: > > G = Graph(M) > > That is: to use the associated intersection graph, 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. > It turns out that the matrix I consider (M) is the adjacency matrix of this graph. > > Then, I can do: > > first_stick in G.connected_component_containing_vertex(second_stick) > > This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with 'second_stick'. > > The problem is that > > G.connected_component_containing_vertex() > > explore all the sub-graph. > > How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'?
networkx.has_path(G, first_stick, second_stick) http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.shortest_paths.generic.has_path.html#networkx.algorithms.shortest_paths.generic.has_path If you are going to be doing many queries, you should compute all of the path lengths, then you can query the final data structure easily. lengths = networkx.all_pairs_shortest_path_length(G) second_stick in lengths[first_stick] -- Robert Kern On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta < joseluismie...@yahoo.com.ar> wrote: > Hi experts! > > If I do: > > G = Graph(M) > > That is: to use the associated intersection > graph<https://en.wikipedia.org/wiki/Intersection_graph>, > 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. > It turns out that the matrix I consider (M) is the adjacency > matrix<https://en.wikipedia.org/wiki/Adjacency_matrix>of this graph. > > Then, I can do: > > first_stick in G.connected_component_containing_vertex(second_stick) > > This is 'True' if 'first_stick' is in the sub-graph formed by > 'second_stick' and all sticks 'connected' with 'second_stick'. > > The problem is that > > G.connected_component_containing_vertex() > > explore all the sub-graph. > > How can I do (what is the code) for stop the iteration when the algorithm > found 'first-stick'? > > Waiting for your answers. > > Thanks a lot!! > > > ------------------------------ > *De:* Robert Kern <robert.k...@gmail.com> > > *Para:* Discussion of Numerical Python <numpy-discussion@scipy.org> > *Enviado:* lunes, 2 de septiembre de 2013 10:40 > > *Asunto:* Re: [Numpy-discussion] Stick intersection path algorithm > > On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta < > joseluismie...@yahoo.com.ar> wrote: > > > > Hi experts! > > > > I wanna study the intersection between line segments (sticks). > > 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). > > > > Given two arbitrary sticks, i need a simple and effective algorithm that > determinate if that two sticks are conected by a 'intersected-sticks' path. > > 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. > > 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. > > 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. > > -- > Robert Kern > > _______________________________________________ > NumPy-Discussion mailing list > NumPy-Discussion@scipy.org > http://mail.scipy.org/mailman/listinfo/numpy-discussion > > > > _______________________________________________ > NumPy-Discussion mailing list > NumPy-Discussion@scipy.org > http://mail.scipy.org/mailman/listinfo/numpy-discussion > > -- Robert Kern
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
