Logo Search packages:      
Sourcecode: fastlink version File versions  Download package

loopbrk.c

#include "unknown.h"

static FILE *pedfile;
static FILE *countfile;
static FILE *tpedfile;

#define MAX_RANDOM_RUNS 100

static int         NumOfNodesInGraph;     /* one more than the number of nodes in undirected graph */
static int         NumOfIndividualsWC;   /* one more than the number of individuals with copies of loopbreakers*/
static DNODE       DirectedGraph[maxnode];     /* directed graph */
static NODE        GraphForGreedy[maxnode];    /* undirected graph used for greedy algorithm */
static NODE        GraphForRandom[maxnode];    /* undirected graph used for random algorithm */
static NODE        OriginalGraph[maxnode];     /* undirected input graph */
static NODE        BranchyGraph[maxnode];     /* undirected branchy graph */
static NODE        OutputGraph[maxnode];       /* undirected graph for output */
static NODE          TREE[maxnode];      /* undirected tree */
static NODE          GraphForRedundantNodes[maxnode];  /*internal graph copy for local work*/
static int         cycle[maxnode];             /* cycle[cycleIndex] = individual */
static int         recycle[maxnode];           /* recycle[individual] = cycleIndex */
static int         numCycle;                   /* number of cycles */
static int         proband;                    /* id of proband */
static int         table[maxindperpedigree];   /* global strucure for lines table[LineIndex]= individual */
static long        line[maxindperpedigree][LINEN];        /* array of lines of relevant fields */   
static char        *rest[maxindperpedigree];  /* array of genotype fields */
static PERSON      ped[maxindperpedigree];                /* array of persons */
static int         pedLineLength;      /*Overestimate of length of a line in the pedigree file*/

/*Procedure for testing the ending of a file; used also in unknown.c, taken originally  from the p2c library*/
static int P_eof(FILE *f)
{
    register int ch;

    if (feof(f))
        return 1;
    if (f == stdin)
        return 0;    /* not safe to look-ahead on the keyboard! */
    ch = getc(f);
    if (ch == EOF)
        return 1;
    ungetc(ch, f);
    return 0;
}

/******************************************************************************
*
*       function        close_files
*       parameters  none
*       output          none
*       description closes files
*       creation        Thu Mar 27 18:52:00 1997
*       changes     changed by A. A. Schaffer in June 1999
                    to test file descriptors for NULL and
                    set descriptor values to NULL
*       comments
******************************************************************************/
void close_files()
{
  if (NULL != pedfile) 
    fclose(pedfile);
  pedfile = NULL;
  if (NULL != countfile);
    fclose(countfile);
  countfile = NULL;
  if (NULL != tpedfile)
    fclose(tpedfile);
  tpedfile = NULL;
}

/******************************************************************************
*
*       function        open_files
*       parameters      countfileWrite determines whether
*                                      to open contfile for reading
*                                      or writing
*       output          none
*       description opens files, if file doesn't exist program exits and 
*                               returns alert
*       creation        Thu Mar 27 18:51:00 1997
*       changes
*       comments
*
******************************************************************************/
void open_files(boolean countfileWrite)
{

  if (countfile != NULL)
    {
      fclose(countfile);
      printf("Reopening COUNTFILE.DAT\n");
      if (countfileWrite)
      countfile = fopen("countfile.dat", "w");
      else
      countfile = fopen("countfile.dat", "r");
    }
  else
    {
      printf("Opening COUNTFILE.DAT\n");
      if (countfileWrite)
      countfile = fopen("countfile.dat", "w");
      else
      countfile = fopen("countfile.dat", "r");
    }
  if (NULL == countfile)
    {
      printf(
      "ERROR: File nonexistent. Press <Enter> to continue or <Ctrl-C> to abort\n");
      scanf("%*[^\n]");
      getchar();
    }
  if (pedfile != NULL)
    {
      fclose(pedfile);
      printf("Reopening PEDFILE.DAT\n");
      pedfile = fopen(pedfilename, "r");
    }
  else
    {
      printf("Opening PEDFILE.DAT\n");
      pedfile = fopen(pedfilename, "r");
    }
  if ((pedfile == NULL) || (P_eof(pedfile)))
    {
      printf(
     "ERROR: File empty or nonexistent. Press <Enter> to continue or <Ctrl-C> to abort\n");
      scanf("%*[^\n]");
      getchar();
    }

  printf("Opening TPEDFILE.DAT\n");
  tpedfile = fopen("tpedfile.dat", "w");
}


/*
      Additive random number generator

      Modelled after "Algorithm A" in
      Knuth, D. E. (1981). The art of computer programming, volume 2, page 27.

      7/26/90 Warren Gish
*/

static long state[33] = {
      (long)0xd53f1852,  (long)0xdfc78b83,  (long)0x4f256096,  (long)0xe643df7,
      (long)0x82c359bf,  (long)0xc7794dfa,  (long)0xd5e9ffaa,  (long)0x2c8cb64a,
      (long)0x2f07b334,  (long)0xad5a7eb5,  (long)0x96dc0cde,  (long)0x6fc24589,
      (long)0xa5853646,  (long)0xe71576e2,  (long)0xdae30df,  (long)0xb09ce711,
      (long)0x5e56ef87,  (long)0x4b4b0082,  (long)0x6f4f340e,  (long)0xc5bb17e8,
      (long)0xd788d765,  (long)0x67498087,  (long)0x9d7aba26,  (long)0x261351d4,
      (long)0x411ee7ea,  (long)0x393a263,  (long)0x2c5a5835,  (long)0xc115fcd8,
      (long)0x25e9132c,  (long)0xd0c6e906,  (long)0xc2bc5b2d,  (long)0x6c065c98,
      (long)0x6e37bd55 };

#define r_off     12
#define DIM(A) (sizeof(A)/sizeof((A)[0]))

static long *rJ = &state[r_off],
                  *rK = &state[DIM(state)-1];

/*adapted from ncbitime.c of NCBI toolkit*/
time_t  GetSecs (void)
{
  return time(NULL);
}

/*Next two functions adapted from ncbimath.c of NCBI toolkit*/

long RandomNum(void)
{
      register long     r;

      r = *rK;
      r += *rJ--;
      *rK-- = r;

      if (rK < state)
            rK = &state[DIM(state)-1];
      else
            if (rJ < state)
                  rJ = &state[DIM(state)-1];
      return (r>>1)&0x7fffffff; /* discard the least-random bit */
}

void  RandomSeed(long x)
{
      size_t i;

      state[0] = x;
      /* linear congruential initializer */
      for (i=1; i<DIM(state); ++i) {
            state[i] = 1103515245*state[i-1] + 12345;
      }

      rJ = &state[r_off];
      rK = &state[DIM(state)-1];

      for (i=0; i<10*DIM(state); ++i)
            (void) RandomNum();
}



/******************************************************************************
*
*       function        Random
*       parameters      value              maximum value
*       output          random value
*       description           returns random number in the range [O, 1, ..., 
value-1]
*       creation        Thu Mar 01 18:52:00 1999
*       changes
*       comments       
******************************************************************************/
long Random(long value){

return(RandomNum() % value);
}

/******************************************************************************
*
*       function        NumOfNodes
*       parameters      Graph              undirected graph
*                       root               index of root node
*       output          NumOfNodes
*       description returns number of nodes in connected component of undirected
*                               graph to which root-node belongs
*       creation        Thu Mar 27 18:52:00 1997
*       changes
*       comments        uses depth-first-search
*
******************************************************************************/
int     NumOfNodes(NODE  graph[maxnode], int root)
{
int     NodeIndex;            /* index of the node */
int     NeighIndex;     /* index of the node's neighbor */
int     NumOfNodes;                    
int     Label[maxnode]; /* Label[NodeIndex] = UNVISITED for unvisited node Node
                         * Label[NodeIndex] = VISITED for visited but not fully expanded nodes
                         * Label[NodeIndex] = EXPANDED for fully expanded nodes
                         */    

  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
    Label[NodeIndex] = UNVISITED;
  Label[root] = VISITED;

  while(1) {
    for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
      if (graph[NodeIndex].fSelected && VISITED == Label[NodeIndex]) {
        /* visit all neighbors */
        for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
          if (graph[NodeIndex].D[NeighIndex] && UNVISITED == Label[NeighIndex])
            Label[NeighIndex] = VISITED;
        Label[NodeIndex] = EXPANDED; /* node is fully expanded */
      }
    for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
      if (graph[NodeIndex].fSelected && VISITED == Label[NodeIndex])
      break;
    if (NodeIndex == NumOfNodesInGraph)
      break;
  }

  /* count for number of visited (expanded) nodes */
  for (NumOfNodes = 0, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
    if (DirectedGraph[NodeIndex].fSelected && EXPANDED == Label[NodeIndex])
      NumOfNodes++;
  return (NumOfNodes);
}

/******************************************************************************
*
*     function          NoCycleThrough
*     parameters        graph              undirected graph
*                     root               index of root node
*     output            result
*     description returns TRUE if there is no cycle that goes through root-node
*                     in undirected graph graph
*     creation          Mon Mar 24 14:13:25 1997
*     changes
*     comments          uses DFS
******************************************************************************/
int     NoCycleThrough(NODE  graph[maxnode], int root)
{
int     NodeIndex;              /* index of the node */
int     NeighIndex;             /* index of the node's neighbor */
int     parent[maxnode];        /* parent[i] specifies node from which node
                                 * i was reached at the first time */
int      Label[maxnode]; /* Label[NodeIndex] = UNVISITED for unvisited node Node
                          * Label[NodeIndex] = VISITED for nodes */

  /*Initialize all node labels*/
  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) {
    Label[NodeIndex] = UNVISITED;
    parent[NodeIndex] = -1;
      for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
      graph[NodeIndex].sel[NeighIndex] = FALSE;
  }

  NodeIndex = root;
  Label[NodeIndex] = VISITED;

  while(NodeIndex != -1) {
    for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
            if (graph[NeighIndex].fSelected)
                  {
                  if (graph[NodeIndex].D[NeighIndex] && !graph[NodeIndex].sel[NeighIndex])  {
                  /* visit neighbors of node NodeIndex */
                  graph[NeighIndex].sel[NodeIndex] = graph[NodeIndex].sel[NeighIndex] = TRUE;
                  if (NeighIndex == root)
                        return (FALSE);  /*found cycle by returning to root*/
                  if (UNVISITED == Label[NeighIndex]) {
                        parent[NeighIndex] = NodeIndex;
                        NodeIndex = NeighIndex;
                        Label[NeighIndex] = VISITED;
                        break;
                        }
                  }
            }
            if (NeighIndex == NumOfNodesInGraph)
                  NodeIndex = parent[NodeIndex];
      }
      return TRUE; /* there is no cycle through root */
}

/******************************************************************************
*
*       function        copy_graphs
*       parameters      FromGraph, ToGraph
*       output          none
*       description     copies FromGraph graph to ToGraph graph
*       creation        Wed Apr 02 00:09:23 1997
*       changes
*       comments
*
******************************************************************************/
void    copy_graphs(NODE FromGraph[maxnode], NODE ToGraph[maxnode])
{
int NodeIndex, NeighIndex;

   for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) {
     ToGraph[NodeIndex].fSelected = FromGraph[NodeIndex].fSelected;
     ToGraph[NodeIndex].degree = FromGraph[NodeIndex].degree;
     for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
       ToGraph[NodeIndex].D[NeighIndex] = FromGraph[NodeIndex].D[NeighIndex];
   }
}

/******************************************************************************
*
*       function        AddEdge
*       parameters      graph                     undirected graph
*                       NodeIndex1, NodeIndex2    endpoints of edge to be added
*       output          none
*       description adds edge (NodeIndex1, NodeIndex2) to undirected graph graph
*       creation        Thu Mar 27 18:55:00 1997
*       changes
*       comments
*
******************************************************************************/
void    AddEdge(NODE  graph[maxnode], int NodeIndex1, int NodeIndex2)
{
  graph[NodeIndex1].degree++;
  graph[NodeIndex2].degree++;
  graph[NodeIndex2].D[NodeIndex1] = graph[NodeIndex1].D[NodeIndex2] = TRUE;
}

