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 » dim. sept. 23, 2018 9:21 pm

Yes, interrupting nauty from Xcas works fine for me.
For example:

Code : Tout sélectionner

G:=random_graph(1000,500000);
H:=isomorphic_copy(G);
is_isomorphic(G,H)
nauty needs a couple of seconds to execute the last command, it cancels cleanly when STOP button is pressed.

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 9:27 pm

New updates to the graphtheory source:
* added "approx" option to clustering_coefficient
* improved data structure for adjacency lists

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

Re: graph theory commands for Giac

Message par parisse » lun. sept. 24, 2018 8:59 am

Unstable source updated!

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. 26, 2018 6:34 am

frederic han a écrit :
dim. sept. 23, 2018 7:51 pm
Are you able to interrupt a long computation in nauty?
Actually, there indeed is a problem. I forgot that the conversion process on large graphs (an overhead) lasts couple of seconds. Therefore, in the above example with G=random_graph(1000,500000) I tried to interrupt the computation a bit before the finish time, when nauty is working. Interruption did not work (command has finished and returned the result) but trying to run another command Xcas just gave the info "Aborted" and then my *entire* system crashed. I managed to reproduce this couple of times in a row. Seems like a serious issue (probably has something to do with memory management in nauty) which has to be fixed before the stable release.
I propose that, since nauty is blazingly fast and it never takes more than a few seconds for amounts of data that can be stored in a graphe class instance, we disable the interruption when nauty is running. But I don't know how Xcas GUI could know about it... how to inform the main thread that the other (computing) thread is in a sensitive state?

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

Re: graph theory commands for Giac

Message par parisse » mer. sept. 26, 2018 9:08 am

I think you should be able to disable thread cancelling when calling sensitive code by calling something like

Code : Tout sélectionner

pthread_setcancelstate(PTHREAD_CANCEL_DISABLE,NULL)
and restore it after

Code : Tout sélectionner

pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,NULL);
http://man7.org/linux/man-pages/man3/pt ... ype.3.html

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. 26, 2018 11:04 am

Thanks! I committed a fix. It seems to work, I haven't been able to reproduce the crash with the current revision.

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

Re: graph theory commands for Giac

Message par parisse » mer. sept. 26, 2018 1:22 pm

Great, fix included in my source!

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 » jeu. sept. 27, 2018 7:57 am

In fact my question was about icas. The one I have built for windows doesn't take ctrl-c when in nauty computation, and I was wondering if it was the same on linux.

Frederic

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

Re: graph theory commands for Giac

Message par lukamar » lun. oct. 01, 2018 11:28 am

I added the Optimization, Signal processing and Graph theory menus to xcasmenu (finally), it's attached below.
There are some improvements and bug fixes for graphtheory:
* fixed a bug which caused infinite loops in traveling_salesman on some non-hamiltonian graphs (for example, Petersen graph), which is a regression from a previous bug-fix
* improved triangle counting, now the algorithm is as efficient as it gets, that also speeds up clustering_coefficient and network_transitivity
* improved random graph generation, now vertex degrees can be drawn from an arbitrary discrete distribution and preferential-attachment algorithm is added for constructing realistic networks (power-law degree distribution).
* updated the docs, the new functionality is explained there (random_graph, in particular)

By the way, Bernard, does Giac support sampling from custom discrete distributions? The algorithm of Walker and Vose which I implemented for random_graph is very efficient for generating large number of samples from a given distribution (linear preprocessing time and constant sampling time). I can export this functionality in general as a separate command (called discrete_sampling or something like that), perhaps it could be useful?
Pièces jointes
xcasmenu.zip
(5.85 Kio) Téléchargé 41 fois

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

Re: graph theory commands for Giac

Message par parisse » lun. oct. 01, 2018 6:32 pm

Thanks, I have integrated your changes.

I don't remember having implemented anythinf related to random generation according to custom discrete distributions, so yes, feel free to export your implementation!

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

Re: graph theory commands for Giac

Message par lukamar » dim. oct. 07, 2018 8:46 am

Here, I wrote the command "random_variable" (alias "randvar") which can assist in creating (discrete) random variables. The code is in graphtheory.cc (line 582) because it uses graphe class. It encapsulates a probability distribution to be sampled with rand, randvector or randmatrix. Also, combining independent random variables in an expression is possible, yielding a new random variable which can be sampled fast and easy. Sampling from discrete distributions is fast enough to allow good approximation of custom continuous distributions. See the examples in randvar.tex.

To enable the functionality, several files need to be changed:
* in moyal.h, append

Code : Tout sélectionner

  gen randdiscrete(const vecteur &m, GIAC_CONTEXT);
  extern const unary_function_ptr * const  at_discreted ;
* in moyal.cc, append

Code : Tout sélectionner

  gen randdiscrete(const vecteur &m,GIAC_CONTEXT) {
    int n;
    if (m.empty() || !m.front().is_integer() || (n=m.front().val)<1)
      return gensizeerr(contextptr);
    double ran1=giac_rand(contextptr)/(rand_max2+1.0);
    double ran2=giac_rand(contextptr)/(rand_max2+1.0);
    int i=std::floor(n*ran1);
    int index=is_strictly_greater(m[i+1],ran2,contextptr)?i:m[n+i+1].val;
    if (int(m.size()-1)==3*n)
      return m[2*n+index+1];
    return index+array_start(contextptr);
  }

  gen _discreted(const gen &g,GIAC_CONTEXT) {
    if (g.type==_STRNG && g.subtype==-1) return g;
    return symbolic(at_discreted,g);
  }
  static const char _discreted_s []="discreted";
  static define_unary_function_eval (__discreted,&_discreted,_discreted_s);
  define_unary_function_ptr5( at_discreted,alias_at_discreted,&__discreted,0,true);
