/* iso-update.c: Improved way to find "next bijection" for isomorphisms.
** Written by Michael J. Gourlay
** Fall 1996, University of Colorado at Boulder
** Algorithms
*/


/*

UPDATE to isomorphism code:
---------------------------

This module contains an update to the "isomorph.c" program which
searches for isomorphisms between undirected graphs.

This update contains one subroutine, and a few minor changes to the
routine which calls the new subroutine.  The new subroutine is called
"bijectionNextPlausible" and replaces an older subroutine named
"bijectionNext".

The new subroutine differs from the old subroutine primarily in the
number of bijections generated.

The old subroutine exhaustively generated all possible bijections.
The new subroutine only generates a subset of all possible
bijections, skipping possible bijections which certainly do not
represent an isomorphism.  A bijection is checked for being an
isomorphism by checking all possible edges in two graphs.  The list of
all possible graphs has a natural order.

I will use an analogy of checking to see whether a word is in a
dictionary (except that the words in this dictionary have only words
that never use the same letter twice, but do use each letter at least
once), since there are parallels between that problem and the problem
of checking two graphs for an isomorphism:  Suppose you check each
letter of your word against an entry in the dictionary, from the left
to the right, one letter at a time.  If you find that a letter of
your word doesn't match the corresponding letter of the dictionary
entry (call this letter the "mismatch letter"), then there's no
reason to check for a match of any of the letters to the right.  In
fact, in this dictionary, you can skip forward several entries until
you come to the next word which has a different letter in the
position of the "mismatch letter".  This will save you a lot of time
in finding your word in the dictionary.

Likewise, this new bijection generating algorithm skips over all
bijections which have the same one-to-one map for the vertex which
caused the mismatch.

Note that one reason why this improved "next bijection" is possible
to write is because the bijections have an inherent order to them.
Therefore it is possible to unambiguously skip over regions of the
possible bijections to get to the next bijection which has a
different one-to-one map for the vertex which caused the mismatch
without skipping over other bijections which could possibly represent
an isomorphism.  In the dictionary analogy, it would likewise be
impossible to skip ahead several entries if the words in the
dictionary were not in order.

The phrase "the next bijection which has a different one-to-one map
for the vertex which caused the mismatch" is what is refered to as
"the next /plausible/ bijection".

Note that in order for this new bijection generator to work, it needs
to know which vertex in the bijection caused the mismatch.  This
requires feedback from the "isomorphismCheck" routine -- in particular,
the index of the vertex responsible for the mismatch.  This result
was the value returned in the old version of this program, so no
modification is necessary for the isomorphismCheck routine.

The algorithm
-------------

When the isomorphismCheck routine determines that a bijection is not
an isomorphism, it had been looking at the possible edge between two
vertices within one graph and comparing that connectivity with the
corresponding vertices of the second graph, where the notion of
"corresponding" is defined through the bijection.  The two vertices
have indices Vl_i and Vr_i where Vl_i < Vr_i for all i.  The value of
the index Vr_i is called the "marker" or the "right entry".  This
marker is given to the bijectionNextPlausible routine, along with the
current bijection.

The "tail" is the list of bijection map entries to the right of the
marker.  In other words, the tail is the list of entries whose indices
are greater than the marker.

Search the tail for an entry in the bijection map whose value is the
Smallest which is Greater than the value of the bijection map /at/
the Right entry (i.e. at the "marker").  Call this value the SGRV,
and call its index the SGRI.

  Case 1:  If the SGRV is found, then

    (1a) Swap the value of SGRV with the value in the bijection map at
    the marker.

    (1b) Sort the tail.

  Case 2: No SGRV is found
    At this point, the algorithm falls back to the old algorithm,
    with the minor modification that the rightward search for
    out-of-order elements starts at the marker instead of at the
    rightmost element, although starting at the rightmost element
    would produce the same results, except with more wasted effort.

*/


/* ----------------------- */
/*    Bijection Methods    */
/* ----------------------- */