/******************************************************************************
*
*       function        DeleteEdge
*       parameters      graph   undirected graph
*                       IndexNode1, IndexNode2  endpoints of edge to be deleted
*       output          none
*       description deletes edge (NodeIndex1, NodeIndex2) from undirected graph graph
*       creation        Thu Mar 27 18:55:00 1997
*       changes
*       comments
*
******************************************************************************/
void    DeleteEdge(NODE  graph[maxnode], int NodeIndex1, int NodeIndex2)
{
  graph[NodeIndex1].degree--;
  graph[NodeIndex2].degree--;
  graph[NodeIndex2].D[NodeIndex1] = graph[NodeIndex1].D[NodeIndex2] = FALSE;
}

/******************************************************************************
*
*       function        DeleteNode
*       parameters      graph   undirected graph
*                       NodeIndex  node to be deleted
*       output          none
*       description deletes node NodeIndex from undirected graph graph
*       creation        Mon Mar 27 18:56:00 1997
*       changes
*       comments
*
******************************************************************************/
void    DeleteNode(NODE  graph[maxnode], int NodeIndex)
{
int             NeighIndex; /* index of neighbor */

  graph[NodeIndex].fSelected = FALSE;
  for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
    if (graph[NodeIndex].D[NeighIndex]) {
      graph[NeighIndex].degree -= graph[NodeIndex].D[NeighIndex];  
      graph[NeighIndex].D[NodeIndex] = FALSE;
      /* but not graph[NodeIndex].D[NeighIndex] = FALSE; */
    }
}

/******************************************************************************
*
*       function        AddNodeWithReference
*       parameters      graph             undirected graph
*                 ReferenceGraph          undirected graph of reference
*                       NodeIndex         node to add
*       output          none
*       description     adds node NodeIndex to undirected graph graph
*       creation        Thu Mar 27 18:56:00 1997
*       changes         used to be called AddNode
*                        changed to pass in ReferenceGraph
*       comments    used from spanning tree algorithm, Graph keeps the copy of
*                   graph that was an input for spanning tree algorithm
*
******************************************************************************/
void    AddNodeWithReference(NODE  graph[maxnode], NODE  ReferenceGraph[maxnode], int NodeIndex)
{
int             NeighIndex; /* index of neighbor */

   graph[NodeIndex].fSelected = TRUE;
   for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
       /* neighbor in the ReferenceGraph graph*/
       if (ReferenceGraph[NodeIndex].D[NeighIndex]) { 
       graph[NeighIndex].fSelected = TRUE;
       graph[NodeIndex].degree++;  
       graph[NeighIndex].degree++; 
       graph[NeighIndex].D[NodeIndex] = graph[NodeIndex].D[NeighIndex] = TRUE;
    }
}
/******************************************************************************
*
*       function        SpanningTreeWithReference
*       parameters      ReferenceGraph          undirected graph of reference
*                 first_cycle_index       which cycle to work on
*                       *weight                 used to pass back weight for node selected
*                       *weight_log       used to pass back log(weight) for node selected
*       output          Last Cycle Index
*       description maximum spanning tree algorithm.
*                 create empty graph TREE
*                     In each iteration pick an individual with maximum weight.
*                       If no individual left then exit
*                       Add this node to "tree" TREE
*                       Disable selection of this individual
*                       If there is a cycle that goes throw this indivitual in "tree" TREE
*                          then remove this node from the tree and add it to
*                          vertex-feedback set VFS
*       creation        Thu Mar 27 18:18:00 1997
*       changes         changed from SpanningTree to SpanningTreeWithReference
*                       added ReferenceGraph parameter
*       comments   
*
******************************************************************************/
int     SpanningTreeWithReference(NODE  ReferenceGraph[maxnode], int firstCycleIndex, long *weight, double *weight_log)
{
int     NodeIndex, NeighIndex;  /*indices for nodes and nieghbors*/
int         cycleIndex;                 /* index of cycle */
double  maxWeight;                        /* maximum weight individual */
int   maxWeightIndex;               /* index of maximum weight individual */
int     fEndPointRemoved;           /* Flag is some endpoint node removed */
int     tempWeight;                     /*used to avoid wraparound in weight*/

/*  printf("Spanning Tree algorithm: %d\n",firstCycleIndex); */
   copy_graphs(OriginalGraph, ReferenceGraph);
   for (cycleIndex = 2; cycleIndex < firstCycleIndex; cycleIndex++)
            DeleteNode(ReferenceGraph, cycle[cycleIndex]);

      /* delete nodes with degree 0 and 1 */
      fEndPointRemoved = TRUE;
      while(fEndPointRemoved)
            for (fEndPointRemoved = FALSE, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
                  if (ReferenceGraph[NodeIndex].fSelected && ReferenceGraph[NodeIndex].degree < 2)
                        {
                        DeleteNode(ReferenceGraph, NodeIndex);
                        fEndPointRemoved = TRUE;
                        }

  /* create empty tree TREE */
  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) {
    TREE[NodeIndex].degree = 0;
    TREE[NodeIndex].fSelected = FALSE;
    for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
      TREE[NodeIndex].D[NeighIndex] = 0;
  }

  for (cycleIndex = firstCycleIndex; ;)  {
    maxWeightIndex = -1;
    maxWeight = -1;
    /* find an individual with maximum weight */
    for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
      if (ReferenceGraph[NodeIndex].fSelected && (maxWeight < ped[NodeIndex].weight_log))  {
      maxWeight = ped[NodeIndex].weight_log;
      maxWeightIndex = NodeIndex;
      }
    if (maxWeightIndex == -1) /* if no individual then exit */
      break;
    AddNodeWithReference(TREE, ReferenceGraph, maxWeightIndex);    /* add node to "tree" TREE */
    ReferenceGraph[maxWeightIndex].fSelected = FALSE;    /* disable selection of this individual */
    if (!NoCycleThrough(TREE, maxWeightIndex)) {      
      /* if there is a cycle that goes throw this individual in "tree" TREE
       * remove this node from the tree and add it to VFS */
      DeleteNode(TREE, maxWeightIndex);
      tempWeight = (*weight);
      (*weight) *= ped[maxWeightIndex].weight;
      if ((*weight) < tempWeight)
        (*weight) = tempWeight;
      (*weight_log) += ped[maxWeightIndex].weight_log;
      cycle[cycleIndex] = maxWeightIndex;
      recycle[maxWeightIndex] = cycleIndex;
      cycleIndex++;
    }  /* end if */
  } /* end for */
  return(cycleIndex);
}

/******************************************************************************
*
*       function        RemoveRedundant
*       parameters      *weight used to pass back weight of loop breakers
*                       *weight_log used to pass back log(weight) of loop breakers
*       output          none
*       description     remove redundant nodes
*                       arrange loopbreakers in a preferred order
*                       combine copies of new loopbreakers to get a connected graph 
*                       recompute weight and log(weight) of adjusted
                           loopbreaker set and pass these back
*       creation        Mon Mar 01 20:25:00 1999
*       changes
*       comments        replaces old cleanVFS
******************************************************************************/
void    RemoveRedundant(long *weight, double *weight_log)
{
int     NodeIndex;      /* index of the node */
int     NeighIndex;     /* index of the node's neighbor */
int     numNodes = 0;   /*number of nodes*/
int     cycleIndex, cycleIndex2; /* loop indices for cycles */
int     cycle_order[maxnode];    /* structure that keeps cycles */
double  maxWeight;         /* maximum weight of loopbreaker */
int     maxWeightIndex;    /* index of loopbreaker with maximum weight */
int     tempWeight;        /*used to avoid integer wraparound in weights*/

       (*weight) = 1;
       (*weight_log) = 0;

        /* copy original undirected graph to GraphForRedundantNodes */
        copy_graphs(OriginalGraph, GraphForRedundantNodes);
      for (cycleIndex = 1; cycleIndex < NumOfNodesInGraph; cycleIndex++)
             cycle_order[cycleIndex] = TRUE;

      /*  insert here ordering of loopbreakers by decreasing weights  */
      /*  for every  loop breaker find current maximal */
      for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++) {
        for (maxWeight = -1, cycleIndex2 = 2; cycleIndex2 < numCycle + 2; cycleIndex2++)
          if (cycle[cycleIndex2] && maxWeight < ped[cycle[cycleIndex2]].weight_log) {
            maxWeight = ped[cycle[cycleIndex2]].weight_log;
            maxWeightIndex = cycleIndex2;
          }
        cycle_order[cycleIndex] = cycle[maxWeightIndex];
        cycle[maxWeightIndex] = 0;
      }

      cycle[2] = cycle_order[2]; 
      recycle[cycle[2]] = 2;

      /* put loop breakers 3,4,..., in incresing order of weight*/
      for (cycleIndex = 3; cycleIndex < numCycle + 2; cycleIndex++) {
        cycle[cycleIndex] = cycle_order[numCycle + 4 - cycleIndex];
        recycle[cycle[cycleIndex]] = cycleIndex;
      }

      /* set up cycle_order again*/
      for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++)
        cycle_order[cycleIndex] = cycle[cycleIndex];

      /*loop starts at 2 because loop indicators in column 9 start at 2*/
      for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++) {
        for (cycleIndex2 = 2; cycleIndex2 < numCycle + 2; cycleIndex2++)
          if (cycleIndex2 != cycleIndex && cycle_order[cycleIndex2])
            DeleteNode(GraphForRedundantNodes, cycle[cycleIndex2]);
        if (NoCycleThrough(GraphForRedundantNodes, cycle[cycleIndex])) {
          /* cycle[cycleIndex] node is redundant */
          cycle_order[cycleIndex] = FALSE;
          /* printf("Loopbreaker %d was redundant\n",cycle[cycleIndex]); */
        }
        for (cycleIndex2 = 2; cycleIndex2 < numCycle + 2; cycleIndex2++)
          if (cycleIndex2 != cycleIndex && cycle_order[cycleIndex2]) {
            /* the effect of AddNodeWithReference(GraphForRedundantNodes, NodeIndex); 
             done in the following lines */
            NodeIndex = cycle[cycleIndex2];
            GraphForRedundantNodes[NodeIndex].fSelected = TRUE;
            for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++) 
            
            if (GraphForRedundantNodes[NodeIndex].D[NeighIndex]) {
              GraphForRedundantNodes[NeighIndex].degree += GraphForRedundantNodes[NodeIndex].D[NeighIndex];
              GraphForRedundantNodes[NeighIndex].D[NodeIndex] = GraphForRedundantNodes[NodeIndex].D[NeighIndex];
            }
          }
      }

      /* count and remove redundant loopbreakers */
      for (numNodes = 0, cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++)
        if (!cycle_order[cycleIndex]) {
          cycle[cycleIndex] = 0;
          numNodes++;
        }

      /* adjust array of loop breakers to delete redundant copies */
      for (cycleIndex = 2, cycleIndex2 = 2; cycleIndex < numCycle + 2; cycleIndex++)
        if (cycle[cycleIndex]) {
          cycle[cycleIndex2] = cycle[cycleIndex];
          recycle[cycle[cycleIndex2]] = cycleIndex2;
            tempWeight = *weight;
          (*weight) *= ped[cycle[cycleIndex2]].weight;
            if ((*weight) < tempWeight)
              (*weight) = tempWeight;
          (*weight_log) += ped[cycle[cycleIndex2]].weight_log;
          cycleIndex2++;
        }

      numCycle -= numNodes;
}

