Quelle showg.c Sprache: C

/* showg.c  version 2.1; B D McKay, August 2017.
   Formerly called readg.c.

   This is a stand-alone edition of listg.c that does not
   need nauty or any other files.  Use listg in preference
   if you have installed it.  */

#define USAGE "showg [-p#:#l#o#Ftq] [-a|-A|-c|-d|-e] [infile [outfile]]"

#define HELPTEXT \
" Write graphs in human-readable format.\n\
\n\
   infile is the input file in graph6, sparse6 or digraph6 format\n\
     This program does not support incremental sparse6 files; use listg.\n\
   outfile is the output file\n\
   Defaults are standard input and standard output.\n\
\n\
    -p#, -p#:#, -p#-# : only display one graph or a sequence of\n\
          graphs.  The first graph is number 1.  A second number\n\
          which is empty or zero means infinity.\n\
\n\
    -a  : write the adjacency matrix\n\
    -A  : same as -a with a space between entries\n\
    -d  : write output to satisfy dreadnaut\n\
    -c  : write compact dreadnaut form with minimal line-breaks\n\
    -e  : write a list of edges, preceded by the order and the\n\
          number of edges\n\
\n\
    -o# : specify number of first vertex (default is 0)\n\
    -t  : write upper triangle only (affects -a, -A, -d and default)\n\
    -F  : write a form-feed after each graph except the last\n\
    -l# : specify screen width limit (default 78, 0 means no limit)\n\
          This is not currently implemented with -a or -A.\n\
    -q  : suppress auxiliary output\n\
\n\
    -a, -A, -c, -d and -e are incompatible.\n"

/*
Version 1.1: Fixed sparse6 input for powers of 2.  May 9, 1998.
Version 1.3: Declared errno according to ISO C.  August 22, 1998.
Version 1.4: Change name of getline() so that broken compilers
                which define the GNU function without being asked
                don't cause a conflict.   June 16, 2006.
Version 1.5: Use function prototypes.  Avoid errno.  Sep 19, 2007.
Version 1.6: Very minor tweaks.  Hope you all have string.h. Sep 6, 2009.
Version 1.7: Make it work for n=0. Sep 18, 2013.
Version 2.0: Support digraph6 format.
Version 2.1: Fix digraph6 format and remove limit of 200K or so vertices.
*/

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

#include <stdio.h>
#include <string.h>

/* gtools.h : General header for gtools programs. */

#ifndef MAXN
#define MAXN  0
#endif

#define BIAS6 63
#define MAXBYTE 126
#define SMALLN 62
#define SMALLISHN 258047
#define TOPBIT6 32
#define C6MASK 63

#define SIZELEN(n) ((n)<=SMALLN?1:((n)<=SMALLISHN?4:8))
        /* length of size code in bytes */
#define G6BODYLEN(n) \
   (((size_t)(n)/12)*((size_t)(n)-1) + (((size_t)(n)%12)*((size_t)(n)-1)+11)/12)
#define G6LEN(n) (SIZELEN(n) + G6BODYLEN(n))
  /* exact graph6 string length excluding \n\0
     This twisted expression works up to n=227023 in 32-bit arithmetic
     and for larger n if size_t has 64 bits.  */
#define D6BODYLEN(n) \
   ((n)*(size_t)((n)/6) + (((n)*(size_t)((n)%6)+5)/6))
#define D6LEN(n) (1 + SIZELEN(n) + D6BODYLEN(n))
  /* exact digraph6 string length excluding \n\0
     This twisted expression works up to n=160529 in 32-bit arithmetic
     and for larger n if size_t has 64 bits.  */

#define B(i) (1 << ((i)-1))
#define M(i) ((1 << (i))-1)

/* Remove errno: too hard to get portable without configuration
* #if defined(__unix) || defined(__unix__) || defined(unix) || \
    defined(__ppc__)
#include <errno.h>
#else
int errno = 0;
#endif
#define ABORT(msg) {if (errno != 0) perror(msg); exit(1);}
*/

/* extern long ftell(FILE*);   Should be in stdio.h  */

#define GRAPH6_HEADER ">>graph6<<"
#define SPARSE6_HEADER ">>sparse6<<"
#define DIGRAPH6_HEADER ">>digraph6<<"

#define GRAPH6         1
#define SPARSE6        2
#define DIGRAPH6       4
#define UNKNOWN_TYPE 256
#define HAS_HEADER   512

