% -*- Mode:TeX -*-

%% The documentstyle options along with the pagestyle can be used to generate
%% a technical report, a draft copy, or a regular thesis.  You may need to
%% re-specify the pagestyle after you \include  cover.tex.  For more
%% information, see the first few lines of mitthesis.sty. 

\documentstyle[12pt,tgrind,vi]{edyamp}
\pagestyle{plain}

%% This bit allows you to either specify only the files which you wish to
%% process, or `all' to process all files which you \include.

%\typein [\files]{Enter file names to process, (chap1,chap2 ...), or `all' to
%process all files:}
%\def\all{all}
%\ifx\files\all \typeout{Including all files.} \else \typeout{Including only \files.} \includeonly{\files} \fi

\begin{document}

% This is for Macpix on Sun
\include{psadobe}
\psadobesun
% This is for program environment
\include{program}

\tableofcontents
\newpage
\listoffigures
\pagestyle{plain}
\pagenumbering{roman}
\tableofcontents
\newpage
\listoffigures
\pagenumbering{arabic}
\chapter{Introduction}
A pedigree diagram is the tool that provides a genetic counselor with the
most important information, the family history of the consultand.
Traditionally, pedigree diagrams are drawn by hand after the
counselor has collected the family genealogical history and
information pertaining to each individual's affection.
The counselor then performs probabilistic calculations
based upon the given information and the disease's characteristic to
arrive at his conclusions.

There are a few possible ways to perform calculations on pedigrees.  A
Bayesian approach, using probabilistic belief networks, can be very
complex to do manually, even with the aid of a calculator.
{\sc GenInfer}, a program written by Nomi Harris \cite{t1}, can help automate
this calculation process.  Its user interface, however, requires the
counselor to type in names and other pieces of data for each individual in
the pedigree.  While sufficient, this method is tedious and not easy
to use.  Moreover, it does not provide the pedigree diagram for the
counselor to check on its calculations.

A better interface should take advantage of the high-resolution
graphical interface of modern personal computer by letting the counselor
draw the pedigree with a mouse on the screen, and questioning the
counselor for the required information.  The pedigree diagram generated
should be ``prettified'' by the computer so that an inherently complex
diagram will still be relatively easy to read.

\section{Overview of the Thesis}
The next section provides a review of the literature in the field of
automatic layout of pedigree diagrams and a related field of automatic
layout of graphs.  Chapter 2 specifies the problem in details and
enumerates the requirements that the program has to satisfy.  It also
discusses the aesthetics issue and the design of the program.  Chapter
3 describes the implementation of the program.  Finally, Chapter 4
examines and evaluates the results and discusses future modifications to
the program.

\section{Review of Literature}
A number of pedigree drawing programs have been written
before\cite{round,t2,alun}.  PedDraw
\cite{t2}, running on the Apple Macintosh computers, is one of the more
capable and complete.  It is intended to be used, however, as a
stand-alone program whose sole purpose is to generate diagrams and
thus cannot be used as a front-end to {\sc GenInfer}.
In fact, none of the existing programs can be easily adapted to be
used with {\sc GenInfer}.

If we generalize a little, however, we can find many more applicable
papers.  Pedigree diagrams can be thought of as a specialization of graphs.
The field of automatic graph drawing is much more fertile.  Many papers
were written about ways to draw graphs automatically.  Some of the
approaches are very general and deal with any kind of
graphs\cite{p1,p2}.  Some deal specifically with trees, especially
binary trees\cite{p3,p4}.  Some deal only with a rectilinear
graph\cite{p7}, an entity-relationship diagram\cite{p5}, or a data
flow diagram\cite{p6}.  An implementation also exists that allows the
user to edit and examine graphs while minimizing the number of edge
crossings\cite{p8}.

These papers present many significant concepts that can be applied in
laying out pedigree diagrams as well.  The most important concept is
that of aesthetics, which was explicitly stated in\cite{p3,p4,p1} and
implicitly assumed in other papers.  Aesthetics in this case means the
set of rules that the diagram has to satisfy in order for it to be
judged acceptable (aesthetically pleasing).  For example, in
drawing a tree, which is a planar graph, the edges should never
cross\cite{p3}.  Aesthetics can be thought of as a kind of heuristic
for evaluating whether the drawn diagram is satisfactory.  In some
instances, all the aesthetic rules may not be satisfied at the same
time because they are contradictory.  These self-contradicting rules
can still be used, however, if they produce satisfactory graphs most
of the time.

\chapter{Design and Specification}

This chapter discusses the problem and design issues in details.  The
first section describes the pedigree diagram and its conventions.  The
next section describes the system and its requirements.  Finally, the
last section discusses the concept of readability of diagrams,
specifically, their aesthetics; aesthetics measures are also presented.

\section{Pedigree Diagram}
\label{pedsec}
Genetic counselors use pedigree diagrams to construct a graphical
record of the family health history.  The relationships between members
of the family are presented schematically.
To be useful, the diagram must be arranged to aid
easy viewing and analyzing.

There are many ways to draw a pedigree diagram.  At present, an
international standard for drawing and annotating pedigree diagrams
does not exist.  Some symbols are common to all schemes; a few others
have a number of recognizable variants.  The
common symbols and notations are presented in Figure~\ref{commonsym-f};
existing variants are shown in Figure~\ref{variant-f}\cite{a1,a2,a3,a4,a5,a6}.

\begin{figure}
\begin{center}
\psmac{8.0in}{6.5in}{commonsym.ps}
\end{center}
\caption[Common Pedigree Symbols]{\label{commonsym-f} The common pedigree symbols in most
conventions.  They are pseudo-standard because no standard exists.}
\end{figure}

\begin{figure}
\begin{center}
\psmac{6in}{3in}{variant.ps}
\end{center}
\caption[Variations on Pedigree Symbols]{\label{variant-f} A few
variations of some pedigree symbols.}
\end{figure}

Some definitions of the terms used in both Figures:
\begin{description}
\item[consanguinity] The mating of two individuals who have one or
more ancestors (with respect to the current pedigree diagram) in
common.  For example, marriages between first or second cousins are
consider consanguineous.
\item[heterozygous] Having {\em different} alleles at a given locus on the same
pair of chromosomes.  In the context of genetic counseling, this usually
means that the individual is the {\em carrier} of an autosomal recessive trait.
\item[homozygous] Having {\em identical} alleles at a given locus on the same
pair of chromosomes.  In the context of genetic counseling, this usually
means that the individual is {\em affected} by an autosomal recessive trait.
\item[proband] The individual who first brings the family to attention
for genetic evaluation and counseling; also called index case or
propositus\cite{a5}.  Note that the consultand is not necessarily the
proband; for example, the consultand can be the parent of the proband.
\item[twins]  Twins can be monozygotic (identical), or dizygotic
(non-identical).  Zygosity can also possibly be undetermined.
\end{description}

\section{General Description of the System}
{\sc GenInfer} was first written for the Symbolics Lisp
Machine in 1989\cite{t1} as a prototype program.
The Symbolics Lisp Machine, while being an excellent research and
development tool on its own, is not a practical computer to be put in a typical
genetic counselor's office.  Fortunately, {\sc GenInfer} was written in
CommonLisp, a relatively portable language.  Thus it was soon afterwards
ported to the Apple Macintosh system running Macintosh Allegro Common Lisp.  

