graph theory commands for Giac

[lukamar]

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

[lukamar]

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]

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

[lukamar]

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]

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]

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]

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

[parisse]

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]

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]

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]

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]

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]

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]

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]

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?