* in vecteur.cc, insert the following above the implementation of vranm (void):

Code : Tout sélectionner

  static int randvar_count=0;

  void find_randvars(gen &g,gen_map &rv,GIAC_CONTEXT) {
    stringstream ss;
    if (g.type==_IDNT) {
      if (rv.find(g)!=rv.end())
        g=rv[g];
      else {
        ss << " var" << randvar_count;
        identificateur v(ss.str().c_str());
        rv[g]=v;
        g=v;
        ++randvar_count;
      }
    } else if (g.is_symb_of_sommet(at_discreted) || is_distribution(g)>0) {
      ss << " tmp" << randvar_count;
      identificateur t(ss.str().c_str());
      ss.str("");
      ss << " var" << randvar_count;
      identificateur v(ss.str().c_str());
      _eval(symbolic(at_sto,makesequence(g,t)),contextptr);
      rv[t]=v;
      g=v;
      ++randvar_count;
    } else if (g.type==_SYMB) {
      gen &f=g._SYMBptr->feuille;
      if (f.type==_VECT) {
        for (iterateur it=f._VECTptr->begin();it!=f._VECTptr->end();++it) {
          find_randvars(*it,rv,contextptr);
        }
      } else find_randvars(f,rv,contextptr);
    }
  }
* also in vecteur.cc, insert the following lines in vranm (void) subroutine, immediately above the final for loop (last two lines):

Code : Tout sélectionner

    if (f.is_symb_of_sommet(at_discreted)) {
      const vecteur &args=*f._SYMBptr->feuille._VECTptr;
      for (int i=0;i<n;++i) {
        res.push_back(randdiscrete(args,contextptr));
      }
      return;
    }
    if (f.type==_SYMB) {
      gen_map rv;
      gen e(f);
      randvar_count=0;
      find_randvars(e,rv,contextptr);
      if (!rv.empty()) {
        int nv=rv.size();
        vecteur vars;
        matrice R;
        vars.reserve(nv);
        R.reserve(nv);
        for (gen_map::const_iterator it=rv.begin();it!=rv.end();++it) {
          vars.push_back(it->second);
          R.push_back(vranm(n,_eval(it->first,contextptr),contextptr));
        }
        R=mtran(R);
        for (const_iterateur it=R.begin();it!=R.end();++it) {
          res.push_back(_subs(makesequence(e,vars,*it),contextptr));
        }
        return;
      }
    }
* in prog.cc, insert in the implementation of gen _rand, below the clause "if (args.is_symb_of_sommet(at_rootof))":

Code : Tout sélectionner

    if (args.is_symb_of_sommet(at_discreted))
      return vranm(1,args,contextptr)[0];
    if (args.type==_VECT && args._VECTptr->front()==at_multinomial) {
      vecteur v=*args._VECTptr;
      v.insert(v.begin(),1);
      return _randvector(v,contextptr)._VECTptr->at(0);
    }
* For Maple compatibility, i propose the following implementation of gen _sample in prog.cc (now it can accept random variable with optional number of samples n, by default 1):

Code : Tout sélectionner

  gen _sample(const gen & args,GIAC_CONTEXT){
    if (args.is_symb_of_sommet(at_discreted) || is_distribution(args)>0)
      return _rand(args,contextptr);
    if (args.type!=_VECT || args._VECTptr->size()<2)
      return gensizeerr(contextptr);
    vecteur &argv=*args._VECTptr;
    gen a=argv.front(),b=argv.back();
    if (a==at_multinomial) {
      if (argv.size()==3) {
        vecteur v=argv;
        v.insert(v.begin(),1);
        return _randvector(v,contextptr)._VECTptr->at(0);
      } if (argv.size()==4 && b.is_integer()) {
        return _randvector(makesequence(b,at_multinomial,argv[1],argv[2]),contextptr);
      }
      return gensizeerr(contextptr);
    }
    if (args._VECTptr->size()!=2 || !is_integral(b) || b.type==_ZINT || b.val<0)
      return gensizeerr(contextptr);
    if (a.is_symb_of_sommet(at_discreted) || is_distribution(a)>0)
      return _randvector(makesequence(b,a),contextptr);
    if (a.type!=_VECT)
      return gensizeerr(contextptr);
    return _rand(makesequence(b,a),contextptr);
  }
That's all. I attached the documentation for randvar (as .tex) and updated aide_cas file from 1.5.0-5 (I also revised and corrected the examples of graph theory).

Graphtheory update: I fixed another bug in traveling_salesman.
Dernière modification par lukamar le dim. oct. 07, 2018 10:09 am, modifié 1 fois.

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

Re: graph theory commands for Giac

Message par lukamar » dim. oct. 07, 2018 10:24 am

The mentioned doc files are below.

By the way, can a list of samples be visualized with histogram only on a certain range? That would be useful for visualizing populations with far outliers.
Pièces jointes
doc.zip
(18.5 Kio) Téléchargé 42 fois
aide_cas.zip
(187.54 Kio) Téléchargé 42 fois

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

Re: graph theory commands for Giac

Message par parisse » lun. oct. 08, 2018 2:30 pm

Thanks, that should now be in giac_unstable.tgz
What do you mean by visualized with histogram only on a certain range? It's always possible to set the window with gl_x=... and gl_y=... but I guess that's not what you are talking about.

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

Re: graph theory commands for Giac

Message par lukamar » lun. oct. 08, 2018 3:54 pm

Thank you!
What do you mean by visualized with histogram only on a certain range?
I mean discarding sample data which does not fall into the range before binning, i.e. to bin only the samples s which are between a and b.

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

Re: graph theory commands for Giac

Message par parisse » mar. oct. 09, 2018 11:32 am

There is nothing builtin to do that, on a list you can call select before histogram.

Répondre