/* bijectionNextPlausible: find next plausible bijection
** I'll define some terms to make the description compact:
**
** bijP (in/out): input is previously tested bijection
**                output is next plausible bijection
** rfi (in): index of the right element which lead to failure of
**           the bijection tested for an isomorphism
**
** The "tail" is the set of numbers to the right of the rfi element (i.e. the
**   elements which have indices rfi+1 through N-1, where N is the
**   number of vertices.)
** SGR is the value of the Smallest element Greater than the Right value
**   in the tail of the bijection.
**
** Search the tail for an entry in the bijection map whose value is the
** Smallest which is Greater than the value of the bijection map /at/
** the Right entry (i.e. at the "marker").  Call this value the SGRV,
** and call its index the SGRI.
**
**   Case 1:  If the SGRV is found, then
**
**     (1a) Swap the value of SGRV with the value in the bijection map at
**     the marker.
**
**     (1b) Sort the tail.
**
**   Case 2: No SGRV is found
**     At this point, the algorithm falls back to the old algorithm,
**     with the minor modification that the rightward search for
**     out-of-order elements starts at the marker instead of at the
**     rightmost element, although starting at the rightmost element
**     would produce the same results, except with more wasted effort.
*/
int
bijectionNextPlausible(BijectionT *bijP, const int rfi)
{
  int bi;
  int sgri; /* index of smallest greater than map[rfi] */
  int sgrv; /* value of smallest greater than map[rfi] */
  int si;

  /* Scan to right for smallest greater than map[rfi] */

  sgri = -1;  /* initialize with invalid value */
  sgrv = bijP->num_vertices + 1;  /* largest possible value */

  for(bi = rfi+1; bi < bijP->num_vertices; bi++) {
    /* Test for element greater than map[rfi]
    **  --and-- element smaller than previous candidate for sgrv
    */
    if((bijP->map[bi] > bijP->map[rfi]) && (bijP->map[bi] < sgrv)) {
      /* Found a new candidate so remember it */
      sgri = bi;
      sgrv = bijP->map[sgri];
    }
  }

  /* If sgri is a valid value, then Case 1 is the case so go on.
  ** If sgri is still the initial invalid value, then Case 1 failed
  */
  if(sgri > -1) {
    /* Case 1 is the case */
    /* (1a) Swap the sgri and rfi values */
    {
      int tmp = bijP->map[sgri];
      bijP->map[sgri] = bijP->map[rfi];
      bijP->map[rfi] = tmp;
    }

    /* (1b) Sort the tail */
    qsort(/* base */ &(bijP->map[rfi+1]),
        /* number of elements */ bijP->num_vertices - (rfi+1),
        /* size of an element */ sizeof(int),
        /* comparison function */ bijectionElementCompare); /* ignore warning */

  } else {

    /* try Case 2:  Find nearest pair to left with LEFT < RIGHT */

#define LEFT  (bijP->map[bi])
#define RIGHT (bijP->map[bi+1])

    /* Step (1a): scan from right to left for L < R */
    for(bi = rfi-1; bi >= 0; bi--) {
      if(LEFT < RIGHT) {
        /* Found an "out of order pair" */
        break;  /* break out of loop */
      }
    }

#undef LEFT
#undef RIGHT

    /* (1b) See whether we've already hit the last bijection */
    if(bi < 0) return DONE;

    /* (2) Scan to right for next largest value
    ** The "next largest" value is the minimum value which is still
    ** larger than than map[bi].
    */
    si = bi+1;
#define NEXT_LARGEST (bijP->map[si])
    {
      int ti;
      for(ti = bi+1; ti < bijP->num_vertices; ti ++) {
        if(bijP->map[bi] < bijP->map[ti]) {
          /* Found a new candidate for "next largest".
          ** If it is smaller than the previous candidate, remember its
          ** value and its location in the map.
          */
          if(bijP->map[ti] < NEXT_LARGEST) {
            si = ti;
          }
        }
      }
    }
#undef NEXT_LARGEST

    /* (3) Swap values bi and si */
    {
      int tmp_val = bijP->map[bi];
      bijP->map[bi] = bijP->map[si];
      bijP->map[si] = tmp_val;
    }

    /* (4) sort the tail */
    qsort(/* base */ &(bijP->map[bi+1]),
          /* number of elements */ bijP->num_vertices - (bi+1),
          /* size of an element */ sizeof(int),
          /* comparison function */ bijectionElementCompare); /* ignore warn */
  }
  return OKAY;
}




