[sage-devel] Enhancement of Kruskal Algorithmn

[hy15]

Hello guys,
I would like implement an enhancement of kruskal algorithm as provided 
in this paper http://algo2.iti.kit.edu/documents/fkruskal.pdf. 

This Algorithm gives an expected complexity of  O(E + Vlog(v)*log(E/V) 
where E is number of edges and V be number of edges. This Algorithm works 
quite well for large and dense graph. After seeing source code of MST, the 
code had a TODO task under 
 kruskal function. Any suggestions ?

-- 
*Disclaimer: *This email and any files transmitted with it are confidential 
and intended solely for the use of the individual or entity to whom they 
are addressed. If you have received this email in error please notify the 
system manager. This message contains confidential information and is 
intended only for the individual named. If you are not the named addressee 
you should not disseminate, distribute or copy this e-mail. Please notify 
the sender immediately by e-mail if you have received this e-mail by 
mistake and delete this e-mail from your system. If you are not the 
intended recipient you are notified that disclosing, copying, distributing 
or taking any action in reliance on the contents of this information is 
strictly prohibited.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Jeroen Demeyer]

On 2019-03-08 19:18, Volker Braun wrote:

* If  is optional then add a #warning that it is recommended


Yes, it's optional but the hard part is figuring out whether it's 
supported or not.


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: efficiency in creating multivariate polynomial rings [Re: [sage-devel] problem with scalar multiplication: polynomial and vector]

[Daniel Krenn]

On 01.03.19 03:59, Travis Scrimshaw wrote:> IMO we do not want there to
be too much of a distinction between
> multivariate polynomial rings in 1 variable and univariate
> polynomial rings. I would say the proper thing to do is to pass along
> the underlying implementation as part of the MPoly functor (which is
> what you proposed change is secretly doing).

Somehow. There is still a distinction between the Poly and the MPoly
functor.

> Although I don't currently see why this change leads to such a
> slowdown, but my guess is it is just taking a lot longer to do the
> coercion (checks). I would have to look into this in more detail than
> I have the time right now.

This would also be my guess, but not sure what can be done against that
(or how to find this).

Daniel

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] fix or not? [Re: efficiency in creating multivariate polynomial rings]

[Daniel Krenn]

The question remains: Do we want the change proposed in
  https://trac.sagemath.org/ticket/27364
fixing the mentioned issue (but introducing a slowdown) or not?