#define ARG_OK 0
#define ARG_MISSING 1
#define ARG_TOOBIG 2
#define ARG_ILLEGAL 3

#define MAXARG 2000000000L
#define NOLIMIT (MAXARG+1L)

#define SWBOOLEAN(c,boool) if (sw==c) boool=TRUE;
#define SWINT(c,boool,val,id) if (sw==c) \
    {boool=TRUE;arg_int(&arg,&val,id);}
#define SWRANGE(c,boool,val1,val2,id) if (sw==c) \
    {boool=TRUE;arg_range(&arg,&val1,&val2,id);}

#define FREES free
#define ALLOCS calloc

#define DYNALLSTAT(type,name,name_sz) static type *name; static size_t name_sz=0
#define DYNALLOC1(type,name,name_sz,sz,msg) \
if ((size_t)(sz) > name_sz) \
{ if (name_sz) FREES(name); name_sz = (sz); \
if ((name=(type*)ALLOCS(sz,sizeof(type))) == NULL) alloc_error(msg);}
#define DYNALLOC2(type,name,name_sz,sz1,sz2,msg) \
if ((size_t)(sz1)*(size_t)(sz2) > name_sz) \
{ if (name_sz) FREES(name); name_sz = (size_t)(sz1)*(size_t)(sz2); \
if ((name=(type*)ALLOCS((sz1),(sz2)*sizeof(type))) == NULL) alloc_error(msg);}
#define DYNFREE(name,name_sz) if (name_sz) {FREES(name); name_sz = 0;}
#define DYNREALLOC(type,name,name_sz,sz,msg) \
{if ((size_t)(sz) > name_sz) \
{ if ((name = (type*)realloc(name,(sz)*sizeof(type))) == NULL) \
      alloc_error(msg); else name_sz = (sz);}}

#define alloc_error gt_abort

#ifdef __STDC__
#include <stddef.h>
#include <stdlib.h>
#else
#include <sys/types.h>
extern char *calloc();
extern char *malloc();
extern char *realloc();
#endif

#ifdef __alpha
typedef unsigned int setword;
#else
typedef unsigned long setword;
#endif
typedef setword set;
typedef setword graph;
typedef int boolean;

static setword bit[32]=
  {020000000000,010000000000,04000000000,02000000000,
   01000000000,0400000000,0200000000,0100000000,040000000,
   020000000,010000000,04000000,02000000,01000000,0400000,
   0200000,0100000,040000,020000,010000,04000,02000,01000,
   0400,0200,0100,040,020,010,04,02,01};
static int leftbit[] =
  {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,
   3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
static int labelorg = 0;

#define WORDSIZE 32
#define FIRSTBIT(x) ((x) & 037777600000 ? ((x) & 037700000000 ? \
                 leftbit[((x)>>24) & 0377] : 8+leftbit[(x)>>16]) \
                : ((x) & 0177400 ? 16+leftbit[(x)>>8] : 24+leftbit[x]))
#define BITMASK(x)  (017777777777 >> (x)) /* setword whose rightmost
  WORDSIZE-x-1 (numbered) bits are 1 and the rest 0 (0 <= x < WORDSIZE) */
#define TIMESWORDSIZE(w) ((w)<<5)
#define SETWD(pos) ((pos)>>5)
#define SETBT(pos) ((pos)&037)
#define ISELEMENT(setadd,pos)  (((setadd)[SETWD(pos)] & bit[SETBT(pos)]) != 0)
#define ADDELEMENT(setadd,pos)  ((setadd)[SETWD(pos)] |= bit[SETBT(pos)])
#define GRAPHROW(g,v,m) ((set*)(g) + (long)(v) * (long)(m))

#define FALSE 0
#define TRUE  1

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

#ifndef SEEK_SET
#define SEEK_SET 0
#define SEEK_CUR 1
#define SEEK_END 2
#endif

#ifndef SEEK_CUR
#define SEEK_CUR SEEK_CURRENT
#endif

static long ogf_linelen;

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

static void
gt_abort(char *msg)     /* Write message and halt. */
{
    if (msg) fprintf(stderr,"%s",msg);
    exit(1);
}

/*****************************************************************************
*                                                                            *
*  itos(i,s) converts the int i to a nul-terminated decimal character        *
*  string s.  The value returned is the number of characters excluding       *
*  the nul.                                                                  *
*                                                                            *
*  GLOBALS ACCESSED: NONE                                                    *
*                                                                            *
*****************************************************************************/

