Quelle hamheuristic.c Sprache: C

/* hamheuristic.c  */

#define USAGE "hamheuristic [-sgu] [-vq] [-L#] [-t#] [infile [outfile]]"

#define HELPTEXT \
" Apply a heuristic for finding hamiltonian cycles.\n\
  Output those which are unsuccessful.\n\
\n\
    -s  force output to sparse6 format\n\
    -g  force output to graph6 format\n\
        If neither -s or -g are given, the output format is\n\
        determined by the header or, if there is none, by the\n\
        format of the first input graph.\n\
    -u  Suppress output to outfile, give statistics instead.\n\
\n\
    The output file will have a header if and only if the input file does.\n\
\n\
    -p  Be content with a hamiltonian path\n\
    -v  Give a cycle or path if one is found.\n\
    -L# Limit number of sideways steps (default 1000+5*n)\n\
    -t# Try # times (default 1)\n\
\n\
    -q  suppress auxiliary information\n"

#define DEBUG(X) X

/*************************************************************************/

#include "gtools.h"

#define NO 0
#define YES 1
#define TIMEOUT 2

static long seed = 314159265;

/**************************************************************************/

static int
hamheur(sparsegraph *sg, boolean pathok, unsigned long limit, int *cyc)
/* Try up to limit, fill cyc if YES and cyc!=NULL */
/* For pathok = TRUE, return when a hamiltonian path is found */
{
    DYNALLSTAT(int,path,path_sz);
    DYNALLSTAT(int,work,work_sz);
    DYNALLSTAT(int,pos,pos_sz);  /* position on path or -1 */
    int end0,end1,v0,v1;
    size_t *v;
    int n,*e,*d,len,d0,*e0,d1,*e1,dx,*ex;
    int i,ix,x,j,w,vext,exts;
    unsigned long count;
    boolean left,cycle;
    long ran;

    SG_VDE(sg,v,d,e);
    n = sg->nv;
    if (n < 3) return NO;

    DYNALLOC1(int,path,path_sz,2*n+4,"malloc");
    DYNALLOC1(int,pos,pos_sz,n,"malloc");
    DYNALLOC1(int,work,work_sz,n,"malloc");

    for (i = 0; i < n; ++i)
    {
        if (d[i] < 2) return NO;
        pos[i] = -1;
    }
    count = 0;

    v0 = KRAN(n);
    v1 = e[v[v0]+KRAN(d[v0])];
    end0 = n+1;
    end1 = n+2;
    path[end0] = v0; pos[v0] = end0;
    path[end1] = v1; pos[v1] = end1;
    len = 2;

    for (; count < limit;)
    {
     /* First look for an extension, but note if cycle */

        if (pathok && len == n)
        {
            if (cyc)
            {
                j = 0;
                for (i = end0; i <= end1; ++i)
                    cyc[j++] = path[i];
            }
            return YES;
        }

        v0 = path[end0];
        v1 = path[end1];

        exts = 0;
        d0 = d[v0];
        e0 = e + v[v0];
        cycle = FALSE;
        ran = NEXTRAN;
        for (i = 0; i < d0; ++i)
        {
            w = e0[i];
            if (pos[w] < 0)
            {
                ++exts;
                if (ran%exts == 0) {left = TRUE; vext = w;}
            }
            else if (w == v1) cycle = TRUE;
        }
        d1 = d[v1];
        e1 = e + v[v1];
        ran = NEXTRAN;
        for (i = 0; i < d1; ++i)
        {
            w = e1[i];
            if (pos[w] < 0)
            {
                ++exts;
                if (ran%exts == 0) {left = FALSE; vext = w;}
            }
        }

        if (exts > 0)
        {
            if (left)
            {
                --end0;
                path[end0] = vext;
                pos[vext] = end0;
            }
            else
            {
                ++end1;
                path[end1] = vext;
                pos[vext] = end1;
            }
            ++len;
            continue;
        }

     /* Can't extend but a cycle was found */

        if (cycle)
        {
            if (len == n)
            {
                if (cyc)
                {
                    j = 0;
                    for (i = pos[0]; i <= end1; ++i) cyc[j++] = path[i];
                    for (i = end0; i < pos[0]; ++i) cyc[j++] = path[i];
                }
                return YES;
            }

            ix = end0 + KRAN(len);
            for (i = 0; i < len; ++i)
            {
                x = path[ix];

                exts = 0;
                dx = d[x];
                ex = e + v[x];
                ran = NEXTRAN;
                for (j = 0; j < dx; ++j)
                {
                    w = ex[j];
                    if (pos[w] < 0)
                    {
                        ++exts;
                        if (ran%exts == 0) vext = w;
                    }
                }
                if (exts > 0) break;
                if (ix == end1) ix = end0; else ++ix;
            }
            if (i == len) return NO;    /* isolated component */

            work[0] = vext;
            j = 1;
            for (i = ix; i <= end1; ++i) work[j++] = path[i];
            for (i = end0; i < ix; ++i) work[j++] = path[i];

            for (i = 0; i < j; ++i)
            {
                path[end0+i] = work[i];
                pos[work[i]] = end0+i;
            }
            ++end1;
            ++len;
            continue;
        }

     /* In the last resort, do a sideways move. */

        exts = 0;
        d0 = d[v0];
        e0 = e + v[v0];
        ran = NEXTRAN;
        for (i = 0; i < d0; ++i)
        {
            w = e0[i];
            if (pos[w] >= 0 && w != path[end0+1])
            {
                ++exts;
                if (ran%exts == 0) {left = TRUE; vext = w;}
            }
        }
        d1 = d[v1];
        e1 = e + v[v1];
        ran = NEXTRAN;
        for (i = 0; i < d1; ++i)
        {
            w = e1[i];
            if (pos[w] >= 0 && w != path[end1-1])
            {
                ++exts;
                if (ran%exts == 0) {left = FALSE; vext = w;}
            }
        }

        if (left)
        {
            i = end0;
            j = pos[vext]-1;
        }
        else
        {
            i = pos[vext]+1;
            j = end1;
        }
        for (; i < j; ++i, --j)
        {
            w = path[i];
            path[i] = path[j];
            path[j] = w;
            pos[path[i]] = i;
            pos[path[j]] = j;
        }

        ++count;
    }

    return TIMEOUT;
}