/******************************************************************************
*
*       function        FindGreedyVFS
*       parameters      long    *weight  returns weight of selected node
*                       double  *weight_log  returns log(weight) of selected node
*       output          none
*       description runs greedy algorithm
*                   In each iteration
*                     first delete nodes with degree 0 and 1
*                     if no individuals have more than one marriage
*                       then run spanning tree algorithm
*                     else
*                       if graph is not empty
*                       pick individual with smallest ratio of log(w) and degree
*                       update resulting weight of VFS
*                       remove this node from graph
*                       add node to VFS
*       creation        Sat Mar 29 20:19:00 1997
*       changes         returns TRUE if there are multiple marriages
*                       and spanning tree algorithm cannot be used directly
*       comments
*
******************************************************************************/
boolean    FindGreedyVFS(long *weight, double *weight_log)
{
int     NodeIndex;      /* node index used in loops */
double  minRatio;       /* minimum ratio of weight ogf node x to degree of x */
int     minRatioIndex;  /* index of node x with minimal ratio */
int     first = 1;      /* flag of first time in Greedy algorithm */
int     numNodes = 0;   /* number of nodes */
int     cycleIndex;     /* index of cycle */
boolean returnValue;    /* TRUE if there are multiple marriages*/
int     tempWeight ;    /*used to avoid wraparound in weights*/

  copy_graphs(OriginalGraph, GraphForGreedy);
  (*weight) = 1;
  (*weight_log) = 0;

  /* count number of nodes and put 0 as a cycle number for each node */
  for (NodeIndex = 0; NodeIndex < NumOfNodesInGraph; NodeIndex++)  {
    recycle[NodeIndex] = 0;
    if (GraphForGreedy[NodeIndex].fSelected)
      numNodes++;
  }
  /*start cycleIndex at 2 because loop indicator in column 9 is 2 for first loop*/
  returnValue = FALSE;
  for (cycleIndex = 2; numNodes; )  {
    /* first delete nodes with degree 0 and 1 */
    for (NodeIndex = 0; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
      if (GraphForGreedy[NodeIndex].fSelected && NoCycleThrough(GraphForGreedy, NodeIndex)) {
      DeleteNode(GraphForGreedy, NodeIndex);
      numNodes--;
      }
    /* check for individuals with degree more than 2 */
    for (NodeIndex = 0; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
      if (GraphForGreedy[NodeIndex].fSelected &&
        !DirectedGraph[NodeIndex].fFamilyNode && GraphForGreedy[NodeIndex].degree > 2)
      break;
    /* if no individuals have more than one marriage then run spanning tree algorithm */
    if (numNodes && NodeIndex == NumOfNodesInGraph) {
      cycleIndex = SpanningTreeWithReference(GraphForGreedy, cycleIndex, weight, weight_log);
      break;
    }
    /* otherwise  individuals with degree > 2  exist, and must start with Greedy algorithm */
    else 
      if (first) {
        first = 0;
        /*printf("Greedy Algorithm: \n");*/
      }

    returnValue = TRUE;
    if (numNodes) { /* if graph is not empty */
      /* pick individual with smallest ratio of log(w) and degree */
      for (minRatio = MAXIN, NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
     /*limitation to avoid founders*/
      if (GraphForGreedy[NodeIndex].fSelected &&
          minRatio > ped[NodeIndex].weight_log/GraphForGreedy[NodeIndex].degree) {
        minRatio = ped[NodeIndex].weight_log/GraphForGreedy[NodeIndex].degree;
        minRatioIndex = NodeIndex;
      }
      /* update resulting weight of VFS */
      tempWeight = (*weight);
      (*weight) *= ped[minRatioIndex].weight;
      if ((*weight) < tempWeight)
        (*weight) = tempWeight;
      (*weight_log) += ped[minRatioIndex].weight_log;
      /* remove this node from graph */
      DeleteNode(GraphForGreedy, minRatioIndex);
      numNodes--;
      /* add node to VFS */
      cycle[cycleIndex] = minRatioIndex;
      recycle[minRatioIndex] = cycleIndex;
      cycleIndex++;
    } /* end of if(numNodes) */
  } /* end of for  on cycles*/
  numCycle = cycleIndex - 2;

  RemoveRedundant(weight, weight_log);
  printf("Greedy algorithm:\n");
  for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++)
      {
      printf("cycle[%d] = %ld", cycleIndex, ped[cycle[cycleIndex]].weight);
      if (cycleIndex < numCycle + 1)
            printf(",  ");
      else
            printf("\n");
      }
  return(returnValue);
}

/******************************************************************************
*
*       function        ReduceToBranchyGraph
*       parameters      int    *pNumNodes
*       output          none
*       description           Reduces graph to brapnchy graph
*                                         delete nodes with degree 0 and 1
*                                         remove linkpoints 
*       creation        Sat Mar 01 20:19:00 1999
*       changes
*       comments
*
******************************************************************************/
void    ReduceToBranchyGraph(NODE  graph[maxnode], int *pNumNodes)
{
int     NodeIndex;              /* loop index over nodes in copied graph */
int     NeighIndex;             /* loop index to find the nigher of a node
                                   with degree 0 or 1 */
int     NeighIndex2;            /* loop index to look for neighbors of NeighIndex */
int     numNodes = 0;               /* number of nodes */
int     fEndPointRemoved;           /* Flag is some endpoint node removed */
int         fLinkPointRemoved;            /* Flag is some linkpoint node removed */

numNodes = (*pNumNodes);
/* delete nodes with degree 0 and 1 */
fEndPointRemoved = TRUE;
while(fEndPointRemoved)
      for (fEndPointRemoved = FALSE, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
        if (graph[NodeIndex].fSelected && graph[NodeIndex].degree < 2)
                  {
                  DeleteNode(graph, NodeIndex);
                  fEndPointRemoved = TRUE;
            numNodes--;
                  }

/* replace each linkpoints with lightest linkpoint; i.e. every vertex of degree == 2 has
   as neighbors only vertices of degree > 2 or linkpoints with heavier weights */
fLinkPointRemoved = TRUE;
while(fLinkPointRemoved)
      for (fLinkPointRemoved = FALSE, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
            if (graph[NodeIndex].fSelected && graph[NodeIndex].degree == 2)
                  {     
                  for   (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
                        if (graph[NeighIndex].fSelected && graph[NodeIndex].D[NeighIndex])
                              break;
                  /* if it is not a loop consisting of two paraller edges between NeighIndex and NodeIndex */
                  if (graph[NodeIndex].D[NeighIndex] != 2)
                        {
                        for (NeighIndex2 = NeighIndex + 1;  NeighIndex2 < NumOfNodesInGraph; NeighIndex2++)
                              if (graph[NeighIndex2].fSelected && graph[NodeIndex].D[NeighIndex2]) 
                                    break;
                        if ((DirectedGraph[NeighIndex].fFamilyNode && DirectedGraph[NeighIndex2].fFamilyNode && !DirectedGraph[NodeIndex].fFamilyNode)
                              || (!DirectedGraph[NeighIndex].fFamilyNode && DirectedGraph[NeighIndex2].fFamilyNode && !DirectedGraph[NodeIndex].fFamilyNode &&
                                    ped[NeighIndex].weight_log > ped[NodeIndex].weight_log)
                              || (DirectedGraph[NeighIndex].fFamilyNode && !DirectedGraph[NeighIndex2].fFamilyNode && !DirectedGraph[NodeIndex].fFamilyNode &&
                                    ped[NeighIndex2].weight_log > ped[NodeIndex].weight_log)
                              || (!DirectedGraph[NeighIndex].fFamilyNode && !DirectedGraph[NeighIndex2].fFamilyNode && !DirectedGraph[NodeIndex].fFamilyNode &&
                                    ped[NeighIndex].weight_log > ped[NodeIndex].weight_log && ped[NeighIndex2].weight_log > ped[NodeIndex].weight_log))
                              continue;
                        DeleteNode(graph, NodeIndex);
                        fLinkPointRemoved = TRUE;
                        graph[NeighIndex2].D[NeighIndex]++;
                        graph[NeighIndex].D[NeighIndex2]++;
                        graph[NeighIndex2].degree++;
                        graph[NeighIndex].degree++;
                        numNodes--;
                        }
                  }

*pNumNodes = numNodes;
}

/******************************************************************************
*
*       function        SingleWeightedGuess
*       parameters      long    *weight
*                       double  *weight_log
*       output          none
*       description           runs single random guess algorithm
*                       In each iteration 
*                            if graph is not empty
*                                               if exist self-loop (loop of size 2, with two paraller edges)
*                                                     then 
*                                                           pick one of the self loop nodes to FVS
*                                   else
*                                                     pick individual randomly by first choosing an edge, and then the vertex
*                               update resulting weight of VFS
*                               remove this node from graph
*                               add node to VFS
*                                               reduce to branchy graph 
*                                               if no individuals have more than one marriage
*                                   then run spanning tree algorithm
*
*       creation        Sat Mar 01 20:19:00 1999
*       changes
*       comments
*
******************************************************************************/
void    SingleWeightedGuess(int numNodes, long *weight, double *weight_log)
{
int     NodeIndex;            /*loop index over nodes in copied graph*/
int     NeighIndex;           /*loop index to find the nigher of a node
                                with degree 0 or 1*/
int     chosenIndex;           /* index of the node chosen to FVS */
long    numEdges;              /* number of edges */
long    selectedEdge;          /* number of secelted edge */
long  EdgeIndex;               /* index of the edge */
int     cycleIndex;                  /* index of cycle */
int     RandomValue;             /*holds value returned by random-number
                                   generator*/

copy_graphs(BranchyGraph, GraphForRandom);

/* put 0 as a cycle number for each node */
for (NodeIndex = 0; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
    {
    recycle[NodeIndex] = 0;
      cycle[NodeIndex] = 0;
    }

for (cycleIndex = 2; numNodes; )
      {
      chosenIndex = -1;
      /* check for self-loops */
      for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
            if (GraphForRandom[NodeIndex].fSelected && GraphForRandom[NodeIndex].degree == 2) 
                  for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++) 
                        if (GraphForRandom[NeighIndex].fSelected && GraphForRandom[NodeIndex].D[NeighIndex] == 2) 
                              {
                              if (DirectedGraph[NeighIndex].fFamilyNode)
                                    chosenIndex = NodeIndex;
                              else 
                                    if (DirectedGraph[NodeIndex].fFamilyNode || ped[NeighIndex].weight > ped[NodeIndex].weight)
                                          chosenIndex = NeighIndex;
                                    else 
                                          chosenIndex = NodeIndex;
                                    break;
                              }

      if (numNodes) /* if graph is not empty */
            {
            if (chosenIndex == -1)
                  {
                  /* count edges */
                  numEdges = 0;
                  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
                        if (GraphForRandom[NodeIndex].fSelected)
                              for (NeighIndex = NodeIndex + 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
                                    if (GraphForRandom[NeighIndex].fSelected && GraphForRandom[NodeIndex].D[NeighIndex])
                                          numEdges += GraphForRandom[NodeIndex].D[NeighIndex];

                  /* pick an edge */
                  selectedEdge = Random(numEdges);
                  
                  /* select picked edge */
                  for (EdgeIndex = 0, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
                        if (GraphForRandom[NodeIndex].fSelected)
                              {
                              for (NeighIndex = NodeIndex + 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
                                    if (GraphForRandom[NeighIndex].fSelected && GraphForRandom[NodeIndex].D[NeighIndex])
                                          {
                                          EdgeIndex += GraphForRandom[NodeIndex].D[NeighIndex];
                                          if (EdgeIndex >= selectedEdge)
                                                break;
                                          }
                              if (NeighIndex < NumOfNodesInGraph)
                                    break;
                              }
                  /* pick an node */
                  if (DirectedGraph[NodeIndex].fFamilyNode && DirectedGraph[NeighIndex].fFamilyNode)
                        printf("ERROR in LOOPBRK function: family node is chosen!\n");
                  if (!DirectedGraph[NodeIndex].fFamilyNode && DirectedGraph[NeighIndex].fFamilyNode)
                        chosenIndex = NodeIndex;
                  if (DirectedGraph[NodeIndex].fFamilyNode && !DirectedGraph[NeighIndex].fFamilyNode)
                        chosenIndex = NeighIndex;
                  if (!DirectedGraph[NodeIndex].fFamilyNode && !DirectedGraph[NeighIndex].fFamilyNode)
                        {
                                RandomValue = Random(8);
                        if (RandomValue < 4)
                              chosenIndex = NodeIndex;
                        else
                              chosenIndex = NeighIndex;
                        }
                  }
            /* remove this node from graph */
            DeleteNode(GraphForRandom, chosenIndex);
            numNodes--;
            /* add node to VFS */
            cycle[cycleIndex] = chosenIndex;
            recycle[chosenIndex] = cycleIndex;
            cycleIndex++;

            /* reduce to branchy graph */
            ReduceToBranchyGraph(GraphForRandom, &numNodes);

            for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) 
                  if (GraphForRandom[NodeIndex].fSelected &&
                        !DirectedGraph[NodeIndex].fFamilyNode && GraphForRandom[NodeIndex].degree > 2)
                        break;
  
            /* if no individuals have more than one marriage then run spanning tree algorithm */
            if (numNodes && NodeIndex == NumOfNodesInGraph)
                  {
                  cycleIndex = SpanningTreeWithReference(GraphForRandom, cycleIndex, weight, weight_log);
                  break;
                  }
            } /* end of if */
      } /* end of for */

numCycle = cycleIndex - 2;
RemoveRedundant(weight, weight_log);
}
/******************************************************************************
*
*       function        RepeatedWeightedGuess
*       parameters      long    *weight returns weight of selected node
*                       double  *weight_log returns log(weight) of selected node
*                       long    weight_greedy  weight of greedy solution
*                               for comparison
*                       long    numCycle_greedy  size of greedy solution
*                               for comparison
*       output          none
*       description     runs single random guess algorithm MAX_RANDOM_RUNS times
*                 and chooses the FVS with minimal weight
*
*       creation        Mon Mar 01 20:19:00 1999
*       changes
*       comments
*
******************************************************************************/
void    RepeatedWeightedGuess(long *weight, double *weight_log, long weight_greedy, int numCycle_greedy)
{
int     min_cycle[maxnode];  /*stores copy of cycle array
                               for minimum weight solution*/
int     min_recycle[maxnode]; /*stores copy of recycle array for
                                minimum weight solution*/
int     numCycle_min;         /*number of loopbreakers in minimum
                                weight solution*/
int         cycleIndex;   /*index for printing diagnostics*/
long    weight_min; /*mininum weight of a solution seen so far*/
double    weight_min_log; /*approximate log of mininum weight of a solution seen so far*/
long    weight_rand; /*weight of current randomized solution*/
double  weight_rand_log; /*placeholder for log(weight_rand)*/
int     NodeIndex;       /*loop index to copy out arrays for best solution*/
int     iTimes; /*index over iterations of SingleWeightedGuess*/
int         numNodes;

  weight_min = weight_greedy;
  numCycle_min = numCycle_greedy;
  /* copy loop breaker set from greedy algorithm */
  for (NodeIndex = 0; NodeIndex < maxnode; NodeIndex++)
    {
      min_cycle[NodeIndex] = cycle[NodeIndex];
      min_recycle[NodeIndex] = recycle[NodeIndex];
    }

  /* count number the nodes in original graph */
  for (numNodes = 0, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
    if (OriginalGraph[NodeIndex].fSelected)
      numNodes++;
  copy_graphs(OriginalGraph, BranchyGraph);
  /* reduce to branchy graph */
  ReduceToBranchyGraph(BranchyGraph, &numNodes);

  for (iTimes = 1; iTimes < MAX_RANDOM_RUNS; iTimes++)
    {
      SingleWeightedGuess(numNodes, &weight_rand, &weight_rand_log);
      if ((weight_rand < weight_min) ||
      ((weight_rand == weight_min) && (numCycle < numCycle_min)) ||
        (1 == iTimes))
      {    
        weight_min = weight_rand;
        weight_min_log = weight_rand_log;
        numCycle_min = numCycle;
        for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
          {
            min_cycle[NodeIndex] = cycle[NodeIndex];
            min_recycle[NodeIndex] = recycle[NodeIndex];
          }
      }
    }

  /* the result is */
  numCycle = numCycle_min;
  for (NodeIndex = 0; NodeIndex < maxnode; NodeIndex++)
    {
      cycle[NodeIndex] = min_cycle[NodeIndex];
      recycle[NodeIndex] = min_recycle[NodeIndex];
    }

  *weight = weight_min;
  *weight_log = weight_min_log;
  if ((weight_min < weight_greedy) ||
      ((weight_min == weight_greedy) && (numCycle < numCycle_greedy))) {
    printf("Random algorithm:\n");
    for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++)
      {
      printf("cycle[%d] = %ld", cycleIndex, ped[cycle[cycleIndex]].weight);
      if (cycleIndex < numCycle + 1)
        printf(",  ");
      else
        printf("\n");
      }
  }
}

/******************************************************************************
*
*       function        arrangeFVS
*       parameters     
*       output          none
*       description     arranges loopbreakers
*                 combine copies of new loopbreakers to get a connected graph
*       creation        Mon Mar 01 20:25:00 1999
*       changes         modification of what used to be cleanVFS, called
*                       only from loopbreakers, the part that removed
*                       loopbreakers and reordered them is now in 
*                       procedure RemoveRedundant
*       comments
******************************************************************************/
void    arrangeFVS()
{
int     NodeIndex;      /* index of the node */
int     NeighIndex;     /* index of the node's neighbor */
int     numNodes = 0;   /*number of nodes*/
int     cycleIndex;     /* loop indices for cycles */

  /* combine copies of new loopbreakers to get a connected graph */
  for (numNodes = 0, NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
    if (OriginalGraph[NodeIndex].fSelected)
      numNodes++;

  copy_graphs(OriginalGraph, OutputGraph);
  for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++) {
    /*Test the loop breaker for cycle number cycleIndex*/
    NodeIndex = cycle[cycleIndex];
    ped[NodeIndex].numCopies = 0;
    for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
      if (OutputGraph[NodeIndex].D[NeighIndex]) {
        /*Tentatively delete this edge incident to NodeIndex
          to see if it disconnects the graph*/
            DeleteEdge(OutputGraph, NodeIndex, NeighIndex);
      if (OutputGraph[NodeIndex].degree > 0) { /* it was not the last edge */
        if (NumOfNodes(OutputGraph, NeighIndex) < numNodes)
            /*Graph became disconnected, put the edge back*/
          AddEdge(OutputGraph, NodeIndex, NeighIndex);
        else
          ped[NodeIndex].numCopies++;
      }
      else {
        numNodes--;
        if (NumOfNodes(OutputGraph, NeighIndex) < numNodes) {
            /*Graph became disconnected, put the edge back*/
          numNodes++;
          AddEdge(OutputGraph, NodeIndex, NeighIndex);
        }
        else
          ped[NodeIndex].numCopies++;
      } /* end if OutputGraph[NodeIndex].degree > 0 */
      }
  } /* end for */
}

/******************************************************************************
*
*       function        Read_homoz_heteroz
*       parameters      none
*       output          next PedigreeWithLoops or 0
*       description reads number of homozygous and heterozygous at each
*                           individual and locus and assigns weights for each individual
*       creation        Thu Mar 27 18:35:00 1997
*       changes
*       comments
******************************************************************************/
int     Read_homoz_heteroz()
{
int     NumOfLoci;  /* number of loci */
int     LocusIndex; /* Index of locus */
int     PersonId;   /* id of individual */
int     tempid1, tempid2; /* help integers */
long    numgeno; /* number of genotypes per individual */
long  homozProduct; /* produc of homoz per individual */
int     PedigreeWithLoops = 0;  /* count number of next pedigree with loops */
char    str[COUNTFILE_WORD_LENGTH];
char    str1[COUNTFILE_LINE_LENGTH];  /*pedigree string from countfile*/
char    str2[COUNTFILE_LINE_LENGTH];  /*person line from countfile*/

  while (!P_eof(countfile)) {
    fgets(str1, COUNTFILE_LINE_LENGTH, countfile);
    /*Find the number of the next pedigree with loops*/
    if (str1[0] == 'P') {
      sscanf(str1, "%s %d\n", str, &PedigreeWithLoops);
      break;
    }
    fgets(str2, COUNTFILE_LINE_LENGTH -1, countfile);
    sscanf(str1, "%s %s %d %s %d %s  %d %s %s %s",
         str, str, &LocusIndex, str, &PersonId, str, &tempid1, str, str, str);
    sscanf(str2, "%d %s %s\n", &tempid2, str ,str);
    ped[PersonId].homoz[LocusIndex] = tempid1;
    ped[PersonId].heteroz[LocusIndex] = tempid2;
  }

  NumOfLoci = LocusIndex;   
  /*  Compute weight to ped which is number of possible genotypes for each person  */
  for (PersonId = 1; PersonId < NumOfIndividualsWC; PersonId++) {
    for (homozProduct = numgeno = LocusIndex = 1; LocusIndex <= NumOfLoci; LocusIndex++) {
        homozProduct *= ped[PersonId].homoz[LocusIndex];
        numgeno *= (2 * ped[PersonId].heteroz[LocusIndex] + ped[PersonId].homoz[LocusIndex]);
    }
    ped[PersonId].weight = (numgeno - homozProduct)/2 + homozProduct;
    ped[PersonId].weight_log = log((double)ped[PersonId].weight) + epsilon;
  }
  return  PedigreeWithLoops;
}

/******************************************************************************
*
*       function     read_write_ped_non_loop
*       parameters   long currentPedigreeId     current pedigree id
*                    long *nextPedigreeId       next pedigree id
*       output           none
*       description  copies current pedigree from pedfile to 
                        outputFile
*                         and saves id of next pedigree in nextPedigreeId
*       creation     Thu Mar 27 18:40:00 1997
*       changes      A.A. Schaffer added parameter outputFile in June 1999
*       comments
******************************************************************************/
void    read_write_ped_non_loop(long currentPedigreeId, long *nextPedigreeId,
                                FILE *outputFile)
{
long    PersonInfo;       /* individual's information */
int     PersonInfoIndex;  /* id of individual */
char    *rest;
long    line[LINEN];

  rest = (char *) malloc(pedLineLength * sizeof(char));
  while (!P_eof(pedfile) && currentPedigreeId == *nextPedigreeId) {
    line[0] = currentPedigreeId;
    for (PersonInfoIndex = 1; PersonInfoIndex < LINEN; PersonInfoIndex++) {
      fscanf(pedfile, "%ld", &PersonInfo);
      line[PersonInfoIndex] = PersonInfo;
    }
    fgets(rest, pedLineLength - 1, pedfile);

    fprintf(outputFile, "%5ld%4ld%4ld%4ld%4ld%4ld", line[LINE_PEDIGREE], line[LINE_ID],
       line[LINE_PA], line[LINE_MA], line[LINE_FOFF], line[LINE_NEXTPA]);
   /* 3 spaces needed for profield, when >= 9 loop breakers*/
    fprintf(outputFile, "%4ld%2ld%3ld ", line[LINE_NEXTMA], line[LINE_GENDER], line[LINE_PROFIELD]);
    fputs(rest, outputFile);
    if (!P_eof(pedfile))
      fscanf(pedfile, "%ld", nextPedigreeId);
  } /* end of while */
  free(rest);
} /* end of read_write_ped_non_loop */

/******************************************************************************
*
*       function     coalesce_parents
*       parameters   keptParent id of a copy of a loop breaker that should
*                                be retained
*                    deletedParent id of another copy of the same
                                   loop breaker that should be deleted
*                    long numPersons  (number of people in pedigree counting
*                                      duplicates)
*       output      
*                   
*       description  Code assumes that keptParent < deletedParent
*                    merge list of deletedParent's children into the
*                    list for keptParent
*                    decrement by 1 all numbers larger than deletedParent
*                    in ped and line and rest arrays, so that id numbers
*                    remain consecutive    
*       creation     June 1999
*       changes
*       comments
*
******************************************************************************/
void coalesce_parents(int keptParent, int deletedParent, int numPersons)
{
   int sex;   /*gender of this parent*/
   int lastChild; /*last child on the implicit linked list
                    kept by the foff, nextpa, nextma fields*/
   int PersonId, fieldId; /*loop indices*/

   sex = ped[keptParent].sex;
   if (MALE == sex) {
     lastChild = ped[keptParent].foff;
     while(ped[lastChild].nextpa > 0)
       lastChild = ped[lastChild].nextpa;
     ped[lastChild].nextpa = ped[deletedParent].foff;
     line[lastChild][LINE_NEXTPA] = line[deletedParent][LINE_FOFF];
     for(PersonId = 1; PersonId <= numPersons; PersonId++) 
       if(ped[PersonId].paid == deletedParent) {
         ped[PersonId].paid = keptParent;
         line[PersonId][LINE_PA] = keptParent;
       }
   }
   else {
     lastChild = ped[keptParent].foff;
     while(ped[lastChild].nextma > 0)
       lastChild = ped[lastChild].nextma;
     ped[lastChild].nextma = ped[deletedParent].foff;
     line[lastChild][LINE_NEXTMA] = line[deletedParent][LINE_FOFF];
     for(PersonId = 1; PersonId <= numPersons; PersonId++) 
       if(ped[PersonId].maid == deletedParent) {
         ped[PersonId].maid = keptParent;
         line[PersonId][LINE_MA] = keptParent;
       }
   }
   for(PersonId = 1; PersonId <= numPersons; PersonId++) {
     if (ped[PersonId].id > deletedParent) {
       ped[PersonId].id --;
       line[PersonId][LINE_ID]--;
     } 
     if (ped[PersonId].paid > deletedParent) {
       ped[PersonId].paid--;
       line[PersonId][LINE_PA]--;
     }
     if (ped[PersonId].maid > deletedParent) {
       ped[PersonId].maid--;
       line[PersonId][LINE_MA]--;
     }
     if (ped[PersonId].foff > deletedParent) {
       ped[PersonId].foff--;
       line[PersonId][LINE_FOFF]--;
     }
     if (ped[PersonId].nextpa > deletedParent) {
       ped[PersonId].nextpa--;
       line[PersonId][LINE_NEXTPA]--;
     }
     if (ped[PersonId].nextma > deletedParent) {
       ped[PersonId].nextma--;
       line[PersonId][LINE_NEXTMA]--;
     }
   }
   for(PersonId = deletedParent; PersonId < numPersons; PersonId++) {
     for(fieldId = LINE_ID; fieldId <= LINE_PROFIELD; fieldId++)
       line[PersonId][fieldId] = line[PersonId+1][fieldId];
     ped[PersonId].id = ped[PersonId+1].id;
     ped[PersonId].paid = ped[PersonId+1].paid;
     ped[PersonId].maid = ped[PersonId+1].maid;
     ped[PersonId].foff = ped[PersonId+1].foff;
     ped[PersonId].nextpa = ped[PersonId+1].nextpa;
     ped[PersonId].nextma = ped[PersonId+1].nextma;
     ped[PersonId].sex = ped[PersonId+1].sex;
     ped[PersonId].cycle = ped[PersonId+1].cycle;
     strcpy(rest[PersonId], rest[PersonId+1]);
   }
   if (proband == deletedParent)
     proband = keptParent;
   if (proband > deletedParent)
     proband--;
}

/******************************************************************************
*
*       function     coalesce_breakers
*       parameters   long numPersons  (number of people in pedigree counting
*                                      duplicates)
*       output       returns adjusted value of numberPersons
*                    subtracting 1 for each person coalesced
*       description  Whenever there are 2 person numbers that are
*                    copies of the same loop breaker and both are parents
*                    they are coalesced to keep the lower-numbered person
*                    the field for first offspring, next offspring of
*                    same father and next offspring of same mother
*                    are updated
*                    Details of a single coalesced pair are carried out
*                    in coalesce_parents   
*       creation     June 1999
*       changes      fixed in October 2002 to wipe out coalesced ped entries
*       comments
*
******************************************************************************/
int coalesce_breakers(int numPersons)
{
   int firstParentAsBreaker[maxloop+2]; /*what is the lowest id of a parent
                              whose cyce (profield) field is this index*/
   int otherIdentity[maxindperpedigree]; /*if 17 and 34 are both parents
               with cycle field 3, then
               firstParentAsBreaker[3] ==17
               otherIdentity[34] == 17
             when there is no duplicate, otherIdentity stores a 0*/
   int i, PersonId, PersonId2;
   int origNumPersons; /*value of numPersons passed in*/

   origNumPersons = numPersons;
   for(i = 2; i < maxloop +2; i++)
     firstParentAsBreaker[i] = 0;
   for(PersonId = 1; PersonId <= numPersons; PersonId++)
     otherIdentity[PersonId] = 0;
   for(PersonId = 1; PersonId <= numPersons; PersonId++) {
     if ((ped[PersonId].cycle > 1) && (ped[PersonId].foff > 0)) {
       if (0 == firstParentAsBreaker[ped[PersonId].cycle])
         firstParentAsBreaker[ped[PersonId].cycle] = PersonId;
       else 
         otherIdentity[PersonId] = firstParentAsBreaker[ped[PersonId].cycle];
     }
   }
   PersonId = 1;
   while(PersonId <= numPersons) {
     if (otherIdentity[PersonId]) {
       /*have to coalesce this pair, adjust id numbers, before looking
       for next pair*/ 
       coalesce_parents(otherIdentity[PersonId], PersonId, numPersons);
       numPersons--;
       for(i = 2; i < maxloop +2; i++)
       firstParentAsBreaker[i] = 0;
       for(PersonId2 = 1; PersonId2 <= numPersons; PersonId2++)
       otherIdentity[PersonId2] = 0;
       for(PersonId2 = 1; PersonId2 <= numPersons; PersonId2++) {
       if ((ped[PersonId2].cycle > 1) && (ped[PersonId2].foff > 0)) {
         if (0 == firstParentAsBreaker[ped[PersonId2].cycle])
           firstParentAsBreaker[ped[PersonId2].cycle] = PersonId2;
         else 
           otherIdentity[PersonId2] = firstParentAsBreaker[ped[PersonId2].cycle];
       }
       }
     }
     else  /*if Personid is coalesced, new one may be duplicate also*/
       PersonId++;
   }
   for(PersonId = numPersons+1; PersonId <= origNumPersons; PersonId++) {
     ped[PersonId].foff = 0;
     ped[PersonId].nextpa = 0;
     ped[PersonId].nextma = 0;
     ped[PersonId].sex = 0;
     ped[PersonId].cycle = 0;
   }
     
  return(numPersons);
}

/******************************************************************************
*
*       function     order_children
*       parameters   long numPersons  (number of people in pedigree counting
*                                      duplicates)
*       output       none
*       description  arranges foff, nextpa, and next ma fields so that
*                    all children of the same pair of parents are consecutive
*                    This is achieved by sorting the children by parent pair.
*       creation     April 23, 1997
*       changes
*       comments
*
******************************************************************************/
void order_children(int numPersons)
{
  int numChildren; /*number of people with parents in the pedigree*/
  int p;  /*index over persons*/
  int c, c2; /*indices over children*/
  int minChild; /*current minimum father, mother for sorting*/
  int childrenSorted[maxindperpedigree][2];  /*children sorted by pa and ma */
  int parent, otherParent; /*0 for father, 1 for mother*/
  int temp; /*used for swapping*/

  numChildren = 0;

  /*Count number of children and list them*/
  for (p = 1; p <= numPersons; p++) {
     line[p][LINE_FOFF] = line[p][LINE_NEXTPA] = line[p][LINE_NEXTMA] = 0;
     if (0 != line[p][LINE_PA]) {
       childrenSorted[numChildren][0] = p;
       childrenSorted[numChildren][1] = p;
       numChildren++;
     }
   }
  if (0 == numChildren) {
    fprintf(stderr, "Cannot have a pedigree with 0 children");
    exit(EXIT_FAILURE);
  }
  /*Sort children according to the father and mother*/
  for(parent = 0; parent <= 1; parent++) {
    otherParent = 1 - parent;
    for(c = 0; c < numChildren; c++) {
      minChild = c;
      for(c2 = c+1; c2 < numChildren; c2++) {
      if ((line[childrenSorted[c2][parent]][LINE_PA+parent] <
          line[childrenSorted[minChild][parent]][LINE_PA+parent]) ||
          ((line[childrenSorted[c2][parent]][LINE_PA+parent] ==
          line[childrenSorted[minChild][parent]][LINE_PA+parent]) &&
           (line[childrenSorted[c2][parent]][LINE_PA+otherParent] <
          line[childrenSorted[minChild][parent]][LINE_PA+otherParent])) ||
          ((line[childrenSorted[c2][parent]][LINE_PA+parent] ==
          line[childrenSorted[minChild][parent]][LINE_PA+parent]) &&
           (line[childrenSorted[c2][parent]][LINE_PA+otherParent] ==
          line[childrenSorted[minChild][parent]][LINE_PA+otherParent]) &&
            (childrenSorted[c2][parent] < childrenSorted[minChild][parent])))
        minChild = c2;
      }
      /*swap c and minChild*/     
      if (c != minChild){
      temp = childrenSorted[c][parent];
      childrenSorted[c][parent] = childrenSorted[minChild][parent];
      childrenSorted[minChild][parent] = temp;
      }
    }
  }

  /*adjust foff, nextpa, and nextma fields in sorted order*/
  for(parent = 0; parent <= 1; parent++) {
    for(c = 0; c < numChildren; c++) {
      if ((0 == c) || (line[childrenSorted[c][parent]][LINE_PA+parent] !=
                   line[childrenSorted[c - 1][parent]][LINE_PA+parent])) {
      line[line[childrenSorted[c][parent]][LINE_PA+parent]][LINE_FOFF] =
        childrenSorted[c][parent];
      line[childrenSorted[c][parent]][LINE_NEXTPA + parent] = 0;
      }
      else   /*same parent as preceding child*/
      line[childrenSorted[c - 1][parent]][LINE_NEXTPA + parent] = childrenSorted[c][parent];
    }
   line[childrenSorted[numChildren - 1][parent]][LINE_NEXTPA + parent] = 0;
  }

  /*Copy from line to ped*/
  for(p = 1; p <= numPersons; p++) {
    ped[p].foff = line[p][LINE_FOFF];
    ped[p].nextpa = line[p][LINE_NEXTPA];
    ped[p].nextma = line[p][LINE_NEXTMA];
  }
}  /*end order_children*/



/******************************************************************************
*
*       function     readped_with_loop
*       parameters   long currentPedigreeId     current pedigree id
*                    long *nextPedigreeId       next pedigree id
*       output       none
*       description reads pedigree and fills persons structures
*       creation     Thu Mar 27 18:43:00 1997
*       changes
*       comments
*
******************************************************************************/
void    readped_with_loop(long currentPedigreeId, long *nextPedigreeId)
{
long    PersonInfo;       /* individual's information */
int     PersonId;   /* id of individual */
int     LineIndex;        /*Index of field column in person line*/
int     numBreakers[maxloop+3]; /*number of breakers for each loop*/
int     l;                    /*loop index*/

  proband = 0;
  for (l = 0; l < maxloop+3; l++)
    numBreakers[l] = 0;
  /*read lines as long as pedigree number stays the same*/
  for(LineIndex = 0; LineIndex < maxindperpedigree; LineIndex++)
    rest[LineIndex] = NULL;
  rest[0] = (char *) malloc(pedLineLength * sizeof(char));
  for (NumOfIndividualsWC = 1; !P_eof(pedfile) &&
       currentPedigreeId == *nextPedigreeId; NumOfIndividualsWC++) {
    /* have already scanned pedigree number for first person in pedigree*/
    fscanf(pedfile, "%ld", &PersonInfo); 
    PersonId = PersonInfo;
    line[PersonId][LINE_PEDIGREE] = currentPedigreeId;
    line[PersonId][LINE_ID] = PersonId;
    for (LineIndex = 2; LineIndex < LINEN; LineIndex++) {
      fscanf(pedfile, "%ld", &PersonInfo);
      line[PersonId][LineIndex] = PersonInfo;
    }
    rest[PersonId] = (char *) malloc(pedLineLength * sizeof(char));
    fgets(rest[PersonId], pedLineLength, pedfile);
    ped[PersonId].id      = line[PersonId][LINE_ID];
    ped[PersonId].paid    = line[PersonId][LINE_PA];
    ped[PersonId].maid    = line[PersonId][LINE_MA];
    ped[PersonId].foff    = line[PersonId][LINE_FOFF];
    ped[PersonId].nextpa  = line[PersonId][LINE_NEXTPA];
    ped[PersonId].nextma  = line[PersonId][LINE_NEXTMA];
    ped[PersonId].sex     = line[PersonId][LINE_GENDER];
    ped[PersonId].numCopies = 0;
    if ((ped[PersonId].cycle = line[PersonId][LINE_PROFIELD]) == 1)
      proband = PersonId;
    if (ped[PersonId].cycle > 1)
      numBreakers[ped[PersonId].cycle]++;
    if ((ped[PersonId].cycle > 1) && (ped[PersonId].cycle > (maxloop + 1))) {
        /*Is this loopbreaker a proband*/
      ped[PersonId].cycle -= maxloop;
      proband = PersonId;
    }
    if (PersonId == (maxindperpedigree - 1)) {
      printf("\n About to exceed the maximum number of individuals per pedigree");
      exit(EXIT_FAILURE);
    }
    if (!P_eof(pedfile))
      fscanf(pedfile, "%ld", nextPedigreeId);
    else
      *nextPedigreeId = 0;
  } /* end for */
  /*find that proband labeled as 1 is really a loop breaker also*/
  for (l = 2; l < maxloop+3; l++)
    if (1 == numBreakers[l]) {
      ped[proband].cycle = l;
    }      
  if (!proband) /* no proband was found */
    proband = 1;
  NumOfIndividualsWC = 1 + coalesce_breakers(NumOfIndividualsWC -1);  
order_children(NumOfIndividualsWC - 1);
}
/******************************************************************************
*
*       function        Convert_to_undirected_graph
*       parameters      none
*       output          none
*       description creates OriginalGraph of undirected graph that
*                               corresponds to directed graph DirectedGraph
*       creation        Thu Mar 27 18:44:00 1997
*       changes
*       comments
*
******************************************************************************/
void    Convert_to_undirected_graph()
{
  int NodeIndex, NeighIndex;  /*loop indices*/

  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++) {
    OriginalGraph[NodeIndex].fSelected = FALSE;
    OriginalGraph[NodeIndex].degree = 0;
    for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++) 
      OriginalGraph[NodeIndex].D[NeighIndex] = FALSE;
  }

  for (NodeIndex = 1; NodeIndex < NumOfNodesInGraph; NodeIndex++)
    if (DirectedGraph[NodeIndex].fSelected) {
      OriginalGraph[NodeIndex].fSelected = TRUE;
      OriginalGraph[NodeIndex].degree =
      DirectedGraph[NodeIndex].outdegree + DirectedGraph[NodeIndex].indegree;
      for (NeighIndex = 1; NeighIndex < NumOfNodesInGraph; NeighIndex++)
      if (DirectedGraph[NodeIndex].out[NeighIndex] || DirectedGraph[NodeIndex].in[NeighIndex])
        OriginalGraph[NodeIndex].D[NeighIndex] = TRUE;
    }
}
/******************************************************************************
*
*       function     Convert_to_graph
*       parameters   none
*       output       none
*       description  creates directed graph that corresponds to pedigree's topology
*                    and unifies copies of loopbreakers
*       creation     Thu Mar 27 18:47:00 1997
*       changes
*       comments
*
******************************************************************************/
void    Convert_to_graph()
{
int     NodeIndex, NeighIndex, kNodeIndex; /*loop incides*/
int     motherIndex, fatherIndex; /*father and mother in current nuclear family */
int     FamilyIndex;  /* an index of node that represents a nuclear family in which paid(maid) is the father(mother)*/
int     NumOfFamilies;  /* number of nuclear families */

  for (NodeIndex = 1; NodeIndex < maxnode; NodeIndex++) {
    DirectedGraph[NodeIndex].fSelected = FALSE;
    DirectedGraph[NodeIndex].outdegree = DirectedGraph[NodeIndex].indegree = 0;
    for (NeighIndex = 1; NeighIndex < maxnode; NeighIndex++)
      DirectedGraph[NodeIndex].out[NeighIndex] = DirectedGraph[NodeIndex].in[NeighIndex] = FALSE;
  }

  NumOfFamilies = 0;
  for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++) {
    DirectedGraph[NodeIndex].fSelected = TRUE;
    DirectedGraph[NodeIndex].fFamilyNode = FALSE;
    if (ped[NodeIndex].paid || ped[NodeIndex].maid) {
      for (NeighIndex = 0; NeighIndex < NumOfFamilies; NeighIndex++) {
      FamilyIndex = NumOfIndividualsWC + NeighIndex;
      /* index of node that represents a nuclear
         family in which paid(maid) is the father(mother)*/
      if ((!ped[NodeIndex].paid       ||
           (ped[NodeIndex].paid &&
            DirectedGraph[FamilyIndex].in[ped[NodeIndex].paid]))
                   && (!ped[NodeIndex].maid ||
                    (ped[NodeIndex].maid &&
                 DirectedGraph[FamilyIndex].in[ped[NodeIndex].maid])))
        break;
      }  /*end of for loop */
      FamilyIndex = NumOfIndividualsWC + NeighIndex;
      if (NeighIndex == NumOfFamilies) { /* new family */
      NumOfFamilies++;
      DirectedGraph[FamilyIndex].fSelected = TRUE;
      DirectedGraph[FamilyIndex].fFamilyNode = TRUE;
      if (fatherIndex = ped[NodeIndex].paid) {
        DirectedGraph[FamilyIndex].in[fatherIndex] =
          DirectedGraph[fatherIndex].out[FamilyIndex] = TRUE;
        DirectedGraph[FamilyIndex].indegree++;
        DirectedGraph[fatherIndex].outdegree++;
      }
      if (motherIndex = ped[NodeIndex].maid)
        {
          DirectedGraph[FamilyIndex].in[motherIndex] =
            DirectedGraph[motherIndex].out[FamilyIndex] = TRUE;
          DirectedGraph[FamilyIndex].indegree++;
          DirectedGraph[motherIndex].outdegree++;
        }
      }
      DirectedGraph[FamilyIndex].outdegree++;
      DirectedGraph[NodeIndex].indegree++;
      DirectedGraph[NodeIndex].in[FamilyIndex] =
      DirectedGraph[FamilyIndex].out[NodeIndex] = TRUE;
    } /* end if paid || maid */
   } /* end of saving into directed graph */

  /* unify cycle copies */
  NumOfFamilies++;
  NumOfNodesInGraph = NumOfIndividualsWC + NumOfFamilies;

  for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
    if (ped[NodeIndex].cycle > 1 && DirectedGraph[NodeIndex].fSelected)
      for (NeighIndex = NodeIndex + 1; NeighIndex < NumOfIndividualsWC; NeighIndex++)
      if (ped[NeighIndex].cycle == ped[NodeIndex].cycle && DirectedGraph[NeighIndex].fSelected){
        DirectedGraph[NeighIndex].fSelected = FALSE;
        for (kNodeIndex = NumOfIndividualsWC; kNodeIndex < NumOfNodesInGraph; kNodeIndex++) {
          if (DirectedGraph[kNodeIndex].in[NeighIndex]) {
            DirectedGraph[kNodeIndex].in[NeighIndex] = FALSE;
            DirectedGraph[kNodeIndex].in[NodeIndex] = DirectedGraph[NodeIndex].out[kNodeIndex] = TRUE;
            DirectedGraph[NodeIndex].outdegree++;
          }
          if (DirectedGraph[kNodeIndex].out[NeighIndex]) {
            DirectedGraph[kNodeIndex].out[NeighIndex] = FALSE;
            DirectedGraph[kNodeIndex].out[NodeIndex] = DirectedGraph[NodeIndex].in[kNodeIndex] = TRUE;
            DirectedGraph[NodeIndex].indegree++;
          }
        }
        }
}

/******************************************************************************
*
*       function        copy_line
*       parameters      int  FromLineIndex 
*                       int  ToLineIndex
*       output          none
*       description copy line of pedigree file (FromLineIndex) to line (ToLineIndex)
*
*       creation        Sun Mar 30 15:47:06 1997
*       changes
*       comments
*
******************************************************************************/
void    copy_line(int FromLineIndex, int ToLineIndex)
{
int     FieldIndex;  /*index for column in pedigree file*/
int     charIndex;   /*loop index over characters*/

  if (rest[ToLineIndex] == NULL)
    rest[ToLineIndex] = (char *) malloc(pedLineLength * sizeof(char));
  for (FieldIndex = 0; FieldIndex < LINEN; FieldIndex++)
    line[ToLineIndex][FieldIndex] = line[FromLineIndex][FieldIndex];
  for (charIndex = 0; charIndex < pedLineLength; charIndex++)
    rest[ToLineIndex][charIndex] = rest[FromLineIndex][charIndex];
}

/******************************************************************************
*
*       function    rearrange_children
*       parameters  int NodeIndex              index of new loopbreaker
*                    int SpouseIndex           index of spouse of NodeIndex
*                    int *firstchild           index of first child to
*                                              be updated
*       output          none
*       description rearrange children, in particular the nextpa, nextma, and
*                       foff fields of full sibs who are children
*                        of NodeIndex and SpouseIndex
*       creation        thu apr 18 12:33:02 1997
*       changes
*       comments
*
******************************************************************************/
void    Rearrange_children(int NodeIndex, int SpouseIndex, int *firstchild)
{
int     ChildIndex;  /*current child*/     
int   nextChild;   /*next half sibling*/

/*male and female cases are symmetric, comments are in male case*/
if (line[NodeIndex][LINE_GENDER] == MALE)
   {
   /*start at *firstchild */
   ChildIndex = (*firstchild);
   (*firstchild) = -1;
   /*Iterate over the half-siblings with same parent NodeIndex*/
   for (; ChildIndex != 0; ChildIndex = nextChild)
      {
      nextChild = line[ChildIndex][LINE_NEXTPA];
      if (line[ChildIndex][LINE_MA] == SpouseIndex)
        { /* siblings of this family */
        if (line[NodeIndex][LINE_FOFF] == -1)
              /*set foff field for the parent NodeIndex*/
            line[NodeIndex][LINE_FOFF] = ChildIndex;
        line[ChildIndex][LINE_PA] = NodeIndex;
          }
       else  /* for stranger siblings */
          {
          if ((*firstchild) == -1)
              (*firstchild) = ChildIndex;
        }
       } /* end of for children index */
   /*clean up last full sibling*/
   } /* end of if male */

else /* if Node is FEMALE */
    {
    ChildIndex = (*firstchild);
    (*firstchild) = -1;
    for ( ; ChildIndex != 0; ChildIndex = nextChild)
        {
        nextChild = line[ChildIndex][LINE_NEXTMA];
        if (line[ChildIndex][LINE_PA] == SpouseIndex)
            { /* siblings of this family */
            if (line[NodeIndex][LINE_FOFF] == -1)
                    line[NodeIndex][LINE_FOFF] = ChildIndex;
          line[ChildIndex][LINE_MA] = NodeIndex;
            }
        else  /* for stranger siblings */
          {
          if ((*firstchild) == -1)
              (*firstchild) = ChildIndex;
          }
       } /* end of for children index */
   } /* end of if female */
}
/******************************************************************************
*
*       function    Set_up_new_copies
*       parameters  int NodeIndex              index of new loopbreaker
*                   int combine_with_father flag that says that father shouldn't  be disconnected
*                   int *NumOfInd       number of individuals (includes new opies of loopbreakers)
*       output          none
*       description set up copies of new loopbreaker
*                               for each marriage (if needed) creates new copy of lb
*                               if creating new copy will disconnect pedigree
*                               and if combine_with_father is TRUE then creates copy
*                           that connects father with this marriage
*
*       creation        Sun Mar 30 16:56:02 1997
*       changes
*       comments
*
******************************************************************************/
void    Set_up_new_copies(int NodeIndex, int combine_with_father, int *NumOfInd)
{
int     firstchild; /* index of first child */
int     MarriageIndex, SpouseMarriage; /* indices over spouses*/
int     SpouseIndex; /*members of a nuclear family*/
int     FamilyIndex;                /*index of node for a nuclear family*/
int     CopyIndex;                /* ondex of copy of loopbreaker */
int     TableIndex;                 /*index into table*/
int     start = 0;                  /*0 on first time */

firstchild = line[0][LINE_FOFF];

for (MarriageIndex = 0; MarriageIndex < ped[NodeIndex].numMarriages; MarriageIndex++) {
    SpouseIndex = ped[NodeIndex].marriages[MarriageIndex];
    /* find FamilyIndex of family that includes Node and Node's spouse as parents */
    for (SpouseMarriage = 0; SpouseMarriage < ped[SpouseIndex].numMarriages; SpouseMarriage++)
         if (ped[SpouseIndex].marriages[SpouseMarriage] == NodeIndex)
             break;
    for (FamilyIndex = 1; FamilyIndex < NumOfNodesInGraph; FamilyIndex++)
         if (DirectedGraph[FamilyIndex].fSelected &&
               DirectedGraph[FamilyIndex].in[NodeIndex] &&
                  DirectedGraph[FamilyIndex].in[SpouseIndex])
           break;

    if (!OutputGraph[NodeIndex].D[FamilyIndex])
    {
      /* no edge to this family, build a new copy */
      for (CopyIndex = 1; CopyIndex < maxindperpedigree; CopyIndex++)
      if (!table[CopyIndex] && (!combine_with_father || NodeIndex != CopyIndex))
        break;
      (*NumOfInd)++;
       
      copy_line(0, CopyIndex);
      table[CopyIndex] = CopyIndex;
      line[CopyIndex][LINE_PA] = line[CopyIndex][LINE_MA]
      = line[CopyIndex][LINE_NEXTPA] = line[CopyIndex][LINE_NEXTMA] = 0;
      line[CopyIndex][LINE_GENDER] = line[0][LINE_GENDER];
      Rearrange_children(CopyIndex, SpouseIndex, &firstchild);
      line[CopyIndex][LINE_PROFIELD] = NumOfIndividualsWC + recycle[NodeIndex];
      line[CopyIndex][LINE_ID] = CopyIndex; /* id */
      /* fix the rest of the individuals */
      ped[SpouseIndex].marriages[SpouseMarriage] = CopyIndex;
      ped[CopyIndex].marriages[ped[CopyIndex].numMarriages] = SpouseIndex;
      if (NodeIndex != CopyIndex)  /*avoid making an extra copy of the founder*/
      ped[CopyIndex].numMarriages++;
      DirectedGraph[FamilyIndex].in[NodeIndex] = FALSE;
      DirectedGraph[FamilyIndex].in[CopyIndex] = TRUE;
    } /* if end for build a new copy */

    else  {
      if (!start) {
      /* create new copy */
      start = 1;
      if (combine_with_father)
        TableIndex = NodeIndex;
      else {
        (*NumOfInd)++;
        for (TableIndex = 1; TableIndex < maxindperpedigree; TableIndex++)
          if (!table[TableIndex])
            break;
      }

      copy_line(0, TableIndex);
      table[TableIndex] = TableIndex;

      if (!combine_with_father)
        line[TableIndex][LINE_PA] = line[TableIndex][LINE_MA] =
          line[TableIndex][LINE_NEXTPA] = line[TableIndex][LINE_NEXTMA] = 0;

      line[TableIndex][LINE_GENDER] = line[0][LINE_GENDER];
      line[TableIndex][LINE_PROFIELD]=NumOfIndividualsWC + recycle[NodeIndex];
      line[TableIndex][LINE_ID] = TableIndex;

      } /* end if !start */
      /* fix the rest of the individuals */
      Rearrange_children(TableIndex, SpouseIndex, &firstchild);
      ped[SpouseIndex].marriages[SpouseMarriage] = TableIndex;
      ped[TableIndex].marriages[ped[TableIndex].numMarriages] = SpouseIndex;
      if (NodeIndex != TableIndex)  /*avoid making an extra copy of the founder*/
      ped[TableIndex].numMarriages++;
      DirectedGraph[FamilyIndex].in[NodeIndex] = FALSE;
      DirectedGraph[FamilyIndex].in[TableIndex] = TRUE;

    } /* else end for build a new copy for big marriages*/
  } /* end for */
} /* end of Set_up_new_copies */

/******************************************************************************
*
*       function        write_to_file
*       parameters      long  weight_new 
*                       double  weight_log_new
*       output          none
*       description writes pedigree with new loopbreakers to tpedfile
*                               initialises structure of marriages for each person
*                               sets marriages for each person
*                               sorts marriages by time using list of sons
*                               unifies old loopbreakers
*                               creates  copies for new loopbreakers
*                               prints lines to tpedfile
*
*       creation        Sun Mar 30 16:26:24 1997
*       changes         A.A. Schaffer added parameter outputFile in June 1999
*       comments
*
******************************************************************************/
void    write_to_file(long weight_new, double weight_log_new, FILE *outputFile)
{
int     NodeIndex, NeighIndex;     /*Indices for a node and a neighbor*/
int     MarriageIndex;             /*Index for spouse*/
int     FatherIndex, MotherIndex;  /*A father and mother in a nuclear family*/
int     CopyIndex;                 /*Index over copies of a loop breaker*/
int     NumOfInd;       /* one more than the number of Individuals with new loopbreakers copies */
long    weight_old = 1;            /*loop breaker weight in input pedigree*/
double  weight_log_old = 0;        /*log loop breaker weight in input pedigree*/
int     FieldIndex, FieldInfo;     /*Index of field among first 9 on a line and contents*/
int     personIndex;               /*index for a an individual*/
int     cycleIndex;                /*index for loops*/
int     FamilyIndex;               /*index for nuclear families*/
int     tempWeight;                /*used to avoid wraparound in weights*/

  NumOfInd = NumOfIndividualsWC;
  /* initialize table of lines */
  for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
    table[NodeIndex] = NodeIndex;
  for (; NodeIndex < maxindperpedigree; NodeIndex++)
    table[NodeIndex] = 0;

  /* initialize marriages for each person */
  for (NodeIndex = 1; NodeIndex < maxindperpedigree; NodeIndex++) {
    ped[NodeIndex].numMarriages = 0;
    for (NeighIndex = 0; NeighIndex < maxmar; NeighIndex++)
      ped[NodeIndex].marriages[NeighIndex] = -1;
  }
  /* set marriages for each person */
  for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++)
    if ((FatherIndex = ped[NodeIndex].paid) && (MotherIndex = ped[NodeIndex].maid)) {
      for (MarriageIndex = 0; MarriageIndex < ped[FatherIndex].numMarriages; MarriageIndex++)
      if (ped[FatherIndex].marriages[MarriageIndex] == MotherIndex)
        break;
      if (MarriageIndex == ped[FatherIndex].numMarriages) {
      ped[FatherIndex].marriages[ped[FatherIndex].numMarriages] = MotherIndex;
      ped[FatherIndex].numMarriages++;
      }
      for (MarriageIndex = 0; MarriageIndex < ped[MotherIndex].numMarriages; MarriageIndex++)
      if (ped[MotherIndex].marriages[MarriageIndex] == FatherIndex)
        break;
      if (MarriageIndex == ped[MotherIndex].numMarriages) {
      ped[MotherIndex].marriages[ped[MotherIndex].numMarriages] = FatherIndex;
      ped[MotherIndex].numMarriages++;
      }
    }

  /* unify old loopbreakers */
  for (NodeIndex = 1;  NodeIndex < NumOfIndividualsWC; NodeIndex++)
    if (ped[NodeIndex].cycle > 1 && ped[NodeIndex].cycle < NumOfIndividualsWC) {
      tempWeight = weight_old;
      weight_old *= ped[NodeIndex].weight;
      if (weight_old < tempWeight)
        weight_old = tempWeight;
      weight_log_old += (ped[NodeIndex].weight_log - epsilon);
      line[NodeIndex][LINE_PROFIELD] = 0;
      for (CopyIndex = NodeIndex + 1; CopyIndex < maxindperpedigree; CopyIndex++)
      if (ped[NodeIndex].cycle == ped[CopyIndex].cycle) {
        ped[CopyIndex].cycle = 0;
        line[CopyIndex][LINE_PROFIELD] = 0;
        NumOfInd--;
        table[CopyIndex] = 0;
        line[CopyIndex][LINE_ID] = 0;
        ped[NodeIndex].numCopies = ped[CopyIndex].numCopies;
        if (!ped[NodeIndex].numMarriages) {
          ped[NodeIndex].numMarriages = ped[CopyIndex].numMarriages;
          for (MarriageIndex = 0; MarriageIndex < ped[CopyIndex].numMarriages; MarriageIndex++) {
            ped[NodeIndex].marriages[MarriageIndex] = ped[CopyIndex].marriages[MarriageIndex];
              /*AAS*/
              ped[CopyIndex].marriages[MarriageIndex] = -1;
          }
            ped[CopyIndex].numMarriages = 0;
        }
        for (FieldIndex = LINE_PA; FieldIndex < LINE_GENDER; FieldIndex++)
          if (0 == line[NodeIndex][FieldIndex])
            line[NodeIndex][FieldIndex] = line[CopyIndex][FieldIndex]; /* unify lines */
        for (personIndex = 1; personIndex < NumOfIndividualsWC; personIndex++)   /* fix the rest */
          if (table[personIndex]) {
            for (FieldIndex = LINE_PA; FieldIndex < LINE_GENDER; FieldIndex++)
            if (line[personIndex][FieldIndex] == CopyIndex)
              line[personIndex][FieldIndex] = NodeIndex;
            for (MarriageIndex = 0; MarriageIndex < ped[personIndex].numMarriages; MarriageIndex++)
            if (ped[personIndex].marriages[MarriageIndex] == CopyIndex)
              ped[personIndex].marriages[MarriageIndex] = NodeIndex;
          }
        break; /* if CopyIndex is a second copy */
      }
      ped[NodeIndex].cycle = 0;
    }

  /* create copies for new loopbreakers */
  for (cycleIndex = 2; cycleIndex < numCycle + 2; cycleIndex++) {
    NodeIndex = cycle[cycleIndex];
    /* copy line of Node to line 0 (zero line is reserved for tmp line)*/
    copy_line(NodeIndex, 0);
    for (FamilyIndex = 1; FamilyIndex < NumOfNodesInGraph; FamilyIndex++)
      if (DirectedGraph[FamilyIndex].fSelected && DirectedGraph[FamilyIndex].out[NodeIndex])
      break;
    if (FamilyIndex != NumOfNodesInGraph)  { /* Node is not a founder (has parents) */
      if (OutputGraph[NodeIndex].D[FamilyIndex]) { /* no separation to the parent family */
      table[NodeIndex] = 0;
      Set_up_new_copies(NodeIndex, 1, &NumOfInd);
      }
      else  { /* separate from to the parent family */
      Set_up_new_copies(NodeIndex, 0, &NumOfInd);   
      line[NodeIndex][LINE_FOFF] = 0; /* Node stays chiledless son */
      line[NodeIndex][LINE_PROFIELD] =  NumOfIndividualsWC + recycle[NodeIndex];
      }
    }  
    else { /* Node is a founder (no parents) */
      table[NodeIndex] = 0;
      Set_up_new_copies(NodeIndex, 0, &NumOfInd);
      NumOfInd--;
    }
  }

  /* uncode loopbreakers */  
  for (NodeIndex = 1; NodeIndex < maxindperpedigree; NodeIndex++)
    if (table[NodeIndex] && line[NodeIndex][LINE_PROFIELD] > NumOfIndividualsWC)
      line[NodeIndex][LINE_PROFIELD] -= NumOfIndividualsWC;

  /*
   * if there are gaps in lines (empty lines)
   *      then repeatedly swap last last line with first gap
   */
  if (NumOfIndividualsWC > NumOfInd)
    for (;  NumOfIndividualsWC > NumOfInd; NumOfIndividualsWC--) {
      for (NeighIndex = 1; NeighIndex < NumOfIndividualsWC; NeighIndex++)
      if (!table[NeighIndex])
        break;
      for (NodeIndex = NumOfIndividualsWC - 1; NodeIndex > NeighIndex; NodeIndex--)
      if (table[NodeIndex])
        break;
      copy_line(NodeIndex, NeighIndex);
      line[NeighIndex][LINE_ID] = NeighIndex;
      table[NodeIndex]=0;
      for (personIndex = 1; personIndex < NumOfIndividualsWC; personIndex++)   /* fix the rest */
      if (table[personIndex])
        for (FieldIndex = 2; FieldIndex < 7; FieldIndex++)
          if (line[personIndex][FieldIndex] == NodeIndex)
            line[personIndex][FieldIndex] = NeighIndex;
      table[NeighIndex] = NeighIndex;
    }
   
  /* set proband */
  if (line[proband][LINE_PROFIELD] == 0)
    line[proband][LINE_PROFIELD] = 1;
  if (line[proband][LINE_PROFIELD] > 1)
    for (NeighIndex = 1; NeighIndex < NumOfIndividualsWC; NeighIndex++)
      if (line[proband][LINE_PROFIELD] == line[NodeIndex][LINE_PROFIELD] && line[proband][LINE_PA] == 0)
      for (FieldIndex = 0; FieldIndex < LINEN; FieldIndex++) {
        FieldInfo = line[1][FieldIndex];
        line[1][FieldIndex] = line[NodeIndex][FieldIndex];
        line[NodeIndex][FieldIndex] = FieldInfo;
      }

 /*Fix foff, nextpa, nextma fields that may be disconnected*/
 order_children(NumOfInd - 1);
 /* print lines to tpedfile */
 for (NodeIndex = 1; NodeIndex < NumOfInd; NodeIndex++) {
   fprintf(outputFile, "%6ld %6ld %6ld ",
         line[NodeIndex][LINE_PEDIGREE],line[NodeIndex][LINE_ID],line[NodeIndex][LINE_PA],
           line[NodeIndex][LINE_MA], line[NodeIndex][LINE_FOFF],line[NodeIndex][LINE_NEXTPA]);
   /* 3 spaces needed for profield, when >= 9 loop breakers*/
   fprintf(outputFile, "%6ld %6ld %6ld ",
         line[NodeIndex][LINE_NEXTMA],line[NodeIndex][LINE_GENDER],
         line[NodeIndex][LINE_PROFIELD]);
   fputs(rest[NodeIndex],outputFile);
   free(rest[NodeIndex]);
 }

  weight_log_new -= numCycle * epsilon;
  printf("Old weight is %ld\nNew weight is %ld\n", weight_old, weight_new);
  printf("Old log(weight) is %f\nNew log(weight) is %f\n", weight_log_old, weight_log_new);
 }

/******************************************************************************
*
*       function        computeLineLength
*       parameters      none
*       output          none
*       description     reads pedigree file and puts an overestimate of the
*                        line length into the global variable pedLineLength
*
*       creation        Mon Apr 7 1997
*       changes         
*       comments      
*
******************************************************************************/
void computeLineLength()
{
  char c;
  int count;

  count = 0;

  do {
    fscanf(pedfile,"%c", &c);
    count++;
  } while (c != '\n');

  pedLineLength = 2 * count;
  rewind(pedfile);
}

/******************************************************************************
*
*       function        computePositionsForLoci
*       parameters      none
*       output          returns an array showing
*                         how many positions in pedigree file
*                        occupied by each locus
*       description     
*                       
*                       
*
*
*       creation        June 1999
*       changes         
*       comments        
*
******************************************************************************/
int *computePositionsForLoci()
{
  int l; /*loop index*/
  int *returnArray; /*array to return*/

  returnArray = (int *) malloc(nsystem * sizeof(int));
  for (l = 0; l < nsystem; l++) {
    switch(thislocus[l]->which) {
    case quantitative:
      returnArray[l] = thislocus[l]->UU.ntrait;
      break;
    case affection:
      if (thislocus[l]->UU.U0.nclass == 1)
        returnArray[l] = 1;
      else
        returnArray[l] = 2;
      break;
    case binary_:
      if (thislocus[l]->UU.U2.format == 3)
        returnArray[l] = 2;
      else
        returnArray[l] = thislocus[l]->UU.U2.nfactor;
      break;
    }
  }
  return(returnArray);
}

/******************************************************************************
*
*       function        computeInitialWeight
*       parameters      p index of person whose weight we need
*       output          returns a weight
*       description     Figure out for how many loci p has
*                       unknown phenotype, call it numUnknown
*                       and returns a weight of 4^u
*
*       creation        June 1999
*       changes         
*       comments        
*
******************************************************************************/
int computeInitialWeight(int p, int *positionsForLoci)
{
  int numUnknown;  /*number of loci for which p is unknown*/
  int u;           /*loop index*/
  int l;           /*index over loci*/
  int returnWeight; /*weight to return*/
  int numPositions; /*number of positions for the phenotype of this locus*/
  int pos;           /*loop index over positions*/
  int quanValue;   /*quantitative value read*/
  int discreteValue, junk; /*discrete value read*/
  boolean thisKnown; /*is this person known at this locus*/
  char *lineCopy;   /*copy of genotype part of line*/
  char *token, *lineStatus, *thisValue; /*used to read items in lineCopy*/

  numUnknown = 0;
  lineCopy = (char *) malloc(pedLineLength * sizeof(char));
  strcpy(lineCopy, rest[p]); 
  lineStatus = lineCopy;
  returnWeight = 1;
  for (l = 0; l < nsystem; l++) {
    numPositions = positionsForLoci[l];
    switch(thislocus[l]->which) {
    case quantitative:
      for (pos = 0; pos < numPositions; pos++) {
        token = strtok(lineStatus, WHITE_SPACE);
        if (NULL != lineStatus)
          lineStatus =NULL;
        thisValue = (char*) strdup(token);
        quanValue = atof(thisValue);
        if ((0 == pos) && (quanValue == missval))
          numUnknown++;
      }
      break;
    case affection:
      token = strtok(lineStatus, WHITE_SPACE);
      if (NULL != lineStatus)
      lineStatus =NULL;
      thisValue = (char*) strdup(token);
      discreteValue = atoi(thisValue);
      if (numPositions > 1) {
      token = strtok(lineStatus, WHITE_SPACE);
      thisValue = (char*) strdup(token);
      junk = atoi(thisValue);
      }
      if (0 == discreteValue)
        numUnknown++;
      break;
    case binary_:
      if (thislocus[l]->UU.U2.format == 3) {
      token = strtok(lineStatus, WHITE_SPACE);
      if (NULL != lineStatus)
        lineStatus =NULL;
      thisValue = (char*) strdup(token);
      discreteValue = atoi(thisValue);
      token = strtok(lineStatus, WHITE_SPACE);
      thisValue = (char*) strdup(token);
      junk = atoi(thisValue);
      if (0 == discreteValue)
          numUnknown++;
      }
      else {
        thisKnown = FALSE;
      for(pos = 0; pos < numPositions; pos++) {
        token = strtok(lineStatus, WHITE_SPACE);
        if (NULL != lineStatus)
          lineStatus =NULL;
        thisValue = (char*) strdup(token);
        discreteValue = atoi(thisValue);
          if (0 != discreteValue)
            thisKnown = TRUE;
      }
        if (!thisKnown)
          numUnknown++;
      }
      break;
    }
  }
  if (numUnknown > 10)
    numUnknown = 10;
  for(u = 0; u < numUnknown; u++) 
    returnWeight *= 4;
  free(lineCopy);
  return(returnWeight);
}

/******************************************************************************
*
*       function        detectLoopedPedigrees
*       parameters      pedfile   file to red from
                        islooped  array to return FALSE of TRUE for each pedigree
*       output          none
*       description     reads pedigrees from pedfile and decides
*                        which pedigrees have a loop
*                       
*
*       creation        June 1999
*       changes         
*       comments        
*
******************************************************************************/
void detectLoopedPedigrees(boolean *islooped)
{
  boolean hasCycle;  /*does this pedigree have a loop?*/
  int NodeIndex; /*loop index*/
  int *positionsForLoci; /*how many positions in each locus*/
  int currentPedigreeCount; /*count of pedigrees*/
  long currentPedigreeId, nextPedigreeId; /*ids of pedigrees*/
  int thisWeight; /*weight for this person based on loci*/
  int presult; 

  open_files(TRUE);
  computeLineLength(); /*sets pedLineLength*/

  positionsForLoci = computePositionsForLoci();
  /* get first ped id */

  if (!P_eof(pedfile)) {
    fscanf(pedfile,"%ld",&nextPedigreeId);
    line[1][LINE_PEDIGREE] = nextPedigreeId;
  }
  for (currentPedigreeCount = 1; nextPedigreeId != 0; currentPedigreeCount++) {
    currentPedigreeId = nextPedigreeId;
    readped_with_loop(currentPedigreeId, &nextPedigreeId); /*checked*/
    Convert_to_graph(); /*checked*/
    Convert_to_undirected_graph(); /*checked*/
    hasCycle = FALSE;
    /*all individual nodes come first, before family nodes*/
    for (NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++) {
      if (FALSE ==  NoCycleThrough(OriginalGraph, NodeIndex)) {
        hasCycle = TRUE;
        break;
      }
    }
    if (hasCycle) {
        presult = fprintf(countfile,"Pedigree %d\n", currentPedigreeCount);
        fflush(countfile);
        fsync(fileno(countfile));
        for(NodeIndex = 1; NodeIndex < NumOfIndividualsWC; NodeIndex++) {
          thisWeight = computeInitialWeight(NodeIndex, positionsForLoci);
          presult = fprintf(countfile,"At locus 1 person %d has 0 homozygous genotypes and\n %d heterozygous genotypes\n",NodeIndex,thisWeight);
        fflush(countfile);
        fsync(fileno(countfile));
        }
    }
  }
  close_files();
}

/******************************************************************************
*
*       function        loopbreakers
*       parameters      none
*       output          none
*       description     reads pedigrees with old loopbreakers from pedfile.dat
*                       finds new set of loopbreakers and saves new topology
*                       in tpedfile.dat
*
*       creation        Sat Mar 29 20:27:00 1997
*       changes         changed to add use of random algorithm
*       comments        uses greedy algorithm
*
******************************************************************************/
void loopbreakers() 
{
long    nextPedigreeId;         /* id of next pedigree */
long    currentPedigreeId;      /* id of current pedigree */
int     currentPedigreeCount;   /* sequential number of current pedigree */
long    weight_greedy;          /* (product) weight of loop breakers of greedy */
double  weight_log_greedy;      /* (sum of) log weight of loop breakers of greedy */
long    weight_random;          /* (product) weight of loop breakers of random */
double  weight_log_random;      /* (sum of) log weight of loop breakers of random */
int     PedigreeWithLoops = 0;  /* sequential number of pedigree that has loops */
 boolean multipleMarriages;     /* does this pedigree have multiply married indivduals*/

  open_files(FALSE);
  computeLineLength();

  /* get first ped id */
  if (!P_eof(pedfile)) {
    fscanf(pedfile,"%ld",&nextPedigreeId);
    line[1][LINE_PEDIGREE] = nextPedigreeId;
  }

  /* get num of pedigree that has loops */
  if (!P_eof(countfile))
    fscanf(countfile, "Pedigree %d\n", &PedigreeWithLoops);
  for (currentPedigreeCount = 1; !P_eof(pedfile); currentPedigreeCount++) {
    currentPedigreeId = nextPedigreeId;
    if (currentPedigreeCount != PedigreeWithLoops)
      /* pedegree without loops */
      read_write_ped_non_loop(currentPedigreeId, &nextPedigreeId, tpedfile);
    else { /* pedigree with loops */
      readped_with_loop(currentPedigreeId, &nextPedigreeId);
      PedigreeWithLoops  = Read_homoz_heteroz();
      Convert_to_graph();
      Convert_to_undirected_graph();
      multipleMarriages = FindGreedyVFS(&weight_greedy, &weight_log_greedy);
      if (multipleMarriages)
      RepeatedWeightedGuess(&weight_random, &weight_log_random, weight_greedy, numCycle);
      arrangeFVS();
      if (multipleMarriages && (weight_random < weight_greedy))
      write_to_file(weight_random, weight_log_random, tpedfile);
      else
      write_to_file(weight_greedy, weight_log_greedy, tpedfile);
    }
  }
  close_files();
}

/******************************************************************************
*
*       function        loopbreakers2
*       parameters      islooped   array indicating which pedigrees have
                                   a loop
                        lpedfile   file to output to
*       output          none
*       description     reads pedigrees with from pedfile.dat
*                       finds initial set of loopbreakers and saves new topology
*                       in pedfile.dat
*
*       creation        June 1999
*       changes         derived from loopbreakers
*       comments        uses greedy algorithm
*
******************************************************************************/
void loopbreakers2(FILE * lpedfile)
{
long    nextPedigreeId;         /* id of next pedigree */
long    currentPedigreeId;      /* id of current pedigree */
int     currentPedigreeCount;   /* sequential number of current pedigree */
long    weight_greedy = 0;          /* (product) weight of loop breakers of greedy */
double  weight_log_greedy = 0;      /* (sum of) log weight of loop breakers of greedy */
long    weight_random;          /* (product) weight of loop breakers of random */
double  weight_log_random;      /* (sum of) log weight of loop breakers of random */
int     PedigreeWithLoops = 0;  /* sequential number of pedigree that has loops */
 boolean multipleMarriages;     /* does this pedigree have multiply married indivduals*/

  open_files(FALSE);

  /* get first ped id */
  if (!P_eof(pedfile)) {
    fscanf(pedfile,"%ld",&nextPedigreeId);
    line[1][LINE_PEDIGREE] = nextPedigreeId;
  }

  /* get num of pedigree that has loops */
  if (!P_eof(countfile))
    fscanf(countfile, "Pedigree %d\n", &PedigreeWithLoops);
  for (currentPedigreeCount = 1; !P_eof(pedfile); currentPedigreeCount++) {
    currentPedigreeId = nextPedigreeId;
    if (currentPedigreeCount != PedigreeWithLoops)
      /* pedegree without loops */
      read_write_ped_non_loop(currentPedigreeId, &nextPedigreeId, lpedfile);
    else { /* pedigree with loops */
      readped_with_loop(currentPedigreeId, &nextPedigreeId);
      PedigreeWithLoops  = Read_homoz_heteroz();
      Convert_to_graph();
      Convert_to_undirected_graph();
      multipleMarriages = FindGreedyVFS(&weight_greedy, &weight_log_greedy);
      if (multipleMarriages)
      RepeatedWeightedGuess(&weight_random, &weight_log_random, weight_greedy, numCycle);
      arrangeFVS();
      if (multipleMarriages && (weight_log_random < weight_log_greedy))
      write_to_file(weight_random, weight_log_random, lpedfile);
      else 
      write_to_file(weight_greedy, weight_log_greedy, lpedfile);
    }
  }
  close_files();
  if (NULL != lpedfile)
    fclose(lpedfile);
  lpedfile = NULL;
}



Generated by  Doxygen 1.6.0   Back to index