static int
itos(int i, char *s)
{
    int digit,j,k;
    char c;
    int ans;

    if (i < 0)
    {
        k = 0;
        i = -i;
        j = 1;
        s[0] = '-';
    }
    else
    {
        k = -1;
        j = 0;
    }

    do
    {
        digit = i % 10;
        i = i / 10;
        s[++k] = digit + '0';
    }
    while (i);

    s[k+1] = '\0';
    ans = k + 1;

    for (;j < k; ++j, --k)
    {
        c = s[j];
        s[j] = s[k];
        s[k] = c;
    }

    return(ans);
}

/*****************************************************************************
*                                                                            *
*  nextelement(set1,m,pos) = the position of the first element in set set1   *
*  which occupies a position greater than pos.  If no such element exists,   *
*  the value is -1.  pos can have any value less than n, including negative  *
*  values.                                                                   *
*                                                                            *
*  GLOBALS ACCESSED: none                                                    *
*                                                                            *
*****************************************************************************/

static int
nextelement(set *set1, int m, int pos)
{
    setword setwd;
    int w;

    if (pos < 0)
    {
        w = 0;
        setwd = set1[0];
    }
    else
    {
        w = SETWD(pos);
        setwd = set1[w] & BITMASK(SETBT(pos));
    }

    for (;;)
    {
        if (setwd != 0)
            return(TIMESWORDSIZE(w) + FIRSTBIT(setwd));
        if (++w == m) return -1;
        setwd = set1[w];
    }
}