/**************************************************************************/

int
main(int argc, char *argv[])
{
    sparsegraph sg;
    int n,codetype;
    int argnum,i,j,outcode,tvalue;
    char *arg,sw;
    boolean badargs;
    boolean pswitch,sswitch,gswitch,qswitch,Lswitch,tswitch,vswitch,uswitch;
    long Lvalue;
    double t;
    char *infilename,*outfilename;
    FILE *infile,*outfile;
    nauty_counter nin,nout,nNO,nYES,nTIMEOUT;
    int status;
    DYNALLSTAT(int,cyc,cyc_sz);

    HELP; PUTVERSION;

    INITRANBYTIME;

    uswitch = sswitch = gswitch = Lswitch = qswitch = FALSE;
    pswitch = vswitch = tswitch = FALSE;
    infilename = outfilename = NULL;

    argnum = 0;
    badargs = FALSE;
    for (j = 1; !badargs && j < argc; ++j)
    {
        arg = argv[j];
        if (arg[0] == '-' && arg[1] != '\0')
        {
            ++arg;
            while (*arg != '\0')
            {
                sw = *arg++;
                     SWBOOLEAN('s',sswitch)
                else SWBOOLEAN('g',gswitch)
                else SWBOOLEAN('u',uswitch)
                else SWBOOLEAN('p',pswitch)
                else SWBOOLEAN('q',qswitch)
                else SWBOOLEAN('v',vswitch)
                else SWLONG('L',Lswitch,Lvalue,"-L")
                else SWINT('t',tswitch,tvalue,"-t")
                else badargs = TRUE;
            }
        }
        else
        {
            ++argnum;
            if      (argnum == 1) infilename = arg;
            else if (argnum == 2) outfilename = arg;
            else                  badargs = TRUE;
        }
    }

    if ((sswitch != 0) + (gswitch != 0) + (uswitch != 0) > 1)
        gt_abort(">E hamheuristic: -s, -g and -u are incompatible\n");

    if (!tswitch) tvalue = 1;

    if (badargs || argnum > 2)
    {
        fprintf(stderr,">E Usage: %s\n",USAGE);
        GETHELP;
        exit(1);
    }

    if (!qswitch)
    {
        fprintf(stderr,">A hamheuristic");
        if (pswitch || sswitch || gswitch || vswitch || tswitch || Lswitch)
            fprintf(stderr," -");
        if (sswitch) fprintf(stderr,"s");
        if (gswitch) fprintf(stderr,"g");
        if (uswitch) fprintf(stderr,"u");
        if (vswitch) fprintf(stderr,"v");
        if (pswitch) fprintf(stderr,"p");
        if (Lswitch) fprintf(stderr,"L%ld",Lvalue);
        if (tswitch) fprintf(stderr,"t%d",tvalue);
        if (argnum > 0) fprintf(stderr," %s",infilename);
        if (argnum > 1) fprintf(stderr," %s",outfilename);
        fprintf(stderr,"\n");
        fflush(stderr);
    }

    if (infilename && infilename[0] == '-') infilename = NULL;
    infile = opengraphfile(infilename,&codetype,FALSE,1);
    if (!infile) exit(1);
    if (!infilename) infilename = "stdin";

    NODIGRAPHSYET(codetype);

    if (!uswitch)
    {
        if (!outfilename || outfilename[0] == '-')
        {
            outfilename = "stdout";
            outfile = stdout;
        }
        else if ((outfile = fopen(outfilename,"w")) == NULL)
        {
            fprintf(stderr,"Can't open output file %s\n",outfilename);
            gt_abort(NULL);
        }

        if (sswitch || (!gswitch && (codetype&SPARSE6)))
            outcode = SPARSE6;
        else
            outcode = GRAPH6;

        if (codetype&HAS_HEADER)
        {
            if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
            else                    writeline(outfile,GRAPH6_HEADER);
        }
    }

    nin = nout = 0;
    nNO = nYES = nTIMEOUT = 0;
    t = CPUTIME;
    SG_INIT(sg);

    while (read_sg(infile,&sg) != NULL)
    {
        ++nin;

        n = sg.nv;

        if (vswitch) { DYNALLOC1(int,cyc,cyc_sz,n,"malloc"); }
        else         cyc = NULL;

        status = TIMEOUT;
        for (i = 0; i < tvalue; ++i)
        {
            status = hamheur(&sg,pswitch,(Lswitch?Lvalue:1000+5*n),cyc);
            if (status != TIMEOUT) break;
        }

        if (status == NO) ++nNO;
        else if (status == YES) ++nYES;
        else ++nTIMEOUT;

        if (status != YES && !uswitch)
        {
            if (outcode == SPARSE6) writes6_sg(outfile,&sg);
            else if (outcode == GRAPH6) writeg6_sg(outfile,&sg);
            ++nout;
        }

        if (vswitch)
        {
            fprintf(stderr,">H " COUNTER_FMT ":",nin);
            if (status == TIMEOUT)
                fprintf(stderr," timed out\n");
            else if (status == NO)
                    fprintf(stderr," disconnected or low degree\n");
            else
            {
                for (i = 0; i < n; ++i) fprintf(stderr," %d",cyc[i]);
                fprintf(stderr,"\n");
            }
        }
    }
    t = CPUTIME - t;

    if (uswitch)
    {
        fprintf(stderr,">Z " COUNTER_FMT " graphs read from %s; "
           COUNTER_FMT " hamiltonian, " COUNTER_FMT " not, "
           COUNTER_FMT " timed out; %3.2f sec.\n",
           nin,infilename,nYES,nNO,nTIMEOUT,t);
    }
    else if (!qswitch)
    {
        fprintf(stderr,
                ">Z " COUNTER_FMT " graphs read from %s, "
                COUNTER_FMT " written to %s; %3.2f sec.\n",
                nin,infilename,nout,outfilename,t);
    }

    exit(0);
}

quality93%

¤ Dauer der Verarbeitung: 0.35 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.