[Numpy-discussion] length - sticks algorithm
Hi experts! Im working with conductivity of sticks film - systems. In my algorithm (N sticks) I have the intersection graph matrix M (M is a NxN matrix, M_ij=1 if sticks 'i' and 'j' do intersect, and M_ij=0 if sticks 'i' and 'j' do not). Also I have 2 lists with the end-points of each stick. In addition, I can calculate the intersection point (If exist) between sticks. I want to calculate all the distances between the points of intersection (1,2,3,...N) in the next figure: without lose the connectivity information (which intersection is connected to which). In the figure, (A) is the system with sticks. I dont know how to do this. Im a python + numpy user. Waiting for your answers! Thans a lot ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
[Numpy-discussion] plt.show() and plt.draw() doesnt work
Hi experts! I have a numpy array M. I generate a graph using NetworkX and then I want to draw this graph: import networkx as nx import matplotlib.pyplot as plt G=nx.graph(M) nx.draw(G) plt.draw() Doing this, no picture appears. In addition, if I do `plt.show()` no picture appears. Please help! Best regards___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
[Numpy-discussion] Number of elements in a intersection graph
Hi experts!! I am studying the intersection between line segments (sticks). I have an Numpy array (M) corresponding to the intersection graph of the system (the element Mij = 1 if the sticks' i 'and' 'j' intersect, and Mij = 0 if not intersect). I want to determine the number of elements that form the path that connects two sticks (N and K), i.e.: the number of sticks that form the spanning cluster between stick N and K. How I can do?? Please explain step by step. Best regards! Thanks a lot. José Luis ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
[Numpy-discussion] At.: use less RAM memory and increase execution speed
Hi experts! I wanna use less RAM memory in my Monte Carlo simulations. In my algorithm I use numpy arrays and xrange() function. I hear that I can reduce RAM used in my lagorithm if I do the next: 1) replace xrange() for range(). 2) replace numpya arrays for python lists 3) use reset() function for deleting useless arrays. Is that true? In adition, I wanna increase execution speed of my code (I use numpy and SciPy functions). How can I apply Cython? Will it help? Please help. Thanks a lot!! ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
[Numpy-discussion] Networkx graph - numpy array - networkx.has_path() function
Hi experts! I wanna use networkx.has_path(). This is applies, necesary, to a networkx graph. I have a adjacency matrix of a undirected graph (M, wich is a numpy matrix (array of N x N elements)). How can I do for use M in networkx.has_path()? If I must transform M into a networkx graph: how can I do that? Waiting for your answers. Thanks a lot!! José Luis___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Stick intersection path algorithm
Thanks so much!! Best regards, José Luis De: Daπid Para: Discussion of Numerical Python Enviado: jueves, 5 de septiembre de 2013 12:56 Asunto: Re: [Numpy-discussion] Stick intersection path algorithm On 5 September 2013 17:03, Josè Luis Mietta wrote: The array ([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) means that in the sistem (graph) are : 4 cluster of size 1, one cluster of size 3, one cluster of size 7 and one cluste of size 39? No, it means there are 39 of size 1, 7 of size 2 and so on. David. ___ 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
Re: [Numpy-discussion] Stick intersection path algorithm
Hi experts! How can I create a networkx graph from the adjacency matrix M? Thanks a lot, José Luis De: Daπid Para: Discussion of Numerical Python Enviado: jueves, 5 de septiembre de 2013 12:56 Asunto: Re: [Numpy-discussion] Stick intersection path algorithm On 5 September 2013 17:03, Josè Luis Mietta wrote: The array ([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) means that in the sistem (graph) are : 4 cluster of size 1, one cluster of size 3, one cluster of size 7 and one cluste of size 39? No, it means there are 39 of size 1, 7 of size 2 and so on. David. ___ 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
Re: [Numpy-discussion] Stick intersection path algorithm
Hi experts! The array ([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) means that in the sistem (graph) are : 4 cluster of size 1, one cluster of size 3, one cluster of size 7 and one cluste of size 39? What does means 'zero' (13 times) in the array? Thans a lot! José Luis De: Daπid Para: Discussion of Numerical Python Enviado: jueves, 5 de septiembre de 2013 11:06 Asunto: Re: [Numpy-discussion] Stick intersection path algorithm On 5 September 2013 13:14, Josè Luis Mietta wrote: 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)? This is best asked in their mailing list. A possible way is: np.bincount([len(i) for i in nx.connected_components(G)]) For example: np.bincount([len(i) for i in nx.connected_components(nx.erdos_renyi_graph(100, 0.01))]) array([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) ___ 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
Re: [Numpy-discussion] Stick intersection path algorithm
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 Para: Discussion of Numerical Python 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 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 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 > >Para: Discussion of Numerical Python >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 > 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 closu
Re: [Numpy-discussion] Stick intersection path algorithm
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 Para: Discussion of Numerical Python 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 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
Re: [Numpy-discussion] Stick intersection path algorithm
Hi Chris. I wanna see if two line segments are connected by a path formed by line segments intersected. Waiting for your answers. Thanks a lot! De: Chris Barker - NOAA Federal Para: Discussion of Numerical Python Enviado: domingo, 1 de septiembre de 2013 21:18 Asunto: Re: [Numpy-discussion] Stick intersection path algorithm On Sun, Sep 1, 2013 at 3:55 PM, Josè Luis Mietta wrote: Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-sticks' path. > > > do you mean a test to see if two line segments intersect? This looks reasonable: http://wiki.processing.org/w/Line-Line_intersection It probably makes sense to translate to Cython (or use the C and call with cython). I"ve also got similar code in a little package of mine: https://github.com/ChrisBarker-NOAA/py_geometry Already Cython, and includes code to check a whole bunch at once, stored in numpy arrays: https://github.com/ChrisBarker-NOAA/py_geometry/blob/master/py_geometry/line_crossings.pyx I hope it's useful to you. -Chris -Chris -Chris Any idea for that? > > >Thanks a lot! > > >___ >NumPy-Discussion mailing list >NumPy-Discussion@scipy.org >http://mail.scipy.org/mailman/listinfo/numpy-discussion > > -- Christopher Barker, Ph.D. Oceanographer Emergency Response Division NOAA/NOS/OR&R (206) 526-6959 voice 7600 Sand Point Way NE (206) 526-6329 fax Seattle, WA 98115 (206) 526-6317 main reception chris.bar...@noaa.gov ___ 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
[Numpy-discussion] Stick intersection path algorithm
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. Any idea for that? Thanks a lot! ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Stick (line segments) percolation algorithm - graph theory?
Thanks a lot!! José Luis De: Brett Olsen Para: Discussion of Numerical Python Enviado: lunes, 26 de agosto de 2013 14:08 Asunto: Re: [Numpy-discussion] Stick (line segments) percolation algorithm - graph theory? I can see a couple opportunities for improvements in your algorithm. Running your code on a single experiment, I get about 2.9 seconds to run. I get this down to about 1.0 seconds by (1) exploiting the symmetry of the M matrix and (2) avoiding the costly inner loop over k in favor of array operations: def check_segments(j, others, data): x1, y1, x2, y2 = data x_A1B1 = x2[j]-x1[j] y_A1B1 = y2[j]-y1[j] x_A1A2 = x1[others]-x1[j] y_A1A2 = y1[others]-y1[j] x_A2A1 = -1*x_A1A2 y_A2A1 = -1*y_A1A2 x_A2B2 = x2[others]-x1[others] y_A2B2 = y2[others]-y1[others] x_A1B2 = x2[others]-x1[j] y_A1B2 = y2[others]-y1[j] x_A2B1 = x2[j]-x1[others] y_A2B1 = y2[j]-y1[others] p1 = x_A1B1*y_A1A2 - y_A1B1*x_A1A2 p2 = x_A1B1*y_A1B2 - y_A1B1*x_A1B2 p3 = x_A2B2*y_A2B1 - y_A2B2*x_A2B1 p4 = x_A2B2*y_A2A1 - y_A2B2*x_A2A1 condition_1=p1*p2 condition_2=p3*p4 return (p1 * p2 <= 0) & (p3 * p4 <= 0) for j in xrange(1, N): valid = check_segments(j, range(j), (x1, y1, x2, y2)) M[j,0:j] = valid M[0:j,j] = valid I don't see any other particularly simple ways to improve this. You could probably add an interval check to ensure that the x and y intervals for the segments of interest overlap before doing the full check, but how much that would help would depend on the implementations. ~Brett On Fri, Aug 23, 2013 at 5:09 PM, Josè Luis Mietta wrote: I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectangular box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Written like that, very much RAM is consumed: Here, the element Mij=1 if stick i intersects stick j and Mij=0 if not. > >How can I optimize my algorithm? Graph theory is useful in this case? ___ 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
[Numpy-discussion] Stick (line segments) percolation algorithm - graph theory?
Hi experts! I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectanglar box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Writen like that, very much RAM is consumed: array_x1=uniform.rvs(loc=-b/2,scale=b,size=N) array_y1=uniform.rvs(loc=-h/2,scale=h,size=N) array_x2=uniform.rvs(loc=-b/2,scale=b,size=N) array_y2=uniform.rvs(loc=-h/2,scale=h,size=N) M =np.zeros([N,N]) foru inxrange(100): >This'100'isthe number of experiments. forj inxrange(N): ifj>0: x_A1B1 =array_x2[j]-array_x1[j] y_A1B1 =array_y2[j]-array_y1[j] x_A1A2 =array_x1[0:j]-array_x1[j] y_A1A2 =array_y1[0:j]-array_y1[j] x_A2A1 =-1*x_A1A2 y_A2A1 =-1*y_A1A2 x_A2B2 =array_x2[0:j]-array_x1[0:j] y_A2B2 =array_y2[0:j]-array_y1[0:j] x_A1B2 =array_x2[0:j]-array_x1[j] y_A1B2 =array_y2[0:j]-array_y1[j] x_A2B1 =array_x2[j]-array_x1[0:j] y_A2B1 =array_y2[j]-array_y1[0:j] p1 =x_A1B1*y_A1A2 -y_A1B1*x_A1A2 p2 =x_A1B1*y_A1B2 -y_A1B1*x_A1B2 p3 =x_A2B2*y_A2B1 -y_A2B2*x_A2B1 p4 =x_A2B2*y_A2A1 -y_A2B2*x_A2A1 condition_1=p1*p2 condition_2=p3*p4 fork inxrange (j): ifcondicion_1[k]<=0andcondicion_2[k]<=0: M[j,k]=1 ifj+1___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
[Numpy-discussion] At.: question about RAM problem in numpy array code
Hi experts! I have a core i3 3GB RAM Toshiba laptop. Im a newby Ubuntu 13.04, python and sage user. I note that RAM memory becomes full while running script (starts in 50% of RAM ocupation and becomes to 100% (full)). This generate that operating system become slower... In the code few numpy arrays are gereated (each one with ~700 elements or more). The script looks like this: OUTPUT=[] number of elements=[n1,n2,.] numbers of executions =N forj innumber of elements: lalala=[] fori insrange(N): Algorithmisexecuted 'N'times an append one value inarray 'lalala'each time.Ineach execution three numpy matrix of 300x 300(=9)elements (each one)participate.Thismatrix are called 'M','M_v'and'M_h'andare re-generated foreach 'i'index inthe for-cycle. Doingmath on all 'N'elements in'lalala'a 'pipipi'element isgenerated an thenappend intoOUTPUT array. When execution ends the OUTPUT array have the same lenght that 'number of elements' array. In each 'for' cycle, other arrayrs participate. What can I do for throubleshooting that? IS possible that the algorithm and old arrays are saving in RAM memory? If tahts possible, how can I di for deleting that? Waiting for your answers. Thanks a lot!___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