While the program performs its calculation task satisfactorily, the
tedious user interface prevents it from becoming a real workaday tool.
To begin a session, the program will ask detailed questions about each
individual in the family.  People belonging to the earlier generations
must be entered first to establish proper lineages from them to the
later generations.  Moreover, the program does not produce any pedigree
diagram for the counselor to check on the calculations.

A better interface should take advantage of the high-resolution
graphical interface of modern personal computer by letting the counselor
draw the pedigree with a mouse on the screen, and questioning the
counselor for the required information.
At the present, a new implementation of {\sc GenInfer}, {\sc
GenInfer-II}, has been developed for the Apple Macintosh
computers\cite{peter}.  The structure of of the program is now centered
on a graphical user interface, which allow the user to design a pedigree
diagram with great flexibility.  The program is a functioning prototype
which has all the capabilities of the original {\sc GenInfer}.  It will
not automatically lay out the pedigree diagrams, however.  The counselor
will have to arrange the layout manually on the screen, using the mouse
and a tool palette to draw the diagram.

Automating the task of laying out pedigree diagrams will then be a
useful functionality to be added to {\sc Geninfer-II}.
The pedigree diagram generated should be ``prettified'' by the computer
so that an inherently complex diagram will still be relatively easy to read.
The pedigrees displayed by the program must be aesthetically pleasing.  The
aesthetic measures against which the diagrams will be judged and applied
is described in the next section.


\section{Aesthetics}
\label{aes-sec}
The great value of the pedigree diagram to the counselor is that it
provides, at the same time, detailed information about each
individual and the conceptual structure of the family as a whole.
The readability of the diagram is thus very important for the counselor
to be able to grasp the structure of the pedigree easily.  Readability
can be characterized in term of two broad categories: semantics and
aesthetics\cite{p5}.

The diagram must be drawn with the knowledge of its meaning, or
semantics.  If the common, accepted standards in using symbols and
connections are not followed, the readers of the diagram will certainly
interpret the meaning of it differently from what the drawer intends.
Thus there must be an explicit agreement on how to draw the diagram.  This
agreement can be thought of as a set of constraints within which the
drawer has to stay  when drawing, and the readers when interpreting.
In the case of pedigree diagrams, these semantic-capturing constraints
are evident when we examine the pedigree diagram:
\begin{itemize}
\item The meanings of symbols and connectives as described in Section
\ref{pedsec}.
\item The hierarchical structure of the diagram, based upon the concept
of {\em generation}.  The diagram is thus separated into layers for easy
analysis.
\item The agreement on how the connectives are drawn.  For example, the
marriage line can be straight-joined or drop-joined (see Section \ref{dropstraight}).  In this case,
there is a choice between two constraints.  Once a constraint is selected,
however, it should be applied consistently.
\end{itemize}


In contrast to semantics, aesthetics is a somewhat fuzzy concept.  Semantics
can be specified using standards, while aesthetics can only use
general guidelines.  The rules of aesthetics are not set in stone, but
rather are issues that the designer has to think about even if he
eventually decides not to follow some of them.  
Aesthetics can be thought of as a kind of heuristic
for evaluating whether the drawn diagram's readability is satisfactory.

Usually, a number of aesthetic rules must be considered.  Some of these
rules can contradict one another in some, or even all, instances.  The
designer must then take into account the relative importance of each rules
as applied to the situation and decide on the best combination.
To some degree, aesthetics is subjective.

With the subjectivity of aesthetics in mind, I will now present a few
aesthetic rules as applied to the pedigree diagram.  All the rules
should in fact be read with the suffix ``as much as possible'' appended
to them because,
as stated above, they can be contradictory and even impossible to follow.
Yet they provide a good general guideline that will result in
aesthetically pleasing diagrams.

\subsection{Generation Placement}
\label{gp-sec}
{\em People should be placed in the ``correct'' generation.}

In most cases,
this rule is not hard to follow.  It is useful to make one addition to
the guideline in laying out people:  If a person has no other direct
relative in the pedigree diagram other than his/her own spouse, then that
person is considered to belong to the generation of his/her spouse.
Figure~\ref{genplace-f} illustrates this point.

\begin{figure}
\begin{center}
\psmac{4.5in}{2.5in}{gp.ps}
\end{center}
\caption[Using Spouse's Generation]{\label{genplace-f} The male pointed to by an arrow should
belong to generation-II because he is married to a generation-II woman.}
\end{figure}	

However, if there is an inter-generational marriage, the correct
generation of the marrying couple and their children is not obvious.
The couple are placed in the generation where they should be, had
the marriage not occured; that is, the marriage should not change their
generation levels.  The children resulting from inter-generational
marriages should be placed in the generation right under that of the
younger parent so that both parents will always be in the older
generation than the children's.  See Figure~\ref{genplace2-f}.

\begin{figure}
\begin{center}
\psmac{4.5in}{3.5in}{gp2.ps}
\end{center}
\caption[Inter-generational Marriage]{\label{genplace2-f} Inter-generational marriage occurs between
the two shaded people, resulting in the blackened child.  All three of
them are assigned to the correct generations.}
\end{figure}

\subsection{Spacing}
\label{sp-sec}
{\em The diagram should be as compact as possible and still be comfortable
to read.  The spacing should also look natural.}

Laying the symbols out
on a fixed grid is thus not satisfactory because the ``natural-looking''
diagram has a variable amount of spacing between the symbols.
Examinations of a few diagrams yield the conclusion that this variable
amount of spacing is dependent upon the number of people in the
generation.  If there are many more people in generation-II than in
generation-I, the spacing between people in generation-II should be
slightly less than the spacing between people in generation-I.  See
Figure~\ref{space-f}.
Note that the space between people in generation-IV is also slightly
more than the space in generation-III because of the same reason.

\begin{figure}
\begin{center}
\psmac{6.5in}{3.5in}{space.ps}
\end{center}
\caption[Spacing Between Symbols]{\label{space-f} Generation-III is the most crowded generation.
The space between people in generation-III is thus slight smaller than
that of other generations.}
\end{figure}

\subsection{Line crossings}
{\em The numbers of connection crossings should be minimal.}

There are many reasons for connection crossings.  Some pedigree diagrams
are inherently complex such that it is not possible to avoid crossings.
For example, if there are group marriages between clans (see
Figure~\ref{clanm-f}), we cannot avoid some crossings without violating
a number of other aesthetics.
Although the
diagram is still a planar graph, to redraw it without crossings will
necessitate moving people into wrong generations---the parents of the
shaded clan must be moved to the place below their children, for example.

\begin{figure}
\begin{center}
\psmac{3.5in}{2in}{clanm.ps}
\end{center}
\caption[Clan Marriages]{\label{clanm-f} Clan marriages.  The crossing cannot be avoided.}
\end{figure}

Multiple marriages can also wreak havoc to an otherwise nicely-drawn
diagram.  While double marriage can be easily accommodated by joining
the twice-married person with each of the spouses on each side of the
symbol (see Figure~\ref{dblm-f}), there is no agreed upon way to draw
multiple marriages that are of greater degree than two.  

\begin{figure}
\begin{center}
\psmac{3.75in}{2in}{dblm.ps}
\end{center}
\caption[Double Marriage]{\label{dblm-f} How to draw a double marriage.}
\end{figure}

Some variations
in drawing triple marriages are presented in Figures~\ref{tplm1-f},
\ref{tplm2-f}, and \ref{tplm3-f}.

