graph theory commands for Giac

[parisse]

Got an unresolved symbol get_current_dir_name with emscripten, can you modify the code in graphtheory.cc like this:

Code : Tout sélectionner

#ifdef HAVE_NO_CWD
    string path="/"+relative_path;
#else
    string path=string(get_current_dir_name())+"/"+relative_path;
#endif

[lukamar]

Synchronized, also fixed several bugs:
1. when generating regular graphs the necessary condition check was skipped, causing infinite loops. Now the check is propery included.
2. the box packing algorithm for combining drawings of individual connected components of a graph was too slow, now I improved it and it's several times faster.
3. there were some bugs in dot file parser, which are now fixed and the vertex attributes are now assigned properly.

Vertex labels are now accessible as attributes. Also, line styles may be set for individual edges as well as shapes for individual vertices.

[parisse]

Got another problem compiling on os x, I replaced get_current_dir_name with getcwd(0,0).

[lukamar]

Is there maybe a different (better) way to convert a path from relative to absolute?
Which changes should I make in my source (if any)?

[parisse]

Replace get_current_dir_name() with getcwd(0,0) and it should work. I have no idea how to make this more portable...

[parisse]

Got another small problem while compiling for win 32 bits with an old version of cygwin (I don't want to reinstall...): line 5736 and 5740 of graphe.cc, you are using a return value for labels.pop_back(), it seems that old STL versions declare pop_back() as void, therefore I fixed it by replacing labels.pop_back() by labels.back() and I inserted the labels.pop_back() command just after.

[lukamar]

Thanks, I replicated the changes in my source.

[lukamar]

I've fixed bugs in several commands and made error reporting simpler and more informative.
Also, documenting the implemented commands is almost finished.

Still to be implemented:
- nauty inclusion for graph isomporhism
- edge connectivity
- edge coloring
- Hamiltonian paths an traveling salesman problem
- Tutte polynomial
- support for networks

[jocaps]

@lukamar

Thank you for considering nauty implementation. I will certainly be very interested if this is done. Currently I am using nauty in C++ which is much faster than using it in XCas and giac. But for minor computations and computations involving multiple CAS and giacpy I will be interested in using your implementation.

Jose

[lukamar]

@jocaps: I think nauty will operate inside Giac as fast as usual, if I manage to incorporate it (should be no problems with that). All the hard work with graphs is done at a level using structures much simpler than gen. Graph is only converted to gen when the particular algorithm is finished.
I plan to deal with this soon, because I'm interested too to see how it would work. We'll see, probably before August.

Luka

[lukamar]

I have succeeded to incorporate nauty. The latest revision of the code contains an implementation of is_isomorphic command which uses sparse nauty. As nauty is clashing with std namespace I had to make a wrapper as a separate class, hence the new files nautywrapper.h and nautywrapper.cc.
I managed to compile on Debian 9 by installing libnauty2-dev package (ver. 2.6) from the Stretch repositories.
Inclusion of nauty in Giac is optional; the switch HAVE_LIBNAUTY is defined on line 20 in graphe.h and should be removed once nauty is incorporated in the Giac build process.

Here's the short help for is_isomorphic command:

Code : Tout sélectionner

# is_isomorphic
0 G1,G2,[I]
2 Returns true if the input graphs G1 and G2 are isomorphic, else returns false. If an unassigned identifier 'I' is given, the isomorphism is stored to it in form of a list.
-1 isomorphic_copy
-2 permute_vertices
G1:=graph("petersen"); G2:=kneser_graph(5,2); is_isomorphic(G1,G2,I)

Also, this revision contains some improvements to the vertex coloring algorithm:
- cut generation
- better branching technique

Edit: I've just committed an implementation of one more command related to nauty, called graph_automorphisms. The description is below.

Code : Tout sélectionner

# graph_automorphisms
0 G
2 Returns the sequence of generators of Aut(G), the automorphism group of the input graph G. Each element is a permutation in form of list of disjoint cycles.
-1 cycles2permu
-2 isomorphic_copy
-3 permute_vertices
graph_automorphisms(graph("petersen"))

[lukamar]

I suspect that nauty has some problems in C++. When calling sparsenauty, it sometimes immediately returns without apparently doing anything and without any errors. However, in the other instance in the same file it works fine. To make a less macroified interface to nauty perhaps I should code nautywrapper in pure C, which would require to run gcc on that file and link it with g++ aftwerwards. I think it would be safer and also want to try how it works. Bernard, is it a problem to compile one source file in C during the build?

[parisse]

It should not be a problem. Just make sure to put the header in extern "C" { } when called from c++ with a check like this:

Code : Tout sélectionner

#if defined(__cplusplus)
extern "C" {
#endif
...
#if defined(__cplusplus)
}
#endif

[lukamar]

I've redesigned nauty wrapper, now it is in pure C (nautywrapper.cpp changed the extension to .c) and uses dense nauty. Apparently it works fine!

Currently only undirected graphs are supported, but I plan to extend the support to digraphs too and perhaps implement an option to use Traces instead of nauty (it seems to be faster for some classes of graphs, e.g. for random graphs).

Bernard, I think you can now synchronize the source with the last revision of graphtheory (when you find some time).

Edit: there is another new command, canonical_labeling:

Code : Tout sélectionner

# canonical_labeling
0 G
2 Returns the permutation representing the canonical labeling of the input graph G.
-1 isomorphic_copy
-2 relabel_vertices
canonical_labeling(graph("petersen"))

Edit2: added support for digraphs.

[parisse]

I must make changes to nautywrapper.c so that it compiles and links even if nauty is not installed.

Code : Tout sélectionner

#if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H
#include "nauty/nauty.h"
#include "nauty/nautinv.h"
#include "nautywrapper.h"

int nautywrapper_is_isomorphic(int isdir,int n,int *adj1,int *adj2,int *sigma) {
    DYNALLSTAT(int,lab1,lab1_sz);
    DYNALLSTAT(int,lab2,lab2_sz);
    DYNALLSTAT(int,ptn,ptn_sz);
    DYNALLSTAT(int,orbits,orbits_sz);
    DYNALLSTAT(graph,g1,g1_sz);
    DYNALLSTAT(graph,g2,g2_sz);
    DYNALLSTAT(graph,cg1,cg1_sz);
    DYNALLSTAT(graph,cg2,cg2_sz);
    static DEFAULTOPTIONS_GRAPH(opts_undir);
    static DEFAULTOPTIONS_DIGRAPH(opts_dir);
    optionblk *options=isdir!=0?&opts_dir:&opts_undir;
    statsblk stats;
    int m=SETWORDSNEEDED(n);
    nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
    DYNALLOC1(int,lab1,lab1_sz,n,"malloc");
    DYNALLOC1(int,lab2,lab2_sz,n,"malloc");
    DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
    DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
    DYNALLOC2(graph,g1,g1_sz,n,m,"malloc");
    EMPTYGRAPH(g1,m,n);
    DYNALLOC2(graph,g2,g2_sz,n,m,"malloc");
    EMPTYGRAPH(g2,m,n);
    DYNALLOC2(graph,cg1,cg1_sz,n,m,"malloc");
    DYNALLOC2(graph,cg2,cg2_sz,n,m,"malloc");
    options->getcanon=TRUE;
    options->writeautoms=FALSE;
    options->outfile=NULL;
    int i=0,j=0,k;
    /* create the first graph */
    while (1) {
        if ((k=adj1[i++])==-1) { if ((++j)==n) break; }
        else if (j<k && isdir==0) { ADDONEEDGE(g1,j,k,m); }
        else if (isdir!=0) { ADDONEARC(g1,j,k,m); }
    }
    /* create the second graph */
    i=j=0;
    while (1) {
        if ((k=adj2[i++])==-1) { if ((++j)==n) break; }
        else if (j<k && isdir==0) { ADDONEEDGE(g2,j,k,m); }
        else if (isdir!=0) { ADDONEARC(g2,j,k,m); }
    }
    /* canonically label both graphs */
    densenauty(g1,lab1,ptn,orbits,options,&stats,m,n,cg1);
    densenauty(g2,lab2,ptn,orbits,options,&stats,m,n,cg2);
    /* return nonzero iff the canonical labelings match */
    size_t cnt=0;
    for (;cnt<m*(size_t)n;++cnt) {
        if (cg1[cnt]!=cg2[cnt]) break;
    }
    boolean isomorphic=cnt==m*(size_t)n?TRUE:FALSE;
    if (isomorphic) {
        for (i=0;i<n;++i) {
            sigma[lab1[i]] = lab2[i];
        }
    }
    DYNFREE(lab1,lab1_sz);
    DYNFREE(lab2,lab1_sz);
    DYNFREE(ptn,ptn_sz);
    DYNFREE(orbits,orbits_sz);
    DYNFREE(g1,g1_sz);
    DYNFREE(g2,g2_sz);
    DYNFREE(cg1,cg1_sz);
    DYNFREE(cg2,cg2_sz);
    return isomorphic;
}

void nautywrapper_aut_generators(int isdir,int n,int *adj,FILE *f) {
    DYNALLSTAT(int,lab,lab_sz);
    DYNALLSTAT(int,ptn,ptn_sz);
    DYNALLSTAT(int,orbits,orbits_sz);
    DYNALLSTAT(graph,g,g_sz);
    static DEFAULTOPTIONS_GRAPH(opts_undir);
    static DEFAULTOPTIONS_GRAPH(opts_dir);
    optionblk *options=isdir!=0?&opts_dir:&opts_undir;
    statsblk stats;
    int m=SETWORDSNEEDED(n);
    nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
    DYNALLOC1(int,lab,lab_sz,n,"malloc");
    DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
    DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
    DYNALLOC2(graph,g,g_sz,n,m,"malloc");
    EMPTYGRAPH(g,m,n);
    options->getcanon=FALSE;
    options->writeautoms=TRUE;
    options->linelength=RAND_MAX;
    options->outfile=f;
    int i=0,j=0,k;
    /* create the graph */
    while (1) {
        if ((k=adj[i++])==-1) { if ((++j)==n) break; }
        else if (j<k && isdir==0) { ADDONEEDGE(g,j,k,m); }
        else if (isdir!=0) { ADDONEARC(g,j,k,m); }
    }
    densenauty(g,lab,ptn,orbits,options,&stats,m,n,NULL);
    DYNFREE(lab,lab_sz);
    DYNFREE(ptn,ptn_sz);
    DYNFREE(orbits,orbits_sz);
    DYNFREE(g,g_sz);
}

void nautywrapper_canonical(int isdir,int n,int *adj,int *clab) {
    DYNALLSTAT(int,lab,lab_sz);
    DYNALLSTAT(int,ptn,ptn_sz);
    DYNALLSTAT(int,orbits,orbits_sz);
    DYNALLSTAT(graph,g,g_sz);
    DYNALLSTAT(graph,cg,cg_sz);
    static DEFAULTOPTIONS_GRAPH(opts_undir);
    static DEFAULTOPTIONS_DIGRAPH(opts_dir);
    optionblk *options=isdir!=0?&opts_dir:&opts_undir;
    statsblk stats;
    int m=SETWORDSNEEDED(n);
    nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
    DYNALLOC1(int,lab,lab_sz,n,"malloc");
    DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
    DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
    DYNALLOC2(graph,cg,cg_sz,n,m,"malloc");
    DYNALLOC2(graph,g,g_sz,n,m,"malloc");
    EMPTYGRAPH(g,m,n);
    options->getcanon=TRUE;
    options->writeautoms=FALSE;
    options->outfile=NULL;
    int i=0,j=0,k;
    /* create the graph */
    while (1) {
        if ((k=adj[i++])==-1) { if ((++j)==n) break; }
        else if (j<k && isdir==0) { ADDONEEDGE(g,j,k,m); }
        else if (isdir!=0) { ADDONEARC(g,j,k,m); }
    }
    densenauty(g,lab,ptn,orbits,options,&stats,m,n,cg);
    for (i=0;i<n;++i) clab[i]=lab[i];
    DYNFREE(lab,lab_sz);
    DYNFREE(ptn,ptn_sz);
    DYNFREE(orbits,orbits_sz);
    DYNFREE(g,g_sz);
    DYNFREE(cg,cg_sz);
}
#else // HAVE_LIBNAUTY
#include <stdio.h>
int nautywrapper_is_isomorphic(int isdir,int n,int *adj1,int *adj2,int *sigma){
  return 0;
}

/* write the generators of Aut(G), where G is represented by the sequence
 * adj of adjacency lists, to the temporary file f and returns length of f
 * (leaves the file open, it should be closed afterwards) */
void nautywrapper_aut_generators(int isdir,int n,int *adj,FILE *f){}

/* compute the canonical labeling for the graph represented by the sequence
 * adj of adjacency lists */
void nautywrapper_canonical(int isdir,int n,int *adj,int *clab){}

#endif // HAVE_LIBNAUTY