/*********************************************************************
opengraphfile(filename,codetype,assumefixed,position)
      opens and positions a file for reading graphs.

  filename = the name of the file to open
            (NULL means stdin, assumed already open)
  codetype   = returns a code for the format.
            This is a combination of SPARSE6, GRAPH6,
            UNKNOWN_TYPE and HAS_HEADER.  If a header is
            present, that overrides the data.  If there is
            no header, the first graph is examined.
  assumefixed = nonzero if files other than stdin should be assumed to
            be seekable and have equal record sizes.
            Ignored if there is a sparse6 header or the first
            graph has sparse6 format.
  position = the number of the record to position to
            (the first is number 1; 0 and -NOLIMIT also mean
             to position at start)

  If the file starts with ">", there must be a header, either
  GRAPH6_HEADER, SPARSE6_HEADER or DIGRAPH6_HEADER.  Otherwise
  opengraphfile() fails.

  The value returned is a file pointer or NULL.
  If assumedfixed is not zero and position > 1, the global variable
  ogf_linelen is set to the length (including \n) of the length of the
  first record.

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

static FILE*
opengraphfile(char *filename, int *codetype, int assumefixed, long position)
{
    FILE *f;
    int c,firstc;
    long i,l,pos,pos1,pos2;
    boolean bad_header;

    if (filename == NULL)
        f = stdin;
    else
    {
        f = fopen(filename,"r");
        if (f == NULL)
        {
            fprintf(stderr,">E opengraphfile: can't open %s\n",filename);
            return NULL;
        }
    }

    firstc = c = getc(f);
    if (c == EOF)
    {
        *codetype = GRAPH6;
        return f;
    }

    if (c != '>')
    {
        *codetype = firstc == ':' ? SPARSE6 : firstc == '&' ? DIGRAPH6 : GRAPH6;
        ungetc(c,f);
    }
    else
    {
        bad_header = FALSE;
        if ((c = getc(f)) == EOF || c != '>')
            bad_header = TRUE;
        if (!bad_header &&
                ((c = getc(f)) == EOF || (c != 'g' && c != 's')))
            bad_header = TRUE;
        if (!bad_header && c == 'g')
        {
            if ((c = getc(f)) == EOF || c != 'r' ||
                (c = getc(f)) == EOF || c != 'a' ||
                (c = getc(f)) == EOF || c != 'p' ||
                (c = getc(f)) == EOF || c != 'h' ||
                (c = getc(f)) == EOF || c != '6' ||
                (c = getc(f)) == EOF || c != '<' ||
                (c = getc(f)) == EOF || c != '<')
                    bad_header = TRUE;
            else
                *codetype = GRAPH6 | HAS_HEADER;
        }
        else if (!bad_header && c == 'd')
        {
            if ((c = getc(f)) == EOF || c != 'i' ||
                (c = getc(f)) == EOF || c != 'g' ||
                (c = getc(f)) == EOF || c != 'r' ||
                (c = getc(f)) == EOF || c != 'a' ||
                (c = getc(f)) == EOF || c != 'p' ||
                (c = getc(f)) == EOF || c != 'h' ||
                (c = getc(f)) == EOF || c != '6' ||
                (c = getc(f)) == EOF || c != '<' ||
                (c = getc(f)) == EOF || c != '<')
                    bad_header = TRUE;
            else
                *codetype = DIGRAPH6 | HAS_HEADER;
        }
        else if (!bad_header && c == 's')
        {
            if ((c = getc(f)) == EOF || c != 'p' ||
                (c = getc(f)) == EOF || c != 'a' ||
                (c = getc(f)) == EOF || c != 'r' ||
                (c = getc(f)) == EOF || c != 's' ||
                (c = getc(f)) == EOF || c != 'e' ||
                (c = getc(f)) == EOF || c != '6' ||
                (c = getc(f)) == EOF || c != '<' ||
                (c = getc(f)) == EOF || c != '<')
                    bad_header = TRUE;
            else
                *codetype = SPARSE6 | HAS_HEADER;
        }
        if (bad_header)
        {
            fprintf(stderr,">E opengraphfile: illegal header in %s\n",
                    filename == NULL ? "stdin" : filename);
            *codetype = UNKNOWN_TYPE | HAS_HEADER;
            return NULL;
        }
    }

    if (position <= 1) return f;

    if (filename == NULL || !assumefixed || (*codetype&SPARSE6)
                         || firstc == ':')
    {
        l = 1;
        while ((c = getc(f)) != EOF)
        {
            if (c == '\n')
            {
                ++l;
                if (l == position) break;
            }
        }
        if (l == position) return f;

        fprintf(stderr,
           ">E opengraphfile: can't find line %ld in %s\n",position,
            filename == NULL ? "stdin" : filename);
        return NULL;
    }
    else
    {
        pos1 = ftell(f);
        if (pos1 < 0)
        {
            fprintf(stderr,">E opengraphfile: error on first ftell\n");
            return NULL;
        }

        for (i = 1; (c = getc(f)) != EOF && c != '\n'; ++i) {}
        ogf_linelen = i;

        if (c == EOF)
        {
            fprintf(stderr,
                    ">E opengraphfile: required record no present\n");
            return NULL;
        }

        pos2 = ftell(f);
        if (pos2 < 0)
        {
            fprintf(stderr,">E opengraphfile: error on second ftell\n");
            return NULL;
        }

        pos = pos1 + (position-1)*(pos2-pos1);
        if (fseek(f,pos,SEEK_SET) < 0)
        {
            fprintf(stderr,">E opengraphfile: seek failed\n");
            return NULL;
        }
    }

    return f;
}

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

static char*
showg_getline(FILE *f)     /* read a line with error checking */
       /* includes \n (if present) and \0.
    Immediate EOF causes NULL return. */
{
    DYNALLSTAT(char,s,s_sz);
    int c;
    long i;

    DYNALLOC1(char,s,s_sz,500,"showg_getline");

    i = 0;
    while ((c = getc(f)) != EOF && c != '\n')
    {
        if (i == s_sz-2) DYNREALLOC(char,s,s_sz,s_sz+1000,"showg_getline");
        s[i++] = c;
    }

    if (i == 0 && c == EOF) return NULL;

    if (c == '\n') s[i++] = '\n';
    s[i] = '\0';
    return s;
}

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

int
graphsize(char *s)
/* Get size of graph out of graph6, digraph6 or sparse6 string. */
{
    char *p;
    int n;

    if (s[0] == ':' || s[0] == '&') p = s+1;
    else                            p = s;
    n = *p++ - BIAS6;

    if (n > SMALLN)
    {
        n = *p++ - BIAS6;
        if (n > SMALLN)
        {
            n = *p++ - BIAS6;
            n = (n << 6) | (*p++ - BIAS6);
            n = (n << 6) | (*p++ - BIAS6);
            n = (n << 6) | (*p++ - BIAS6);
            n = (n << 6) | (*p++ - BIAS6);
            n = (n << 6) | (*p++ - BIAS6);
        }
        else
        {
            n = (n << 6) | (*p++ - BIAS6);
            n = (n << 6) | (*p++ - BIAS6);
        }
    }
    return n;
}

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