\begin{figure}
\begin{center}
\psmac{4in}{2in}{tplm1.ps}
\end{center}
\caption[Triple Marriage]{\label{tplm1-f} A way to draw a triple marriage.  Note that the
``spliced in'' husband belongs to the same generation as the other
husbands, but he is placed slightly below them.}
\end{figure}

\begin{figure}
\begin{center}
\psmac{4in}{2.2in}{tplm2.ps}
\end{center}
\caption[Another Triple Marriage]{\label{tplm2-f} Another way to draw a triple marriage.  The
curved line is used to jump the extra marriage line up in order to avoid crossings.}
\end{figure}

\begin{figure}
\begin{center}
\psmac{4in}{2.5in}{tplm3.ps}
\end{center}
\caption[Yet Another Triple Marriage]{\label{tplm3-f} Yet another way to draw a triple marriage.
This method only works for the drop-join marriage convention.}
\end{figure}

Some semantic-related constraints also contribute to the increased
number of crossings.  For example, in some cases, the diagram is
required to preserve the order of birth (i.e., the older child should be
placed to the left of the younger ones).  As another example, some
people prefer that the male is placed to the left of the
female in marriage.  Both constraints can severely limit the number of possible
layouts and can eliminate the layouts in which there are no crossings.

\subsection{Marriage Line}
\label{dropstraight}
{\em Use straight join to signify marriage.}

Currently, there are two different conventions with regard to how the
marrying persons are to be joined.  Both methods are illustrated in Figure~\ref{drpstt-f}.

\begin{figure}
\begin{center}
\psmac{4.5in}{2.5in}{drpstt.ps}
\end{center}
\caption[Drop Join vs. Straight Join]{\label{drpstt-f} Two marriage conventions.}
\end{figure}

The current trend, especially in the United States, is the straight join
method\cite{t2}, which is also the preferred way of leading journals in
medical genetics\cite{a6}.  The straight join method has a distinct
advantage is that it is less complicated, requiring fewer line segments.
The drop method, needing three separate lines as compared to one line of the
straight method, tends to clutter the diagram more.  

\subsection{Order of Birth}
{\em Do not preserve order of birth unless it is necessary.}

Some pedigree diagrams require that the older child is placed to the
left of the younger ones.  Most of the diagrams, fortunately, do not
have this requirement.  The order-of-birth constraint, if followed, can
greatly constrict the freedom in laying out symbols and can result in
many line crossings.

\subsection{Parents-Children Placement}
\label{embed-sec}
{\em Parents should be centered over their children.}

The reason for this rule is obvious.  A skewed pairing between children and
parents does not look pleasing.
Note that, by {\em children}, we also include the children's spouses who
do not have any parents in the pedigree diagram.  Figure~\ref{pcp-f}
illustrates this point.  We simply embed the spouse into the family as
if it is one of the siblings.  The other spouse which has a parent
does not need to be included in the centering process.

\begin{figure}
\begin{center}
\psmac{4.5in}{2.5in}{pcp.ps}
\end{center}
\caption[Centering of Parents]{\label{pcp-f} Parents are centered over their group of children
(and the children's spouses).}
\end{figure}

\subsection{Nearness}
\label{near-sec}
{\em People who should be close to one another should be placed so.}

Some of the obvious examples: twins should be placed next to each other.
To formalize this rule, the concept of {\em nearness} is developed.
Nearness score is high for people who are\footnote{the list is of
decreasing importance}:
\begin{itemize}
\item Twins.
\item Siblings.
\item Spouses.
\item closely related (a catch-all clause).
\end{itemize}

The measurement of ``closely related'' is done by counting the number of
in-between people that we must pass through as we trace the most direct
path from one person to another.  See Figure~\ref{count-f} for an example.
As there are only two possible kinds
of paths (marriage and parent-child), this measurement is not difficult
to perform.

\begin{figure}
\begin{center}
\psmac{5in}{3in}{count.ps}
\end{center}
\caption[Closely-Related Measure]{\label{count-f} {\em A} is 3 persons away from {\em B}.}
\end{figure}



\chapter{Implementation}

Because the layout program is designed to be used with {\sc GenInfer}, it must
be clearly written so that the task of coupling it to {\sc GenInfer} will not be
difficult.  Also, as furthur modifications and extensions are probably
needed in the future, the clarity of the program is essential in order
for it to be useful.

\section{Object Classes}
\label{oc-sec}
The layout program employs a significant amount of object-oriented
programming, via CLOS (Common Lisp Object System)\cite{lisp1,lisp2}, mostly for clarity
and ease of modifications.
With the objects and methods clearly defined, the code is easy to understand.
Features can be added, in most cases, by adding slots to the class
and/or defining a few more methods to handle the new functionalities.

Two classes of objects are used in the program.  The more
important one is the {\em person} class.  Currently, the {\em person}
class has the following slots:
\begin{itemize}
\item {\em name}---the person's name (a symbol).
\item {\em sex}---the person's gender (a symbol: can be {\tt male}, {\tt
female}, or {\tt unknown}.)
\item {\em father}---the person's father (a {\em person} object or nil).
\item {\em mother}---the person's mother (a {\em person} object or nil).
\item {\em children}---a list of the person's children (a list of {\em
person} objects or nil).
\item {\em spouses}---a list of the person's spouses (a list of {\em
person} objects or nil).
\end{itemize}

Additional slots such as age, disease type, genotype, phenotype,
abortion, miscarriage, stillborn, infant death, pregnant, and so
on can be included later as needed.  The {\em person} class actually has
a few more slots which are used internally for book-keeping and drawing
tasks.  These slots are:
\begin{itemize}
\item {\em level}---the person's generation number.
\item {\em pos-x}---the person's location in the x-dimension on the plot.
\item {\em pos-y}---the person's location in the y-dimension on the plot.
\item {\em seen?}---a boolean marker used in measuring
``closely-relatedness'' (see Section \ref{near-sec}).
\end{itemize}

Another class of object used in the program is the {\em marriage} class.
The {\em marriage} class contains the following slots:
\begin{itemize}
\item {\em groom}---the male member of the marriage (a {\em person} object or nil).
\item {\em bride}---the female member of the marriage (a {\em person} object or nil).
\item {\em clist}---the list of children resulting from this marriage
(a list of {\em person} objects or nil).
\end{itemize}
The {\em marriage} class contains {\em all} the information we need
about how people related to one another in the pedigree.  It can
accommodate the case of a single
parent (i.e., the other parent is not defined in the pedigree) by
setting one of the groom/bride slots to nil as appropriate.  Multiple
marriages are handled gracefully likewise, because different
marriages will create different pairs of bride and groom and thus we
will not get confused by a groom whose name appears in five different
{\em marriage} objects.  A so-far childless marriage can also be noted
by setting the {\em clist} slot to nil.  Clearly, the {\em marriage}
object is all that we need to keep track of relations between people.

\section{Interface to {\sc GenInfer}}
\label{interface-sec}
All that is necessary to set up a pedigree is to define all {\em person}
and {\em marriage} objects.  The parent-child relation (i.e., the
{\em father}, {\em mother}, and {\em children} slots) do not need to be
specified as the program can figure it out from the {\em marriage}
objects.  The marriage-relation ({\em spouses} slot) is also explicitly
specified by the {\em marriage} objects already and therefore is not needed.