#ifdef NEW_MAIN

/* This "main" routine is nearly the same as the old "main" routine.
** The changes are contained entirely withing "BRUTE_FORCE" precompiler
** blocks.  I would normally not include the entire new subroutine --
** context diffs would suffice -- but this has been requested.
*/

#define FOUND -1


/* #define BRUTE_FORCE /**/

int
main(int argc, char **argv)
{
  char *graph_file_1, *graph_file_2;  /* graph files' names */
  GraphT graph1, graph2;
  BijectionT bijection;
  long bij_count; /* number of bijections explicitly tested for isomorphism */

#ifndef BRUTE_FORCE
  int right_fail_index;  /* index of the right element in failed bijection */
#endif


  /* Parse command line arguments */
  if(argc != 3) {
    /* The wrong number of arguments was present so explain usage */
    fprintf(stderr, "usage: isomorph <graph file 1> <graph file 1>\n");
    exit(1);
  } else {
    /* First command line argument is the name of the first graph file */
    /* Second command line argument is the name of the second graph file */

    /* Read in the first graph */
    if(graphRead(&graph1, argv[1])) exit(1);
    printf("Graph 1: '%s'\n--------\n", argv[1]);
    graphPrintMatrix(&graph1);
    graphPrintVertexNames(&graph1);

    /* Read in the second graph */
    if(graphRead(&graph2, argv[2])) exit (1);
    printf("\nGraph 2: '%s'\n--------\n", argv[2]);
    graphPrintMatrix(&graph2);
    graphPrintVertexNames(&graph2);
  }

  /* Do the simplest level of checking for isomorphism */
  graphIdiotCheck(&graph1, &graph2);

  /* The graphs have the same number of vertices, so the member of
  ** either graph1 or graph2 will suffice from now on.
  */

  /* Initialize first bijection */
  bijection.num_vertices = graph1.num_vertices;
  bijectionInitialize(&bijection);

  bij_count = 0;
  do {
    bij_count ++;
    /* If isomorphismCheck returns negative, then isomorphism was found.
    ** If returns positive, then given bijection was not isomorphism.
    */
#ifdef BRUTE_FORCE
    if(isomorphismCheck(&bijection, &graph1, &graph2) < 0) {
#else
    if((right_fail_index=isomorphismCheck(&bijection, &graph1, &graph2))<0) {
#endif
      printf("\n--- Found isomorphism ---\n");
      printf("Bijection of isomorphism:\n");
      bijectionPrintNumbers(&bijection);
      bijectionPrintNames(&bijection, &graph1, &graph2);

      /* If we were looking for /all/ isomorphisms, then the special
      ** value for right_fail_index which indicates that an isomorphism
      ** was actually found is not a valid index.    In that case, we
      ** just want to move to the next bijection in the next iteration
      ** of this loop.  That's tantamount to setting right_fail_index to
      ** the rightmost index of the bijection map, which is, i.e., the
      ** number of vertices minus one.
      */

#ifndef BRUTE_FORCE
      right_fail_index = bijection.num_vertices - 1;
#endif

      exit(0);
    }
#ifdef BRUTE_FORCE
  } while ( ! bijectionNext(&bijection) );
#else
  } while ( ! bijectionNextPlausible(&bijection, right_fail_index) );
#endif

  /* If we get this far, then no isomorphism exist */
  printf("\n--- No isomorphisms (searched %li)---\n", bij_count);

  /* Free up allocated memory */
  graphFree(&graph1);
  graphFree(&graph2);

  return OKAY;
}
#endif /* NEW_MAIN */