gb_lisa.w

模拟器提供了一个简单易用的平台

The fifth and final line of each row contains $4+4+2=10$ more pixels,
represented as $5+5+3$ radix-85 digits.

@<Open the data file, skipping unwanted rows at the beginning@>=
if (gb_open("lisa.dat")!=0)
  panic(early_data_fault); /* couldn't open the file; |io_errors| tells why */
for (i=0;i<m0;i++)
  for (j=0;j<5;j++) gb_newline(); /* ignore one row of data */

@ @<Close the data file, skipping unwanted rows at the end@>=
for (i=m1;i<MAX_M;i++)
  for (j=0;j<5;j++) gb_newline(); /* ignore one row of data */
if (gb_close()!=0)
  panic(late_data_fault);
   /* checksum or other failure in data file; see |io_errors| */

@ @<Read a row of input into |in_row|@>=
{@+register long dd;
  for (j=15,cur_pix=&in_row[0];;cur_pix+=4) {
    dd=gb_digit(85);@+dd=dd*85+gb_digit(85);@+dd=dd*85+gb_digit(85);
    if (cur_pix==&in_row[MAX_N-2]) break;
    dd=dd*85+gb_digit(85);@+dd=dd*85+gb_digit(85);
    *(cur_pix+3)=dd&0xff;@+dd=(dd>>8)&0xffffff;
    *(cur_pix+2)=dd&0xff;@+dd>>=8;
    *(cur_pix+1)=dd&0xff;@+*cur_pix=dd>>8;
    if (--j==0) gb_newline(),j=15;
  }
  *(cur_pix+1)=dd&0xff;@+*cur_pix=dd>>8;@+gb_newline();
}

@ @<Private var...@>=
static long in_row[MAX_N];

@* Planar graphs. We can obtain a large family of planar graphs based on
digitizations of Mona Lisa by using the following simple scheme: Each matrix
of pixels defines a set of connected regions containing pixels of the same
value. (Two pixels are considered adjacent if they share an edge.)
These connected regions are taken to be vertices of an undirected graph;
two vertices are adjacent if the corresponding regions have at least
one pixel edge in common.

We can also state the construction another way. If we take any planar
graph and collapse two adjacent vertices, we obtain another planar
graph. Suppose we start with the planar graph having $mn$ vertices
$[k,l]$ for $0\le k<m$ and $0\le l<n$, where $[k,l]$ is adjacent to
$[k,l-1]$ when $l>0$ and to $[k-1,l]$ when $k>0$. Then we can attach
pixel values to each vertex, after which we can repeatedly collapse
adjacent vertices whose pixel values are equal. The resulting planar
graph is the same as the graph of connected regions that was described
in the previous paragraph.

The subroutine call |plane_lisa(m,n,d,m0,m1,n0,n1,d0,d1)| constructs
the planar graph associated with the digitization produced by |lisa|.
The description of |lisa|, given earlier, explains the significance of
parameters |m|, |n|, |d|, |m0|, |m1|, |n0|, |n1|, |d0|, and |d1|. There will
be at most $mn$ vertices, and the graph will be simply an $m\times n$
grid unless |d| is small enough to permit adjacent pixels to have
equal values. The graph will also become rather trivial if |d| is
too small.

Utility fields |first_pixel| and |last_pixel| give, for each vertex,
numbers of the form $k*n+l$, identifying the topmost/leftmost
and bottommost/rightmost positions $[k,l]$ in the region corresponding
to that vertex. Utility fields |matrix_rows| and |matrix_cols| in
the |Graph| record contain the values of |m| and~|n|; thus, in particular,
the value of |n| needed to decompose |first_pixel| and |last_pixel| into
individual coordinates can be found in |g->matrix_cols|.

The original pixel value of a vertex is placed into its |pixel_value|
utility field.

@d pixel_value x.I
@d first_pixel y.I
@d last_pixel z.I
@d matrix_rows uu.I
@d matrix_cols vv.I