There are three possible ways to define the {\em person} and {\em
marriage} objects.  The most straightforward method is to define them
directly in Lisp:
\begin{program}
(setf dad (make-instance 'person :name 'dad :sex 'male))
(setf mom (make-instance 'person :name 'mom :sex 'female))
(setf bro (make-instance 'person :name 'bro :sex 'male))
(setf sis (make-instance 'person :name 'sis :sex 'female))
(setf m (make-instance 'marriage
                       :groom dad
                       :bride mom
                       :clist (list bro sis)))
\end{program}
This method, while perfectly useful for testing the layout
algorithm, is not acceptable to be used by the counselor.
With a few short procedures acting as a pure verbal front-end simply to
eliminate the repetitive typing, however, the
interface is up to the level of the original {\sc GenInfer}, with less tedium.

With the minimal requirement that the user specify {\em person} and {\em
marriage} objects (see Section \ref{oc-sec}), the program can also
readily read in a text file of the format:
\begin{program}
dad   male
mom   female
bro   male
sis   female
+++
;;; the +++ is placed between person and marriage definitions
dad   mom   bro   sis
;;; the marriage format is: groom  bride  child1 child2 ...
\end{program}
Similar to the querying interface, a few short routines are sufficient
to convert between this file format and the underlying object definitions.

To be really useful, however, the program should be coupled to an
interactive pedigree drawing tool.  The interface will then allow the
counselor to draw the pedigree on the fly as the family history of the
consultand is being collected.  The interactive pedigree tool has been
written before\cite{peter}.  The tool, as it currently exists, does not perform
any automatic layout and thus is suitable to be coupled with the layout
program.

\section{How It Works}
The layout program subdivides the task into five phases: prior processing,
which performs bookkeeping chores necessary before any real work can be
done; generation assignment, in which the people are assigned their
generation levels; laying out the most populated generation, which lay
out the crucial generation; laying out other generations; and drawing
the pedigree on the screen.  The rest of this chapter will describe each
phase in details.

\subsection{Prior Processing}
The program first needs to set up the slots of {\em person} objects to
correctly reflect the relationships between people within the pedigree.
The {\em father}, {\em mother}, {\em children}, and {\em spouses} slots
are cleared.
Note that two global variables are used to keep track of the {\em
person} and {\em marriage} objects: *all-p* and *all-m*.  Each one is a
list that contain all the objects: {\em person} in *all-p*, and {\em
marriage} in *all-m*. 


The {\em children} slots are filled first by looking at the
{\em marriage} objects, finding any marriage that results in children:
\begin{program}
(defun set-children ()
  (dolist (m *all-m*)
    (if (groom m)                       ; must check for existence
      (setf (children (groom m))        ; because it may be nil.
            (append (children (groom m))
                    (clist m))))
    (if (bride m)                       ; similarly, we need to
      (setf (children (bride m))        ; check the bride, too.
            (append (children (bride m))
                    (clist m))))))
\end{program}

The {\em mother} and {\em father} slots are then easily filled because
all the parent-child information needed is already put in the {\em
children} slots:
\begin{program}
(defun set-parents ()
  ;; look at each person's children
  ;; and set the children's parent slot accordingly
  (dolist (p *all-p*)
    (cond ((eq (sex p) 'female)
           (dolist (c (children p))
             (setf (mother c) p)))
          (t	  
           (dolist (c (children p))
             (setf (father c) p))))))
\end{program}

The {\em spouses} slots are filled last by setting it according to the
information stored in the {\em marriage} objects.
\begin{program}
(defun set-spouses ()
  (dolist (m *all-m*)
    (when (and (groom m) (bride m))     ; when there is a marriage
      (setf (spouses (groom m))         ; set spouses respective slots
            (append (spouses (groom m)) (list (bride m))))
      (setf (spouses (bride m))
            (append (spouses (bride m)) (list (groom m)))))))
\end{program}

\subsection{Generation Assignment}
\label{genass-sec}
To assign people to generations, we first clear the {\em level} slot of
each person, which contain the generation level value, to 0.  
The assignment algorithm makes use of a hash table, *gentab*.  People
are hashed into the table with their generation levels as keys.  The
*gentab* will also be useful later on.
Two abstractions, {\tt get-genlist} and {\tt set-genlist} are used in
reading from and writing to the hash table, respectively.

First, we tentatively assign people who do not have any parents within
the pedigree to generation $0^{th}$.  The key value of 0 will now
fetch the list of these people.
\begin{program}
(defun assign-level ()
  (let ((remain nil)) ; keep track of people unassigned
    ;;; First, we put all the "orphan" nodes at generation 0th
    (dolist (p *all-p*)
      (cond ((and (null (father p))
                  (null (mother p)))
             (setf (level p) 0)
             (set-genlist 0 (append (list p) (get-genlist 0))))
            (t
             (push p remain))))
\end{program}
Then, we go through the $0^{th}$ generation and put all their children
to the $1^{st}$ generation.  We then do this for the $1^{st}$
generation to get the $2^{nd}$ generation, and so on, until we have
assigned generation levels to all people.
\begin{program}
;;; When REMAIN is nil, we have seen all nodes.
;;; we also have to check that the last generation assigned 
;;; are all leaves.
(setf *lastgen*
      (do ((gen 1 (+ gen 1)))
           ()
          (dolist (p (get-genlist (- gen 1)))
            (dolist (c (children p))
              (setf remain (remove c remain))
              (setf (level c) gen)
              (set-genlist gen
                           (append (list c) (get-genlist gen))))))
          ;; exit the do loop when we have seen all
          (if (and (null remain) (all-leaf? gen))
            (return gen)))
\end{program}
After this initial assignment, there may be some duplicates in the
generation table from two possible causes.  Each generation may contain
the same person twice because that person's mother and father are both
in the previous generation.  In this case, we simply have to go through
each entry in the hash table and remove any duplicates.  Another
cause for duplicates is due to the person's father and mother being
assigned to different generation.  The person is then assigned to two
entries in the hash table.  According to the generation placement
aesthetics (see Section \ref{gp-sec}), we should put the person lower
than both parents.  Thus the earlier generation duplicates are the ones
that we remove.
\begin{program}
;;; delete duplicated persons inside each level
(dotimes (gen (1+ *lastgen*))       
  (set-genlist gen (remove-duplicates (get-genlist gen))))
;;; Inter-level duplicates
;;; We remove the higher generation duplicates.
(loop for gen from *lastgen* downto 0
      do (dolist (p (get-genlist gen))
           (loop for lower-g from (- gen 1) downto 0
                 do (set-genlist lower-g
                                 (remove p 
                                        (get-genlist lower-g))))))

\end{program}

Each person should be placed in the same generation as his/her spouses,
if possible.  So we compare each person's generation to his/her spouses'
generation.  If they are inconsistent, shift the person who belong to an
earlier generation down to the appropriate level.
We also need to propagate this generation change to that person's
children and parents, and update them as well.
\begin{program}
(dolist (m *all-m*)
  (if (and (bride m) (groom m))
    (cond ((< (level (bride m)) (level (groom m)))
           (correct (bride m) (level (groom m))))
          ((> (level (bride m)) (level (groom m)))
           (correct (groom m) (level (bride m)))))))
\end{program}

When the generation assignment procedure is done, the hash table
*gentab* will contain all the people in the pedigree, with the key to
the hash table mapping the generation number to the list of people in
that generation.

\subsection{Laying out the Most Populated Generation}
\label{poplay-sec}
Because the most populated generation is the crucial generation that
determines how the whole pedigree is going to be laid out due to the
spacing aesthetics (see Section \ref{sp-sec}), this generation will be
the first to be laid out.

To find the most populated generation:
\begin{program}
(defun most-pop ()
  ; return the most populated generation
  (let ((pop 0) (max -1))
    (dotimes (i (1+ *lastgen*))
      (when (> (length (get-genlist i)) max)
        (setf max (length (get-genlist i)))
        (setf pop i)))
    pop))
\end{program}

The layout algorithm makes use of another hash table, *poptab*, which
will contain groups of people.  People are grouped according to their
{\em nearness} (see Section \ref{near-sec}).  Generally, people in the
same group are siblings, but there can also be embedded spouses (see
Section \ref{embed-sec}).

First, we tentatively group people according to their parents.  So we
use a cons of {\em father} and {\em mother} as the key.
\begin{program}
(defun group-pop ()
  (setf *poptab* (make-hash-table :test \#'equal))
  (setf *popkeys* nil)
  (let ((plist (get-genlist (most-pop))))
    (dolist (p plist)
      (let ((k (cons (mother p) (father p))))
        (setf (gethash k *poptab*)
            (append (list p)
                    (gethash k *poptab*)))
      (pushnew k *popkeys* :test \#'equal)))))
\end{program}
The variable *popkeys* is used to keep the list of all the keys used in
the *poptab* hash table.


To embed spouses, we merge spouses into the biggest group. Then, we
merge any leftover spouses into the other groups.  To find the biggest
group, we use:
\begin{program}
(defun bgg-key ()
 ;return the key to *pop-tab* for the largest group
  (let ((key nil) (max 0))
    (dolist (k *popkeys*)
      (when (and (> (length (gethash k *poptab*)) max)
                 (not (equal k (cons nil nil))))
        (setf key k)
        (setf max (length (gethash k *poptab*)))))
    key))
\end{program}
The reason we filter out the group with the key of {\tt (cons nil nil)}
is that this group consist of orphans (people with no parents in the
pedigree).  They are not closely related to each other but are lumped
together only because of them being orphans.
Thus we don't want them to be the core group, no matter how
numerous they are.

Merging into the biggest group is done by looking for spouses of each
person in the biggest group that also belong to this generation.  The
spouses are then removed from their group and placed into the biggest
group, wedged next to the person he/she marries.
\begin{program}
(defun merge-pop ()
 (let ((bg (gethash (bgg-key) *poptab*)))
    (dolist (p bg)
      (when (spouses p)
       (dolist (s (spouses p))
         (dolist (k *popkeys*)
           (when (member s (gethash k *poptab*))
            (setf (gethash k *poptab*)
               (remove s (gethash k *poptab*)))
            (setf (gethash (bgg-key) *poptab*)
               (insert-after s
                   (position p (gethash (bgg-key) *poptab*))
                   (gethash (bgg-key) *poptab*)))
              ))))))
\end{program}
The procedure {\tt insert-after} is defined as:
\begin{program}
(defun insert-after (thing place list)
  ;;; return the list with THING inserted after PLACE position
  (append (subseq list 0 place)
          (list thing)
          (subseq list place)))
\end{program}

Merging spouses into the other groups is done similarly.  We hide the
biggest group (so that the people in it are not moved out) by simply
removing the biggest group's key from the key list.
\begin{program}
  (let ((keys (remove (bgg-key) *popkeys* :test \#'equal)))
    (dolist (k keys)
      (dolist (p (gethash k *poptab*))
        (when (spouses p)
          (dolist (s (spouses p))
            (dolist (other-k (remove k keys :test \#'equal))
              (when (member s (gethash other-k *poptab*))
                (setf (gethash other-k *poptab*)   
                      (remove s (gethash other-k *poptab*)))
                (setf (gethash k *poptab*)
                      (insert-after s
                        (position p (gethash k *poptab*))
                        (gethash k *poptab*)))
                ))))))))
\end{program}
We do not need to worry about a spouse being pulled back and forth
indefinitely because, once it is moved, it will be hidden and thus
immune from being pulled out again.  Hiding is done by removing the key
to its new group from the key list.

A function is also defined to help with the closely-related measure of
the {\em nearness} aesthetics (see Section \ref{near-sec}).
{\tt Hop} takes as arguments two {\em person} objects and return the
closely-related measure between the two persons.
\begin{program}
(defun hop (source destination)
  (clear-marker)
  (mark source)
  (if (eq source destination)
    0
    (hop-helper (expand source 0) destination)))
\end{program}
The {\tt clear-marker} procedure performs the bookkeeping task of
clearing the {\em seen?} slot of each person.  The search performed is a
BFS and the {\tt expand} procedure sets up the queue of persons to be
searched.  It takes as input the current person being examined, and
his/her distance from the source, and return a list of the person's
mother, father, spouses, and childrenl, with each of these direct
relatives cons'ed with their distances from the source.
\begin{program}
(defun expand (source distance)
  ; Expand the source and return the list of
  ;( (mother.d+1) (father.d+1) (spouse1.d+1)
  ;  (spouse2.d+1) ... (child1.d+1) (child2.d+1) ...)
  ; The relatives who don't exist in the pedigree will
  ;   not be included in the list.
  (let ((d (1+ distance))
        (m (mother source))
        (f (father source))
        (c (children source))
        (s (spouses source)))
    (remove (cons nil d)
            (append (list (cons m d) (cons f d))
                    ; spouses \& children are spliced out
                    (mapcar \#'(lambda (p) (cons p d)) c)
                    (mapcar \#'(lambda (p) (cons p d)) s))
            :test \#'equal)))
\end{program}
The procedure that does the real work of measurement is {\tt
hop-helper}, which is a bread-first search.
\begin{program}
(defun hop-helper (searchlist destination)
  ;; do a BFS
  (let ((newlist nil))
    (dolist (chunk searchlist)
      (if (eq (car chunk) destination)
        (return-from hop-helper (cdr chunk))))
    (dolist (chunk searchlist)
      (unless (seen? (car chunk))
        (mapcar \#'(lambda (i) (pushnew i newlist :test \#'equal))
                (expand (car chunk) (cdr chunk)))))
    (hop-helper newlist destination)))
\end{program}

Finally, we actually lay out the most populated generation by assigning
numerical coordinates to the people.  We can assign the number directly
because, if later on we ran out of place to draw, the position assigning
procedure will simply call a ``trap'' procedure which shift all people's
position in the right direction to regain enough drawing space.  People
grouped together will be placed a little closer than people belonging to
different groups.

\subsection{Laying Out Other Generations}
After laying out the most populated generation, we lay out the other
generations, using the most populated generation as the reference point.
First, we lay out the earlier generation, starting from the one closest
to the most populated one, going from the bottom up.  Then we lay out
the later generation, also starting from the one closest to the most
populated one, going from the top down.
\begin{program}
(defun layout-rest ()
  (loop for g from (1- (most-pop)) downto 0
        do (lay-up g (* (- (most-pop) g) 75)))
  (loop for g from (1+ (most-pop)) to *lastgen*
        do (lay-down g (* (- g (most-pop)) 75))))
\end{program}
The {\tt loop} primitive can deal with the case of {\tt most-pop}
returning 0 (the most populated generation being the topmost one), and
will not erroneously get into an infinite loop.  The variable *lastgen*
keeps track of the maximum generation value used in the pedigree (see
Section \ref{genass-sec}).

Both {\tt lay-up} and {\tt lay-down} also makes use of a hash table,
*temptab*, which performs similar task to that of the *poptab* hash
table.  The {\tt lay-temp} function is used to set up this hash table by
grouping and merging people like {\tt group-pop} and {\tt merge-pop}
(see Section \ref{poplay-sec}).
\begin{program}
(defun lay-temp (people)
  ;; reset the table first of all
  (setf *temptab* nil)
  (setf *tempkeys* nil)
  (group-temp people)
  (merge-temp))

(defun group-temp (people)
  (setf *temptab* (make-hash-table :test \#'equal))
  (setf *tempkeys* nil)
  (dolist (p people)
    (let ((k (cons (mother p) (father p))))
      (setf (gethash k *temptab*)
          (append (list p)
                  (gethash k *temptab*)))
      (pushnew k *tempkeys* :test \#'equal))))

(defun merge-temp ()
 (let ((bg (gethash (tbgg-key) *temptab*)))
    (dolist (p bg)
      (when (spouses p)
       (dolist (s (spouses p))
         (dolist (k *tempkeys*)
           (when (member s (gethash k *temptab*))
            (setf (gethash k *temptab*)
                  (remove s (gethash k *temptab*)))
            (setf (gethash (tbgg-key) *temptab*)
                  (insert-after s
                     (position p (gethash (tbgg-key) *temptab*))
                     (gethash (tbgg-key) *temptab*)))
              ))))))
 (let ((keys (remove (tbgg-key) *tempkeys* :test \#'equal)))
    (dolist (k keys)
      (dolist (p (gethash k *temptab*))
        (when (spouses p)
         (dolist (s (spouses p))
           (dolist (other-k (remove k keys :test \#'equal))
             (when (member s (gethash other-k *temptab*))
               (setf (gethash other-k *temptab*)   
                     (remove s (gethash other-k *temptab*)))
               (setf (gethash k *temptab*)
                     (insert-after s
                        (position p (gethash k *temptab*))
                        (gethash k *temptab*)))
                ))))))))

(defun tbgg-key ()
  (let ((key nil) (max 0))
    (dolist (k *tempkeys*)
      (when (and (> (length (gethash k *temptab*)) max)
                 (not (equal k (cons nil nil))))
        (setf key k)
        (setf max (length (gethash k *temptab*)))))
    key))

\end{program}


To lay up, first we set up the *temptab* by calling {\tt lay-temp} on
the people belonging to this generation.  Then we set the {\em x-pos}
slot of each person to nil, which marks it as being unassigned.  We then
find out whether they have any children in the generation just below
them.  If so, center these parents over their children.  If the parent
is a lone parent (i.e., the other parent is not in the pedigree), we
simply assign the average of the x-coordinates of the children.  If both
parents are present, we put both of them slightly off the average, one
on each side.  After these parents are assigned, the only people left
are those with no children in the generation below; they usually are sterile
siblings of these parents.  The ``fertile'' person will get his/her
x-coordinate basing upon the x-coordinate of the closest relative in
this generation who has an x-coordinate assigned.
\begin{program}
(defun lay-up (generation y)
  (let ((people (get-genlist generation)))
    (dolist (p people)
      (setf (y-pos p) y)
      (setf (x-pos p) nil))  ; clear them all
    (lay-temp people)
    (dolist (k *tempkeys*)
      (let ((group (gethash k *temptab*)))
        (dolist (p group)
          (when (null (pos-x p))
            (if (has-children-in? p (1+ generation))
              (if (find (spouse p) people)
                (progn
                  (setf (x-pos p)
                        (- (middle (children p)) 50))
                  (setf (x-pos (spouse p))
                        (+ (middle (children p)) 50)))
                (progn
                  (setf (x-pos p) (middle (children p)))))
              )))
        ;; sterile people look for closest relative
        (dolist (p group)
          (if (null (pos-x p))
            (assign-from-closest-one (position p group)
                                     group)))))))
\end{program}

The procedure {\tt has-children-in?} simply check whether a given person
has any child in a specified generation:
\begin{program}
(defun has-children-in? (person child-gen)
  (let ((people (get-genlist child-gen)))
    (dolist (c (children person))
      (if (find c people)
        (return-from has-children-in? t)))
    nil))
\end{program}

The procedure {\tt middle} takes a list of people and return their
average x-coordinate.
\begin{program}
(defun middle (people)
  (let ((x 0))
    (dolist (p people)
      (setf x (+ x (pos-x p))))
    (/ x (length people))))
\end{program}

The procedure {\tt assign-from-closest-one} takes a group of people and
the position of the unassigned person.  It then assigns an x-coordinate
to the unassigned person by looking for the closest person to the
unassigned person who has his/her x-coordinate assigned.  If the closest
person is to the left of the unassigned person, then we assign a
position slightly to the right of the found x-coordinate to the
unassigned person, and conversely.
\begin{program}
(defun assign-from-closest-one (here people)
  (let ((c (find-closest here people)))
    (if (< c here)
      (setf (x-pos (nth here people))
            (+ (x-pos (nth c people)) 50))
      (setf (x-pos (nth here people))
            (- (x-pos (nth c people)) 50)))))
\end{program}

The procedure {\tt find-closest} returns the position of the closest
person having the x-coordinate assigned.  It compares the closest person
to the left to the closest person to the right, and return the position
that is closer.  Note that sometimes a search in one direction will
return nil, meaning that there is no one in that direction of the
unassigned person who has his/her x-coordinate assigned.
\begin{program}
(defun find-closest (here people)
  (let ((left (closest-left here people))
        (right (closest-right here people)))
    (cond ((null left)
           right
          ((null right)
           left
          ((> (- here left) (- right here))
           right)
          (t
           left))))
\end{program}

The procedures {\tt closest-left} and {\tt closest-right} returns the
closest position to the left and right, respectively.  If no one in that
direction has his/her x-coordinate assigned, the procedures will return
nil, which will be caught by {\tt find-closest} (see above).
\begin{program}
(defun closest-left (start people)
  (loop for place from start downto 0
        do (if (pos-x (nth place people))
             (return-from closest-left place)))
  nil)
(defun closest-right (start people)
  (loop for place from start to (1- (length people))
        do (if (pos-x (nth place people))
             (return-from closest-right place)))
  nil)
\end{program}


To lay down, first we also set up the *temptab* by calling {\tt
lay-temp} on  the people belonging to this generation.  Then we set the
{\em x-pos} slot of each person to nil, which marks it as being
unassigned.
We then find out whether they have any parents in the generation just above
them.  If so, spread these children under the parents.  If the parent
is a lone parent (i.e., the other parent is not in the pedigree), we
simply spread the children under him/her.  If both
parents are present, we spread the children under the average of the
parents' x-coordinates.
After these children are assigned, the only people left
are those with no parents in the generation above; they usually are 
embedded spouses of these children.  These people will get their
x-coordinates basing upon the x-coordinate of the closest relative in
this generation who has an x-coordinate assigned.
\begin{program}
(defun lay-down (generation y)
  (let ((people (get-genlist generation)))
    (dolist (p people)
      (setf (y-pos p) y)
      (setf (x-pos p) nil))             ; clear them all
    (lay-temp people)
    (dolist (k *tempkeys*)
      (let* ((group (gethash k *temptab*))
             (mom (group-mother group))
             (dad (group-father group)))
        (cond ((null mom)
               (spread group (x-pos dad)))
              ((null dad)
               (spread group (x-pos mom)))
              (t
               (spread group (/ (+ (x-pos mom)
	                           (x-pos dad)) 2))))))
    (dolist (p group)
      (if (null (pos-x p))
        (assign-from-closest-one (position p group)
                                 group)))))
\end{program}

The ``real'' father of the group is the father that most people in the
group share.  Similar case applies to the mother.
\begin{program}
(defun group-father (group)
  (let* ((dad nil)
         (current-count 0)
         (fatherlist (mapcar \#'father group))
         (fatherset (remove-duplicates fatherlist)))
    (dolist (f fatherset)
      (when (> (count f fatherlist) current-count)
        (setf dad f)
        (setf current-count (count f fatherlist))))
    dad))               

(defun group-mother (group)
  (let* ((mom nil)
         (current-count 0)
         (motherlist (mapcar \#'mother group))
         (motherset (remove-duplicates motherlist)))
    (dolist (m motherset)
      (when (> (count m motherlist) current-count)
        (setf mom m)
        (setf current-count (count m motherlist))))
    mom))
\end{program}

Spreading out the children under an x-coordinate is done by the {\tt
spread} procedure.
\begin{program}
(defun spread (people x)
  (let ((n (length people)))
    (loop for pos from (* -1 (/ (- n 1) 2)) to (/ (- n 1) 2)
          for place from 0 to (- n 1)
          do (setf (pos-x (nth place people))
                   (+ x (* 50 pos))))))
\end{program}

\subsection{Drawing}

When we get to this point, each person in the pedigree will have his/her
coordinates set.
Each person is then drawn by calling a {\tt draw} method on each person.
The {\tt draw} method, in skeletal form is presented:
\begin{program}
(defmethod draw ((p person) (v view))
  (let ((x (pos-x p))
        (y (pos-y p)))
    (cond ((eq (sex p) 'unknown)
           (move-to v x (- y 10))
           (line v 10 10) (line v -10 10)
           (line v -10 -10) (line v 10 -10))
          ((eq (sex p) 'male)
           (frame-rect v (- x 10) (- y 10)
                         (+ x 10) (+ y 10)))
          ((eq (sex p) 'female)
           (frame-oval v (- x 10) (- y 10)
                         (+ x 10) (+ y 10))))))
\end{program}

Extending this skeletal form to account for all the symbols and
variations is easy.  The method itself can be modified, or a few {\tt
:before} and {\tt :after} methods can be added, for example, to make the
program display the person's name next to the symbol.  An {\tt :after}
method to display the person's name and add the crossed-out symbol to
signify a deceased person is shown:
\begin{program}
(defmethod draw :after ((p person) (v view))
  (let ((x (pos-x p))
        (y (pos-y p)))
    (when (and (dead? p) (not (aborted? p)))
      (move-to v (+ x 15) (- y 15))
      (line v -30 +30))
    (when (name p)
      (move-to v (+ x 10) (- y 10))
      (format v (string (name p))))))
\end{program}

The marriage lines are easily drawn by looking at the {\em marriage}
objects and join all the brides and grooms, using the {\tt marry} method.
\begin{program}
(defmethod marry ((m person) (f person) (v view))
  (if (eq (sex m) (sex f))
    (error "~s and ~s are of the same sex." 
           (name m) (name f)))
  (if (or (eq (sex m) 'unknown) (eq (sex f) 'unknown))
    (error "One of the partner is of unknown sex."))
  (if (eq (sex m) 'female)
    (marry f m v))
  (let ((mx (pos-x m)) (my (pos-y m))
        (fx (pos-x f)) (fy (pos-y f)))
    (when (< mx fx)
      (move-to v (+ mx 10) my)
      (line-to v (- fx 10) fy))
    (when (< fx mx)
      (move-to v (+ fx 10) fy)
      (line-to v (- mx 10) my))))
\end{program}
Consanguinity is drawn in almost the same way, except that we use a
double line.

By looking at the {\em marriage} objects again,
we grow a short vertical line extending up from each children, and a
horizontal line is drawn, for each marriage, to join these small vertical
lines if there is more than one child.  A vertical line is then drawn
from the average x-coordinates of the bride and groom down to this
horizontal line.  The diagram is done.

\chapter{Results}
\section{Evaluation}
\subsection{Strong Points}
The best part of the program is its clarity and flexibility.  The code
is clear enough to be read at a single sitting.  The use of objects  and
the separation of different functionalities make it easy to modify and
interface the code.

There is no inherent limit on the program's capacity.
The hash tables used can automatically grow as they are overfilled by a
large pedigree.
Actually, the program currently can handle 50 people/pedigree,
which is quite a large number.  Very few pedigrees, if any at all, will
need larger hash tables than the current ones.  The drawing trap
procedure, mentioned in Section \ref{poplay-sec}, will also correctly
adjust the drawing area if the pedigree is so large or unbalanced that
the diagram spills over the current display area.

Because of the numerous heuristics used, the program gains in speed with
just a
little lost in the quality of the diagram.  In fact, only an exhaustive
generate and test approach (see Section \ref{impmod-sec}) can adequately
handle the pedigrees that cause troubles with our program.

\subsection{Weak Points}
The program is not yet coupled to {\sc GenInfer} and the interactive pedigree
drawing tool.  The full testing of the system is thus not possible until
all three modules are put together.

The layout algorithm, due to its consideration for speed, uses heuristic
in some places.  These heuristics occasionally fail, resulting in
a number of less-than-optimal diagrams.  To be fair, however, the
pedigrees that create this problem are almost always inherently complex
and the optimal diagrams are not intuitively obvious even to a human drawer.

\section{Possible Future Modifications}
\subsection{Functional Extensions}
The most needed extension to the program is interfacing it to {\sc GenInfer}.
The program's transparency and flexibility should make that task easy,
however.  A few front-end routines are needed to process the user input
into a pedigree (see Section \ref{interface-sec}).  They are not written
because, as of now, I do not have a clear idea of how {\sc GenInfer} is going
to be used by the counselor.  Once the requirements for the workaday
{\sc GenInfer} are specified, however, the routines should be easy to write.

The more interesting extension is interfacing the program to the interactive
pedigree drawing tool.  As with the interface to {\sc GenInfer},
the interfacing routines are not written out because the working
requirements of how the program is going to be used are yet to be
specified.

One usual, but possible extension, which may or may not be useful, is that of a
circular diagram.  Figure~\ref{cd-f} shows an example of such a diagram.
This diagram is a compact way to present a very large pedigree.
A number of aesthetics will have to be revised to accommodate this new
style, however.

\begin{figure}
\begin{center}
\psmac{10in}{6.5in}{cd.ps}
\end{center}
\caption[Circular Diagram]{\label{cd-f} Circular Pedigree Diagram\cite{a4}.}
\end{figure}

\subsection{Implementation Modifications}
\label{impmod-sec}
The current method of layout relies heavily on the most populated
generation as a heuristic on where to place people.  This heuristic
works well almost all of the time because the most populated level is
almost always the one that is the most complex (containing large numbers
of connections).  The heuristic can sometimes fail, however.

If we want to generate the ``best'' diagram possible, it might be better
if, instead of using the nearness measurement (see Section \ref{near-sec})
to guess the best layout, we generate all possible layouts from the
starting set of people in the most populated generation by looking at
all possible (and not obviously stupid) permutations of them.  The
layouts are then compared using the rules of aesthetics as specified in
Section \ref{aes-sec}.  The most aesthetically pleasing diagram is then
chosen to be displayed.

There is a slight problem with this approach, however.  The pedigrees
that cause the nearness heuristic to fail tend to contain a large number
of people and connections.  In this case, the time taken to generate and
test so many possible permutation on the most populated level will be
intolerably long.  This approach is thus not suitable for interactive
layout updating and display.  It can be quite useful, however, if we
want a pretty display after we have completed drawing the whole pedigree.

We can also apply graph algorithms, especially planarization algorithms,
to the layout problem.  By separating the diagram into planar subgraphs,
the crossings problem should be minimized.  But there is a difficult
problems in applying planarization to pedigree diagrams.
Although pedigree diagrams are special cases of graphs, some aesthetic
considerations are more important than edge crossings.  For example, the
rule requiring higher position of a parent with regard to its children
is quite inflexible; the pedigree diagram might otherwise be very
difficult to read.  We can, of course, adapt the algorithm to
accommodate these higher rules but it is not clear how the
algorithm should be modified.
Moreover, a planarization algorithm can be very time-consuming.
We may conceivably take advantage of the new development of a near-optimum
parallel planarization algorithm which runs in O(1) time\cite{planar}.
But the approach requires parallel computations to provide a decent
simulacrum of a big neural network array, making the approach
impractical because of {\sc GenInfer}'s personal computer hardware base.
Adapting this new parallel algorithm to the constraints of pedigree
diagrams may also be harder than adapting the normal, sequential
planarization algorithms; it is not clear how we can adjust the numerous
coefficients in the planarizing neural network in order to stay within the
constraints.

One promising implementation modification is in the implementation of the
{\em nearness} aesthetics (see Section \ref{near-sec}).  Currently, the
nearness score is actually an estimate rather than an exact numerical
score.  To fully apply the nearness aesthetics, we must calculate the
nearness values between each pair of persons, for all persons in the
pedigree.  We can then apply an assignment algorithm, probably a
variation of linear programming, to find the optimal layout.  The
problem, again, is speed.  This approach appears to take shorter time
than the generate and test approach mentioned above, however, especially
if the linear programming part is optimized enough for speed.

\section{Summary}
In this thesis I have discussed the issues in the layout of pedigree
diagrams.  The concept of aesthetics is created and categorized in
details.  A program to perform automatic layout of pedigree diagrams is
implemented according to the aesthetics rules specified.
The program is able to deal with non-trivial complications and generate
aesthetically pleasing diagrams. The program is flexible and can be
quickly modified to accommodate its user's idiosyncratic choices of
symbols, layout styles, and interface requirements.

\begin{thebibliography}{99}
\bibitem{a6}
Instructions for contributors.
\newblock {\em American Journal of Medical Genetics}, 1988.

\bibitem{p6}
Carlo Batini, Enrico Nardelli, and Roberto Tamassia.
\newblock A layout algorithm for data flow diagrams.
\newblock {\em IEEE Transactions on Software Engineering}, SE-12(4), April
  1986.

\bibitem{a5}
Ruth~Y. Berini and Eva Kahn, editors.
\newblock {\em Clinical Genetics Handbook}.
\newblock Medical Economics Books, Oradell, NJ, 1987.

\bibitem{a1}
C.~O. Carter.
\newblock {\em Human Heredity}.
\newblock Penguin Books, Middlesex, England, 1962.

\bibitem{t1}
Nomi Harris.
\newblock Probabilistic reasoning in the domain of genetic counseling.
\newblock Technical Report TR 460, Massachusetts Institute of Technology,
  Laboratory for Computer Science, October 1989.

\bibitem{p7}
F. Hoffmann and K. Kriegel
\newblock Embedding Rectilinear Graphs in Linear Time.
\newblock {\em Information Processing Letters}, vol. 29, 1988.

\bibitem{lisp2}
Sonya~E. Keene
\newblock {\em Object-Oriented Programming in Common Lisp: A
Programmer's Guide to CLOS.}
\newblock Addison-Wesley Publishing Company, Massachusetts, USA, 1989.

\bibitem{t2}
Paul~M. Mamelka, Bennett Dyke, and Jean~W. MacCluer.
\newblock Pedigree/draw for the apple macintosh.
\newblock Technical Report TR 1, Southwest Foundation for Biomedical Research,
  Population Genetics Laboratory, 1990.

\bibitem{a3}
Victor~A. McKusick.
\newblock {\em Human Genetics}.
\newblock Prentice-Hall Inc., Englewood Cliffs, NJ, second edition, 1969.

\bibitem{p4}
Edward~M. Reingold and John~S. Tilford.
\newblock Tidier drawing of trees.
\newblock {\em IEEE Transactions on Software Engineering}, SE-7(2), March 1981.

\bibitem{a2}
J.~A.~Fraser Roberts and Marcus~E. Pembrey.
\newblock {\em An Introduction to Medical Genetics}.
\newblock Oxford University Press, Oxford, England, eighth edition, 1985.

\bibitem{round}
A.~P.~Round.
\newblock A Novel Pedigree Plotting Algorithm.
\newblock {\em Genetic Analysis Workshop 7, 1990.}

\bibitem{p8}
Lawrence~A. Rowe, Michael Davis, Eli Messinger, Carl Meyer, Charles Spirakis, and Allen Tuan.
\newblock A Browser for Directed Graphs.
\newblock {\em Software---Practice and Experience}, 17(1), January 1987.

\bibitem{lisp1}
Guy~L. Steele Jr.
\newblock {\em Common Lisp: The Language.}
\newblock Digital Press, Massachusetts, USA, second edition, 1990.

\bibitem{p2}
Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda.
\newblock Methods for visual understanding of hierarchical system structures.
\newblock {\em IEEE Transactions on Systems, Man, and Cybernetics}, SMC-11(2),
  February 1981.

\bibitem{peter}
Peter Szolovits.
\newblock {\em Application for NIH Grant: A Clinical Geneticist's Workstation.}
\newblock MIT Laboratory for Computer Science, 1990.

\bibitem{planar}
Yoshiyasu Takefuji and Kuo-Chun Lee.
\newblock A Near-Optimum Parallel Planarization Algorithm.
\newblock {\em Science}, volume 245, September 1989.

\bibitem{p5}
Roberto Tamassia.
\newblock New Layout Techniques for Entity-Relationship Diagrams.
\newblock {\em Proceedings of the $4^{th}$ International Conference on
  Entity-Relationship Approach, 1985.}

\bibitem{p1}
Roberto Tamassia, Giuseppe di~Battista, and Carlo Batini.
\newblock Automatic graph drawing and readability of diagrams.
\newblock {\em IEEE Transactions on Systems, Man, and Cybernetics}, 18(1),
  January/February 1988.

\bibitem{alun}
Thomas Alun.
\newblock Drawing Pedigrees.
\newblock {\em IMA Journal of Mathematics Applied in Medicine \& Biology}, 5, 1988.

\bibitem{a4}
F.~Vogel and A.~G. Motulsky.
\newblock {\em Human Genetics: Problems and Approaches}.
\newblock Springer-Verlag, Berlin, Germany, second edition, 1986.

\bibitem{p3}
Charles Wetherell and Alfred Shannon.
\newblock Tidy drawing of trees.
\newblock {\em IEEE Transactions on Software Engineering}, SE-5(5), September
  1979.

\end{thebibliography}
\end{document}