(I somehow tend to say "we want that", because the change obviously
fixes a bug. (It seems natural that the MPoly functor returns a MPoly
ring in all cases and that

>             sage: T = PolynomialRing(QQ, 't', 1); t = T.gen(); T
>             sage: F, R = T.construction()
>             sage: F(R) is T
>             True

is satisfied.

Daniel

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: efficiency in creating multivariate polynomial rings [Re: [sage-devel] problem with scalar multiplication: polynomial and vector]

[Daniel Krenn]

On 01.03.19 03:59, Travis Scrimshaw wrote:> IMO we do not want there to
be too much of a distinction between
> multivariate polynomial rings in 1 variable and univariate
> polynomial rings. I would say the proper thing to do is to pass along
> the underlying implementation as part of the MPoly functor (which is
> what you proposed change is secretly doing).

Somehow. There is still a distinction between the Poly and the MPoly
functor.

> Although I don't currently see why this change leads to such a
> slowdown, but my guess is it is just taking a lot longer to do the 
> coercion (checks). I would have to look into this in more detail than
> I have the time right now.

This would also be my guess, but not sure what can be done against that
(or how to find this).

Daniel

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Linux build fails on sagelib (and numpy?)

[Dima Pasechnik]

On Fri, Mar 8, 2019 at 5:29 PM Michael Orlitzky  wrote:
>
> On 3/7/19 10:34 PM, Ike Stoddard wrote:
> > Do you have/know a developer working on it? Shell or m4 or whatever to
> > fold detection in?
> > The authors of these packages ought to have canonical tests for
> > existence/version that can be included.
>
> For C and C++ libraries, autoconf provides most of what you need
> already. If you want *any* version of a library, then it might suffice
> to check for the headers that you #include in your own program. The
> AC_CHECK_HEADER macro can do that.
>
> If you need a specific version, then usually that's because you want a
> function that appeared in the new version. In that case, it's best to
> test for the existence of the function rather than the version number.
> The AC_SEARCH_LIBS macro can do that.
>
> A good example for those two macros is the following:
>
> https://git.sagemath.org/sage.git/commit?id=20c3d7a1b87cf650dcec54133d9f9cee05e82677
>
> In essence that whole macro is very simple if you can ignore the
> compile-test in the middle.
>
> The "modern" way to do an existence/version check is through pkg-config.
> Not everyone integrates with pkg-config; but if they do, then autoconf
> has a PKG_CHECK_MODULES macro that can check for existence of specific
> versions.

An example on how to use PKG_CHECK_MODULES is in
https://github.com/sagemath/sage/blob/develop/build/pkgs/libffi/spkg-configure.m4
(we don't check the version, but if we wanted to, say, make sure it is
a least 1.2.3 we would have done
[libffi >= 1.2.3] instead of just [libffi])

>
> The "Autotools Mythbuster" at https://autotools.io/ is a good reference
> for this stuff, but none of them are perfect. You'll still need the
> official autotools docs, and a good bit of trial and error if my own
> experience is typical.
>
> --
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Volker Braun]

You only need MACOSX_DEPLOYMENT_TARGET / -mmacosx-version-min when building 
binaries to run on older mac versions. Whoever distributes cysignals should 
decide which min sdk version they support. What is bound to go wrong is 
that somebody builds an application that includes your library with their 
chosen MACOSX_DEPLOYMENT_TARGET, and the binaries don't work because some 
dependency thought it would be fun to require a higher version. And the 
distributor of the app (like Sage) typically doesn't have a basement full 
of old macs to test if the binaries really are downward compatible.

* If you definitely require  then just include it. Add a comment 
with the min sdk version for anyone hitting that #include error.

* If  is optional then add a #warning that it is recommended


-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Linux build fails on sagelib (and numpy?)

[Michael Orlitzky]

On 3/7/19 10:34 PM, Ike Stoddard wrote:
> Do you have/know a developer working on it? Shell or m4 or whatever to
> fold detection in?
> The authors of these packages ought to have canonical tests for
> existence/version that can be included.

For C and C++ libraries, autoconf provides most of what you need
already. If you want *any* version of a library, then it might suffice
to check for the headers that you #include in your own program. The
AC_CHECK_HEADER macro can do that.

If you need a specific version, then usually that's because you want a
function that appeared in the new version. In that case, it's best to
test for the existence of the function rather than the version number.
The AC_SEARCH_LIBS macro can do that.

A good example for those two macros is the following:

https://git.sagemath.org/sage.git/commit?id=20c3d7a1b87cf650dcec54133d9f9cee05e82677

In essence that whole macro is very simple if you can ignore the
compile-test in the middle.

The "modern" way to do an existence/version check is through pkg-config.
Not everyone integrates with pkg-config; but if they do, then autoconf
has a PKG_CHECK_MODULES macro that can check for existence of specific
versions.

The "Autotools Mythbuster" at https://autotools.io/ is a good reference
for this stuff, but none of them are perfect. You'll still need the
official autotools docs, and a good bit of trial and error if my own
experience is typical.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] HN discussion of Sage

[William Stein]

There is a short HN discussion of Sage here, that is possibly of interest:

https://news.ycombinator.com/item?id=19335269#19336424



-- 

Best Regards,
William Stein

CEO, SageMath, Inc.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Dima Pasechnik]

On Fri, Mar 8, 2019 at 2:00 PM Jeroen Demeyer  wrote:
>
> On 2019-03-08 10:42, Jeroen Demeyer wrote:
> > (*) For some reason, the analogous C header  works
> > regardless of MACOSX_DEPLOYMENT_TARGET. Unfortunately, this header is
> > not compatible with C++, so I really need .
>
> I just realized that I tried this only with g++ on Linux. With clang++
> on OS X,  does work. So this avoids needing to mess with
> MACOSX_DEPLOYMENT_TARGET.
>
> I'll also try g++ on OS X (do we still support that actually?).

no, I don't think it works since OSX 10.12 or even earlier---due to
changes in Apple's header files you'd need the compiler to know about
"blocks", at least for some spkgs.

>
> --
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Jeroen Demeyer]

On 2019-03-08 10:42, Jeroen Demeyer wrote:

(*) For some reason, the analogous C header  works
regardless of MACOSX_DEPLOYMENT_TARGET. Unfortunately, this header is
not compatible with C++, so I really need .


I just realized that I tried this only with g++ on Linux. With clang++ 
on OS X,  does work. So this avoids needing to mess with 
MACOSX_DEPLOYMENT_TARGET.


I'll also try g++ on OS X (do we still support that actually?).

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Samuel Lelievre]

Fri 2019-03-08 11:21:09 UTC+1, Dima Pasechnik:
>
> I gather openblas has moved to 10.8 from 10.6, see 
> https://github.com/xianyi/OpenBLAS/issues/1580 
>
> Realistically, 10.9 is OK too, I don't think it's actually possible to 
> build current Sage on anything older than 10.11 or so... 

