graph theory commands for Giac

[parisse]

The debian 9 binaries should be updated, graph(1) does not segfault anymore.

[jocaps]

@lukamar: I think this is a great development. Thank you for the implementation.

Is there an implementation for checking isomorphic graphs as well? If so, any way to compare it with known implementations (e.g. naughty).

Jose

[lukamar]

Thank you Jose, the implementation of checking graph isomorphism is planned but not yet implemented, I haven't tackled the problem yet at all, so I'll appreciate any idea of how to do it best. I know it's a difficult problem. In the worst case the algorithm will be a naive one (with a high complexity), based on checking graph invariants, if all known algorithms are too complex.

[lukamar]

I've written short help for the commands, they're located in the "doc" directory. It is meant to be appended to the "aide_cas" file. Also, I've mirrored all changes made before inclusion to the Giac source so that changing the headers every time is not needed. I've also fixed a couple of bugs affecting some commands.
There are however some issues in the latest Xcas binaries.
1. Firefox interface prints the string created by the "is_graphe" function and displays it properly, but Xcas displays the gen structure as if the "is_graphe" hasn't been called at all.
2. The enum move_to_dispatch_h in "dispatch.h" may be removed, and its elements included at the end of maple_conversion enum:

Code : Tout sélectionner

_GT_CONNECTED = 142, // connected
_GT_SPRING = 143, // spring
_GT_TREE = 144, // tree
_GT_PLANAR = 145, // planar
_GT_DIRECTED = 146, // directed
_GT_WEIGHTED = 147, // weighted
_GT_WEIGHTS = 148 // weights

How to make these numbers assigned to keywords "connected", "spring", "tree" etc. in Xcas? These are the options for some commands.
3. When displaying graph drawings, edges are not displayed, only vertices and labels are. However when outputted to cout and copied in Xcas, everything works. Edges are created by adding symbolic(at_segment,...) and arcs by adding symbolic(at_vector,...) to the list containing all geometrical objects comprising the graph. Why are these not displayed? Here's an example:

Code : Tout sélectionner

draw_graph(complete_graph(5))

4. Xcas crashes on executing the following command:

Code : Tout sélectionner

draw_graph(digraph(10,0.1))

The command gives the expected results in my project.

[lukamar]

@jocaps: this algorithm seems like a good candidate for implementation, but I still have to read the paper carefully.
https://www.microsoft.com/en-us/researc ... re2013.pdf
Mendivelso J., Kim S., Elnikety S., He Y., Hwang S., Pinzón Y. (2013) Solving Graph Isomorphism Using Parameterized Matching. In: Kurland O., Lewenstein M., Porat E. (eds) String Processing and Information Retrieval. SPIRE 2013. Lecture Notes in Computer Science, vol 8214. Springer, Cham

[parisse]

Some answers and remarks:
1. The giacPCH.h include should be included first in the C++ files. I have also fixed the .h headers, begin with:

Code : Tout sélectionner

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "first.h"

2. Adding new keywords for integers values should be done in lexer_tab_int.h

3. Edges are not displayed because segment/vector/... must be evaled. You can do that by calling _segment(makesequence(...),contextptr) instead of the inert symbolic form in graphe::append_segment

4. I get a Bad argument type error, not a crash.

[lukamar]

Sorry Bernard, I've indicated the wrong command. The problematic one is

Code : Tout sélectionner

draw_graph(random_digraph(10,0.1))

Actually I also get the segfault, so it's possible related to my code, but I can't find the problem and don't understand the backtrace.
I have changed the lexer_tab_int.h file, adding the new options after lp_ ones. The file is attached below.
Adding edges to the drawing is now fixed and graphs should be displayed properly.
I've changed the order of the headers in my source as you specified. However, now my example program crashes before entering main. It probably has something to do with the header inclusion order. Here's the minimal main.cpp:

Code : Tout sélectionner

#include "giacPCH.h"
#include "giac.h"
#include "graphtheory.h"

int main(){
  return 0;
}

The newest revision of my code contains your ordering of headers nevertheless. Can you check if it's correct?

[parisse]

The new ordering seems correct for inclusion in the library. Perhaps it does not work for some strange reason if you write a standalone executable...
For drawings, can you check that the points are also evaluated?

The segfault happens at line 5802 in graphe.cc,

Code : Tout sélectionner

double phi1=adj_phi[j==0?n-1:j-1],phi2=adj_phi[j%n];

