graph theory commands for Giac

Librairie C++ de calcul formel/ C++ symbolic computation library

Modérateur : xcasadmin

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » mar. oct. 09, 2018 5:45 pm

Yes, using select is a solution, I forgot about it, thanks!

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » ven. oct. 12, 2018 5:04 pm

Back to the graph theory commands, now I remembered having corrected few typos in the manual few days ago, can you please update?
The files are now here: https://github.com/marohnicluka/giac

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » sam. oct. 13, 2018 5:58 am

Thanks! That will indeed be easier for me.

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. nov. 18, 2018 3:24 pm

There is an update of graphtheory.cc/h and graphe.cc/h:
* fixed some bugs
* st-ordering now optionally parametrizable, letting user to control the length of the longest path in the corresponding DAG.
* clique_stats now optionally lists all maximal cliques, sorted by size.
* added bellman_ford command which finds shortest path in weighted (di)graph (it accepts negative weights so it's more general than dijkstra).
* the docs are updated accordingly.

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » mar. nov. 20, 2018 8:02 am

Something's wrong with charpoly command, when I input

Code : Tout sélectionner

G:=graph("mcgee");
charpoly(G,x)
I get

Code : Tout sélectionner

x^24-2320472437043855012790056*x^22-806701636645395553936764*x^21+1359501168309792938078699*x^20-1938012298650297670297103*x^19-4534884549564777526815607*x^18+2336542190219622512964151*x^17+793846205601941791458846*x^16-3731396778686636913738360*x^15-1719465303177852483561508*x^14-4769503251775710115859734*x^13-1292003678150528067945302*x^12-2738284346275211196411716*x^11+1131303344151298804358165*x^10+1555547780753350343422067*x^9-1234151003867639907026582*x^8-874188846581278546457148*x^7-1542697457796036532359512*x^6-5039477696001094009168952*x^5+1722676406735577567439314*x^4-2159775057407850568985592*x^3
which is not correct, the commands

Code : Tout sélectionner

A:=adjacency_matrix(G);
collect(det(A-idn(24)*x))
give the correct answer:

Code : Tout sélectionner

x^3*(x+1)^2*(x+2)*(x-2)^3*(x-3)*(x^2+x-4)*(x^3+x^2-4*x-2)^4

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » mar. nov. 20, 2018 1:09 pm

Indeed, using pseudo-mod division is incorrect in Danilevsky algorithm here. I will disable this small speedup. Too late for stable 1.5.0-17, will be in 1.5.0-19...

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » mar. nov. 20, 2018 2:21 pm

Fixed in Xcas for Firefox.

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. déc. 30, 2018 3:26 pm

Hi,
I committed some new updates and fixes just now.
* fixed a bug in is_hamiltonian, the degree sequence was not initialized
* hardcoded 10 new special graphs
* added missing entry for minimum_cut in aide_cas
* updated the documentation

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. déc. 30, 2018 3:27 pm

By the way, when will nauty be available in Giac/Xcas for Linux and Windows?

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » dim. déc. 30, 2018 3:50 pm

For Linux, the debian 9 package is compiled with nauty. For windows, it is not straightforward because the nauty tarball compiles to executables, and not to a library.

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. déc. 30, 2018 3:58 pm

Indeed, I installed 1.5.0-31 from deb file and nauty is working fine.
As for the Windows problem, could nauty be called as a child process? I could help coding this workaround.

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » dim. déc. 30, 2018 4:18 pm

I don't think it will be required. I ran ranlib nauty.a then I copied nauty.a to /usr/local/lib/libnauty.a, made a few change to Makefile.win64 to include nautywrapper.o and link to libnauty.a and it compiles. Can you give a short commandline to check if it's ok?

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. déc. 30, 2018 5:10 pm

Great! Here's a commandline:

Code : Tout sélectionner

is_isomorphic(kneser_graph(5,2),petersen_graph(5,2)) => true

parisse
Messages : 5082
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: graph theory commands for Giac

Message par parisse » dim. déc. 30, 2018 7:58 pm

I have updated the windows 64 bits version, let me know if it's ok!

lukamar
Messages : 294
Inscription : ven. juin 30, 2017 9:55 am
Localisation : Zagreb, Croatia

Re: graph theory commands for Giac

Message par lukamar » dim. déc. 30, 2018 9:40 pm

Unfortunately, Xcas crashes in win7 with the above commandline...

Répondre