static void
stringtograph(char *s, graph *g, int m)
/* Convert string (graph6, digraph6 or sparse6 format) to graph. */
/* Assumes g is big enough to hold it.   */
{
    char *p;
    int n,i,j,k,v,x,nb,need;
    size_t ii;
    set *gi,*gj;
    boolean done;

    n = graphsize(s);
    if (n == 0) return;

    p = s + (s[0] == ':' || s[0] == '&') + SIZELEN(n);

    if (TIMESWORDSIZE(m) < n)
        gt_abort(">E stringtograph: impossible m value\n");

    for (ii = m*(size_t)n; --ii > 0;) g[ii] = 0;
    g[0] = 0;

    if (s[0] != ':' && s[0] != '&')       /* graph6 format */
    {
        k = 1;
        for (j = 1; j < n; ++j)
        {
            gj = GRAPHROW(g,j,m);

            for (i = 0; i < j; ++i)
            {
                if (--k == 0)
                {
                    k = 6;
                    x = *(p++) - BIAS6;
                }

                if ((x & TOPBIT6))
                {
                    gi = GRAPHROW(g,i,m);
                    ADDELEMENT(gi,j);
                    ADDELEMENT(gj,i);
                }
                x <<= 1;
            }
        }
    }
    else if (s[0] == '&')
    {
        k = 1;
        for (i = 0; i < n; ++i)
        {
            gi = GRAPHROW(g,i,m);

            for (j = 0; j < n; ++j)
            {
                if (--k == 0)
                {
                    k = 6;
                    x = *(p++) - BIAS6;
                }

                if ((x & TOPBIT6))
                {
                    ADDELEMENT(gi,j);
                }
                x <<= 1;
            }
        }
    }
    else    /* sparse6 format */
    {
        for (i = n-1, nb = 0; i != 0 ; i >>= 1, ++nb) {}

        k = 0;
        v = 0;
        done = FALSE;
        while (!done)
        {
            if (k == 0)
            {
                x = *(p++);
                if (x == '\n' || x == '\0')
                {
                    done = TRUE; continue;
                }
                else
                {
                    x -= BIAS6; k = 6;
                }
            }
            if ((x & B(k))) ++v;
            --k;

            need = nb;
            j = 0;
            while (need > 0 && !done)
            {
                if (k == 0)
                {
                    x = *(p++);
                    if (x == '\n' || x == '\0')
                    {
                        done = TRUE; continue;
                    }
                    else
                    {
                        x -= BIAS6; k = 6;
                    }
                }
                if (need >= k)
                {
                    j = (j << k) | (x & M(k));
                    need -= k; k = 0;
                }
                else
                {
                    k -= need;
                    j = (j << need) | ((x >> k) & M(need));
                    need = 0;
                }
            }
            if (done) continue;

            if (j > v)
                v = j;
            else if (v < n)
            {
                ADDELEMENT(GRAPHROW(g,v,m),j);
                ADDELEMENT(GRAPHROW(g,j,m),v);
            }
        }
    }
}

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

graph*                 /* read graph into nauty format */
readgg(FILE *f, graph *g, int reqm, int *pm, int *pn, boolean *digraph)
/* graph6, digraph6 and sparse6 formats are supported
   f = an open file
   g = place to put the answer (NULL for dynamic allocation)
   reqm = the requested value of m (0 => compute from n)
   *pm = the actual value of m
   *pn = the value of n
   *digraph = whether the input is a digraph
*/
{
    char *s,*p;
    int m,n;
    int readg_code;

    if ((s = showg_getline(f)) == NULL) return NULL;

    if (s[0] == ':')
    {
        *digraph = FALSE;
        p = s + 1;
    }
    else if (s[0] == '&')
    {
        readg_code = DIGRAPH6;
        *digraph = TRUE;
        p = s + 1;
    }
    else
    {
        readg_code = GRAPH6;
        *digraph = FALSE;
        p = s;
    }

    while (*p >= BIAS6 && *p <= MAXBYTE)
        ++p;
    if (*p == '\0')
        gt_abort(">E readgg: missing newline\n");
    else if (*p != '\n')
        gt_abort(">E readgg: illegal character\n");

    n = graphsize(s);
    if (readg_code == GRAPH6 && p - s != G6LEN(n))
        gt_abort(">E readgg: truncated graph6 line\n");
    if (readg_code == DIGRAPH6 && p - s != D6LEN(n))
        gt_abort(">E readgg: truncated digraph6 line\n");

    if (reqm > 0 && TIMESWORDSIZE(reqm) < n)
        gt_abort(">E readgg: reqm too small\n");
    else if (reqm > 0)
        m = reqm;
    else
        m = (n + WORDSIZE - 1) / WORDSIZE;

    if (g == NULL)
    {
        if ((g = (graph*)ALLOCS(n,m*sizeof(graph))) == NULL)
            gt_abort(">E readgg: malloc failed\n");
    }

    *pn = n;
    *pm = m;

    stringtograph(s,g,m);
    return g;
}

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