Current Sage actually builds perfectly fine on older macOS,
in particular macOS 10.10.5 "Yosemite".

Of course, Apple no longer supports Yosemite, so it gets
no security upgrades and is therefore quite vulnerable,
so anyone using that or older is advised to upgrade...

Which reminds me we should really update the wiki page
where we list our supported platforms:

https://wiki.sagemath.org/SupportedPlatforms

There is a link to that page from the documentation;
I no longer dare to include that link in the new version
announcements sent to sage-announce.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Dima Pasechnik]

I gather openblas has moved to 10.8 from 10.6, see
https://github.com/xianyi/OpenBLAS/issues/1580

Realistically, 10.9 is OK too, I don't think it's actually possible to
build current Sage on anything older than 10.11 or so...

On Fri, Mar 8, 2019 at 9:42 AM Jeroen Demeyer  wrote:
>
> Hello,
>
> While working on cysignals, I encounted an issue with
> $MACOSX_DEPLOYMENT_TARGET. I have a fix, but I don't know if it's good.
> It's not specific to Sage, but it will affect Sage since cysignals is a
> Sage package.
>
> For cysignals, I'd really like to use MACOSX_DEPLOYMENT_TARGET >= 10.9
> since that enables the C++  header (*) which is needed to fix
> Sage ticket #24288. The tricky part is that not only cysignals itself
> should be compiled with MACOSX_DEPLOYMENT_TARGET >= 10.9 but also every
> package using cysignals.
>
> I have a solution which adds the command-line flag
> -mmacosx-version-min=10.9 when compiling cysignals:
> https://github.com/sagemath/cysignals/commit/17062a64bf5672375982cf295ed93b346b55d680
> Thanks to Cython magic, this flag will be passed on to every package
> that cimports cysignals.
>
> This solution seems to work and passes CI tests. These tests are done
> using Conda, which uses a Python compiled with
> MACOSX_DEPLOYMENT_TARGET=10.6, which is then used for every Python
> package (analogous to CFLAGS, distutils uses the value for
> MACOSX_DEPLOYMENT_TARGET which was used to compile Python).
>
> So my question is basically: what could possibly go wrong? One thing
> which worries me is that the command-line flag -mmacosx-version-min=10.9
> overrides the environment variable MACOSX_DEPLOYMENT_TARGET. So if
> somebody really wanted a higher value for MACOSX_DEPLOYMENT_TARGET than
> 10.9, it wouldn't work. But I see no solution for this.
>
>
> Jeroen.
>
>
> (*) For some reason, the analogous C header  works
> regardless of MACOSX_DEPLOYMENT_TARGET. Unfortunately, this header is
> not compatible with C++, so I really need .
>
> --
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] How to deal with MACOSX_DEPLOYMENT_TARGET in Python packages

[Jeroen Demeyer]

Hello,

While working on cysignals, I encounted an issue with 
$MACOSX_DEPLOYMENT_TARGET. I have a fix, but I don't know if it's good. 
It's not specific to Sage, but it will affect Sage since cysignals is a 
Sage package.


For cysignals, I'd really like to use MACOSX_DEPLOYMENT_TARGET >= 10.9 
since that enables the C++  header (*) which is needed to fix 
Sage ticket #24288. The tricky part is that not only cysignals itself 
should be compiled with MACOSX_DEPLOYMENT_TARGET >= 10.9 but also every 
package using cysignals.


I have a solution which adds the command-line flag 
-mmacosx-version-min=10.9 when compiling cysignals:

https://github.com/sagemath/cysignals/commit/17062a64bf5672375982cf295ed93b346b55d680
Thanks to Cython magic, this flag will be passed on to every package 
that cimports cysignals.


This solution seems to work and passes CI tests. These tests are done 
using Conda, which uses a Python compiled with 
MACOSX_DEPLOYMENT_TARGET=10.6, which is then used for every Python 
package (analogous to CFLAGS, distutils uses the value for 
MACOSX_DEPLOYMENT_TARGET which was used to compile Python).


So my question is basically: what could possibly go wrong? One thing 
which worries me is that the command-line flag -mmacosx-version-min=10.9 
overrides the environment variable MACOSX_DEPLOYMENT_TARGET. So if 
somebody really wanted a higher value for MACOSX_DEPLOYMENT_TARGET than 
10.9, it wouldn't work. But I see no solution for this.



Jeroen.


(*) For some reason, the analogous C header  works 
regardless of MACOSX_DEPLOYMENT_TARGET. Unfortunately, this header is 
not compatible with C++, so I really need .


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.