ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 12 Mar 2021 10:46:11 +0100FFloyd-Warshall doesn't workshttps://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/ In `https://stackoverflow.com/questions/55518900/seeking-pseudo-code-for-calculating-the-smith-and-schwartz-set` I have found the following application of Ffloyd-Warshall algorithm :
`I guess python is close enough to pseudocode.
Let's say we have n candidates numbered from 0 to n - 1.
First you can compute a matrix beats[i][j] equal to True if candidate i beats candidate j and False otherwise.
Now compute the transitive closure of the matrix using the Floyd-Warshall algorithm:
for k in range(n):
for i in range(n):
for j in range(n):
beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])`
There is my code for `n=3`
B =[["False","True","True","False"],["False","False","True","True"],["False","False","False","False"],["True","False","True","False"]]
def floydWarshall1(graph,n=3): #n=no. of vertex
beats=graph
[[["True" if (beats[i][j]=="True" or (beats[i][k] and beats[k][j])=="True") else "False" for j in range(n)] for i in range(n)]for k in range(n)]
return beats
fw=floydWarshall1(B,3)
show(B)
show(fw)
I wonder why `B` and `fw` are the sames since
show(B[0][3])
show(B[0][1] and B[1][3])
returns `False` for the first and `True` for the second. Certainly an error of mine.CyrilleFri, 12 Mar 2021 10:46:11 +0100https://ask.sagemath.org/question/56128/A simple sum causes division by zero exceptionhttps://ask.sagemath.org/question/55766/a-simple-sum-causes-division-by-zero-exception/I'm very new to SageMath and did some small experiments yesterday. This is my Code:
x, n, r, i = var('x, n, r, i')
f(x, n, r) = x * sum((1 + r) ^ i, i, 1, n)
f(1, 30, 0.0)
It works well if `r != 0`, but will raise a exception of "division by zero" if equal.
My ipynb file: nbviewer.jupyter.org/gist/7sDream/5db3cfd153269fd1a1cacaf0b60f69bb
It seems some optimizations of sum did not consider the range of variable `r`.
But there is also no change if I added `assume(r >= 0)`before define `f`.
So how can I disable this sum optimizations? Or what is wrong with the way I use it?7sDreamFri, 19 Feb 2021 12:53:02 +0100https://ask.sagemath.org/question/55766/"Affine diagonalization algorithm" in n-dimensions?https://ask.sagemath.org/question/55345/affine-diagonalization-algorithm-in-n-dimensions/Does Sage have a general implementation of the "affine diagonalization algorithm"
for n-dimensional vector spaces?
I found some pseudo-code, see page 15 (in section 3 "affine diagonalization" which begins on page 12) of
- [Lecture 21: Surfaces](https://cs.nyu.edu/yap/bks/egc/09/21Surfaces.pdf) in [Robust geometric computation](https://cs.nyu.edu/yap/bks/egc/)
Searching online led me also to this answer from 2008 where someone does it with Maple:
- [Maple primes: Normal forms for quadratic functions](https://www.mapleprimes.com/posts/38766-Normal-Forms-For-Quadratic-Functions)
but unfortunately, I cannot open the `.mws` file (I get an error message concerning the version number).
Thank you very much for the help.BernMon, 18 Jan 2021 19:59:25 +0100https://ask.sagemath.org/question/55345/Default algorithm for cardinalityhttps://ask.sagemath.org/question/49070/default-algorithm-for-cardinality/Hello, I am using Sage for operations on elliptic curves and I was curious what is the default algorithm used to compute the cardinality of a curve when: "E.cardinality()" is used? I tried to find it here: http://doc.sagemath.org/html/en/reference/curves/sage/schemes/elliptic_curves/ell_finite_field.html but I only found out there are some algorithms which you can choose as an optional argument. Is it the Schoof's algorithm?JanoutVWed, 18 Dec 2019 20:00:15 +0100https://ask.sagemath.org/question/49070/About algorithm for testing whether a point is in a V-polyhedronhttps://ask.sagemath.org/question/48462/about-algorithm-for-testing-whether-a-point-is-in-a-v-polyhedron/ Hi there,
I have two questions and I wonder if any of you may know the answer.
1 What algorithm does sage use to test whether a given point is in a polyhedron, namely in the function polyhedron.contains()?
2. Is there a difference in the algorithm according to whether the V-polyhedron is a V-polytope or is unbounded?
Thank you, and best regards,
GuillermoguillermoTue, 22 Oct 2019 11:42:20 +0200https://ask.sagemath.org/question/48462/Problem of m travelling salesmen (TSP) in Sage. [Linear programming]https://ask.sagemath.org/question/46781/problem-of-m-travelling-salesmen-tsp-in-sage-linear-programming/I have to solve problem of m TSP's by linear programming.
Distances are euclidean, so one of good solutions is when only one salesman visits all the cities.
This is the solution i get when running that program (start city is city number 8, so it is 7th in sage cause we count from 0):
This is link to my program in Cocalc [comments are in Polish]:
- https://share.cocalc.com/share/88eb1fdd-546a-48ea-80b3-c63b047adfa8/kopiasage.ipynb?viewer=share
After running this, i get solution with 1 salesman. However, if in two constraint in for I change <=2 to ==2; that change requires putting 2 salesmen on the battlefield. However, my program still does solution with only one.
Why? In another worksheet I did also with 3, and also I got only 1 salesman when doing ==3 instaed of <=3 in constraints.
I program in Cocalc, not in SageMath installed on PC.
By the way, that forum has extremely annoying captcha - I spent 10 minutes doing it, bcs it always was saying that i picked wrong images....MaciejFicekMon, 03 Jun 2019 22:24:32 +0200https://ask.sagemath.org/question/46781/can we use BFS and DFS algorithm in sagemath?https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/ hello,
I want to color the vertices of graphs using greedy or BFS algorithm. can do that in sagemath?
NagarjunWed, 09 Jan 2019 12:18:58 +0100https://ask.sagemath.org/question/44970/Set Covering Algorithmhttps://ask.sagemath.org/question/38764/set-covering-algorithm/ Is there a Sage implementation of the Set Covering Algorithm?
Thanks in advanceAntonioSat, 09 Sep 2017 01:02:27 +0200https://ask.sagemath.org/question/38764/Elements in the lattice $A_n$https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/Sorry in advance if this is not the right place to ask this simple question.
As it is usual, $A_n =\{ (a_1,\dots,a_{n+1}) \in\mathbb Z^{n+1}:a_1+\dots+a_{n+1}=0\}$. Now we define the norm
$$
\|(a_1,\dots,a_{n+1})\|:= \sum_{i:a_i>0} a_i.
$$
I would like an algorithm with input $(n,k)$, that returns all elements in $A_n$ with norm equal to $k$.
For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.
For $n=2$ and $k=2$, we have $(2,0,-2), (2,-1,-1), (2,-2,0), (1,1,-2), (1,-2,1), (0,2,-2), (0,-2,2), (-1,2,-1), (-1,-1,2), (-2,2,0), (-2,0,2)$.
emiliocbaTue, 19 May 2015 12:57:50 +0200https://ask.sagemath.org/question/26873/division algorithmhttps://ask.sagemath.org/question/37581/division-algorithm/
Hello,good morning! I am a beginner in the Sagemath program, can you give me a little help?
How can I write a program that, given two polynomials p (x) and g (x), determines the
Quotient and the remainder of the division of p (x) by g (x). Not being able to use the functions p // g or p% g, but can use the predefined functions
.lc (), .degree (), .is unit ().MathematicFri, 12 May 2017 13:06:52 +0200https://ask.sagemath.org/question/37581/Error with .cardinality(algorithm='sae') for elliptic curvehttps://ask.sagemath.org/question/26761/error-with-cardinalityalgorithmsae-for-elliptic-curve/Hello please i have a problem. I have already defined an elliptic curve over a ring `Zn` and i want to compute its cardinality but i can not use `.cardinality(algorithm='sae')`. Thank you.
Here is the programme that i want to implement.
def cardin(n,A,B)
Z = Zmod(n) # n is not a prime then Z is a ring
E = EllipticCurve(Z,(A,B))
return E.cardinality(algorithm='sae') "sae=Schoof Atkin"
TypeError: cardinality() got an unexpected keyword argument 'algorithm'kotorakotoFri, 08 May 2015 17:11:39 +0200https://ask.sagemath.org/question/26761/Elliptic curve scalar multiplication algorithmhttps://ask.sagemath.org/question/32886/elliptic-curve-scalar-multiplication-algorithm/ I'm doing a prespective on supersinguar elliptic curves. I was wondering how saga calculates scalar multiplications? Does it just calculate it naively or does it use succesive doubling as default? Til is most interesting since there are well known ways of making "shortcuts" when oberating with supersingular curves, but does sage use these?BelphegorFri, 25 Mar 2016 14:41:10 +0100https://ask.sagemath.org/question/32886/Code stopped compiling out of nowhere for no apparent reasonhttps://ask.sagemath.org/question/30649/code-stopped-compiling-out-of-nowhere-for-no-apparent-reason/ Sage has all of a sudden stopped compiling my code. It happened seemingly out of nowhere and im getting very worried because i spent ALOT of time writing an algorithm. Basically nothing happens when i run the code the long grey line comes up with a green bar flashing and the normal output rectangle but it jsut stays in that state permanently. Nothing seems to fix the problem, i've tried going back in the history, copying and pasting to a new folder and worksheet changing the code, trying to get literally anything to compile but to no avail. Im literally dumbfounded at the moment.
EDIT: The green loading bar actually seems to be appearing at the top of the code when i try to compile. Also, I dont know if length is ever an issue with Sage Math worksheets but my code is 235 lines if that helps at all.
EDIT 2: I am using SageMathCloud via. the link on sagemath.org, my web browser is google chrome, the code is written in a SageMath Worksheet, just in case my OS is Windows 10, here is a link to the code itself [Problematic Code](http://pastebin.com/8A02NJau).lolWhoCaresThu, 12 Nov 2015 01:50:03 +0100https://ask.sagemath.org/question/30649/Hierholzer's algorithmhttps://ask.sagemath.org/question/26643/hierholzers-algorithm/ Hi, I have a question, I need to implement Hierholzer's algorithm but I don't know how to start it.
The conditions are:
We started with a vertex v of the graph and either we build a ride (one way) with new edges (not previously used) until we reach a vertex in which no edges remain unused. That vertex v must necessarily, because this ride to reach any other vertex (for the first time or several times), will have used an odd number of edges that come together in him (and, by hypothesis, each vertex has degree par - called degree of a vertex the number of edges that meet in him--). So we have obtained a closed $ C $ promenade that no repeated edges. But perhaps C does not contain all edges of G.
If there are edges go, consider the graph G 'that formed from G by removing the edges Ride C (and possible vertices that have been cut). Note that G 'is still satisfy the parity condition grades. Some of the edges of this new graph must have in common a vertex, say w, with the ride C (because G is connected). Now we take w as a new origin with the previous argument, form a closed C ride 'in G' that no repeated edges, and which is attached to C (at least) by w. Redefining now C "inserting" C "in the first vertex have in common.
And we repeat the procedure: either we have included all the edges, or locate an edge with a vertex in common with this new C.
The process ends when you have used all the edges.rocrosnajarSat, 25 Apr 2015 20:05:58 +0200https://ask.sagemath.org/question/26643/Finding the maximum of a parameterhttps://ask.sagemath.org/question/23724/finding-the-maximum-of-a-parameter/I was trying to use integrals, in order to find the average radius. What I did was I took a function, like $$f'(x,y)$$, and then I replaced f'(rcos(theta),rsin(theta)). Then I replaced r with y, and theta with x.
This was divided into the positives above the x-axis, and the negatives below. Using computer programming I got used it all inorder to find the area under the positive curve.
var('n a b x y s u v A')
n = 5100
a = 0
b =2*pi
h =(b-a)/n
s =0
for i in range(n):
x = a + i*h
s = s +find_root((y*cos(x)+u)^2)/4+((y*sin(x)+v)^2)/9-1,1.9,3.1)
A= float((b-a)/n*s)
Where a is the start of the integral, b is the end of it, h is the intervals for the integral, s is the root to identify the region for integration, the float is the summation,A is the area, and u and v are parameters.. Note: This is an **2-D implicit function**, you can't use a direct integral, but you can use the definition.
I'm trying to use the co-ordinates to find the maximum of u, and v in terms of A, or the area. I would like to find the co-ordinates of the maximum that comes out of this function.
You can think of it as
$$x=u$$
$$y=v$$
$$z=A$$.
I tried this (at the very top of this post) on sage, but it gave...
Error in lines 7-9
Traceback (most recent call last):
File "/projects/180e8f3c-9dc5-424f-abcc-5267257c0d31/.sagemathcloud/sage_server.py", line 736, in execute
exec compile(block+'\n', '', 'single') in namespace, locals
File "", line 3, in <module>
File "/usr/local/sage/sage-6.3.beta6/local/lib/python2.7/site-packages/sage/numerical/optimize.py", line 77, in find_root
return f.find_root(a=a,b=b,xtol=xtol,rtol=rtol,maxiter=maxiter,full_output=full_output)
File "expression.pyx", line 9685, in sage.symbolic.expression.Expression.find_root (build/cythonized/sage/symbolic/expression.cpp:42561)
NotImplementedError: root finding currently only implemented in 1 dimension.
19
Krishnan ArbujaFri, 08 Aug 2014 21:23:25 +0200https://ask.sagemath.org/question/23724/How to use Sage to find a pair of vertex-disjoint paths of minimal total length?https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/I want to find a pair of vertex-disjoint (s,t)-paths with minimal total length in a graph G, where the length is the sum of the edge weights of the paths. For this I would like to use the [Suurballe and Tarjan Algorithm](http://en.wikipedia.org/wiki/Suurballe%27s_algorithm"), but it seems to be a hidden (if I am right?) method. Is there any way I can still use this algorithm other than reprogram it myself?BartMon, 28 Jul 2014 15:15:00 +0200https://ask.sagemath.org/question/23609/Networkx algorithmhttps://ask.sagemath.org/question/10098/networkx-algorithm/Hi experts!
I know that shortest_path() function (Networkx ) uses Dijkstra algorithm.
What algorithm is based connected_components() function?
Waiting for your answers.
Thanks a lot.
Best regards!mresimulatorTue, 08 Oct 2013 16:20:59 +0200https://ask.sagemath.org/question/10098/Networkx algorithmhttps://ask.sagemath.org/question/10598/networkx-algorithm/Hi experts!
I know that shortest_path() function (Networkx ) uses Dijkstra algorithm.
What algorithm is based connected_components() function?
Waiting for your answers.
Thanks a lot.
Best regards!mresimulatorTue, 08 Oct 2013 16:18:10 +0200https://ask.sagemath.org/question/10598/Line segments instersection algorithmhttps://ask.sagemath.org/question/10497/line-segments-instersection-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-stick' path.
Any idea for that?
Thanks a lot!
mresimulatorSun, 01 Sep 2013 19:53:07 +0200https://ask.sagemath.org/question/10497/speed up execution time of script (Cython or other...)https://ask.sagemath.org/question/10407/speed-up-execution-time-of-script-cython-or-other/Hi experts!
I have a TOSHIBA laptop with next specifications:
4x Intel core i3 CPU M350 2.27GHz
3gb RAM
I write a script of Monte Carlo simulation that work fine, but i would speed up it.
How can I speed up the execution time of my algorithm?
I heard about Cython, but I dont know what it is and if that works for my goal (speed up algorithm)
Please explain step by step (im a totaly newby...)
Waiting for your answers.
Thanks a lot.
mresimulatorSat, 03 Aug 2013 10:46:18 +0200https://ask.sagemath.org/question/10407/Number of line segments in a group - algorithmhttps://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/Hi experts!
Im a newby SAGE, SciPy, Numpy and Python user.
I'm trying to write an algorithm that accounts for how many straight segment groups ('clusters') of a given dimension (dimension = number of lines that form the cluster).
Each line in my algorith is random-generated and characterized by his start point (xi,yi) and his end-point (xf,yf).
For example, in the image attached
http://subefotos.com/ver/?8818abc218ccd909f8c0bba71446c3b5o.png
there are: one cluster formed by 9 line segments, one cluster consists of four line segments, one cluster consists of five line segments, two cluster formed by three line segments, four cluster formed by two line segments and one cluster consists of one single line segments.
Until now i only could write a code that generates a matrix of NxN (where N = total number of line segments ). In this matrix, the element located in row A column B is 'True' if the segment A is cut with segment B, and its value is 'False' if that two segments are NOT intersect.
¿Any idea?
Waiting for your answers.
Thanks a lot!
mresimulatorTue, 18 Jun 2013 15:39:38 +0200https://ask.sagemath.org/question/10252/Sympy integration algorithm towards -infinityhttps://ask.sagemath.org/question/8653/sympy-integration-algorithm-towards-infinity/Following achrzesz [hint](http://ask.sagemath.org/question/1078/interactive-question-in-notebooks) about integral's algorithm option, I tried (Sage 4.7.2):
integral(1/x^2, x, -infinity, -1, algorithm='sympy')
Unfortunately, I got:
Traceback (click to the left of this block for traceback)
...
AttributeError: 'MinusInfinity' object has no attribute '_sympy_'
What's going wrong?Green diodSat, 21 Jan 2012 19:00:39 +0100https://ask.sagemath.org/question/8653/Euclidean algorithmhttps://ask.sagemath.org/question/9760/euclidean-algorithm/Hi,
I wrote these commands in sage to have Euclidean algorithm but I only get an error.. what is the problem of this algorithm?
r=a%b
print (a,b,r)
while r != 0:
a=b; b=r
r=a%b
print (a,b,r)
by the way how can I create a file named euclid.sage and save the above command in it?NedaFri, 29 Mar 2013 07:23:51 +0100https://ask.sagemath.org/question/9760/Rational reconstruction in ring of integershttps://ask.sagemath.org/question/9586/rational-reconstruction-in-ring-of-integers/I was wondering how to do the following in sage: let's say I have a number field $F$, an embedding $i$ of that field in the complex numbers, and an algebraic integer $\alpha\in F$, for which I know $i(\alpha)$ with good numerical precision. How can I find the exact value?SnarkTue, 25 Dec 2012 15:14:36 +0100https://ask.sagemath.org/question/9586/Univariate Polynomial Multiplicationhttps://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/What algorithms does sage use for univariate polynomial multiplication?
In particular, I am curious about the algorithm used for multiplication over finite fields and polynomials with coefficients in Z or Q.
More generally, is there an easy way to look under the hood and trace down the exact functions being called in the event I have a question like this again?mathmajorThu, 21 Jul 2011 18:30:28 +0200https://ask.sagemath.org/question/8241/