graph theory commands for Giac

[lukamar]

It worked! The compiler option -DHAVE_CONFIG_H was required indeed. Now i can also run graphtheory standalone program normally as before. Thanks!

[parisse]

Great! It's a real mess all these options, but unfortunately I don't know how to sort it.

[lukamar]

This template can be used to link to Giac 1.4.9 in Debian 9:

1. if Giac is already installed, skip to the step 5
2. enable wheezy backports (add "deb http://ftp.de.debian.org/debian wheezy main" to /etc/apt/sources.list)
3. add "deb http://www-fourier.ujf-grenoble.fr/~parisse/debian/ stable main" to /etc/apt/sources.list and optionally download the GPG key as explained in https://www-fourier.ujf-grenoble.fr/~Pa ... n#packages
4. install giac by typing: apt-get update && apt-get install giac && ldconfig
5. if g++ is not installed, type: apt-get install g++
6. use the following minimal program template to start with, say giactest.cc:

Code : Tout sélectionner

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

using namespace giac;
using namespace std;

int main() {
  context ct;
  gen g;
  stringstream ss;
  ss << "int(x^2,x)"; // put the textual representation of a gen to ss
  ss >> g; // create the gen object from its textual representation
  // do something with the object
  cout << g << " evaluates to " << _eval(g,&ct) << endl;
  // ...
  return 0;
}

7. compile the code with

Code : Tout sélectionner

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

(maybe some -dev packages will have to be installed)
8. type ./a.out to run the program.

Hope this helps someone!

[lukamar]

Bernard, when you'll have time to build new Giac/Xcas binaries?

[parisse]

I will update the debian 9 package Monday. I'm waiting a little for the stable/testing packages, to insure that students preparing the agregation (math teacher exam) do not update with a too recent version.

[lukamar]

OK, please also update aide_cas by appending the shorthelp.txt file located in the doc directory of my repository.

[parisse]

Yes, the new commands are in aide_cas, I'll try to add translations in French.
For lexer_tab_int.h, I forgot to tell you that the names should be alphabetically sorted otherwise they will not be recognized, I sorted them.

[jocaps]

@lukamar: Sorry for the late reply. I do not know about the paper you cite (apparently by microsoft researchers). But I know that the algorithms of McKay are trusted and cited regularly by graph-theorists. His C++ package (nauty) is very light-weight and has absolutely no dependencies whatsoever (I was able to compile it both in windows and linux, yielding a binary of only ca. 63kb). I believe his package is used in many of the commercial CAS as well (at least I believe Mathmatica uses it). He describes his algorithm in his paper which is cited also in his website: http://users.cecs.anu.edu.au/~bdm/nauty/

I hope my information helps. I don't know if it make sense to just incoroporate nauty in giac. But maybe it will at least inspire you.

@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

[lukamar]

@jocaps: Thanks for the valuable suggestions Jose. The nauty library seems perfectly appropriate indeed. It is a lot more llightweight than GLPK, which was already (optionally) included in Giac for linear programming. Also, the Apache 2.0 license under which nauty is distributed is compatible with GNU GPL v3 according to FSF. I'll definitely try to realize this approach to implementing is_isomorphic command (the inclusion of nauty in Giac, if realized successfully, will - as GLPK is - be made optional).

[lukamar]

Further improvements to graphtheory committed recently:
1. new commands are added: graph_spectrum, seidel_spectrum, graph_charpoly and is_integer_graph, the corresponding short help entries are appended to shorthelp.txt
2. fixed short help description for import_graph
3. updated the user manual in doc/ (this is meant to be inserted in cascmd_en.tex when finished)
4. fixed several bugs while testing the commands during writing docs

[lukamar]

Four new commands added just now: spanning_tree, minimal_spanning_tree (Kruskal's algorithm), number_of_spanning_trees, graph_rank

[parisse]

Ok, I will synchronize later this week, I have updated the debian 9 packages (the output of graphs in xcas is still not updated).

[lukamar]

I fixed short help, the calling syntax was defined improperly. The line starting with 0 now contains only the arguments, without the command name (which is printed automatically).
Also, there is a new command, lowest_common_ancestor(T,r,u,v) which computes LCA for vertices u,v in tree T with root r (or LCAs for a list of pairs of vertices) using Tarjan's offline algorithm operating on union-find data structure.
I also made several improvements, for example Fleury's algorithm for eulerian trail (quadratic time) was replaced with Hierholzer's algorithm (linear time) and generating random planar graphs is much faster and with a greater level of control.

Edit: further improvements to short help, now it is really brief (the explanations are shortened when possible) and the entry for is_eulerian command is fixed.

[parisse]

I have synchronized. I had to make changes in graphtheory.cc because old versions of <string> do not have front(), back() and pop_back() :

Code : Tout sélectionner

string strip_string(const string &str) {
    string res(str);
    int i=0;
    for (;res[i]==' ';++i);
    res=res.substr(i);
#if 1
    i=int(res.size())-1;
    for (;i>=0;--i){
      if (res[i]!=' ')
	break;
    }
    res=res.substr(0,i+1);
#else
    while (res.back()==' ') {
        res.pop_back();
    }
#endif
    return res;
}

Replaced front() by [0]

Code : Tout sélectionner

668c659
<     if (filename[0]!='/')
---
>     if (filename.front()!='/')
691c682
<     if (filename[1]!='/')
---
>     if (filename.front()!='/')

It was a little bit complicated for the short help because I have translated a few items in French and I did not want to loose that (I tried to merge I hope I did not make too many mistakes).

[lukamar]

Thanks! As for the short help, you may continue to translate it, I won't make any more changes unless something is wrong (I hope I have fixed all those entries). I'll check merged version troughout for any mistakes.