Thanks experts!
Thanks Robert Kern!
Two more questions about it:
1. networkx.has_path(G, first_stick, second_stick) stop when find second_stick
or compute all the sub-graph and then evaluate if first_stick and second_stick
are connected?
2. Using networkx or other tool: how can I obtain the 'clusters size'
distribution (that is: number of clusters of size 'D', for all cluster-sizes)?
Thanks a lot!!
José Luis
________________________________
De: Robert Kern <[email protected]>
Para: Discussion of Numerical Python <[email protected]>
Enviado: miércoles, 4 de septiembre de 2013 18:49
Asunto: Re: [Numpy-discussion] Stick intersection path algorithm
On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta <[email protected]>
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 <[email protected]>
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 inG.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 <[email protected]>
>
>Para: Discussion of Numerical Python <[email protected]>
>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
><[email protected]> 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
>[email protected]
>http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
>
>_______________________________________________
>NumPy-Discussion mailing list
>[email protected]
>http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
--
Robert Kern
_______________________________________________
NumPy-Discussion mailing list
[email protected]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________
NumPy-Discussion mailing list
[email protected]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