because j=0 and n=0, hence n-1 is too large (if you put a breakpoint, this happens the 5th time).

[lukamar]

I've changed inclusion of vertices and labels, now _point ad _legende are called, not symbolic(at_point,...), symbolic(at_legende,...).
Thanks for locating the cause of the segfault, I think the problem happens because the graph has isolated vertices, so label placement algorithm gets confused (it tries to place the label to avoid the edges). I'll fix that.

[lukamar]

By the way, here's the backtrace of the segfault occurring immediately after running my standalone program:

Code : Tout sélectionner

/lib/x86_64-linux-gnu/libc.so.6(+0x70bfb)[0x7f08cac3ebfb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76fc6)[0x7f08cac44fc6]
/lib/x86_64-linux-gnu/libc.so.6(+0x773b8)[0x7f08cac453b8]
/lib/x86_64-linux-gnu/libc.so.6(+0x78dfa)[0x7f08cac46dfa]
/lib/x86_64-linux-gnu/libc.so.6(__libc_calloc+0x27b)[0x7f08cac49b7b]
/lib/x86_64-linux-gnu/libc.so.6(+0x35b40)[0x7f08cac03b40]
/lib/x86_64-linux-gnu/libc.so.6(__cxa_atexit+0x19)[0x7f08cac03be9]
/usr/lib/libgiac.so.0(+0x25e7b5)[0x7f08cbceb7b5]
/lib64/ld-linux-x86-64.so.2(+0xf85a)[0x7f08cd87c85a]
/lib64/ld-linux-x86-64.so.2(+0xf96b)[0x7f08cd87c96b]/lib/x86_64-linux-gnu/libc.so.6(+0x70bfb)[0x7f08cac3ebfb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76fc6)[0x7f08cac44fc6]
/lib/x86_64-linux-gnu/libc.so.6(+0x773b8)[0x7f08cac453b8]
/lib/x86_64-linux-gnu/libc.so.6(+0x78dfa)[0x7f08cac46dfa]
/lib/x86_64-linux-gnu/libc.so.6(__libc_calloc
/lib64/ld-linux-x86-64.so.2(+0xc5a)[0x7f08cd86dc5a]

Does it help to detect the problem?

[lukamar]

I fixed the bug in vertex labels placement algorithm, now the command 'draw_graph(random_digraph(10,0.1))' should not segfault anymore.

[parisse]

Bug fixed indeed!
I checked your simple test program, but it runs for me. The stacktrace does not help, all frames are in the system libraries...

[lukamar]

Why giac can't be installed in debian 9 without apt-get making complaints about missing packages? After enabling the stable branch for giac in /etc/apt/sources.list and running apt-get update && apt-get install giac, I get:

Code : Tout sélectionner

The following packages have unmet dependencies:
 giac : Depends: libjpeg8 (>= 8c) but it is not installable
        Depends: libpng12-0 (>= 1.2.13-4) but it is not installable
        Depends: libreadline6 (>= 6.0) but it is not installable
        Recommends: python3-giacpy but it is not going to be installed
        Recommends: python-giacpy but it is not going to be installed
        Recommends: libao-dev but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

I got past this error by enabling wheezy backports, but I'm not sure that's the best way to do it.
Maybe this has something to do with my problems with standalone program?
Things worked at first, but apparently something changed in my system since then, I don't know what.

[lukamar]

I've made a test program consisting only of the file giactest.cc:

Code : Tout sélectionner

#include "giac/giacPCH.h"
#include "giac/giac.h"
#include <sstream>

using namespace std;
using namespace giac;

int main() {
gen g;
stringstream ss;
ss << "[1,2,3]";
ss >> g;
cout << g << endl;
return 0;
}

This program compiles fine with

Code : Tout sélectionner

g++ -g -Wall giactest.cc -lgiac -lgmp

and runs at expected, but segfaults in the end, this is the backtrace:

Code : Tout sélectionner

#0  0x0000555555554f88 in giac::gen::~gen (this=0x7fffffffe140, 
    __in_chrg=<optimized out>) at /usr/include/giac/gen.h:692
#1  0x0000555555554e52 in main () at giactest.cc:9

This is with the latest Xcas binaries installed (rev. 63)

[parisse]

The stable and testing repositories are for older debian. For debian 9, you must install by hand (I mean with dpkg from the .deb on my web page).
For the standalone binary, does it work if you add -DHAVE_CONFIG_H?