[Numpy-discussion] Stick intersection path algorithm

[Robert Kern]

On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta <
joseluismietta at 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 <
joseluismietta at 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.kern at gmail.com>
>
> *Para:* Discussion of Numerical Python <numpy-discussion at 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 <
> joseluismietta at 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 at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>


-- 
Robert Kern
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20130904/ad14ecaf/attachment.html>