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 » mer. sept. 12, 2018 4:25 pm

By the way, here's the aide_cas file with corrected list of graph theory commands.
There's no need to change any of the French translations.

Edit: added the missing entry for random_sequence_graph
Pièces jointes
aide_cas-corr2.zip
(186.46 Kio) Téléchargé 38 fois
Dernière modification par lukamar le jeu. sept. 13, 2018 8:36 am, modifié 2 fois.

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

Re: graph theory commands for Giac

Message par lukamar » mer. sept. 12, 2018 5:16 pm

Newly fixed bugs (discovered by running the examples one by one):
* in sequence_graph (Havel-Hakimi algorithm). It prevented the command from working properly.
* a minor one in circular graph drawing. Now the vertices are always drawn clockwise in sorted order, starting from the top.
* in is_planar, which led to a false assertion.
* in random_regular_graph, causing non-regular graphs to be returned.
* in to_gen, where custom attribute tags were stored as a vecteur, which did not copy properly. Now tags are simply inserted to main list, one after another.
* in tutte_polynomial, leading to a false assertion when weighted graph was provided.
* in draw_graph when a tree with specified root is drawn, the root is now selected correctly.
* in number_of_spanning_trees. An unnecessary conversion of the result to int and back to gen was causing a loss of precision.
* a minor one in traveling_salesman.

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

Re: graph theory commands for Giac

Message par lukamar » jeu. sept. 13, 2018 9:31 am

I fixed as many bugs as I could find. Now all examples work properly.

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

Re: graph theory commands for Giac

Message par lukamar » jeu. sept. 13, 2018 10:15 am

If anyone wishes to translate the manual, it's easy: one needs to copy the "doc" directory from my repository (https://github.com/marohnicluka/graph-theory) to the disk and open the file graphtheory-user_manual.tm in TeXmacs. It's quite comfortable to work in (when in "Papyrus" viewing mode) because it's wysiwyw and only paragraphs of text must be changed (math and examples not necessarily). TeXmacs supports a number of languages, has builtin spellcheck and it's easy to insert additional examples through Giac interactive sessions.

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

Re: graph theory commands for Giac

Message par parisse » jeu. sept. 13, 2018 12:11 pm

Thanks a lot!
I'm not ready to release a bug free stable 1.5.0 (I have some problems with short help on the Firefox version for example), I will probably release a 1.5.0 unstable tomorrow, and incrementaly fix things before a 1.5.0 stable release, you will therefore have some time to fix bugs if required...

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

Re: graph theory commands for Giac

Message par parisse » ven. sept. 14, 2018 3:08 pm

By the way, it would be a good idea to add graph-theory (and maybe also optimization and signal processing) commands in the doc/en/xcamenu file, so that the most important commands are visible from the menu, and you are probably the best one to select them.

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

Re: graph theory commands for Giac

Message par lukamar » lun. sept. 17, 2018 5:11 pm

I'll do that, just to finish some improvements for signal processing so I can do it all at once.

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

Re: graph theory commands for Giac

Message par parisse » mer. sept. 19, 2018 5:59 am

As reported by Frederic Han, there is a little fix to do:

Code : Tout sélectionner

diff graphe.cc graphe.cc~
4860d4859
< #ifdef HAVE_LIBGLPK
4861a4861
> #ifdef HAVE_LIBGLPK

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

Re: graph theory commands for Giac

Message par lukamar » mer. sept. 19, 2018 9:03 am

Fixed! Calling the constructor of painter class needed to be moved to #ifdef HAVE_LIBGLPK block. I hope it works now. The changed files are graphe.cc and graphe.h.

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: graph theory commands for Giac

Message par frederic han » ven. sept. 21, 2018 2:02 pm

Btw, I am trying to build the giac.dll with mingw (for instance for giacpy) with glpk and nauty.
for glpk I had to add --disable-reentrant on configure to have a successfull built. Is it a problem?

Do you have some examples either for icas or giacpy that test if these 2 deps works properly?

Frederic

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

Re: graph theory commands for Giac

Message par lukamar » sam. sept. 22, 2018 9:35 am

Disabling reentrancy should not cause problems.
Here are some test examples for icas:

Code : Tout sélectionner

chromatic_number(graph("petersen")) => 3
graph_automorphisms(cycle_graph(3)) => list[[[1,2]],[[0,1]]]
canonical_labeling(path_graph(3)) => [0,2,1]
is_isomorphic(graph(trail(1,2,3,4,5,6,1,5)),graph(trail(1,2,3,4,5,6,1,3))) => true
The first example tests whether GLPK is working, the other three are for nauty.

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

Re: graph theory commands for Giac

Message par lukamar » sam. sept. 22, 2018 6:54 pm

I've noticed (just now) that Xcas 1.5.0-1 from testing is apparently built without nauty...
Bernard, can you check the configuration?
By the way, GLPK works fine.

The graphtheory source is recently updated, I fixed a bug in read_gen and changed the type of adjacency lists to std::set<int>.

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

Re: graph theory commands for Giac

Message par parisse » sam. sept. 22, 2018 7:06 pm

nauty should be linked with the debian 9 packages https://www-fourier.ujf-grenoble.fr/~pa ... _amd64.deb and https://www-fourier.ujf-grenoble.fr/~pa ... _amd64.deb
It is not linked in the unstable repositories, they are using old debian distributions where nauty is not packaged (and would perhaps not be compatible), I'm planning to move to debian 9 for the stable 1.5.0 repository (at least for amd64).

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

Re: graph theory commands for Giac

Message par lukamar » dim. sept. 23, 2018 1:38 am

Thanks, it works

I pushed another commit to the source, vertex deletion needed some fixing.
Edit: also fixed a minor bug in traveling salesman (Hamiltonian tours were misinterpreted as subtours in small graphs).

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: graph theory commands for Giac

Message par frederic han » dim. sept. 23, 2018 7:51 pm

lukamar a écrit :
sam. sept. 22, 2018 9:35 am
Disabling reentrancy should not cause problems.
Here are some test examples for icas:

Code : Tout sélectionner

chromatic_number(graph("petersen")) => 3
graph_automorphisms(cycle_graph(3)) => list[[[1,2]],[[0,1]]]
canonical_labeling(path_graph(3)) => [0,2,1]
is_isomorphic(graph(trail(1,2,3,4,5,6,1,5)),graph(trail(1,2,3,4,5,6,1,3))) => true
The first example tests whether GLPK is working, the other three are for nauty.
Thanks, it looks to works, I have updated giacpy on Pypi.

Are you able to interrupt a long computation in nauty?

Répondre