static int
longvalue(char **ps, long *l)
{
    boolean neg,pos;
    long sofar,last;
    char *s;

    s = *ps;
    pos = neg = FALSE;
    if (*s == '-')
    {
        neg = TRUE;
        ++s;
    }
    else if (*s == '+')
    {
        pos = TRUE;
        ++s;
    }

    if (*s < '0' || *s > '9')
    {
        *ps = s;
        return (pos || neg) ? ARG_ILLEGAL : ARG_MISSING;
    }

    sofar = 0;

    for (; *s >= '0' && *s <= '9'; ++s)
    {
        last = sofar;
        sofar = sofar * 10 + (*s - '0');
        if (sofar < last || sofar > MAXARG)
        {
            *ps = s;
            return ARG_TOOBIG;
        }
    }
    *ps = s;
    *l = neg ? -sofar : sofar;
    return ARG_OK;
}

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

static void
arg_int(char **ps, int *val, char *id)
{
    int code;
    long longval;

    code = longvalue(ps,&longval);
    *val = longval;
    if (code == ARG_MISSING || code == ARG_ILLEGAL)
    {
        fprintf(stderr,">E %s: missing argument value\n",id);
        gt_abort(NULL);
    }
    else if (code == ARG_TOOBIG || *val != longval)
    {
        fprintf(stderr,">E %s: argument value too large\n",id);
        gt_abort(NULL);
    }
}

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

static void
arg_range(char **ps, long *val1, long *val2, char *id)
{
    int code;
    char *s;

    s = *ps;
    code = longvalue(&s,val1);
    if (code != ARG_MISSING)
    {
        if (code == ARG_ILLEGAL)
        {
            fprintf(stderr,">E %s: bad range\n",id);
            gt_abort(NULL);
        }
        else if (code == ARG_TOOBIG)
        {
            fprintf(stderr,">E %s: value too big\n",id);
            gt_abort(NULL);
        }
    }
    else if (*s != ':' && *s != '-')
    {
        fprintf(stderr,">E %s: missing value\n",id);
        gt_abort(NULL);
    }
    else
        *val1 = -NOLIMIT;

    if (*s == ':' || *s == '-')
    {
        ++s;
        code = longvalue(&s,val2);
        if (code == ARG_MISSING)
            *val2 = NOLIMIT;
        else if (code == ARG_TOOBIG)
        {
            fprintf(stderr,">E %s: value too big\n",id);
            gt_abort(NULL);
        }
        else if (code == ARG_ILLEGAL)
        {
            fprintf(stderr,">E %s: illegal range\n",id);
            gt_abort(NULL);
        }
    }
    else
        *val2 = *val1;

    *ps = s;
}

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

#define LABELORG 0   /* number of first vertex (any integer >= 0) */
#define LINELEN 78   /* max characters per line (0 = no limit) */

static FILE *infile,*outfile;
static long nin;

/*****************************************************************************
*                                                                            *
*  putsetx(f,set1,curlenp,linelength,m,compress,start)   writes the set      *
*  set1 to file f using at most linelength characters per line (excluding    *
*  '\n').   Set elements less than or equal to start are ignored.            *
*  *curlenp is the number of characters on the line so far; it is updated.   *
*  A range j1,j1+1,...,j2 for j2-j1>=2 is written as "j1:j2" if compress     *
*  is nonzero (eg. TRUE); otherwise each element is written separately.      *
*  No final '\n' is written.  labelorg is used.                              *
*                                                                            *
*  FUNCTIONS CALLED: nextelement(),itos()                                    *
*                                                                            *
*****************************************************************************/