@p Graph *plane_lisa(m,n,d,m0,m1,n0,n1,d0,d1)
  unsigned long m,n; /* number of rows and columns desired */
  unsigned long d; /* maximum value desired */
  unsigned long m0,m1; /* input will be from rows $[|m0|\,.\,.\,|m1|)$ */
  unsigned long n0,n1; /* and from columns $[|n0|\,.\,.\,|n1|)$ */
  unsigned long d0,d1; /* lower and upper threshold of raw pixel scores */
{@+@<Local variables for |plane_lisa|@>@;@#
  init_area(working_storage);
  @<Figure out the number of connected regions, |regs|@>;
  @<Set up a graph with |regs| vertices@>;
  @<Put the appropriate edges into the graph@>;
trouble: gb_free(working_storage);
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* oops, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Local variables for |plane_lisa|@>=
Graph *new_graph; /* the graph constructed by |plane_lisa| */
register long j,k,l; /* all-purpose indices */
Area working_storage; /* tables needed while |plane_lisa| does its thinking */
long *a; /* the matrix constructed by |lisa| */
long regs=0; /* number of vertices generated so far */

@ @<gb_lisa.h@>=
#define pixel_value @t\quad@> x.I /* definitions for the header file */
#define first_pixel @t\quad@> y.I
#define last_pixel @t\quad@> z.I
#define matrix_rows @t\quad@> uu.I
#define matrix_cols @t\quad@> vv.I

@ The following algorithm for counting the connected regions considers
the array elements |a[k,l]| to be linearly ordered as they appear
in memory. Thus we can speak of the $n$ elements preceding a given
element |a[k,l]|, if $k>0$; these are the elements |a[k,l-1]|, \dots,
|a[k,0]|, |a[k-1,n-1]|, \dots, |a[k-1,l]|. These $n$ elements appear
in $n$ different columns.

During the algorithm, we move through the array from bottom right
to top left, maintaining an auxiliary table $\langle f[0],\ldots,f[n-1]
\rangle$ with the following significance: Whenever two of the
$n$ elements preceding our current position $[k,l]$ are connected to
each other by a sequence of pixels with equal value, where the connecting
links do not involve pixels more than $n$ steps before our current
position, those elements will be linked together in the $f$ array.
More precisely, we will have $f[c_1]=c_2$, \dots, $f[c_{j-1}]=c_j$,
and $f[c_j]=c_j$, when there are $j$ equivalent elements in columns
$c_1$, \dots,~$c_j$. Here $c_1$ will be the ``last'' column and
$c_j$ the ``first,'' in wraparound order; each element with $f[c]\ne c$
points to an earlier element.

The main function of the |f| table is to identify the topmost/leftmost
pixel of a region. If we are at position |[k,l]| and if we find $f[l]=l$
while $a[k-1,l]\ne a[k,l]$, there is no way to connect |[k,l]| to
earlier positions, so we create a new vertex for it.

We also change the |a| matrix, to facilitate another algorithm
below. If position |[k,l]| is the topmost/leftmost pixel of a region,
we set |a[k,l]=-1-a[k,l]|; otherwise we set |a[k,l]=f[l]|, the column of
a preceding element belonging to the same region.

@<Figure out the number...@>=
a=lisa(m,n,d,m0,m1,n0,n1,d0,d1,working_storage);
if (a==NULL) return NULL; /* |panic_code| has been set by |lisa| */
sscanf(lisa_id,"lisa(%lu,%lu,",&m,&n); /* adjust for defaults */
f=gb_typed_alloc(n,unsigned long,working_storage);
if (f==NULL) {
  gb_free(working_storage); /* recycle the |a| matrix */
  panic(no_room+2); /* there's no room for the |f| vector */
}
@<Pass over the |a| matrix from bottom right to top left, looking
  for the beginnings of connected regions@>;

@ @<Local variables for |plane_lisa|@>=
unsigned long *f; /* beginning of array |f|;
                     $f[j]$ is the column of an equivalent element */
long *apos; /* the location of |a[k,l]| */

@ We maintain a pointer |apos| equal to |&a[k,l]|, so that
|*(apos-1)=a[k,l-1]| and |*(apos-n)=a[k-1,l]| when $l>0$ and $k>0$.

The loop that replaces $f[j]$ by $j$ can cause this algorithm to
take time $mn^2$. We could improve the worst case by using path
compression, but the extra complication is rarely worth the trouble.

@<Pass over the |a| matrix from bottom right to top left, looking
  for the beginnings of connected regions@>=
for (k=m, apos=a+n*(m+1)-1; k>=0; k--)
  for (l=n-1; l>=0; l--,apos--) {
    if (k<m) {
      if (k>0&&*(apos-n)==*apos) {
        for (j=l; f[j]!=j; j=f[j]) ; /* find the first element */
        f[j]=l; /* link it to the new first element */
        *apos=l;
      }@+else if (f[l]==l) *apos=-1-*apos,regs++; /* new region found */
        else *apos=f[l];
    }
    if (k>0&&l<n-1&&*(apos-n)==*(apos-n+1)) f[l+1]=l;
    f[l]=l;
  }

@ @<Set up a graph with |regs| vertices@>=
new_graph=gb_new_graph(regs);
if (new_graph==NULL)
  panic(no_room); /* out of memory before we're even started */
sprintf(new_graph->id,"plane_%s",lisa_id);
strcpy(new_graph->util_types,"ZZZIIIZZIIZZZZ");
new_graph->matrix_rows=m;
new_graph->matrix_cols=n;

@ Now we make another pass over the matrix, this time from top left
to bottom right. An auxiliary vector of length |n| is once again
sufficient to tell us when one region is adjacent to a previous one.
In this case the vector is called |u|, and it contains pointers to
the vertices in the $n$ positions before our current position.
We assume that a pointer to a |Vertex| takes the same amount of
memory as an |unsigned long|, hence |u| can share the space formerly
occupied by~|f|; if this is not the case, a system-dependent
change should be made here.
@^system dependencies@>

The vertex names are simply integers, starting with 0.

@<Put the appropriate edges into the graph@>=
regs=0;
u=(Vertex**)f;
for (l=0;l<n;l++) u[l]=NULL;
for (k=0,apos=a,aloc=0;k<m;k++)
  for (l=0;l<n;l++,apos++,aloc++) {
    w=u[l];
    if (*apos<0) {
      sprintf(str_buf,"%ld",regs);
      v=new_graph->vertices+regs;
      v->name=gb_save_string(str_buf);
      v->pixel_value=-*apos-1;
      v->first_pixel=aloc;
      regs++;
    }@+else v=u[*apos];
    u[l]=v;
    v->last_pixel=aloc;
    if (gb_trouble_code) goto trouble;
    if (k>0 && v!=w) adjac(v,w);
    if (l>0 && v!=u[l-1]) adjac(v,u[l-1]);
  }

@ @<Local variables for |pl...@>=
Vertex **u; /* table of vertices for previous $n$ pixels */
Vertex *v; /* vertex corresponding to position |[k,l]| */
Vertex *w; /* vertex corresponding to position |[k-1,l]| */
long aloc; /* $k*n+l$ */

@ The |adjac| routine makes two vertices adjacent, if they aren't already.
A faster way to recognize duplicates would probably speed things up.

@<Private sub...@>=
static void adjac(u,v)
  Vertex *u,*v;
{@+Arc *a;
  for (a=u->arcs;a;a=a->next)
    if (a->tip==v) return;
  gb_new_edge(u,v,1L);
}

@* Bipartite graphs. An even simpler class of Mona-Lisa-based graphs
is obtained by considering the |m| rows and |n| columns to be individual
vertices, with a row adjacent to a column if the associated pixel value
is sufficiently large or sufficiently small. All edges have length~1.

The subroutine call |bi_lisa(m,n,m0,m1,n0,n1,thresh,c)| constructs
the bipartite graph corresponding to the $m\times n$
digitization produced by |lisa|, using parameters |(m0,m1,n0,n1)| to
define a rectangular subpicture as described earlier.
The threshold parameter |thresh| should be between 0 and~65535.
If the pixel value in row |k| and column |l| is at least |thresh/65535| of
its maximum, vertices |k| and~|l| will be adjacent.
If |c!=0|, however, the convention is reversed; vertices are then
adjacent when the corresponding pixel value is {\sl smaller\/} than
|thresh/65535|. Thus adjacencies come from ``light'' areas of
da Vinci's painting when |c=0| and from ``dark'' areas when |c!=0|. There
are |m+n| vertices and up to $m\times n$ edges.

The actual pixel value is recorded in utility field |b.I| of each arc,
and scaled to be in the range $[0,65535]$.

@p Graph *bi_lisa(m,n,m0,m1,n0,n1,thresh,c)
  unsigned long m,n; /* number of rows and columns desired */
  unsigned long m0,m1; /* input will be from rows $[|m0|\,.\,.\,|m1|)$ */
  unsigned long n0,n1; /* and from columns $[|n0|\,.\,.\,|n1|)$ */
  unsigned long thresh; /* threshold defining adjacency */
  long c; /* should we prefer dark pixels to light pixels? */
{@+@<Local variables for |bi_lisa|@>@;@#
  init_area(working_storage);
  @<Set up a bipartite graph with |m+n| vertices@>;
  @<Put the appropriate edges into the bigraph@>;
  gb_free(working_storage);
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* oops, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Local variables for |bi_lisa|@>=
Graph *new_graph; /* the graph constructed by |bi_lisa| */
register long k,l; /* all-purpose indices */
Area working_storage; /* tables needed while |bi_lisa| does its thinking */
long *a; /* the matrix constructed by |lisa| */
long *apos; /* the location of |a[k,l]| */
register Vertex *u,*v; /* current vertices of interest */

@ @<Set up a bipartite graph...@>=
a=lisa(m,n,65535L,m0,m1,n0,n1,0L,0L,working_storage);
if (a==NULL) return NULL; /* |panic_code| has been set by |lisa| */
sscanf(lisa_id,"lisa(%lu,%lu,65535,%lu,%lu,%lu,%lu",&m,&n,&m0,&m1,&n0,&n1);
new_graph=gb_new_graph(m+n);
if (new_graph==NULL)
  panic(no_room); /* out of memory before we're even started */
sprintf(new_graph->id,"bi_lisa(%lu,%lu,%lu,%lu,%lu,%lu,%lu,%c)",
   m,n,m0,m1,n0,n1,thresh,c?'1':'0');
new_graph->util_types[7]='I'; /* enable field |b.I| */
mark_bipartite(new_graph,m);
for (k=0,v=new_graph->vertices;k<m;k++,v++) {
  sprintf(str_buf,"r%ld",k); /* row vertices are called |"r0"|, |"r1"|, etc. */
  v->name=gb_save_string(str_buf);
}
for (l=0;l<n;l++,v++) {
  sprintf(str_buf,"c%ld",l); /* column vertices are called |"c0"|,
                                            |"c1"|, etc. */
  v->name=gb_save_string(str_buf);
}

@ Since we've called |lisa| with |d=65535|, the determination of
adjacency is simple.

@<Put the appropriate edges into the bigraph@>=
for (u=new_graph->vertices,apos=a;u<new_graph->vertices+m;u++)
  for (v=new_graph->vertices+m;v<new_graph->vertices+m+n;apos++,v++) {
    if (c?*apos<thresh:*apos>=thresh) {
      gb_new_edge(u,v,1L);
      u->arcs->b.I=v->arcs->b.I=*apos;
    }
  }

@* Index. As usual, we close with an index that
shows where the identifiers of \\{gb\_lisa} are defined and used.