Le forum de XCAS

Hello Bernard,

since Giac has no support for graph theory, I decided to facilitate it by making a free replacement of Graph Theory package in Maple, which seems syntactically suitable and extensive enough. My project is hosted here: https://github.com/marohnicluka/graph-theory. Right now it is fairly usable package with over 100 commands already implemented and few more left to go. The implemented commands seem to work fine according to my tests. The library is quite lightweight and it requires no dependencies outside Giac. Everything is coded from scratch.

Making this package a part of Giac is easy. If you're interested, we can discuss the details. Let me know what you think.

Luka

Wow! That would indeed be wonderful to have these functions builtin in giac, let's integrate your code!

Great, here are things that have to be done:

1. Each graph is stored as a "graphe" class object while working with it internally. When a command that creates or modifies a graph is done, the graphe object is converted to a gen object, more precisely a vector holding all vertices and their adjacency lists, as well as all vertex, edge and graph attributes, and returned to the user. Conversely, the commands accepting graph as an argument will convert the gen back to graphe object To avoid printing such a large gen structure out in Giac/Xcas each time it's returned and to output some short meaningful info instead, I propose to add a new vector subtype, namely _GRAPH__VECT with the value 30 (for now defined in line 42 in graphe.h), which is assigned to every gen graph object. The function "is_graphe", defined in line 56 of "graphtheory.h", is used to detect whether a gen holds a graph. It is called with a string pointer &disp in which the basic info on the graph is written (is the graph directed or weighted, followed by the number of vertices and edges, as in Maple). Therefore, somewhere in the Giac code, where the decision of how to display an expression is made, you should include a call to "is_graphe" on the expression and display the string disp if it returns true. I don't know where that code portion is located, but I believe that it shouldn't be a problem.

2. enum items defined in line 44 of "graphe.h" should be moved to dispatch.h, They represent values of options needed for some commands. These options are 'connected', 'spring', 'tree', 'planar', 'directed', 'weighted' and 'weights'.

3. Only graphe.h/cc and graphtheory.h/cc files need to be included in Giac source. Lines 42--52 (inclusively) in graphe.h need to be deleted as they will be contained in dispatch.h. Also, you may remove the demo sections (at the end of graphtheory.h/cc files) as they're massive and actually not needed, I used them to test the commands and remove some bugs (most of them, I hope).

4. It would be nice if 2D graph drawings could be automatically displayed orthonormalized and with axes hidden. Is that kind of automatic configuration possible? (However, it's not so important.)

I think that's all. I forced the compiler to work with respect to the c++98 standard, so you shouldn't have problems compiling the code. As soon as you release the new unstable version of Giac/Xcas containing the new code, I will do more testing and write some documentation along the way. I plan to present some algorithms in detail, in particular for graph drawing, for which Giac now has a fairly strong support.

The commands waiting to be implemented are commented out in graphtheory.h. I will add them in near future, I think we could have the complete and bug-free package by the fall.

I have added two more commands, _topological_sort and _is_acyclic to graphtheory.cc (revision 63), but now the program test.cc segfaults after returning from main. That could mean the stack is messed up, but it actually does so even if I don't call any command from main. However, when I comment out the lines 3968--4004 in graphtheory.cc (where the new commands are defined) the program does not segfault (again, with an empty main function). I don't get this, why is it happening? The program compiles and works fine in any case...

Here's the backtrace from gdb:

Program received signal SIGSEGV, Segmentation fault.
__cxa_finalize (d=0x555555838008) at cxa_finalize.c:41
41 cxa_finalize.c: No such file or directory.
(gdb) bt
#0 __cxa_finalize (d=0x555555838008) at cxa_finalize.c:41
#1 0x000055555555df23 in __do_global_dtors_aux ()
#2 0x00007fffffffde90 in ?? ()
#3 0x00007ffff7de5b73 in _dl_fini () at dl-fini.c:138
Backtrace stopped: frame did not save the PC

That's because the max number of user commands is hardcoded (1600). I will change this to 1700 (perhaps more?).

Thanks for solving the issue. Well, only 40 more commands are planned to be implemented in graphtheory.cc, so I think 1700 is OK for now.

I will set it to 1800 just for safety.
By the way, have you got a few commandlines to test ?

I made debian 9 packages here:
https://www-fourier.ujf-grenoble.fr/~pa ... _amd64.deb
https://www-fourier.ujf-grenoble.fr/~pa ... _amd64.deb

Changes made in the source:
* _GRAPH__VECT set to 31 (30 already used)
* headers include <giac/...> to "..."
* added #include "giacPCH.h" at the beginning of graphe.cc and graphtheory.cc
* typedef unsigned long ulong; in graphe.h (for emscripten compilation)

Thank you very much for the binaries. I will post short help for the commands today or tomorrow and I'll include some examples there.

I installed the new binaries, but giac segfaults if I try to call any of the new commands. What could be the problem?

Can you give a commandline that segfaults?

Apparently it segfaults for any command that includes a call to any of the new functions. The simplest example is:

I think I know why, I added #include "giacPCH.h" after updating the source where the deb was compiled. I will update the deb packages soon, the web version should work.

The web version works fine indeed!