static void
putsetx(FILE *f, set *set1, int *curlenp, int linelength, int m,
    boolean compress, int start)
{
    int slen,j1,j2;
    char s[40];
    boolean first;

    first = TRUE;
    j1 = start;
    while ((j1 = nextelement(set1,m,j1)) >= 0)
    {
        j2 = j1;
        if (compress)
        {
            while (nextelement(set1,m,j2) == j2 + 1)
                ++j2;
            if (j2 == j1+1)
                j2 = j1;
        }
        slen = itos(j1 + labelorg,s);
        if (j2 >= j1 + 2)
        {
            s[slen] = ':';
            slen += 1 + itos(j2 + labelorg,&s[slen+1]);
        }

        if (*curlenp + slen + 1 >= linelength && linelength > 0)
        {
            fprintf(f,"\n ");
            *curlenp = 1;
        }
        if (first)
        {
            fprintf(f,"%s",s);
            *curlenp += slen;
            first = FALSE;
        }
        else
        {
            fprintf(f," %s",s);
            *curlenp += slen + 1;
        }
        j1 = j2;
    }
}

/*****************************************************************************
*                                                                            *
*  STOLEN FROM naututil.c                                                    *
*  putgraphx(f,g,linelength,m,n) writes a list of the edges of g to f        *
*  using at most linelength characters per line (excluding '\n').            *
*  If triang, only write the upper triangle.                                 *
*  labelorg is used.                                                         *
*                                                                            *
*****************************************************************************/

static void
putgraphx(FILE *f, graph *g, int linelength, boolean triang, int m, int n)
{
    int i,curlen;
    set *pg;

    for (i = 0, pg = g; i < n; ++i, pg += m)
    {
        fprintf(f,"%3d : ",i + labelorg);
        curlen = 7;
        putsetx(f,pg,&curlen,linelength,m,FALSE,triang ? i-1 : -1);
        fprintf(f,";\n");
    }
}

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

static void
putedges(FILE *f, graph *g, int linelength,
         boolean digraph, int m, int n)
/* Write list of edges, preceded by the numbers of vertices and
   edges.  Use labelorg */
{
    int i,j,curlen,ne;
    char s[20];
    set *pg;

    ne = 0;
    for (i = 0, pg = g; i < n; ++i, pg += m)
    {
        for (j = (digraph?-1:i-1); (j = nextelement(pg,m,j)) >= 0;)
            ++ne;
    }

    fprintf(f,"%d %d\n",n,ne);

    curlen = 0;
    for (i = 0, pg = g; i < n; ++i, pg += m)
    {
        for (j = (digraph ? -1 : i-1); (j = nextelement(pg,m,j)) >= 0;)
        {
            if (curlen > 0 && curlen > linelength - 10 && linelength > 0)
            {
                fprintf(f,"\n");
                curlen = 0;
            }
            if (curlen > 0)
            {
                fprintf(f," ");
                curlen += 2;
            }
            curlen += itos(i+labelorg,s);
            fprintf(f,"%s",s);
            fprintf(f," ");
            curlen += 1 + itos(j+labelorg,s);
            fprintf(f,"%s",s);
        }
    }
    fprintf(f,"\n");
}

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

static void
putcgraph(FILE *f, graph *g, int linelength, boolean digraph, int m, int n)
/* write compressed form, using labelorg */
{
    int i,curlen,j0;
    int semicolons;
    char s[20];
    set *pg;

    curlen = itos(n,s)+2;
    fprintf(f,";n%s%s",s,(digraph?"dg":"g"));

    semicolons = 0;
    for (i = 0, pg = g; i < n; ++i, pg += m)
    {
        j0 = digraph ? -1: i-1;
        if (nextelement(pg,m,j0) >= 0)
        {
            while (semicolons > 0)
            {
                if (curlen >= linelength-1 && linelength > 0)
                {
                    fprintf(f,"\n ");
                    curlen = 1;
                }
                fprintf(f,";");
                ++curlen;
                --semicolons;
            }
            putsetx(f,pg,&curlen,linelength,m,FALSE,j0);
            semicolons = 1;
        }
        else
            ++semicolons;
    }
    fprintf(f,".\n");
}

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

static void
putam(FILE *f, graph *g, int linelength, boolean space, boolean triang,
      int m, int n)   /* write adjacency matrix */
{
    set *gi;
    int i,j;
    boolean first;

    for (i = 0, gi = (set*)g; i < n - (triang!=0); ++i, gi += m)
    {
        first = TRUE;
        for (j = triang ? i+1 : 0; j < n; ++j)
        {
            if (!first && space) putc(' ',f);
            else                 first = FALSE;
            if (ISELEMENT(gi,j)) putc('1',f);
            else                 putc('0',f);
        }
        putc('\n',f);
    }
}

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

int
main(int argc, char *argv[])
{
    graph *g;
    int m,n,codetype;
    int argnum,j;
    char *arg,sw;
    boolean badargs,digraph;
    long maxin,pval1,pval2;
    boolean fswitch,pswitch,cswitch,dswitch;
    boolean aswitch,lswitch,oswitch,Fswitch;
    boolean Aswitch,eswitch,tswitch,qswitch;
    int linelength;
    char *infilename,*outfilename;

    if (argc > 1 && (strcmp(argv[1],"-help") == 0
                   || (strcmp(argv[1],"--help") == 0)))
    {
        printf("\nUsage: %s\n\n%s",USAGE,HELPTEXT);
        exit(0);
    }

    if (sizeof(setword) < 4)
    {
        fprintf(stderr,">E showg: setword too small\n");
        fprintf(stderr," Please report this to brendan.mckay@anu.edu.au\n");
        exit(1);
    }

    fswitch = pswitch = cswitch = dswitch = FALSE;
    aswitch = lswitch = oswitch = Fswitch = FALSE;
    Aswitch = eswitch = tswitch = qswitch = FALSE;
    infilename = outfilename = NULL;
    linelength = LINELEN;
    labelorg = 0;

    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('a',aswitch)
                else SWBOOLEAN('A',Aswitch)
                else SWBOOLEAN('c',cswitch)
                else SWBOOLEAN('d',dswitch)
                else SWBOOLEAN('e',eswitch)
                else SWBOOLEAN('f',fswitch)
                else SWBOOLEAN('F',Fswitch)
                else SWBOOLEAN('t',tswitch)
                else SWBOOLEAN('q',qswitch)
                else SWRANGE('p',pswitch,pval1,pval2,"showg -p")
                else SWINT('l',lswitch,linelength,"showg -l")
                else SWINT('o',oswitch,labelorg,"listo -o")
                else badargs = TRUE;
            }
        }
        else
        {
            ++argnum;
            if      (argnum == 1) infilename = arg;
            else if (argnum == 2) outfilename = arg;
            else                  badargs = TRUE;
        }
    }

    if (labelorg < 0) gt_abort(">E showg: negative origin forbidden.\n");

    if ((aswitch!=0) + (Aswitch!=0) + (eswitch!=0)
                     + (dswitch!=0) + (cswitch!=0) > 1)
        gt_abort(">E showg: -aAecd are incompatible\n");

    if (badargs)
    {
        fprintf(stderr,">E Usage: %s\n",USAGE);
        fprintf(stderr,"Use showg -help to see a list of the options.\n");
        exit(1);
    }

    if (!pswitch || pval1 < 1) pval1 = 1;

    if (infilename && infilename[0] == '-') infilename = NULL;
    infile = opengraphfile(infilename,&codetype,fswitch,
                           pswitch ? pval1 : 1);
    if (!infile) exit(1);
    if (!infilename) infilename = "stdin";

    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);
    }

    nin = 0;
    if (!pswitch || pval2 == NOLIMIT)
        maxin = NOLIMIT;
    else if (pval1 < 1) maxin = pval2;
    else                maxin = pval2 - pval1 + 1;
    while (nin < maxin || maxin == NOLIMIT)
    {
        if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
        ++nin;

        if (Fswitch && nin > 1) fprintf(outfile,"\f");

        if (cswitch)
            putcgraph(outfile,g,linelength,digraph,m,n);
        else if (dswitch)
        {
            if (qswitch)
                fprintf(outfile,"%d\n",n);
            else
            {
                fprintf(outfile,"\n!Graph %ld.\n",pval1+nin-1);
                fprintf(outfile,"n=%d $=%d g\n",n,labelorg);
            }
            putgraphx(outfile,g,linelength,tswitch,m,n);
            if (!qswitch) fprintf(outfile,"$$\n");
        }
        else
        {
            if (qswitch)
            {
                if (!eswitch) fprintf(outfile,"%d\n",n);
            }
            else fprintf(outfile,"\nGraph %ld, order %d.\n",
                                 pval1+nin-1,n);
            if (aswitch|Aswitch)
                putam(outfile,g,linelength,Aswitch,tswitch,m,n);
            else if (eswitch)
                putedges(outfile,g,linelength,digraph,m,n);
            else
                putgraphx(outfile,g,linelength,tswitch,m,n);
        }
        FREES(g);
    }

    exit(0);
}

quality91%

¤ Dauer der Verarbeitung: 0.22 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.