xref: /dports/math/nauty/nauty27r3/planarity.c

/* planarity.c - code for planarity testing of undirected graphs.
 * Method of Boyer and Myrvold, programmed by Paulette Lieby.
 * The copyright of this program is owned by the Magma project.
 * Distributed with nauty by permission.
 ***************************************************************/

/*
 *  sparseg_adjl.c
 */

/*
  What:
  *****

  Implementing:

  Some high-level functions on the sparse graph as
  an adjacency list.
  In particular, testing if it is planar.



  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif


boolean
sparseg_adjl_plan_and_iso (t_ver_sparse_rep *V, int n, t_adjl_sparse_rep *A,
	int e, int *c, t_ver_sparse_rep **VR, t_adjl_sparse_rep **AR,
	t_embed_sparse_rep **ER, int *nbr_e_obs)
    /*
      the input graph is given as an adjacency list:
      V: array of vertices
      n: size of graph
      A: adjacency list
      e: number of edges

      if the graph is planar the embedding is stored  in VR and ER;
      the embedding contains e edges
      (nbr_e_obs not used)

      if the graph is non planar the obstruction is returned in
      VR and AR together with the number of edges in nbr_e_obs

      in all cases is also returned the number of components (in c)
    */
{
    t_dlcl           **dfs_tree, **back_edges, **mult_edges;
    int              edge_pos, v, w;
    boolean          ans;
    t_ver_edge       *embed_graph;

    ans = sparseg_adjl_is_planar(V, n, A, c,
                                 &dfs_tree, &back_edges, &mult_edges,
                                 &embed_graph, &edge_pos, &v, &w);

    if (!ans)
    {
        embedg_obstruction(V, A, dfs_tree, back_edges,
                           embed_graph, n, &edge_pos,
                           v, w, VR, AR, nbr_e_obs);
    }
    else
    {
        embedg_embedding(V, A, embed_graph, n, e, *c, edge_pos, mult_edges,
                         VR, ER);
    }

    sparseg_dlcl_delete(dfs_tree, n);
    sparseg_dlcl_delete(back_edges, n);
    sparseg_dlcl_delete(mult_edges, n);
    embedg_VES_delete(embed_graph, n);

    return ans;
}



int *
sparseg_adjl_footprint (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep *A, int v)
    /*
      return v's footprint:
      an array fp of size n where fp[i] = index of (directed)
      edge [v, i] in A
    */
{
    /*
      note that we won't initialise the array:
      its subsequent usage doesn't require it
    */
    int        *fp, e;

    fp = (int *) mem_malloc(sizeof(int) * n);

    if (V[v].first_edge == NIL)
        /*
          do nothing
        */
        return fp;

    e = V[v].first_edge;
    while (e != NIL)
    {
        fp[A[e].end_vertex] = e;
        e = A[e].next;
    }

    return fp;
}


void
sparseg_adjl_print (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep *A, boolean user_level)
{
    int        v;

    for (v = 0; v < n; v++)
    {
        int     next;

        if (user_level)
            fprintf(stdout, "%d:\t", v + 1);
        else
            fprintf(stdout, "%d:\t", v);

        next = V[v].first_edge;
        while (next != NIL)
        {
            if (user_level)
                fprintf(stdout, "%d ", A[next].end_vertex + 1);
            else
                fprintf(stdout, "%d ", A[next].end_vertex);

            next = A[next].next;
        }
        fprintf(stdout, "\n");
    }
}




void
sparseg_adjl_embed_print (t_ver_sparse_rep *V_e, int n,
	t_adjl_sparse_rep *A, t_embed_sparse_rep *E, boolean user_level)
    /*
      print the embedding given by E,
      edges are referred to by their index in A

      and V_e[v].first_edge is the index in E of the first edge
      (in the embedding's order) incident from v

      note that E is NOT indexed by the same vertices' array
      that indexes A (at the creation of the sparse graph)
    */
{
    int        v;

    for (v = 0; v < n; v++)
    {
        int      start, next;

        if (user_level)
            fprintf(stdout, "%d:\t", v + 1);
        else
            fprintf(stdout, "%d:\t", v);

        if (V_e[v].first_edge == NIL)
        {
            fprintf(stdout, "\n");
            continue;
        }
        start = next = V_e[v].first_edge;

        if (user_level)
            fprintf(stdout, "%d ", A[ E[next].in_adjl ].end_vertex + 1);
        else
            fprintf(stdout, "%d ", A[ E[next].in_adjl ].end_vertex);

        next = E[next].next;

        while (next != start)
            /*
              recall that in E edges are linked into a circular list
            */
        {
            if (user_level)
                fprintf(stdout, "%d ", A[ E[next].in_adjl ].end_vertex + 1);
            else
                fprintf(stdout, "%d ", A[ E[next].in_adjl ].end_vertex);

            next = E[next].next;
        }
        fprintf(stdout, "\n");
    }
}

graph *
sparseg_adjl_to_nauty_graph (t_ver_sparse_rep *V, int n, t_adjl_sparse_rep *A)
    /*
      write the sparse graph as a nauty graph
    */
{
    int          m, v, e, i;
    graph        *g;

    m = (n + WORDSIZE - 1) / WORDSIZE;
    g = (graph *) mem_malloc(n * m * sizeof(graph));
    for (i = (long) m * n; --i >= 0;)
        g[i] = 0;

    /*
      we first copy V and A's information into g
    */
    for (v = 0; v < n; v++)
    {
        e = V[v].first_edge;
        while (e != NIL)
            /*
              A[e].end_vertex is the next neighbour in the list,
              A[e].next points to the next edge in the list
            */
        {
            if (A[e].end_vertex != v)  /* no loops */
            {
                ADDELEMENT(GRAPHROW(g, v, m), A[e].end_vertex);
            }
            e = A[e].next;
        }
    }

    return g;
}



#if 0
t_edge_sparse_rep *
sparseg_adjl_edges (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep *A, int e, boolean digraph)
    /*
      e is the number of edges
    */
{
    t_edge_sparse_rep *edges;
    int               m, u, v, pos_e;
    graph             *g;

    edges = (t_edge_sparse_rep *) mem_malloc(sizeof(t_edge_sparse_rep) * e);

    m = (n + WORDSIZE - 1) / WORDSIZE;
    g = sparseg_adjl_to_nauty_graph(V, n, A);

    pos_e = 0;
    for (u = 0; u < n; u++)
    {
        v = digraph == TRUE ? 0 : u + 1;
        for (; v < n; v++)
        {
            if (ISELEMENT(GRAPHROW(g, u, m), v))
            {
                t_edge_sparse_rep edge;

                edge.ends[0] = u;
                edge.ends[1] = v;
                edges[pos_e++] = edge;
            }
        }
    }
    ASSERT(pos_e == e);
    mem_free(g);

    return edges;
}
#endif



t_edge_sparse_rep *
sparseg_adjl_edges (t_ver_sparse_rep *V, int n, t_adjl_sparse_rep *A,
	int e, boolean digraph)
    /*
      e is the number of edges
    */
{
#if 0
    t_edge_sparse_rep   *edges;
    int                 u, v, pos_e, *loops, *foot_print;
    graph               *g;

    loops = (int *) mem_malloc(sizeof(int) * n);
    for (v = 0; v < n; v++)
    {
        loops[v] = 0;
    }

    edges = (t_edge_sparse_rep *) mem_malloc(sizeof(t_edge_sparse_rep) * e);
    pos_e = 0;

    foot_print = (int *) mem_malloc(sizeof(int) * n);
    for (u = 0; u < n; u++)
        foot_print[u] = NIL;

    for (v = 0; v < n; v++)
    {
        int               ne;
        t_edge_sparse_rep edge;

        ne = V[v].first_edge;
        while (ne != NIL)
        {
            u = A[ne].end_vertex;
            if (digraph
                || (!digraph && u > v))
            {
                foot_print[u] = v;
            }
            else if (!digraph && u == v)
            {
                if (loops[v] == 0)
                {
                    foot_print[u] = v;
                }

                loops[v] ^= 1;
            }

            ne = A[ne].next;
        }

        for (u = 0; u < n; u++)
            if (foot_print[u] == v)
            {
                edge.ends[0] = v;
                edge.ends[1] = u;
                edges[pos_e++] = edge;
            }
    }
    ASSERT(pos_e == e);
    mem_free(loops);
    mem_free(foot_print);

    return edges;

#endif
    /*
      there must be a simpler way
    */
#if 0
    typedef struct edge_list {
        int               size;
        t_edge_sparse_rep *edges;
    } t_edge_list;

    t_edge_list         *edge_table;
    t_edge_sparse_rep   *edges;
    int                 u, v, nbr_e, pos_e, *loops;
    graph               *g;

    loops = (int *) mem_malloc(sizeof(int) * n);
    for (v = 0; v < n; v++)
    {
        loops[v] = 0;
    }

    /*
      now create an edge table as follows:
      - there are n lists in total
      - their respective size is given by size
      - their contents by *edges:

      edge_table[i] will contain all the edges whose end-point is i:
      these edges, by construction, will be sorted according to their
      starting point

      what for? to finish off each start-vertex processing
      with a bucket sort so that
      the edges are sorted wrt start- & end-point

      bucket sort is linear, hence why...
    */
    edge_table = (t_edge_list *) mem_malloc(sizeof(t_edge_list) * n);
    for (v = 0; v < n; v++)
    {
        edge_table[v].size = 0;
        edge_table[v].edges = NP;
    }

    edges = (t_edge_sparse_rep *) mem_malloc(sizeof(t_edge_sparse_rep) * e);

    nbr_e = 0;
    pos_e = 0;
    for (v = 0; v < n; v++)
    {
        int    ne, w, u;

        ne = V[v].first_edge;
        while (ne != NIL)
        {
            u = A[ne].end_vertex;
            if (digraph
                || (!digraph && u > v))
            {
                t_edge_sparse_rep edge;

                edge.ends[0] = v;
                edge.ends[1] = u;

                /*
                  now stick this edge into the table: one may ponder
                  as to the cost of constantly reallocating memory...
                  some cursory tests in another context tell me that
                  this is pretty much ok
                  (and certainly better than allocating n^2 storage space)
                */
                if (edge_table[u].size == 0)
                {
                    edge_table[u].edges = (t_edge_sparse_rep *)
                        mem_malloc(sizeof(t_edge_sparse_rep));
                }
                else
                {
                    edge_table[u].edges = (t_edge_sparse_rep *)
                         mem_realloc(edge_table[u].edges,
                                     sizeof(t_edge_sparse_rep)
                                     * (edge_table[u].size + 1));
                }

                (edge_table[u].edges)[edge_table[u].size] = edge;
                edge_table[u].size += 1;
                nbr_e++;
            }
            else if (!digraph && u == v)
            {
                if (loops[v] == 0)
                {
                    t_edge_sparse_rep edge;

                    edge.ends[0] = v;
                    edge.ends[1] = u;

                    if (edge_table[u].size == 0)
                    {
                        edge_table[u].edges = (t_edge_sparse_rep *)
                            mem_malloc(sizeof(t_edge_sparse_rep));
                    }
                    else
                    {
                        edge_table[u].edges = (t_edge_sparse_rep *)
                            mem_realloc(edge_table[u].edges,
                                        sizeof(t_edge_sparse_rep)
                                        * (edge_table[u].size + 1));
                    }

                    (edge_table[u].edges)[edge_table[u].size] = edge;
                    edge_table[u].size += 1;
                    nbr_e++;
                }

                loops[v] ^= 1;
            }

            ne = A[ne].next;
        }

        /*
          bucket sort must take place here:
          of course the whole lot is not exactly linear!
          since we perform the sort n times; but we can hope for
          a "good"  ?? average behaviour:

          in any case this must be better that checking adjacencies
          n^2 times in a sparse rep. (see edge_set_iset_assure)
        */
        for (w = 0; w < n; w++)
        {
            if (edge_table[w].size > 0)
            {
                for (u = 0; u < edge_table[w].size; u++)
                {
                    ASSERT((edge_table[w].edges)[u].ends[0] == v);
                    edges[pos_e++] = (edge_table[w].edges)[u];
                }
                mem_free(edge_table[w].edges);
                edge_table[w].size = 0;
                edge_table[w].edges = NP;
            }
        }
    }
    ASSERT(nbr_e == e);
    ASSERT(pos_e == e);
    mem_free(loops);
    mem_free(edge_table);

    return edges;
#endif

    t_edge_sparse_rep *edges;
    int               v, pos_e, *loops;

    edges = (t_edge_sparse_rep *) mem_malloc(sizeof(t_edge_sparse_rep) * e);
    loops = (int *) mem_malloc(sizeof(int) * n);
    for (v = 0; v < n; v++)
    {
        loops[v] = 0;
    }

    pos_e = 0;
    for (v = 0; v < n; v++)
    {
        int    ne;

        ne = V[v].first_edge;
        while (ne != NIL)
        {
            int      u;

            u = A[ne].end_vertex;
            if (digraph
                || (!digraph && u > v))
            {
                t_edge_sparse_rep edge;

                edge.ends[0] = v;
                edge.ends[1] = u;
                edges[pos_e++] = edge;
            }
            else if (!digraph && u == v)
            {
                if (loops[v] == 0)
                {
                    t_edge_sparse_rep edge;

                    edge.ends[0] = v;
                    edge.ends[1] = u;
                    edges[pos_e++] = edge;
                }

                loops[v] ^= 1;
            }
            ne = A[ne].next;
        }
    }
    ASSERT(pos_e == e);
    mem_free(loops);

    return edges;

}

/*
 *  sparseg_adjl_modify.c
 */

/*
  What:
  *****

  Implementing:

  Some high-level functions on the sparse graph as
  an adjacency list.
  In particular, adding/removing vertices/edges.


  NOTE: Most of the functions implicitely assume that the
  graph is undirected;
  this must be slightly rewritten for the general case
  -- just haven't got the time right now...


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */



#ifndef PLANAR_IN_MAGMA
#endif



boolean
sparseg_adjl_add_edge (t_ver_sparse_rep *V, int n, t_adjl_sparse_rep **A,
	int *size_A, int *pos, int u, int v, boolean CHECK)
    /*
      add the UNDIRECTED edge to the sparse graph (V, n, A)
      - pos records where to add the next edge in A
      - if pos + 1 == size_A, we must extend A

      we check if the edge is already in the graph iff CHECK true

      also we assume that the graph (V, n, A) is undirected
    */
{
    boolean             edge_exists;

    edge_exists = FALSE;
    if (CHECK)
    {
        edge_exists = sparseg_adjl_dir_edge_exists(V, n, *A, u, v);

        if (edge_exists)
            return FALSE;
    }

    if (*pos == *size_A)
    {
        IF_DEB(
               fprintf(stdout, "realloc \n");
               )

        *size_A += 2;    /* add two directed edges */
        *A = (t_adjl_sparse_rep *)
            mem_realloc(*A, sizeof(t_adjl_sparse_rep) * *size_A);
    }
    else if (*pos + 1 == *size_A)
    {
        IF_DEB(
               fprintf(stdout, "realloc \n");
               )

        *size_A += 1;    /* add two directed edges */
        *A = (t_adjl_sparse_rep *)
            mem_realloc(*A, sizeof(t_adjl_sparse_rep) * *size_A);
    }
    ASSERT(*pos + 1 < *size_A);

    sparseg_adjl_add_dir_edge(V, n, A, size_A, pos, u, v, FALSE);
    sparseg_adjl_add_dir_edge(V, n, A, size_A, pos, v, u, FALSE);

    return TRUE;
}

boolean
sparseg_adjl_add_edge_no_extend (t_ver_sparse_rep *V, int n,
    t_adjl_sparse_rep *A, int size_A, int *pos, int u, int v, boolean CHECK)
    /*
      like sparseg_adjl_add_edge but here we are guaranteed
      that pos + 1 < size_A
      (unless that for some reason we attempt to add
      an edge which is already there)

      this feature is required when A is part of a Magma block:
      we do not want to reallocate A here
      (would be done at a higher level)

      we check if the edge is already in the graph iff CHECK true

      also, we assume that we use this procedur only when dealing
      with an undirected graph
    */
{
    boolean   edge_added;

    edge_added =
        sparseg_adjl_add_dir_edge_no_extend(V, n, A, size_A, pos, u, v,
                                            CHECK);

    if (edge_added)
        sparseg_adjl_add_dir_edge_no_extend(V, n, A, size_A, pos, v, u,
                                            FALSE);

    return edge_added;
}


boolean
sparseg_adjl_add_dir_edge (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep **A, int *size_A, int *pos, int u, int v,
	boolean CHECK)
    /*
      add the DIRECTED edge to the sparse graph (V, n, A)
      - pos records where to add the next edge in A
      - if pos >= size_A, we must extend A

      we check if the edge is already in the graph iff CHECK true
    */
{
    boolean             edge_exists;

    edge_exists = FALSE;
    if (CHECK)
    {
        edge_exists = sparseg_adjl_dir_edge_exists(V, n, *A, u, v);

        if (edge_exists)
            return FALSE;
    }

    if (*pos == *size_A)
    {
        *size_A += 1;    /* add one directed edge */
        *A = (t_adjl_sparse_rep *)
            mem_realloc(*A, sizeof(t_adjl_sparse_rep) * *size_A);
    }
    ASSERT(*pos < *size_A);

    sparseg_adjl_add_dir_edge_no_extend(V, n, *A, *size_A, pos, u, v,
                                        FALSE);

    return TRUE;
}

boolean
sparseg_adjl_add_dir_edge_no_extend (t_ver_sparse_rep *V, int n,
     t_adjl_sparse_rep *A, int size_A, int *pos, int u, int v, boolean CHECK)
    /*
      add an edge where A is guaranteed to be be big enough
      (unless that for some reason we attempt to add
      an edge which is already there)

      this feature is required when A is part of a Magma block:
      we do not want to reallocate A here
      (would be done at a higher level)

      we check if the edge is already in the graph iff CHECK true
    */
{
    /*
      given the way V and A represent the graph, it is simplest
      to add the new edge at the beginning of i's adj. list
    */
    int                  i_v;
    t_adjl_sparse_rep    a;

    if (CHECK && sparseg_adjl_dir_edge_exists(V, n, A, u, v))
        return FALSE;

    if (*pos >= size_A)
        DIE();

    /*
      otherwise always add the edge
    */
    i_v = *pos;
    a.end_vertex = v;
    a.next = V[u].first_edge;
    A[(*pos)++] = a;
    V[u].first_edge = i_v;

    return TRUE;
}



boolean
sparseg_adjl_remove_edge_no_red (t_ver_sparse_rep *V, t_adjl_sparse_rep *A,
	int u, int v)
    /*
      remove the UNDIRECTED edge from sparse graph (V, A)
      if (u, v) is not an edge then nothing changes (and return FALSE)

      A will be left with "holes"
    */
{
    sparseg_adjl_remove_dir_edge_no_red(V, A, u, v);
    return sparseg_adjl_remove_dir_edge_no_red(V, A, v, u);
}


boolean
sparseg_adjl_remove_dir_edge_no_red (t_ver_sparse_rep *V,
	t_adjl_sparse_rep *A, int u, int v)
    /*
      remove the DIRECTED edge from the sparse graph (V, n, A)
      if (u, v) is not an edge then nothing changes  (and return FALSE)

      A will be left with "holes"
    */
{
    int         cur_e, prev_e;

    cur_e = V[u].first_edge;
    if (cur_e == NIL)
        /*
          (u, v) is not an edge
        */
        return FALSE;

    if (A[cur_e].end_vertex == v)
    {
        V[u].first_edge = A[cur_e].next;
        return TRUE;   /* done */
    }

    while (A[cur_e].end_vertex != v)
        /*
          if (u, v) is an edge then this loop will terminate
        */
    {
        prev_e = cur_e;
        cur_e = A[cur_e].next;
        if (cur_e == NIL)
            /*
              (u, v) is not an edge
            */
            return FALSE;
    }
    ASSERT(A[cur_e].end_vertex == v);

    A[prev_e].next = A[cur_e].next;
    return TRUE;
}

int
sparseg_adjl_remove_all_dir_edge_no_red (t_ver_sparse_rep *V,
	t_adjl_sparse_rep *A, int u, int v)
    /*
      remove all DIRECTED edges [u, v] from the non-simple
      sparse graph (V, n, A)
      if (u, v) is not an edge then nothing changes;
      we return the number of edges removed

      A will be left with "holes"
    */
{
    int         cur_e, prev_e, e_removed;

    if (V[u].first_edge == NIL)
        /*
          (u, v) is not an edge
        */
        return 0;

    e_removed = 0;
    while (A[V[u].first_edge].end_vertex == v)
    {
        V[u].first_edge = A[V[u].first_edge].next;
        e_removed++;

        if (V[u].first_edge == NIL)
            return e_removed;
    }
    ASSERT(A[V[u].first_edge].end_vertex != v);

    prev_e = V[u].first_edge;
    cur_e = A[prev_e].next;
    while (cur_e != NIL)
    {
        if (A[cur_e].end_vertex == v)
        {
            A[prev_e].next = A[cur_e].next;
            e_removed++;
            cur_e = A[cur_e].next;
        }
        else
        {
            prev_e = cur_e;
            cur_e = A[cur_e].next;
        }
    }

    return e_removed;
}



void
sparseg_adjl_add_vertices (t_ver_sparse_rep **V, int n, int nmore)
    /*
      add nmore vertices
      V is assumed to have length n
    */
{
    *V = (t_ver_sparse_rep *)
        mem_realloc(*V, sizeof(t_ver_sparse_rep) * (n + nmore));

    sparseg_adjl_add_vertices_no_extend(*V, n, nmore);
}

void
sparseg_adjl_add_vertices_no_extend (t_ver_sparse_rep *V, int n, int nmore)
    /*
      add nmore vertices,
      here V is assumed to have length n + nmore (ie V has already
      been made bigger)
    */
{
    int                  v;

    for (v = n; v < n + nmore; v++)
    {
        V[v].first_edge = NIL;
    }
}

void
sparseg_adjl_remove_vertex (t_ver_sparse_rep **V, int n,
	t_adjl_sparse_rep *A, int pos_A, int w, int *e)
    /*
      V is assumed to have length n: we will reallocate
      V so that V will have length n-1

      A is occupied from [0..pos-1], A will be left with holes

      we also assume that the graph can have loops and multiple edges;
      further, we the edge counting implicitely assumes that graph
      is undirected!!!

      this must be eventually fixed
    */
{
    int                  v, nv, edge, loops;
    t_ver_sparse_rep     *new_V;

    /*
      we first count the loops if any
    */
    loops = 0;
    edge = (*V)[w].first_edge;
    while (edge != NIL)
    {
        loops = A[edge].end_vertex == w ? loops + 1 : loops;
        edge = A[edge].next;
    }
    ASSERT(loops % 2 == 0);
    loops /= 2;

    /*
      we recreate the vertices array
    */
    new_V = (t_ver_sparse_rep *)
        mem_malloc(sizeof(t_ver_sparse_rep) * (n - 1));

    for (v = 0, nv = 0; v < n; v++, nv++)
    {
        if (v == w)
        {
            nv--;
        }
        else
        {
            new_V[nv].first_edge = (*V)[v].first_edge;
        }
    }
    mem_free(*V);
    *V = new_V;

    *e -= loops;
    sparseg_adjl_remove_vertex_no_red(*V, n, A, w, e);

    /*
      oops! not relabelling vertices can wreck havock!
    */
    sparseg_adjl_relabel_vertex(A, pos_A, w);
}

void
sparseg_adjl_remove_vertex_no_red (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep *A, int w, int *e)
    /*
      here V has already size n - 1 and has been initialised,
      all what remains to do is to remove the edges incident
      from w in A

      A will be left with holes
    */
{
    int                  v, nbr_e_removed;

    nbr_e_removed = 0;
    for (v = 0; v < n - 1; v++)
    {
        nbr_e_removed += sparseg_adjl_remove_all_dir_edge_no_red(V, A, v, w);
    }

    *e= *e - nbr_e_removed;
}

void
sparseg_adjl_relabel_vertex (t_adjl_sparse_rep *A, int pos, int u)
    /*
      relabel all vertices v > u as v-1
      (required when removing a vertex)
    */
{
    int                  i;

    for (i = 0; i < pos; i++)
    {
        A[i].end_vertex = A[i].end_vertex > u ?
            A[i].end_vertex - 1 : A[i].end_vertex;
    }
}

/*
 *  sparseg_adjl_pred.c
 */

/*
  What:
  *****

  Implementing:

  Some high-level functions on the sparse graph as
  an adjacency list: predicates.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif

boolean
sparseg_adjl_dir_edge_exists (t_ver_sparse_rep *V, int n,
	t_adjl_sparse_rep *A, int u, int v)
    /*
      does the directed edge [u, v] already exist in the graph
    */
{
    int         cur_e, prev_e;

    cur_e = V[u].first_edge;
    if (cur_e == NIL)
        return FALSE;

    if (A[cur_e].end_vertex == v)
    {
        return TRUE;
    }

    while (A[cur_e].end_vertex != v)
    {
        prev_e = cur_e;
        cur_e = A[cur_e].next;
        if (cur_e == NIL)
            /*
              (u, v) is not an edge
            */
            return FALSE;
    }
    ASSERT(A[cur_e].end_vertex == v);
    return TRUE;
}



boolean
sparseg_adjl_u_adj_v (t_ver_sparse_rep *V, int n, t_adjl_sparse_rep *A,
	int u, int v)
    /*
      is u adj. to v
    */
{
    return sparseg_adjl_dir_edge_exists(V, n, A, u, v);
}


boolean
sparseg_adjl_sub (t_ver_sparse_rep *V1, int n1, t_adjl_sparse_rep *A1,
	t_ver_sparse_rep *V2, int n2, t_adjl_sparse_rep *A2)
    /*
      test if the (V1, n1, A1) sparse graph is a subgraph of
      the (V2, n2, A2) graph
    */
{
    int             v, *fp, n, bign, i;

    n = n1 > n2 ? n2 : n1;
    bign = n1 > n2 ? n1 : 0;
    fp = (int *) mem_malloc(sizeof(int) * n);
    for (i = 0; i < n; i++)
        fp[i] = NIL;

    for (v = 0; v < n; v++)
    {
        int      ne1, ne2;

        ne1 = V1[v].first_edge;
        ne2 = V2[v].first_edge;
        if (ne1 == NIL)
        {
            continue;
        }
        else if (ne2 == NIL)
        {
            mem_free(fp);
            return FALSE;
        }

        while (ne2 != NIL)
        {
            int u2;

            u2 = A2[ne2].end_vertex;
            fp[u2] = v;
            ne2 = A2[ne2].next;
        }

        while (ne1 != NIL)
        {
            int u1;

            u1 = A1[ne1].end_vertex;
            if (fp[u1] != v)
            {
                mem_free(fp);
                return FALSE;
            }
            ne1 = A1[ne1].next;
        }
    }
    mem_free(fp);

    for (v = n; v < bign; v++)
        /*
          those vertices must not be end points of edges:
          this chcek is only necessary in the digraph case
        */
    {
        if (V1[v].first_edge != NIL)
            return FALSE;
    }

    return TRUE;
}



boolean
sparseg_adjl_eq (t_ver_sparse_rep *V1, int n1, t_adjl_sparse_rep *A1,
	t_ver_sparse_rep *V2, int n2, t_adjl_sparse_rep *A2)
    /*
      compare the two sparse graphs (V1, n1, A1) & (V2, n2, A2)
      we don't know their number of edges
    */
{
    if (n1 != n2)
        return FALSE;

    return sparseg_adjl_sub(V1, n1, A1, V2, n2, A2)
        && sparseg_adjl_sub(V2, n2, A2, V1, n1, A1);
}



/*
 *  sparseg_dlcl_misc.c
 */

/*
  What:
  *****

  Implementing:

  Housekeeping for an internal sparse graph representation
  internal to the planarity tester and obstruction isolator.

  This sparse graph consists of an array of doubly linked circular lists
  (the neighbour lists for each vertex).


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */

/* aproto: beginstatic -- don't touch this!! */
static boolean sparseg_dlcl_is_present (t_dlcl *, int, t_dlcl **);
/* aproto: endstatic -- don't touch this!! */


#ifndef PLANAR_IN_MAGMA
#endif


void
sparseg_dlcl_delete (t_dlcl **g, int n)
{
    int      i;

    for (i = 0; i < n; i++)
    {
       embedg_dlcl_delete(g[i]);
    }
    mem_free(g);
}

void
sparseg_dlcl_print (t_dlcl **g, int n)
{
    int      i;

    for (i = 0; i < n; i++)
    {
        fprintf(stdout,"%d:\t", i);
        embedg_dlcl_print(g[i]);
    }
}


static boolean
sparseg_dlcl_is_present (t_dlcl *l, int label, t_dlcl **p)
{
    *p = embedg_dlcl_find(l, label);
    return *p == NP ? FALSE : TRUE;
}


boolean
sparseg_dlcl_is_adjacent (t_dlcl **g, int n, int v, int u, t_dlcl **p)
    /*
      is u adjacent to v
    */
{
    ASSERT(v >= 0 && v < n && u >= 0 && u < n);
    return sparseg_dlcl_is_present(g[v], u, p);
}

void
sparseg_dlcl_append_to_neigh_list (t_dlcl **g, int n, int v, int u, int in_adjl)
    /*
      append u to the neighbour list of v
    */
{
    t_dlcl   *u_rec;

    u_rec = embedg_dlcl_rec_new(u);
    u_rec->in_adjl = in_adjl;
    g[v] = embedg_dlcl_rec_append(g[v], u_rec);
}




void
sparseg_dlcl_to_sparseg (t_dlcl **g, int n, int e,
	t_ver_sparse_rep **V, t_adjl_sparse_rep **A)
    /*
      e is the number of undirected edges of g

      convert a dlcl into the standard sparseg rep. as an
      adjacency list
    */
{
    int                 i_e, v;

    *V = (t_ver_sparse_rep *) mem_malloc(sizeof(t_ver_sparse_rep) * n);
    *A = (t_adjl_sparse_rep *) mem_malloc(sizeof(t_adjl_sparse_rep) * 2 * e);

    for (v = 0; v < n; v++)
        (*V)[v].first_edge = NIL;

    i_e = 0;
    for (v = 0; v < n; v++)
    {
        t_dlcl     *l, *p;

        l = p = g[v];
        if (!embedg_dlcl_is_empty(p))
        {
            t_adjl_sparse_rep   a;

            ASSERT((*V)[v].first_edge == NIL);
            (*V)[v].first_edge = i_e;
            a.end_vertex = p->info;
            a.next = i_e + 1;
            (*A)[i_e++] = a;

            p = embedg_dlcl_list_next(p);
            while (p != l)
            {
                a.end_vertex = p->info;
                a.next = i_e + 1;
                (*A)[i_e++] = a;

                p = embedg_dlcl_list_next(p);
            }

            /*
              end of list for v
            */
            (*A)[i_e - 1].next = NIL;
        }
    }
    ASSERT(i_e == 2 * e);
}

boolean
sparseg_dlcl_sub (t_dlcl **g1, int n1, t_dlcl **g2, int n2)
    /*
      is g2 a subgraph of g1

      I request that both graphs have same order

      This is not used anywhere... do we need it???
    */
{
    int           n, v, *fp;

    if (n1 != n2)
        return FALSE;

    n = n1;
    fp = (int *) mem_malloc(sizeof(int) * n);
    for (v = 0; v < n; v++)
        fp[v] = NIL;

    for (v = 0; v < n; v++)
    {
         t_dlcl     *l1, *p1, *l2, *p2;

        l1 = p1 = g1[v];
        l2 = p2 = g2[v];
        if (embedg_dlcl_is_empty(p1) && !embedg_dlcl_is_empty(p2))
        {
            mem_free(fp);
            return FALSE;
        }
        if (embedg_dlcl_is_empty(p2))
        {
            continue;
        }

        fp[p1->info] = v;
        p1 = embedg_dlcl_list_next(p1);
        while (p1 != l1)
        {
            fp[p1->info] = v;
            p1 = embedg_dlcl_list_next(p1);
        }

        if (fp[p2->info] != v)
        {
            mem_free(fp);
            return FALSE;
        }
        p2 = embedg_dlcl_list_next(p2);
        while (p2 != l2)
        {
            if (fp[p2->info] != v)
            {
                mem_free(fp);
                return FALSE;
            }
        }
    }
    mem_free(fp);

    return TRUE;
}
/*
 *  VES_misc.c
 */

/*
  What:
  *****

  Implementing:

  All low-level routines for the VES structure:

  - the VES structure is solely used within the planarity tester
    and obstruction isolator

  - it stores vertices, virtual vertices and edges
       --more on this later--

  - it allows for circular doubly linked lists, hence
    enabling us -among other things- to store the
    graph embedding if the tester is successful

  - basic features:
    + the VES has exactly size 2n + 2(3n-5) :
      we add at most one more edge than the max for a planar graph
      (need to x by 2: we store directed edges)
    + a vertex and the edges incident FROM it are linked in a doubly
      linked circular list
    + where a vertex is inserted between two of its outcoming edges
      determines an external face walk for a bicomponent
    + the twin edge is more commonly known as the inverse edge
    + we have tree and back edges (from the DFS), and short-cut edges
      which are added by the tester
      -but short-cut edges are added in such a way as to maintain
       planarity (in a local sense)
    + vertices and edges can be marked (visited for example)
    + they have an orientation which must be eventuall recovered
      and which is set in the merge_bicomp routine
    + vertices are essentially known via their DFI or DFS index
      (though their label is stored too)

     blah, blah.... later then.
     Have a look at embedg_planar_alg_init which initialises the VES
     structure


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_SCE(x)    {}
#define IF_DEB_PROPER_FACE(x) {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */

boolean
embedg_VES_is_vertex (int n, int i)
    /*
      is this a vertex
      (relative to the "big" array of size 2n + 2(3n-5))
    */
{
    return i < n ? TRUE : FALSE;
}

boolean
embedg_VES_is_virtual_vertex (int n, int i)
    /*
      is this a virtual vertex
      (relative to the "big" array of size 2n + 2(3n-5))

      a virtual vertex is a vertex v^c which denotes the
      DFS parent of the child c

      see embedg_planar_alg_init for more
    */
{
    return i >= n && i < 2*n ? TRUE : FALSE;
}

boolean
embedg_VES_is_edge (int n, int i)
    /*
      is this an edge
      (relative to the "big" array of size 2n + 2(3n-5))
    */
{
    return i >= 2*n ? TRUE : FALSE;
}

boolean
embedg_VES_is_tree_edge (t_ver_edge *embed_graph, int n, int i)
    /*
      is this s tree edge
    */
{
    return embedg_VES_is_edge(n, i)
        && embed_graph[i].type == TE;
}

boolean
embedg_VES_is_back_edge (t_ver_edge *embed_graph, int n, int i)
    /*
      is this a back edge
    */
{
    return embedg_VES_is_edge(n, i)
        && embed_graph[i].type == BE;
}

boolean
embedg_VES_is_short_cut_edge (t_ver_edge *embed_graph, int n, int i)
    /*
      as the name indicates...
    */
{
    return embedg_VES_is_edge(n, i)
        && embed_graph[i].type == SCE;
}

void
embedg_VES_print_vertex (int n, int v)
{
    ASSERT(embedg_VES_is_vertex(n, v));
    fprintf(stdout, "%d  ", v);
}

void
embedg_VES_print_virtual_vertex (t_ver_edge *embed_graph, int n, int v)
{
    int          c;

    ASSERT(embedg_VES_is_virtual_vertex(n, v));
    c = v - n;
    fprintf(stdout, "%d^%d  ", embed_graph[c].DFS_parent, c);
}

void
embedg_VES_print_any_vertex (t_ver_edge *embed_graph, int n, int v)
{
    if (embedg_VES_is_vertex(n, v))
    {
        embedg_VES_print_vertex(n, v);
    }
    else
    {
        embedg_VES_print_virtual_vertex(embed_graph, n, v);
    }
}

void
embedg_VES_print_any_rec (t_ver_edge *embed_graph, int n, int r)
{
    if (embedg_VES_is_edge(n, r))
    {
        embedg_VES_print_edge(embed_graph, n, r);
    }
    else
    {
        embedg_VES_print_any_vertex(embed_graph, n, r);
    }
}

void
embedg_VES_print_edge (t_ver_edge *embed_graph, int n, int e)
{
    int          v, prev, cur;

    ASSERT(embedg_VES_is_edge(n, e));

    /*
      must find the vertex in the doubly linked circular list
      of vertices/edges
    */

    prev = e;
    cur = v = embed_graph[e].link[0];
    if (embedg_VES_is_vertex(n, v)
        || embedg_VES_is_virtual_vertex(n, v))
    {
        embedg_VES_print_any_vertex(embed_graph, n, v);
        fprintf(stdout, ", ");
        embedg_VES_print_any_vertex(embed_graph, n,
                                         embed_graph[e].neighbour);
        fprintf(stdout, "):0\n");
    }
    else while (!embedg_VES_is_vertex(n, v)
                && !embedg_VES_is_virtual_vertex(n, v))
    {
        v = embedg_VES_get_next_in_dlcl(embed_graph, n,
                                                   cur, prev);

        if (embedg_VES_is_vertex(n, v)
            || embedg_VES_is_virtual_vertex(n, v))
        {
            embedg_VES_print_any_vertex(embed_graph, n, v);
            fprintf(stdout, ", ");
            embedg_VES_print_any_vertex(embed_graph, n,
                                             embed_graph[e].neighbour);
            fprintf(stdout, "):0\n");
        }
        else
        {
            prev = cur;
            cur = v;
        }
    }
}

void
embedg_VES_print_flipped_edges (t_ver_edge *embed_graph, int n, int edge_pos)
    /*
      print those edges in the structure whose sign is CLOCKW,
      ie which have been flipped at some stage
    */
{
    int          e;

    for (e = 2*n; e <= edge_pos; e++)
    {
        if (!embedg_VES_is_short_cut_edge(embed_graph, n, e))
            /*
              we don't care about the short-cut edges
            */
        {
            if (embed_graph[e].sign != CCLOCKW)
            {
                embedg_VES_print_edge(embed_graph, n, e);
            }
        }
    }
}

#if 0
int
embedg_VES_get_edge_from_ver (t_ver_edge *embed_graph, int n, int v)
    /*
      not used anywhere; why is this here???
    */
{
    int          in, e;

    ASSERT(embedg_VES_is_vertex(n, v)
           || embedg_VES_is_virtual_vertex(n, v));

    in = embedg_VES_is_edge(n, embed_graph[v].link[0]) ? 0 : 1;
    e = embed_graph[v].link[in];
    ASSERT(embedg_VES_is_edge(n, e));

    return e;
}

int
embedg_VES_get_ver_from_edge (t_ver_edge *embed_graph, int n, int e)
{
    int          in, v;

    ASSERT(embedg_VES_is_edge(n, e));

    in = embedg_VES_is_vertex(n, embed_graph[e].link[0])
        || embedg_VES_is_virtual_vertex(n, embed_graph[e].link[0])
        ?
        0 : 1;

    v = embed_graph[e].link[in];
    ASSERT(embedg_VES_is_vertex(n, v)
           || embedg_VES_is_virtual_vertex(n, v));

    return v;
}
#endif

int
embedg_VES_get_twin_edge (t_ver_edge *embed_graph, int n, int e)
    /*
      the twin edge is understood as being the inverse edge
    */
{
    int          twin;

    ASSERT(embedg_VES_is_edge(n, e));

    twin = e % 2 == 0 ? e + 1 : e - 1;
    ASSERT(embedg_VES_is_edge(n, twin));

    return twin;
}

int
embedg_VES_get_ver_from_virtual (t_ver_edge *embed_graph, int n, int vv)
    /*
      get v from the virtual vertex v^c
    */
{
    int          v;

    ASSERT(embedg_VES_is_virtual_vertex(n, vv));
    v = embed_graph[vv - n].DFS_parent;

    return v;
}

int
embedg_VES_get_ver (t_ver_edge *embed_graph, int n, int v)
{
    if (embedg_VES_is_virtual_vertex(n, v))
        return embedg_VES_get_ver_from_virtual(embed_graph, n, v);

    return v;
}


int
embedg_VES_get_next_in_dlcl (t_ver_edge *embed_graph, int n, int r, int prev)
    /*
      r is a (virtual) vertex or edge record in embed_graph:
      get the next in the list (formed by the .link[] fields)
      in the doubly linked circular list

      so that prev != next
      -- NOTE: a priori these lists always contain 2 elts at least
      so that there shouldn't be any problem...
      --> huh? is that true?
    */
{
    return embed_graph[r].link[0] == prev ?
        embed_graph[r].link[1] : embed_graph[r].link[0];
}


void
embedg_VES_walk_bicomp (t_ver_edge *embed_graph, int n, int v, int vin)
    /*
      walk the external face of the bicomp starting
      at VIRTUAL vertex v entered via vin

      this of course assumes that the "thing" rooted at
      v is a bicomponent -- depending where we are at in the
      tester this is not necessarily the case
      -- I comment upon this in merge_bicomps.c:
               embedg_VES_merge_pertinent_bicomps
    */
{
    int        start, startin, s, sin;

    ASSERT(embedg_VES_is_virtual_vertex(n, v));

    embedg_VES_print_virtual_vertex(embed_graph, n, v);

    s = NIL;
    start = v;
    startin = vin;
    while (s != v)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n, start, startin,
                                             FALSE, 0, &s, &sin);
        if (embedg_VES_is_virtual_vertex(n, s))
        {
            embedg_VES_print_virtual_vertex(embed_graph, n, s);
        }
        else
        {
            embedg_VES_print_vertex(n, s);
        }
        start = s;
        startin = sin;
    }
    fprintf(stdout, "\n");
}

void
embedg_VES_print_adj_list (t_ver_edge *embed_graph, int n, int r,
	boolean consistent)
    /*
      print r's adjacency list - r can be a vertex or edge

      the boolean <consistent> if true assumes that
      the list is consistent (will determine the way we traverse the list)

      a priori we should get the same result either way
    */
{
    if (consistent)
    {
        int        next;

        embedg_VES_print_any_rec(embed_graph, n, r);

        next = embed_graph[r].link[0];
        while (next != r)
        {
            embedg_VES_print_any_rec(embed_graph, n, next);
            next = embed_graph[next].link[0];
        }
    }
    else
    {
        int          prev, cur, next;

        embedg_VES_print_any_rec(embed_graph, n, r);

        prev = r;
        cur = embed_graph[r].link[0];

        while (cur != r)
        {
            embedg_VES_print_any_rec(embed_graph, n, cur);
            next = embedg_VES_get_next_in_dlcl(embed_graph, n,
                                                          cur, prev);
            prev = cur;
            cur = next;
        }
    }
}

boolean
embedg_VES_is_adj_list_consistent (t_ver_edge *embed_graph, int n, int r)
    /*
      checks that r's adjacency list is consistent:
      ie, that either traversing it using link[0] always
      or traversing it using embedg_VES_get_next_in_dlcl
      gives the SAME result
    */
{
    int          *list_link, *list_n_dldl, il, id, i;

    list_link = (int *) mem_malloc(sizeof(int) * 2 * n);
    list_n_dldl = (int *) mem_malloc(sizeof(int) * 2 * n);
    /*
      must allocate 2*n space: I could have TE and SCE with same neighbour
      (or BE and SCE as well)
    */
    il = id = -1;

    /*
      traversing the list via link[0]
    */
    {
        int        next;

        list_link[++il] = r;

        next = embed_graph[r].link[0];
        while (next != r)
        {
            list_link[++il] = next;
            next = embed_graph[next].link[0];
        }
    }

    /*
       traversing the list using embedg_VES_get_next_in_dlcl
    */
    {
        int          prev, cur, next;

        list_n_dldl[++id] = r;
        prev = r;
        cur = embed_graph[r].link[0];

        while (cur != r)
        {
            list_n_dldl[++id] = cur;
            next = embedg_VES_get_next_in_dlcl(embed_graph, n,
                                                          cur, prev);
            prev = cur;
            cur = next;
        }
    }

    if (il != id)
    {
        mem_free(list_link);
        mem_free(list_n_dldl);
        return FALSE;
    }

    for (i = 0; i <= il; i++)
    {
        if (list_link[i] != list_n_dldl[i])
        {
            mem_free(list_link);
            mem_free(list_n_dldl);
            return FALSE;
        }
    }

    mem_free(list_link);
    mem_free(list_n_dldl);
    return TRUE;
}


boolean
embedg_VES_are_adj_lists_consistent (t_ver_edge *embed_graph, int n)
    /*
      checks that the adjacency list of each vertex is consistent
      in the manner of embedg_VES_is_adj_list_consistent
    */
{
    int          i;

    /*
      it is enough to visit the vertices and virtual vertices only
      (I don't think it is enough to do the vertices only --??)
    */
    for (i = 0; i < 2*n; i++)
        if (!embedg_VES_is_adj_list_consistent(embed_graph, n, i))
            return FALSE;

    return TRUE;
}



void
embedg_VES_remove_edge (t_ver_edge *embed_graph, int n, int e)
    /*
      remove edge e from the embedding
    */
{
    int          r1, r2, r1out, r2in, twin;

    ASSERT(embedg_VES_is_edge(n, e));

    IF_DEB_SCE(
               fprintf(stdout, "removing an SCE, enter\n");
               embedg_VES_print_edge(embed_graph, n, e);
               )

    r1 = embed_graph[e].link[0];
    r2 = embed_graph[e].link[1];

    /*
      disable e and link r1 and r2 together:
      we had r1 -> e -> r2
    */
    embed_graph[e].link[0] = embed_graph[e].link[1] = e;

    r1out = embed_graph[r1].link[0] == e ? 0 : 1;
    r2in = embed_graph[r2].link[0] == e ? 0 : 1;

    if (r1 == r2)
        /*
          this I think should never happen, but one never knows...
        */
    {
        embed_graph[r1].link[0] = embed_graph[r1].link[1] = r1;
    }
    else
    {
        embed_graph[r1].link[r1out] = r2;
        embed_graph[r2].link[r2in] = r1;
    }

    ASSERT(embedg_VES_is_adj_list_consistent(embed_graph, n, r1));

    /*
      now we must do a similar thing for the twin
      (which must get reomved as well)
    */
    twin = embedg_VES_get_twin_edge(embed_graph, n, e);

    IF_DEB_SCE(
               fprintf(stdout, "removing an SCE, the twin\n");
               embedg_VES_print_edge(embed_graph, n, twin);
               )

    r1 = embed_graph[twin].link[0];
    r2 = embed_graph[twin].link[1];

    embed_graph[twin].link[0] = embed_graph[twin].link[1] = twin;

    r1out = embed_graph[r1].link[0] == twin ? 0 : 1;
    r2in = embed_graph[r2].link[0] == twin ? 0 : 1;

    if (r1 == r2)
    {
        embed_graph[r1].link[0] = embed_graph[r1].link[1] = r1;
    }
    else
    {
        embed_graph[r1].link[r1out] = r2;
        embed_graph[r2].link[r2in] = r1;
    }

    ASSERT(embedg_VES_is_adj_list_consistent(embed_graph, n, r1));
}


void
embedg_VES_set_orientation (t_ver_edge *embed_graph, int n, int *ver_orient)
    /*
      using the vertices' orientation as given in ver_orient
      we set the orientation for each edge in the adjacency list
      for each vertex

      to do this we use the field sign which is NOT needed
      anymore by the tester since by the time we call this
      function we would have finished with that bit (the tester)

      sign is only set when merging bicomps
      - even though we'll perform another walkdown when
      recovering an obstruction (if any) no bicomp merging will occur,
      so we are safe
    */
{
    int          v;

    for (v = 0; v < n; v++)
    {
        int      o, e;

        o = ver_orient[v];
        embed_graph[v].sign = o;

        e = embed_graph[v].link[0];

        while (e != v)
            /*
              just as a note: note the way I get the next in the list
              here (as opposed to using
              embedg_VES_get_next_in_dlcl):
              this is because I implicitely assume that
              the adjacency lists are consistent

              Also note that edges can be SCE, it doesn't really matter
              anyway (they may not have been removed yet
              -- see the way we recover the obstruction:
              embedg_mark_obstruction)
            */
        {
            embed_graph[e].sign = o;
            e = embed_graph[e].link[0];
        }
    }
}


/*
 *  dlcl_misc.c
 */

/*
  What:
  *****

  Implementing:

  Housekeeping for a simple doubly linked circular list:
  this is a data structure ONLY used WITHIN
  the planarity tester and obstruction isolator and is not to be
  confused with the VES structure mentionned elsewhere.

  The VES structure is an array, while the dlcl one is a list of
  pointers.

  The  dlcl is especially useful as it allows for the storage
  of an ordered list.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */

/* aproto: beginstatic -- don't touch this!! */
static void embedg_dlcl_rec_free (t_dlcl *);
static void embedg_dlcl_rec_insert_right (t_dlcl *, t_dlcl *);
static void embedg_dlcl_rec_insert_left (t_dlcl *, t_dlcl *);
static void embedg_dlcl_rec_retrieve (t_dlcl *);
static void embedg_dlcl_rec_delete (t_dlcl *);
static boolean embedg_dlcl_is_singleton (t_dlcl *);
/* aproto: endstatic -- don't touch this!! */


#ifndef PLANAR_IN_MAGMA
#endif


t_dlcl *
embedg_dlcl_rec_new (int info)
    /*
      create a new record with info <info> in the global array
      to insert in the list
    */
{
    t_dlcl    *r;

    r = (t_dlcl *) mem_malloc(sizeof(t_dlcl));
    r->info = info;
    r->in_adjl = r->twin_in_adjl = NIL;
    r->mult = 1;
    r->right = r;
    r->left = r;
    return r;
}

static void
embedg_dlcl_rec_free (t_dlcl *r)
    /*
      free
    */
{
    mem_free(r);
}

void
embedg_dlcl_rec_print (t_dlcl *r)
{
    fprintf(stdout,"%d ", r->info);
}

void
embedg_dlcl_print (t_dlcl *l)
{
    t_dlcl    *p = l;

    if (!embedg_dlcl_is_empty(p))
    {
        embedg_dlcl_rec_print(p);
        p = embedg_dlcl_list_next(p);
        while (p != l)
        {
            embedg_dlcl_rec_print(p);
            p = embedg_dlcl_list_next(p);
        }
    }
    fprintf(stdout,"\n");
}


static void
embedg_dlcl_rec_insert_right (t_dlcl *l, t_dlcl *r)
{
    t_dlcl    *tmp_r, *tmp_l;

    tmp_r = l->right;
    tmp_l = tmp_r->left;

    l->right = r;
    r->right = tmp_r;

    r->left = tmp_l;
    tmp_r->left = r;
}


static void
embedg_dlcl_rec_insert_left (t_dlcl *l, t_dlcl *r)
{
    t_dlcl    *tmp_r, *tmp_l;

    tmp_l = l->left;
    tmp_r = tmp_l->right;

    l->left = r;
    r->left = tmp_l;

    r->right = tmp_r;
    tmp_l->right = r;
}

t_dlcl *
embedg_dlcl_rec_append (t_dlcl *l, t_dlcl *r)
{
    if (embedg_dlcl_is_empty(l))
        return r;

    embedg_dlcl_rec_insert_left(l, r);
    return l;
}

t_dlcl *
embedg_dlcl_rec_prepend (t_dlcl *l, t_dlcl *r)
{
    if (embedg_dlcl_is_empty(l))
        return r;

    embedg_dlcl_rec_insert_left(l, r);
    return r;
}

t_dlcl *
embedg_dlcl_cat (t_dlcl *l, t_dlcl *m)
    /*
      concatenate m to the RIGHT of the end of l
      WITHOUT copying m
    */
{
    t_dlcl    *h1, *h2, *e1, *e2;

    if (embedg_dlcl_is_empty(l))
        return m;
    if (embedg_dlcl_is_empty(m))
        return l;

    h1 = l;
    e1 = l->left;
    h2 = m;
    e2 = m->left;

    e1->right = h2;
    h2->left = e1;
    e2->right = h1;
    h1->left = e2;

    return l;
}

t_dlcl *
embedg_dlcl_find (t_dlcl *l, int info)
{
    t_dlcl    *p = l;

    if (!embedg_dlcl_is_empty(p))
    {
        if (p->info == info)
        {
            return p;
        }
        p = embedg_dlcl_list_next(p);
        while (p != l)
        {
            if (p->info == info)
            {
                return p;
            }
            p = embedg_dlcl_list_next(p);
        }
    }
    return NP;
}

t_dlcl *
embedg_dlcl_find_with_NIL_twin_in_adjl (t_dlcl *l, int info)
{
    t_dlcl    *p = l;

    if (!embedg_dlcl_is_empty(p))
    {
        if (p->info == info && p->twin_in_adjl == NIL)
        {
            return p;
        }
        p = embedg_dlcl_list_next(p);
        while (p != l)
        {
            if (p->info == info && p->twin_in_adjl == NIL)
            {
                return p;
            }
            p = embedg_dlcl_list_next(p);
        }
    }
    return NP;
}



static void
embedg_dlcl_rec_retrieve (t_dlcl *r)
{
    t_dlcl    *right, *left;

    right = r->right;
    left = r->left;

    left->right = right;
    right->left = left;

    r->right = r;
    r->left = r;
}

static void
embedg_dlcl_rec_delete (t_dlcl *r)
{
    embedg_dlcl_rec_retrieve(r);
    embedg_dlcl_rec_free(r);
}


t_dlcl *
embedg_dlcl_delete_first (t_dlcl *l)
    /*
      prune the list from the head:
      - set new head to right of old head
      - delete old head
    */
{
    t_dlcl    *new_head;

    ASSERT(!embedg_dlcl_is_empty(l));
    if (embedg_dlcl_is_singleton(l))
    {
        new_head = NP;
    }
    else
    {
        new_head = l->right;
    }
    embedg_dlcl_rec_delete(l);
    return new_head;
}


t_dlcl *
embedg_dlcl_delete_rec (t_dlcl *l, t_dlcl *r)
    /*
      delete r from l;
      if r == l, set new head to right of old head
    */
{
    if (r == l)
    {
        return embedg_dlcl_delete_first(l);
    }
    embedg_dlcl_rec_delete(r);
    return l;
}


boolean
embedg_dlcl_is_empty (t_dlcl *l)
{
    return (l == NP) ? TRUE : FALSE;
}


static boolean
embedg_dlcl_is_singleton (t_dlcl *l)
{
    return (l->right == l) ? TRUE : FALSE;
    /*
      same as l->left == l
    */
}

t_dlcl *
embedg_dlcl_list_next (t_dlcl *l)
    /*
      this assumes no choice in the direction of the walking
      (always to the right)
      -- good enough when deleting for example or when
      the direction of the walking does not matter
    */
{
    return l->right;
}


t_dlcl *
embedg_dlcl_list_prev (t_dlcl *l)
    /*
      this assumes no choice in the direction of the walking
      (always to the right)
    */
{
    return l->left;
}

t_dlcl *
embedg_dlcl_list_last (t_dlcl *l)
{
    return embedg_dlcl_list_prev(l);
}



void
embedg_dlcl_delete (t_dlcl *l)
{
    if (!embedg_dlcl_is_empty(l))
    {
        while (!embedg_dlcl_is_singleton(l))
        {
            t_dlcl    *next;

            next = embedg_dlcl_list_next(l);
            embedg_dlcl_rec_delete(next);
        }
        embedg_dlcl_rec_delete(l);
    }
}

t_dlcl *
embedg_dlcl_copy (t_dlcl *l)
{
    t_dlcl    *p, *c;

    if (embedg_dlcl_is_empty(l))
        return NP;

    c = embedg_dlcl_rec_new(l->info);

    p = embedg_dlcl_list_next(l);
    while (p != l)
    {
        t_dlcl     *temp;

        temp = embedg_dlcl_rec_new(p->info);
        temp->in_adjl = p->in_adjl;
        temp->twin_in_adjl = p->twin_in_adjl;
        temp->mult = p->mult;
        c = embedg_dlcl_rec_append(c, temp);
        p = embedg_dlcl_list_next(p);
    }
    return c;
}


int
embedg_dlcl_length (t_dlcl *l)
{
    t_dlcl    *p;
    int       n;

    if (embedg_dlcl_is_empty(l))
        return 0;

    p = embedg_dlcl_list_next(l);
    n = 1;
    while (p != l)
    {
        n++;
        p = embedg_dlcl_list_next(p);
    }
    return n;
}
/*
 *  planar_by_edge_addition.c
 */

/*
  What:
  *****

  Implementing:

  The top level for the planarity tester.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}
#define IF_DEB_EDGES(x) {}
#define IF_CPU(x) {}


/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif


boolean
sparseg_adjl_is_planar (
    t_ver_sparse_rep *V,
    int n,
    t_adjl_sparse_rep *A,        /* input sparse graph */
    int *nbr_c,        /* size of the graph, #components
                                    */
    t_dlcl ***dfs_tree,      /* a sparse graph rep. for the dfs tree
                                      -- vertices are as DFIs
                                      -- and children are ordered wrt
                                         lowpoint value
                                   */
    t_dlcl ***back_edges,    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      (vertices are given as DFIs)
                                   */
    t_dlcl ***mult_edges,    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      (vertices are given as DFIs)
                                   */
    t_ver_edge **embed_graph,    /* output graph embedding -- more on that
                                      later
                                   */
    int *edge_pos,        /* pos. in embed_graph for addition
                                      of the next edge */
    int *vr,
    int *wr         /* if graph is non planar, return
                                      the unembedded edge
                                      (where wr descendant of vr)
                                   */
)
    /*
      as the name indicates: is the graph planar?
    */
{
    int          v;

    IF_CPU(
    float      sttime; float time_to_now;
    )


    *embed_graph =
        embedg_planar_alg_init(V, n, A, nbr_c,
                               edge_pos, dfs_tree, back_edges, mult_edges);
    IF_CPU(
    sttime = time_current_user();
          )

    for (v = n - 1; v >= 0; v--)
        /*
          visit all vertices in descending DFI order
        */
    {
        t_dlcl     *be_l, *te_l, *p;

        IF_DEB(
               fprintf(stdout, "top level, vertex   %d\n", v);
               )

        /*
          find all the back edges [w, v] where w is a descendant of v
          and perform a walkup from w to v
          (ie determine which bicomps are pertinent)
        */
        be_l = (*back_edges)[v];
        p = be_l;

        if (!embedg_dlcl_is_empty(p))
        {
            int       w;

            w = p->info;
            IF_DEB(
                   fprintf(stdout, "top level, before walkup for w %d\n", w);
                   )
            embedg_walkup(*embed_graph, n, v, p);

            p = embedg_dlcl_list_next(p);
            while (p != be_l)
            {
                w = p->info;
                IF_DEB(
                       fprintf(stdout, "top level, before walkup for w %d\n", w);
                       )
                embedg_walkup(*embed_graph, n, v, p);

                p = embedg_dlcl_list_next(p);
            }
        }

        /*
          perform a walkdown for each tree edge [v, c], c a descendant of v
          (ie attempt to embed all back edges on the pertinent bicomps)
        */
        te_l = (*dfs_tree)[v];
        p = te_l;

        if (!embedg_dlcl_is_empty(p))
        {
            int             c, vv;
            t_merge_queue   q;

            c = p->info;
            vv = c + n;
            IF_DEB(
                   fprintf(stdout, "top level, before walkdown for c %d\n", c);
                   )
            q = embedg_walkdown(*embed_graph, n, edge_pos, vv);

            IF_DEB(
                   fprintf(stdout, "top level, after walkdown for c %d, state of edges'sign\n", c);
                   embedg_VES_print_flipped_edges(*embed_graph,
                                                       n, *edge_pos);
                   )

            /*
              temp only
            */
            embedg_merge_queue_delete(q);
            p = embedg_dlcl_list_next(p);
            while (p != te_l)
            {
                c = p->info;
                vv = c + n;
                IF_DEB(
                       fprintf(stdout, "top level, before walkdown for c %d\n", c);
                       )
                q = embedg_walkdown(*embed_graph, n, edge_pos, vv);

                IF_DEB(
                       fprintf(stdout, "top level, after walkdown for c %d, state of edges'sign\n", c);
                       embedg_VES_print_flipped_edges(*embed_graph,
                                                           n, *edge_pos);
                       )

                /*
                  temp only
                */
                embedg_merge_queue_delete(q);

                p = embedg_dlcl_list_next(p);
            }
        }


        /*
          check that each back edge [w, v], w a descendant of v,
          has been embedded
        */
        be_l = (*back_edges)[v];
        p = be_l;

        if (!embedg_dlcl_is_empty(p))
        {
            int       w;

            w = p->info;
            IF_DEB(
                   fprintf(stdout, "top level, before checking embedding for w %d\n",
                           w);
                   )
            if ((*embed_graph)[w].adjacent_to == v)
                /*
                  this edge hasn't been embedded:
                  the graph is non-planar
                */
            {
                /*
                  before returning we really want to ensure that
                  the vertices' adjacency lists are consistent
                */
                ASSERT(embedg_VES_are_adj_lists_consistent(
                                                       *embed_graph, n));

                IF_CPU(
                       fprintf(stdout, "CPU for tester only %f\n",
                               (time_current_user() - sttime));
                       )

                *vr = v;
                *wr = w;
                return FALSE;
            }

            p = embedg_dlcl_list_next(p);
            while (p != be_l)
            {
                w = p->info;
                IF_DEB(
                       fprintf(stdout, "top level, before checking embedding for w %d\n",
                               w);
                       )
                if ((*embed_graph)[w].adjacent_to == v)
                {
                    /*
                      before returning we really want to ensure that
                      the vertices' adjacency lists are consistent
                    */
                    ASSERT(embedg_VES_are_adj_lists_consistent(
                                                       *embed_graph, n));

                    IF_CPU(
                           fprintf(stdout, "CPU for tester only %f\n",
                                   (time_current_user() - sttime));
                           )

                    *vr = v;
                    *wr = w;
                    return FALSE;
                }

                p = embedg_dlcl_list_next(p);
            }
        }
    }
    IF_DEB_EDGES(
                 fprintf(stdout, "top level, total number of edges in embedding %d\n",
                         *edge_pos - 2 * n + 1);
                 )


    /*
      before returning we really want to ensure that
      the vertices' adjacency lists are consistent
    */
    ASSERT(embedg_VES_are_adj_lists_consistent(*embed_graph, n));

    IF_CPU(
           fprintf(stdout, "CPU for tester only %f\n",
                   (time_current_user() - sttime));
           )

    return TRUE;
}



/*
 *  walkup.c
 */

/*
  What:
  *****

  Implementing:

  The walkup routine within the VES structure:

  Walking up from w where [w, v^c] is a (directed)
  back edge to be embeeding later.
  Along the way collect all the pertinent bicomps that
  will need to be merged before embedding the back edges
  to v^c.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif


void
embedg_walkup (t_ver_edge *embed_graph, int n, int v, t_dlcl *p)
    /*
      walkup from w = p->info to v: [w, v] is a back edge where w is a DFS
      descendant of v
    */
{
    int          w, x, xin, y, yin;

    w = p->info;

    IF_DEB(
           fprintf(stdout, "walkup from %d to %d, enter\n", w, v);
           )

    embed_graph[w].adjacent_to = v;
    /*
      dirty trick to record some information about the BE [w, v]
      which will be useful at the time of creation and insertion of
      this BE: this happens in the walkdown procedure

      note that what I am doing here is safe: [w].in_adjl,
      [w].twin_in_adjl, [w].mult had no use so far since w is a vertex
      (and not an edge...)
    */
    embed_graph[w].in_adjl = p->in_adjl;
    embed_graph[w].twin_in_adjl = p->twin_in_adjl;
    embed_graph[w].mult = p->mult;

    /*
      set up the traversal contexts for w: one in each direction
    */
    x = w;
    xin = 1;
    y = w;
    yin = 0;

    while (x != v)
    {
        int          vz, z, c;

        IF_DEB(
               fprintf(stdout, "walkup, x %d and y %d\n", x, y);
               )

        if (embed_graph[x].visited == v
            || embed_graph[y].visited == v)
        {
            IF_DEB(
                   if (embed_graph[x].visited == v)
                       fprintf(stdout, "walkup, x visited\n");
                   else
                       fprintf(stdout, "walkup, y visited\n");
                   )
            break;
        }

        /*
          set x and y as visited!
        */
        embed_graph[x].visited = embed_graph[y].visited = v;

        vz = embedg_VES_is_virtual_vertex(n, x) ? x : NIL;
        vz = embedg_VES_is_virtual_vertex(n, y) ? y : vz;

        if (vz != NIL)
            /*
              that is, x (or y) is a virtual vertex
              -- in other words, we are set to find the root of the bicomp
              containing w, or of the bicomp r^c such that w is in the tree
              rooted by c

              consequently, by definition, vz is PERTINENT
            */
        {
            c = vz - n;
            z = embed_graph[c].DFS_parent;

            IF_DEB(
                   fprintf(stdout, "walkup, vz is virtual, %d^%d\n",
                           z, c);
                   )

            if (z != v)
                /*
                  determine if vz externally or internally active
                */
            {
                if (embed_graph[c].lowpoint < v)
                    /*
                      vz is externally active: APPEND to the list
                      of pertinent bicomps
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkup, vz is ext. active\n");
                           )

                    embed_graph[z].pertinent_bicomp_list =
                        embedg_dlcl_rec_append(
                                embed_graph[z].pertinent_bicomp_list,
                                embedg_dlcl_rec_new(vz));
                }
                else
                    /*
                      vz is internally active: PREPEND to the list
                      of pertinent bicomps
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkup, vz is pertinent\n");
                           )

                    embed_graph[z].pertinent_bicomp_list =
                        embedg_dlcl_rec_prepend(
                                embed_graph[z].pertinent_bicomp_list,
                                embedg_dlcl_rec_new(vz));
                }
            }

            /*
              continue the walkup, look if there are any other
              pertinent bicomps
              -- here "jump" to the next bicomp "up"
            */
            x = z;
            xin = 1;
            y = z;
            yin = 0;
        }
        else
            /*
              continue the traversal of the bicomp until one finds
              its (virtual) root
            */
        {
            embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                                 x, xin, FALSE, 0, &x, &xin);
            embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                                 y, yin, FALSE, 0, &y, &yin);
        }
    }
}

/*
 *  walkdown.c
 */

/*
  What:
  *****

  Implementing:

  The walkdown routine within the VES structure:

  walking down a bicomp rooted by a virtual vertex v^c
  and attempting to embed the back edges.
  This cannot be done if the walk has to stop due to the
  presence of externally active vertices on both
  the clockwise and the anticlockwise side of the bicomp.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_EMBED(x)    {}
#define IF_DEB_BE(x) {}
#define IF_DEB_SCE(x) {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif



t_merge_queue
embedg_walkdown (t_ver_edge *embed_graph, int n, int *edge_pos, int vv)
    /*
      walkdown from the virtual vertex:
      embed any back edges incident to vv if any
      and merge the encountered bicomps while walking down
      (very informative isn't it? :))

      ... and return the merge queue: will be useful when
      isolating the Kuratowski subgraphs
    */
{
    t_merge_queue    q;
    int              v, c, vvout;

    ASSERT(embedg_VES_is_virtual_vertex(n, vv));

    /*
      find v and c such that v^c = vv
    */
    c = vv - n;
    v = embed_graph[c].DFS_parent;

    IF_DEB(
           fprintf(stdout, "walkdown from %d^%d, enter\n", v, c);
           )

    IF_DEB_EMBED(
                 fprintf(stdout, "walkdown, embedding at start\n");
                 embedg_VES_print_bigcomps(embed_graph, n);
                 )

    /*
      create an empty merge queue
    */
    q = embedg_merge_queue_new(n);

    for (vvout = 0; vvout <= 1; vvout++)
        /*
          chose a direction for the walk, but walk in both
          directions unless a stopping vertex is encountered
          and other conditions are satisfied (see below)
        */
    {
        int    w, win;

        embedg_VES_get_succ_on_ext_face(embed_graph, n, vv, vvout ^ 1,
                                             FALSE, 0, &w, &win);

        IF_DEB(
               fprintf(stdout, "walkdown, successor (outside while loop) from %d^%d:%d is %d:%d\n",
                       embed_graph[vv-n].DFS_parent, vv-n, vvout ^ 1,
                       w, win);
               )

        while (w != vv)
            /*
              is there no danger we walk the whole way back to vv
              and that all the vertices along the walk are inactive?

              answer: no, because of the short-cut edges.

              Short-cut edges are precisely inserted to remove the inactive
              vertices from the external face (ie they are "pushed"
              to the internal face of the bicomp)
            */
        {
            if (embed_graph[w].adjacent_to == v)
                /*
                  ie there is a (directed) back edge [w, v]
                  (would have been set in the previous walkup routine):
                  embed this edge, but before that, merge all the bicomps
                  previouslsy collected
                */
            {
                IF_DEB(
                       fprintf(stdout, "walkdown, embed BE (%d^%d:%d, %d:%d)\n",
                               embed_graph[vv-n].DFS_parent, vv - n, vvout,
                               w, win);
                       fprintf(stdout, "walkdown, queue before pulling elts\n");
                       embedg_merge_queue_print(q);
                       )

                while (!embedg_merge_queue_empty(q))
                {
                    int     u, uin, vu, vuout;

                    embedg_merge_queue_get(&q, &u, &uin, &vu, &vuout);

                    IF_DEB(
                           fprintf(stdout, "walkdown, pull from queue (%d:%d, %d^%d:%d)\n",
                                   u, uin,
                                   embed_graph[vu-n].DFS_parent, vu-n,
                                   vuout);
                       )

                    embedg_VES_merge_pertinent_bicomps(
                                                        embed_graph, n,
                                                        vu, vuout, u, uin);
                }
                IF_DEB_BE(
                          fprintf(stdout, "walkdown, before embed BE [%d^%d:%d, %d:%d]\n",
                                  embed_graph[vv-n].DFS_parent, vv - n,
                                  vvout, w, win);
                          embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    TRUE);
                          fprintf(stdout, "\n");
                          embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    FALSE);
                          )

                embedg_VES_embed_edge(embed_graph, n, edge_pos,
                                                 BE, vv, vvout, w, win);

                IF_DEB_BE(
                          fprintf(stdout, "walkdown, after embed BE [%d^%d:%d, %d:%d]\n",
                                  embed_graph[vv-n].DFS_parent, vv - n,
                                  vvout, w, win);
                          embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    TRUE);
                          fprintf(stdout, "\n");
                          embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    FALSE);
                          )
                IF_DEB_EMBED(
                       fprintf(stdout, "walkdown, embedding after bicomp merge & back edge embedding\n");
                       embedg_VES_print_bigcomps(embed_graph, n);
                       )

                /*
                  clear the adjacent_to flag
                */
                embed_graph[w].adjacent_to = n;  /* "invalid" value */
            }

            if (!embedg_dlcl_is_empty(embed_graph[w].pertinent_bicomp_list))
                /*
                  each pertinent child bicomp of w
                  (pertinent: contains active (ie more back edges to embed)
                  elts)
                  must be traversed
                  and pushed onto the queue for later bicomp merging
                */
            {
                int           vw, vwout, x, xin, y, yin, s, sin;

                IF_DEB(
                       fprintf(stdout, "walkdown, pertinent list for %d\n",
                               w);
                       embedg_dlcl_print(embed_graph[w].pertinent_bicomp_list);
                       )

                /*
                  get the first child in the pertinent list
                  (see how the list is built in embedg_walkup)

                  the child will eventually be removed from that list
                  when merging the bicomps, and surely
                  this bicomp (rooted at vw) will be merged (later)
                  because it is active and hence pushed on
                  the merge queue
                */

                /*
                  we can start by pushing the vertex (w, win) on
                  the merge queue
                */
                embedg_merge_queue_append_vertex(&q, embed_graph, n, w, win);

                IF_DEB(
                       fprintf(stdout, "walkdown, push 1rst 2-tuple on queue\n");
                       embedg_merge_queue_print(q);
                       )

                /*
                  get the first child in the pertinent list
                */
                vw = (embed_graph[w].pertinent_bicomp_list)->info;

                IF_DEB(
                       fprintf(stdout, "walkdown, get pertinent %d^%d\n",
                               embed_graph[vw - n].DFS_parent, vw - n);
                       )

                /*
                  start two walks starting at vw
                */
                embedg_VES_get_succ_active_on_ext_face(embed_graph, n,
                                                     v , vw, 1,
                                                     FALSE, 0, &x, &xin);
                embedg_VES_get_succ_active_on_ext_face(embed_graph, n,
                                                     v, vw, 0,
                                                     FALSE, 0, &y, &yin);

                /*
                  because of the trick of inserting short-cut edges
                  at previous stages, neighbours of vw are guaranteed
                  to be active

                  (however I'll use the more general
                  embedg_VES_get_succ_active_on_ext_face
                  instead of the restrictive
                  embedg_VES_get_succ_on_ext_face
                  because  the walkdown may be used later to isolate
                  Kuratowski minors, in a situation where SCEs could have
                  been removed and thus where the successor on the
                  external face will no longer be guaranteed to be active)
                  (* actually I have decided to remove the SCE at the
                  very last moment hence the above pb
                  does not occur in the present implementation)


                  it only remains to chose the next vertex where from
                  to continue the walk; the choice is made in that order:
                  - an internally active vertex
                    (incident to v via a backedge but whose lowpoint
                    is NO less than v)
                  - a (externally active) pertinent vertex
                    (incident to v via a backedge but whose lowpoint
                    is less than v: ie which is also externally active)
                  - as a last resort, a non-pertinent externally vertex,
                    which is then a stopping vertex
                */
                IF_DEB(
                       fprintf(stdout, "walkdown, x and y: %d, %d\n", x, y);
                       )

                if (embedg_VES_is_ver_int_active(embed_graph, n,
                                                            v, x))
                    /*
                      x is internally active
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkdown, x is int. active\n");
                           )

                    s = x;
                    sin = xin;
                }
                else if (embedg_VES_is_ver_int_active(
                                                            embed_graph, n,
                                                            v, y))
                    /*
                      y is internally active
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkdown, y is int. active\n");
                           )

                    s = y;
                    sin = yin;
                }
                else if (embedg_VES_is_ver_pertinent(
                                                            embed_graph, n,
                                                            v, x))
                    /*
                      x is pertinent
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkdown, x is pertinent\n");
                           )

                    s = x;
                    sin = xin;
                }
                else
                    /*
                      tough luck: y may be externally active
                    */
                {
                    IF_DEB(
                           fprintf(stdout, "walkdown, tough luck\n");
                           )

                    s = y;
                    sin = yin;
                }

                IF_DEB(
                       fprintf(stdout, "walkdown, succ. on pertinent bicomp is %d:%d\n", s, sin);
                       )

                /*
                  set vwout to respect consistency of traversal
                */
                vwout = s == x ? 0 : 1;

                /*
                  now that we know vwout we can push (vw, vwout)
                  on the merge queue, thus completing the 4-tuple
                  (w, win, vw, vwout) describing a bicomp merge
                  to occur at a later stage
                */
                embedg_merge_queue_append_virtual_vertex(&q, embed_graph, n,
                                                         vw, vwout);

                IF_DEB(
                       fprintf(stdout, "walkdown, push on queue (%d:%d, %d^%d:%d)\n",
                               w, win, embed_graph[vw-n].DFS_parent, vw - n,
                               vwout);
                       embedg_merge_queue_print(q);
                       )

                /*
                  we continue the walk
                */
                w = s;
                win = sin;
            }
            /*
              at this point, w is either inactive or externally active
              (w can't be pertinent: its pertinent bicomp list is empty,
              and the back edge [w, v], if any, has already been embedded)
            */
            else if (embedg_VES_is_ver_inactive(embed_graph, n,
                                                           v, w))
                /*
                  w is inactive: continue with the walk on the external face
                  and, insert a short cut edge so that w is removed
                  from the external face
                */
            {
                int   s, sin;

                IF_DEB(
                       fprintf(stdout, "walkdown, %d has no pertinent bicomps and is inactive\n", w);
                       )

                embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                                     w, win,
                                                     FALSE, 0, &s, &sin);

                IF_DEB(
                       fprintf(stdout, "walkdown, successor from %d:%d is %d:%d\n",
                               w, win, s, sin);
                       )

                /*
                  s is the successor of w: we embed a short circuit edge
                  [vv, s] if
                  - the bicomp is externally active (to ensure that
                    at a later stage this new face gets bisected:
                    so that we don't end up with a face of degree 2
                    (parallel edges))
                  - if [s, vv] is not a back edge

                  CONSEQUENTLY, adding SCE edges
                  + does not destroy the planarity of the graph
                  + ensures that each face has degree > 2 so that
                    |E| <= 3 * |V| - 6 remains valid at all times
                  + that the space allocated to the edges in embed_graph
                    (via MAXDE(n)) is sufficient

                  NOTE:
                  the above still allows to embed a short-cut edge
                  as an edge parallel to a tree edge OR a back edge
                  (which then has been embedded previously
                  so that [w].adjacent has been cleared)

                  but again, since the degree of the face will be
                  > 2, that's ok

                  recall that c = vv - n
                */
                if (embed_graph[c].lowpoint < v
                    /*
                      bicomp rooted at vv is externally active
                    */
                    && embed_graph[s].adjacent_to != v)
                    /*
                      [s, vv] is not a back edge
                    */
                {
                    IF_DEB_SCE(
                           fprintf(stdout, "walkdown, before embed SCE [%d^%d:%d, %d:%d]\n",
                                   embed_graph[vv-n].DFS_parent, vv - n,
                                   vvout, s, sin);
                           embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    TRUE);
                           fprintf(stdout, "\n");
                           embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    FALSE);

                           )

                    embedg_VES_embed_edge(embed_graph,
                                                     n, edge_pos,
                                                     SCE, vv, vvout, s, sin);
                    /*
                      note also that the addition of short cut edges
                      does not change the fact that the graph is planar
                      (when it is, so we never run into the problem
                      of creating/adding too many edges to embed-graph)
                    */
                    IF_DEB_SCE(
                           fprintf(stdout, "walkdown, after embed SCE [%d^%d:%d, %d:%d]\n",
                                   embed_graph[vv-n].DFS_parent, vv - n,
                                   vvout, s, sin);
                           embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    TRUE);
                           fprintf(stdout, "\n");
                           embedg_VES_print_adj_list(
                                                    embed_graph, n, vv,
                                                    FALSE);

                           )
                    IF_DEB(
                           fprintf(stdout, "walkdown, embed SCE [%d^%d:%d, %d:%d]\n",
                                   embed_graph[vv-n].DFS_parent, vv - n,
                                   vvout, s, sin);
                           )

                }
                /*
                  continue the walk
                */
                w = s;
                win = sin;
            }
            else
                /*
                  w is non-pertinent and externally active:
                  it is a stopping vertex:
                  we stop here and see if we can walk in the other direction
                */
            {
                IF_DEB(
                       fprintf(stdout, "walkdown, %d is externally active\n", w);
                       )
                break;
            }
        }
        if (!embedg_merge_queue_empty(q))
            /*
              mumm.... don't understand this one... let's see:
              the queue constains pertinent bicomps collected during one of
              the traversal of the external face, so that once
              a stopping vertex has been encountered and the queue
              is not empty, this means that we will be unable
              to embed any remaining back edges:

              it is important to remember that when w is a stopping vertex
              there is no choice left, since we walk the pertinent
              bicomp in both directions at once, and always choose
              the "best" possible vertex
              (see the choice strategy: (a) internally active, (b) pertinent,
              (c) the rest)
            */
        {
            IF_DEB(
                   fprintf(stdout, "walkdown, merge queue is not empty\n");
                   )
            break;
        }
    }

    /*
      and return the merge queue
    */
    return q;
}




/*
 *  merge_queue_misc.c
 */

/*
  What:
  *****

  Implementing:

  The merge queue stores the pertinent bicomps waiting to
  be merged before a subsequent back edge embedding.
  See walkdown.c

  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif

t_merge_queue
embedg_merge_queue_new (int n)
    /*
      create a merge queue of 4 * (n-1) elts:
      we can only have at most n-1 virtual vertices,
      and for each of those we need to store 4 bits of info
    */
{
    t_merge_queue   q;

    q.start = q.end = 0;
    q.b = (int *) mem_malloc(sizeof(int) * 4 * (n - 1));

    return q;
}

void
embedg_merge_queue_delete (t_merge_queue q)
{
    mem_free(q.b);
}


boolean
embedg_merge_queue_empty (t_merge_queue q)
{
    return q.start == q.end ? TRUE : FALSE;
}

void
embedg_merge_queue_print (t_merge_queue q)
{
    int        i;

    for (i = q.start; i < q.end; i++)
    {
        fprintf(stdout, "%d:%d ", q.b[i], q.b[i+1]);
	++i;
    }
    fprintf(stdout, "\n");
}

void
embedg_merge_queue_append (t_merge_queue *q, t_ver_edge *embed_graph,
	int n, int v, int vin, int vv, int vvout)
    /*
      append the 4-tuple (v, vin, vv, vvout)
      where v is a vertex and vv is its virtual counterpart

      we don't do much here, most of the work is done
      when pulling a bicomp/4-tuple from the queue
    */
{
    /*
      is this really necessary? - YES!!!
    */
    ASSERT((*q).end < 4 * (n - 2));
    ASSERT(embedg_VES_is_vertex(n, v));
    ASSERT(embedg_VES_is_virtual_vertex(n, vv));
    ASSERT(embed_graph[vv - n].DFS_parent == v);

    (*q).b[(*q).end++] = v;
    (*q).b[(*q).end++] = vin;
    (*q).b[(*q).end++] = vv;
    (*q).b[(*q).end++] = vvout;
}

void
embedg_merge_queue_append_vertex (t_merge_queue *q, t_ver_edge *embed_graph,
	int n, int v, int vin)
    /*
      same as above but were we only append the 2-tuple (v, vin),
      appending the 2-tuple (vv, vvout) at a later stage
      (see embedg_merge_queue_append_virtual_vertex)
    */
{
    ASSERT((*q).end < 4 * (n - 2));
    ASSERT(embedg_VES_is_vertex(n, v));

    (*q).b[(*q).end++] = v;
    (*q).b[(*q).end++] = vin;

    IF_DEB(
           fprintf(stdout, "merge_queue_append_vertex, after, end is %d\n",
                   (*q).end);
           )
}

void
embedg_merge_queue_append_virtual_vertex (t_merge_queue *q,
	t_ver_edge *embed_graph, int n, int vv, int vvout)
    /*
      counterpart to embedg_merge_queue_append_vertex:
      here we append the 2-tuple (vv, vvout), vv = v^c,
      where the 2-tuple (v, vin) is already in the queue
      (see embedg_merge_queue_append_vertex)
    */
{
    ASSERT(!embedg_merge_queue_empty(*q));
    ASSERT(embedg_VES_is_virtual_vertex(n, vv));
    ASSERT(embed_graph[vv - n].DFS_parent == (*q).b[(*q).end - 2]);

    (*q).b[(*q).end++] = vv;
    (*q).b[(*q).end++] = vvout;

    IF_DEB(
           fprintf(stdout, "merge_queue_append_virtual_vertex, after, end is %d\n",
                   (*q).end);
           )
}

void
embedg_merge_queue_get (t_merge_queue *q, int *v, int *vin, int *vv, int *vvout)
    /*
      pulling out a 4-tuple from the beginning of the FIFO queue
    */
{
    ASSERT(!embedg_merge_queue_empty((*q)));

    *v = (*q).b[(*q).start++];
    *vin = (*q).b[(*q).start++];
    *vv = (*q).b[(*q).start++];
    *vvout = (*q).b[(*q).start++];
}

void
embedg_merge_queue_prune (t_merge_queue *q, int *v,
			  int *vin, int *vv, int *vvout)
    /*
      pulling out a 4-tuple from the end of the FIFO queue
    */
{
    ASSERT(!embedg_merge_queue_empty((*q)));

    *vvout = (*q).b[--((*q).end)];
    *vv = (*q).b[--((*q).end)];
    *vin = (*q).b[--((*q).end)];
    *v = (*q).b[--((*q).end)];
}

/*
 *  vertex_activity.c
 */

/*
  What:
  *****

  Implementing:

  Determining a vertex's activity. This takes place within
  the VES structure.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif




boolean
embedg_VES_is_ver_pertinent (t_ver_edge *embed_graph, int n, int v, int w)
    /*
      is w pertinent (wrt v)
      - the field adjacent_to = v: means there is a back edge [w, v]
      - or w has a non empty pertinent_bicomp_list
    */
{
    boolean       ans;

    ans = embed_graph[w].adjacent_to == v ? TRUE : FALSE;

    if (ans)
        return TRUE;
    else
        return embedg_dlcl_is_empty(embed_graph[w].pertinent_bicomp_list) ?
            FALSE : TRUE;
}

boolean
embedg_VES_is_ver_ext_active (t_ver_edge *embed_graph, int n, int v, int w)
    /*
      is w externally active (wrt v)
      this is the case when either w's least_ancestor < v
      or the first member of w's separated_DFS_child_list has lowpoint < v
      (the vertices in separated_DFS_child_list are ordered by lowpoint)

      why? because w's separated_DFS_child_list may be empty
      (due to prior bicomp merging say) and so its children are in effect
      inactive
    */
{
    boolean       ans;

    ans = embed_graph[w].least_ancestor < v ? TRUE : FALSE;

    if (ans)
        return TRUE;
    else
    {
        if (embedg_dlcl_is_empty(embed_graph[w].separated_DFS_child_list))
        {
            return FALSE;
        }
        else
        {
            int      c;

            c = (embed_graph[w].separated_DFS_child_list)->info;
            return embed_graph[c].lowpoint < v ? TRUE : FALSE;
        }
    }
}


boolean
embedg_VES_is_ver_int_active (t_ver_edge *embed_graph, int n, int v, int w)
    /*
      is w internally active (wrt v):
      this happens when w is pertinent but NOT externally active
    */
{
    return embedg_VES_is_ver_pertinent(embed_graph, n, v, w)
        && !embedg_VES_is_ver_ext_active(embed_graph, n, v, w);
}

boolean
embedg_VES_is_ver_inactive (t_ver_edge *embed_graph, int n, int v, int w)
    /*
      is w inactive (wrt v), that is w nor pertinent nor externally activ
    */
{
    return !embedg_VES_is_ver_pertinent(embed_graph, n, v, w)
        && !embedg_VES_is_ver_ext_active(embed_graph, n, v, w);
}

/*
 *  merge_bicomps.c
 */

/*
  What:
  *****

  Implementing:

  In the VES structure, merging two bicomponents.
  That is, merging the virtual vertex v^c with the
  actual vertex v while merging their respective
  adjacency lists.
  This must be done in a very specific manner so as to able to
  determine the subsequent internal/external faces.
  Also, great care must be taken so that the resulting
  adj. list for v is consistent (wrt to the direction
  of traversal).


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_ADJL(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */


void
embedg_VES_merge_simple_bicomps (t_ver_edge *embed_graph, int n, int vv,
	int vvout, int v, int vin)
    /*
      merge the bicomp rooted at vv (vv a virtual vertex) with
      its counterpart v so that the resulting adjacency list for v
      is consistent and is the union of the adjacency lists for vv and v

      we treat the case that the bicomp may be flipped (vvout == vin)
      here
    */
{
    int       c, edge, twin, root_edge, cur, prev;
    int       vout, vvin, e1, e2, e3, e4, e1out, e3out, e4in;

    /*
      find c such that [v^c, c] is the root edge of the bicomp
      rooted at vv = v^c
    */
    c = vv - n;
    ASSERT(embed_graph[c].DFS_parent == v);

    IF_DEB(
           fprintf(stdout, "merge_simple_bicomp, start: merge\n");
           embedg_VES_print_virtual_vertex(embed_graph, n, vv);
           fprintf(stdout, ":%d & ", vvout);
           embedg_VES_print_vertex(n, v);
           fprintf(stdout, ":%d\n", vin);
           )

    IF_DEB_ADJL(
           fprintf(stdout, "merge_simple_bicomp, adj. list for %d (before)\n", vv);
           embedg_VES_print_adj_list(embed_graph, n, vv,
                                                TRUE);
           fprintf(stdout, "\n");
           embedg_VES_print_adj_list(embed_graph, n, vv,
                                                FALSE);
           fprintf(stdout, "\n");

           fprintf(stdout, "merge_simple_bicomp, adj. list for %d (before)\n", v);
           embedg_VES_print_adj_list(embed_graph, n, v,
                                                TRUE);
           fprintf(stdout, "\n");
           embedg_VES_print_adj_list(embed_graph, n, v,
                                                FALSE);
           )
    /*
      find all edges incident to vv and (re)set all references
      to incidence to vv to incidence to v

      by the same token, find the root_edge [v^c, c]

      MOREVOVER, when vin == vvout, the bicomp (rooted by v^v = vv)
      will be flipped:
      we must invert the links of all the edges incident
      to vv so that their further union with v's adjacency list
      results in a consistent adjacency list for v!

      we do everything in one go
    */

    /*
      very careful here: a root edge must ALSO be a TE
      (because the same edge could have been added as a SCE)
    */

    root_edge = NIL;
    edge = embed_graph[vv].link[vvout];
    ASSERT(embedg_VES_is_edge(n, edge));
    if (embed_graph[edge].neighbour == c
        && embedg_VES_is_tree_edge(embed_graph, n, edge))
    {
        root_edge = edge;
    }

    if (vin == vvout)
        /*
          invert the links
        */
    {
        int  in, out;

        in = embed_graph[edge].link[0];
        out = embed_graph[edge].link[1];
        embed_graph[edge].link[0] = out;
        embed_graph[edge].link[1] = in;
    }
    /*
      get the twin and set the neighbour there to v (was vv originally)
    */
    twin =  embedg_VES_get_twin_edge(embed_graph, n, edge);
    ASSERT(embed_graph[twin].neighbour == vv);
    embed_graph[twin].neighbour = v;

    prev = vv;
    cur = edge;
    while (edge != vv)
    {
        edge =
            embedg_VES_get_next_in_dlcl(embed_graph, n,
                                                   cur, prev);

        if (embedg_VES_is_edge(n, edge))
            /*
              get the twin again (and invert the links if need be)
            */
        {
            if (embed_graph[edge].neighbour == c
                && embedg_VES_is_tree_edge(embed_graph, n, edge))
            {
                root_edge = edge;
            }

            if (vin == vvout)
            {
                int  in, out;

                in = embed_graph[edge].link[0];
                out = embed_graph[edge].link[1];
                embed_graph[edge].link[0] = out;
                embed_graph[edge].link[1] = in;
            }

            twin =
                embedg_VES_get_twin_edge(embed_graph, n, edge);
            ASSERT(embed_graph[twin].neighbour == vv);
            embed_graph[twin].neighbour = v;

            prev = cur;
            cur = edge;
        }
        else
        {
            ASSERT(edge == vv);
            /*
              only one vertex in the whole circular list
            */
        }
    }
    ASSERT(root_edge != NIL);

    /*
      and now union the adjacency lists of v and vv:

      let e1 be the edge record used to enter v
          e2                            exit  v
          e3                            enter vv
          e4                            exit  vv :

          e1 -> v  -> e2
          e3 -> vv -> e4

      the union of the list is done in such a way that
      - e1 and e4 are consecutive in v's adjacency list:
        they are now in the internal face
      - e3 is now the edge record used to enter v:
        it is on the external face (along with e2) :

          e1 -> e4
          e3 -> v -> e2

      (note that this does not assume that e1 & e2 are distinct
      or that e3 & e4 are distinct)
    */
    /*
      I must not forget the case where v is a lone vertex:
      this is the case where v has no DFS ancestor, ie when
      v is the root of a tree in the DFS forest
    */

    e1 = embed_graph[v].link[vin];
    vout = 1 ^ vin;
    e2 = embed_graph[v].link[vout];

    if (e1 != v)
    {
        ASSERT(e2 != v);
        ASSERT(embedg_VES_is_edge(n, e1));
        ASSERT(embedg_VES_is_edge(n, e2));
    }

    e4 = embed_graph[vv].link[vvout];
    ASSERT(embedg_VES_is_edge(n, e4));

    vvin = 1 ^ vvout;
    e3 = embed_graph[vv].link[vvin];
    ASSERT(embedg_VES_is_edge(n, e3));

    /*
      must take care of the adjacency list's consistency of traversal
      (will be important only when recovering the embedding)
    */
    if (e1 == e2)
    {
        ASSERT(embed_graph[e1].link[0] == embed_graph[e1].link[1]);
        if (vin == vvout)
            /*
              the bicomp will be flipped:
              must take 1 ^ vvout - difficult to explain -- later...
            */
        {
            e1out = 1 ^ vvout;
        }
        else
        {
            e1out = vvout;
        }
    }
    else
    {
        e1out = embed_graph[e1].link[0] == v ? 0 : 1;
    }
    if (e3 == e4)
    {
        ASSERT(embed_graph[e3].link[0] == embed_graph[e3].link[1]);
        e3out = 1 ^ vin;
        e4in = vin;
    }
    else
    {
        e4in = embed_graph[e4].link[0] == vv ? 0 : 1;
        e3out = embed_graph[e3].link[0] == vv ? 0 : 1;
    }

    IF_DEB(
           fprintf(stdout, "merge_simple_bicomp, before union of lists, e1\n");
           embedg_VES_print_edge(embed_graph, n, e1);
           fprintf(stdout, "merge_simple_bicomp, e3\n");
           embedg_VES_print_edge(embed_graph, n, e3);
           fprintf(stdout, "merge_simple_bicomp, e4\n");
           embedg_VES_print_edge(embed_graph, n, e4);
           )

    /*
      make e1 and e4 consecutive in the adjacency list
    */
    embed_graph[e1].link[e1out] = e4;
    embed_graph[e4].link[e4in] = e1;
    embed_graph[e3].link[e3out] = v;
    embed_graph[v].link[vin] = e3;

    IF_DEB(
           fprintf(stdout, "merge_simple_bicomp, after union of lists, e1\n");
           embedg_VES_print_edge(embed_graph, n, e1);
           fprintf(stdout, "merge_simple_bicomp, e3\n");
           embedg_VES_print_edge(embed_graph, n, e3);
           fprintf(stdout, "merge_simple_bicomp, e4\n");
           embedg_VES_print_edge(embed_graph, n, e4);
           )

    /*
      also, want to "disable" vv links, meaning then that
      vv is no longer a root of a bicomp
    */
    embed_graph[vv].link[0] = embed_graph[vv].link[1] = vv;

    IF_DEB_ADJL(
           fprintf(stdout, "merge_simple_bicomp, adj. list for %d (after)\n", vv);
           embedg_VES_print_adj_list(embed_graph, n, vv,
                                                TRUE);
           fprintf(stdout, "\n");
           embedg_VES_print_adj_list(embed_graph, n, vv,
                                                FALSE);
           fprintf(stdout, "\n");

           fprintf(stdout, "merge_simple_bicomp, adj. list for %d (after)\n", v);
           embedg_VES_print_adj_list(embed_graph, n, v,
                                                TRUE);
           fprintf(stdout, "\n");
           embedg_VES_print_adj_list(embed_graph, n, v,
                                                FALSE);
           )

    ASSERT(embedg_VES_is_adj_list_consistent(embed_graph, n, v));

    /*
      finally, give an orientation to the (formerly) root edge [vv, c]
      to keep traversal consistent (when recovering embedding)
    */
    if (vin == vvout)
        /*
          flip: set the sign of the root edge to clockwise

          note: a bicomp is merged only once, so there is no need to
          "flip" the root_edge's sign: it is set once at initialisation
          and then changed here if need be.
        */
    {
        embed_graph[root_edge].sign = CLOCKW;

        IF_VERB(
            fprintf(stdout, "merge_simple_bicomp, flip for %d, sign is now %d for %d of type %d\n",
                    c, embed_graph[root_edge].sign, root_edge, embed_graph[root_edge].type);
            embedg_VES_print_edge(embed_graph, n, root_edge);
            )
    }
}



void
embedg_VES_merge_pertinent_bicomps (t_ver_edge *embed_graph, int n,
	int vv, int vvout, int v, int vin)
    /*
      the bicomps to be merged are pertinent: on top (and before)
      performing a simple merge, there are several things to do
      related to the merging to pertinent bicomps
    */
{
    /*
      a note of caution:
      it is (very) likely that after a bicomp merge the resulting
      bicomp is not biconnected (and hence traversal of the external face
      of the bicomp via embedg_VES_get_succ_on_ext_face is non-sensical)

      remembering that a PERTINENT bicomp merge is ALWAYS followed
      by a back edge embedding we see that the end result is then a bicomp
      where again traversal of the external face
      via embedg_VES_get_succ_on_ext_face will make sense
    */
    t_dlcl    *pertinent_list, *head, *rep_in_parent_list, *parent_list;
    int       c;

    /*
      find c such that [v^c, c] is the root edge of the bicomp
      rooted at vv = v^c
    */
    c = vv - n;
    ASSERT(embed_graph[c].DFS_parent == v);

    /*
      two things to do first:
      - remove vv from head of pertinent_bicomp_list of v
      - remove c from separated_DFS_child_list of v

      one may ask the point of this since the separated_DFS_child_list
      seems to mirror pertinent_bicomp_list: but this is not exactly so:
      + pertinent_bicomp_list is ordered according to the activity
        of the (virtual) vertices
      + separated_DFS_child_list is ordered according to the vertices'
        lowpoint values
      in effect, it could (almost?*) be said that these two lists
      are in reverse order (the *almost bit would warrant some thinking here)
    */

    /*
      remove vv from head of pertinent_bicomp_list of v
    */
    pertinent_list = head = embed_graph[v].pertinent_bicomp_list;
    ASSERT(!embedg_dlcl_is_empty(pertinent_list));
    ASSERT(head->info == vv);

    IF_DEB(
           fprintf(stdout, "merge_pertinent_bicomp, start: merge\n");
           embedg_VES_print_virtual_vertex(embed_graph, n, vv);
           fprintf(stdout, ":%d & ", vvout);
           embedg_VES_print_vertex(n, v);
           fprintf(stdout, ":%d\n", vin);
           )

    IF_DEB(
           fprintf(stdout, "merge_pertinent_bicomp, pertinent bicomp_list of %d (before)\n", v);
           embedg_dlcl_print(embed_graph[v].pertinent_bicomp_list);
           )


    embed_graph[v].pertinent_bicomp_list =
        embedg_dlcl_delete_first(pertinent_list);

    IF_DEB(
           fprintf(stdout, "merge_pertinent_bicomp, pertinent bicomp_list of %d (after)\n", v);
           embedg_dlcl_print(embed_graph[v].pertinent_bicomp_list);
           )

    /*
      vv = v^c: remove c from separated_DFS_child_list of v
    */
    rep_in_parent_list = embed_graph[c].rep_in_parent_list;
    ASSERT(!embedg_dlcl_is_empty(rep_in_parent_list));

    parent_list = embed_graph[v].separated_DFS_child_list;
    ASSERT(!embedg_dlcl_is_empty(parent_list));
    embed_graph[v].separated_DFS_child_list =
        embedg_dlcl_delete_rec(parent_list, rep_in_parent_list);

    /*
      that's it, it remains to merge, ie. union the adjacency list,
      and flipping the bicomp if necessary
    */
    embedg_VES_merge_simple_bicomps(embed_graph, n,
                                               vv, vvout, v, vin);
}






/*
 *  embed_edge.c
 */

/*
  What:
  *****

  Implementing:

  Embedding an edge so that it lies on the external face of a bicomp.
  We work here with the VES structure.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_EMBED(x)    {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */


void
embedg_VES_embed_edge (t_ver_edge *embed_graph, int n, int *edge_pos,
	int edge_type, int vv, int vvout, int w, int win)
    /*
      embed the edge (vv, w) (vv a virtual vertex, w a vertex) between
      vv and the edge vvout
      and the edge win and w

      so that after the embedding, one exits vv via (vv, w) and
      enters w via the twin (w, vv)
    */
{
    int       temp, tempin, tempout;

    ASSERT(edge_type == BE || edge_type == SCE);
    ASSERT(embedg_VES_is_virtual_vertex(n, vv));
    ASSERT(embedg_VES_is_vertex(n, w));

    IF_DEB(
           fprintf(stdout, "embed_edge, (%d:%d)\n", vv, w);
           )

    /*
      first, set the edge [vv, w] with the appropriate info

      when [vv, w] is a back edge there is some more work to do
      (see the walkup procedure for the extra information we need
      to copy here
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = w;
    embed_graph[*edge_pos].type = edge_type;
    embed_graph[*edge_pos].sign = CCLOCKW;
    if (edge_type == BE)
    {
        ASSERT(embed_graph[w].adjacent_to ==
               embed_graph[vv - n].DFS_parent);

        /*
          PLUS: originally when the back edge [w, vv] was
          created (in the dfs preprocessing stage), it carried in
          .in_adjl the index of this directed edge in the
          adjacency list

          but now, note that we are actually inserting the
          directed edge [vv, w] in vv's adjacency list,
          meaning that in_adjl and twin_in_adjl
          must be exchanged!
        */
        embed_graph[*edge_pos].in_adjl = embed_graph[w].twin_in_adjl;
        embed_graph[*edge_pos].twin_in_adjl = embed_graph[w].in_adjl;

        ASSERT(embed_graph[w].mult % 2 == 0);
        /*
          the original graph is always undirected:
          we store its number of undirected edges
        */
        embed_graph[*edge_pos].mult = embed_graph[w].mult / 2;
    }

    /*
      insert this edge between vertex record for vv
      and edge record vv.link[vvout]
    */
    temp = embed_graph[vv].link[vvout];

    if (embed_graph[temp].link[0] == embed_graph[temp].link[1])
        /*
          this needs special treatment to ensure consistency of
          orientation
        */
    {
        ASSERT(embed_graph[temp].link[0] == vv);
        tempin = 1 ^ vvout;
    }
    else
    {
        tempin = embed_graph[temp].link[0] == vv ? 0 : 1;
    }

    IF_DEB(
           fprintf(stdout, "embed_edge, edge out of vv\n");
           embedg_VES_print_edge(embed_graph, n, temp);
           )

    embed_graph[vv].link[vvout] = *edge_pos;
    embed_graph[temp].link[tempin] = *edge_pos;
    /*
      the links for *edge_pos must also be "consistent"
    */
    embed_graph[*edge_pos].link[vvout] = temp;
    embed_graph[*edge_pos].link[vvout ^ 1] = vv;

    /*
      now create/set the twin edge, the directed edge [w, vv]
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = vv;
    embed_graph[*edge_pos].type = edge_type;
    embed_graph[*edge_pos].sign = CCLOCKW;
    if (edge_type == BE)
    {
        embed_graph[*edge_pos].in_adjl = embed_graph[w].in_adjl;
        embed_graph[*edge_pos].twin_in_adjl = embed_graph[w].twin_in_adjl;
        embed_graph[*edge_pos].mult = embed_graph[w].mult / 2;
    }

    /*
      and insert the twin edge between edge record w.link[win]
      and vertex record for w
    */
    temp = embed_graph[w].link[win];

    if (embed_graph[temp].link[0] == embed_graph[temp].link[1])
        /*
          again, special treatment to ensure consistency of orientation
        */
    {
        ASSERT(embed_graph[temp].link[0] == w);
        tempout = 1 ^ win;
    }
    else
    {
        tempout = embed_graph[temp].link[0] == w ? 0 : 1;
    }

    IF_DEB(
           fprintf(stdout, "embed_edge, edge in of w\n");
           embedg_VES_print_edge(embed_graph, n, temp);
           )

    embed_graph[w].link[win] = *edge_pos;
    embed_graph[temp].link[tempout] = *edge_pos;
    /*
      and consistent orientation
    */
    embed_graph[*edge_pos].link[win] = temp;
    embed_graph[*edge_pos].link[win ^ 1] = w;
}



void
embedg_VES_add_edge (t_ver_edge *embed_graph, int n, int *edge_pos,
	int v, int w, boolean MARK, int mark)
    /*
      add the edge (v, w): this is DIFFERENT from
      embedg_VES_embed_edge in the sense
      that the present function will only be used
      when building the Kuratowski homeomorphs:

      that is, we are in a situation where the graph is NON planar

      consequently it doesn't matter much where in the adjacency
      lists of v & w the edge is added:
      let's say that we always add it at the beginning

      for our sanity's sake, we'll ensure that the resulting
      adjacency lists remain consistent!

      and we add the edge as a BE!
      PLUS we mark it with mark in MARK true
    */
{
    int       temp;

    ASSERT(embedg_VES_is_vertex(n, v) ||
           embedg_VES_is_virtual_vertex(n, v));
    ASSERT(embedg_VES_is_vertex(n, w) ||
           embedg_VES_is_virtual_vertex(n, w));

    IF_DEB(
           fprintf(stdout, "add_edge, (%d:%d)\n", v, w);
           )

    /*
      not sure this is the best place to do this: mark the endpoints
    */
    if (MARK)
    {
        embed_graph[v].visited = mark;
        embed_graph[w].visited = mark;
    }

    /*
      first, set the edge [v, w] with the appropriate info
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = w;
    embed_graph[*edge_pos].type = BE;
    /*
      the edge's orientation will be the same as the vertex
    */
    embed_graph[*edge_pos].sign = embed_graph[v].sign;
    /*
      and mark the edge
    */
    if (MARK)
    {
        embed_graph[*edge_pos].visited = mark;
    }

    /*
      insert this edge between vertex record for v
      and edge record v.link[1]
    */
    temp = embed_graph[v].link[1];

    IF_DEB(
           fprintf(stdout, "add_edge, edge out of v\n");
           embedg_VES_print_edge(embed_graph, n, temp);
           )

    embed_graph[v].link[1] = *edge_pos;
    embed_graph[temp].link[0] = *edge_pos;
    /*
      the links for *edge_pos must also be "consistent"
    */
    embed_graph[*edge_pos].link[1] = temp;
    embed_graph[*edge_pos].link[0] = v;

    /*
      now create/set the twin edge, the directed edge [w, v]
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = v;
    embed_graph[*edge_pos].type = BE;
    embed_graph[*edge_pos].sign = embed_graph[w].sign;
    if (MARK)
    {
        embed_graph[*edge_pos].visited = mark;
    }

    /*
      insert this edge between vertex record for w
      and edge record w.link[1]
    */
    temp = embed_graph[w].link[1];

    IF_DEB(
           fprintf(stdout, "add_edge, edge out of w\n");
           embedg_VES_print_edge(embed_graph, n, temp);
           )

    embed_graph[w].link[1] = *edge_pos;
    embed_graph[temp].link[0] = *edge_pos;
    /*
      and consistent orientation
    */
    embed_graph[*edge_pos].link[1] = temp;
    embed_graph[*edge_pos].link[0] = w;
}


/*
 *  recover.c
 */

/*
  What:
  *****

  Implementing:

  From the VES data structure recover either the embedding ot
  the obstruction into the

  t_sparseg_ver_struct,
  t_sparseg_adjl_struct,
  t_sparseg_embed_struct

  data types.


  (This is no even quite true: for some obscure reason
  I recover the obstruction as a dlcl[] structure to be
  converted later.
  The obvious reason being that it is easier to check as such.
  Maybe I leave it as it is...)

  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_EMBED_MULT(x) {}
#define IF_DEB_EMBED_LOOPS(x) {}
#define IF_DEB_EMBED(x)    {}
#define IF_DEB_CHECK_EMBED(x)    {}
#define IF_DEB_FACES(x) {}
#define IF_VERB(x)   {}
#define IF_DEB_SCE(x) {}
#define IF_DEB_OBS(x) {}
#define IF_DEB_CHECK_OBS(x) {}
#define IF_CPU(x) {}



/* aproto: header embed_graph_protos.h */

/* aproto: beginstatic -- don't touch this!! */
static void embedg_recover_embedding_embed_mult
 (t_dlcl **, t_embed_sparse_rep *, int, int, int, int, int *, boolean *, int *);
static void embedg_recover_embedding_embed_loops
 (t_dlcl **, t_embed_sparse_rep *, int, int, int *, boolean *);
static t_dlcl **embedg_get_reduced_obs (t_dlcl **, int);
static boolean embedg_is_red_obs_K33 (t_dlcl **, int);
static boolean embedg_is_red_obs_K5 (t_dlcl **, int);
/* aproto: endstatic -- don't touch this!! */


#ifndef PLANAR_IN_MAGMA
#endif

void
embedg_recover_embedding (
    t_ver_sparse_rep *V,
    t_adjl_sparse_rep *A,             /* input (original sparse graph) */
    t_ver_edge *embed_graph,
    int n,
    int nbr_e,
    t_dlcl **mult_edges,
    t_ver_sparse_rep **vertices,
    t_embed_sparse_rep **embedding
)
    /*
      recover the embedding
      to prepare for the final Magma type for sparse & embedded graph

      we assume that all vertices/edges have been given their
      orientation

      at this stage we also embed the multiple edges and loops
      which were set aside in mult_edges by
      sparseg_adjl_dfs_preprocessing:

      as it turns out the last bit is pretty hairy!
    */
{
    /*
      the idea is to return an array of vertices and an array
      representing the embedding
      (careful: need to weedout the SCE)

      vertices: (*vertices)[i].first_edge contains index
                to first edge in embedding

      embedding: a doubly linked circular list of edges,
                 for each record/edge e = (*embedding)[i]:
                 e.in_adjl: index in A of e
                 e.next:    next edge in CLOCKW
                            (as an index in the embedding)
                 e.prev:    previous edge in CLOCKW
                            (as an index in embedding)
                 e.inv:     inverse edge (as an index in embedding)
                 e.mark:    a mark for this edge

      let's say that this new array is a slimmed down version of embed_graph

      one issue to address:
      - for edge e, find its index in A: this should be found
        in either the embed_graph[v] record of the mult_edges[v] record
    */
    int          index_embed, v, mult, w, v_w_in_embed, new_first_edge;
    boolean      set_next;

    IF_DEB(
           fprintf(stdout, "in recover emb.\n");
           sparseg_dlcl_print(mult_edges, n);
           );

    *vertices = (t_ver_sparse_rep *)
        mem_malloc(sizeof(t_ver_sparse_rep) * n);
    *embedding = (t_embed_sparse_rep *)
        mem_malloc(sizeof(t_embed_sparse_rep) * 2 * nbr_e);

    index_embed = 0;
    set_next = TRUE;
    for (v = 0; v < n; v++)
    {
        int       v_l, orient, in, out, e, cur_e, next_e;

        /*
          we take v's label
        */
        v_l = embed_graph[v].label;

        /*
          first let's deal with the isolated vertex case: those
          that refer to self
        */
        if (embed_graph[v].link[0] == v)
        {
            int       temp_index_embed;

            ASSERT(embed_graph[v].link[1] == v);

            /*
              there may be [v, v] loops for this vertex, must check this
            */
            temp_index_embed = index_embed - 1;
            /*
              temp_index_embed is pre-increased below
            */
            embedg_recover_embedding_embed_loops(mult_edges, *embedding,
                                                 nbr_e, v,
                                                 &temp_index_embed,
                                                 &set_next);

            if (temp_index_embed > index_embed - 1)
                /*
                  must fix beginning and end of adjacency list:
                */
            {
                (*vertices)[v_l].first_edge = index_embed;
                (*embedding)[temp_index_embed].next =
                    (*vertices)[v_l].first_edge;
                (*embedding)[(*vertices)[v_l].first_edge].prev =
                    temp_index_embed;

                index_embed = temp_index_embed;
                index_embed += 1;
            }
            else
            {
                (*vertices)[v_l].first_edge = NIL;
            }
            continue;
        }

        /*
          get v's orientation, and from this decide the way in which
          v's adjacency list will be traversed
          (recall that the list is supposed to be consistent, so no bad
          surprises)
        */
        orient = embed_graph[v].sign;
        in = orient == CCLOCKW ? 0 : 1;
        out = 1 ^ in;

        e = embed_graph[v].link[out];
        while (embedg_VES_is_short_cut_edge(embed_graph, n, e))
        {
            e = embed_graph[e].link[out];
        }
        ASSERT(embedg_VES_is_edge(n, e)
               && !embedg_VES_is_short_cut_edge(embed_graph, n, e));
        /*
          strictly speaking there should be no SCEs left at this stage...

          if there are SCEs in v's list, it must be the case that
          the list also contains tree or back edges...
        */

        (*vertices)[v_l].first_edge = index_embed;

        IF_DEB_EMBED(
                     fprintf(stdout, "recov. embed. DFI %d vertex %d at %d (edges) and %d (embedding)\n",
                             v, v_l, index_e, (*vertices)[v_l].first_edge);
                     )

        cur_e = e;
        while (TRUE)
        {
            next_e = embed_graph[cur_e].link[out];
            while (embedg_VES_is_short_cut_edge(embed_graph, n, next_e))
            {
                next_e = embed_graph[next_e].link[out];
            }
            ASSERT(!embedg_VES_is_short_cut_edge(embed_graph, n, next_e));

            if (next_e == v)
                /*
                  end of adjacency list
                */
            {
                break;
            }

            ASSERT(embedg_VES_is_edge(n, next_e));

            (*embedding)[index_embed].in_adjl = embed_graph[cur_e].in_adjl;
            (*embedding)[index_embed].next = index_embed + 1; /* next in adj.
                                                                list */
            (*embedding)[index_embed].mark = NIL;  /* mark */

            /*
              cur_e's twin is trickier:
              we'll use twin's label field to store cur_e's index in
              the embedding

              if cur_e's label != NIL this means that cur_e's twin
              is already stored in edges/embedding  and consequently
              that cur_e.label = index of its twin (in the embedding)

              note that it is safe to do so since an edge's label
              has no meaning
            */
            if (embed_graph[cur_e].label != NIL)
            {
                (*embedding)[index_embed].inv = embed_graph[cur_e].label;

                /*
                  but fix the twin by the same token
                */
                (*embedding)[embed_graph[cur_e].label].inv = index_embed;
                ASSERT((*embedding)[embed_graph[cur_e].label].in_adjl ==
                       embed_graph[cur_e].twin_in_adjl);
            }
            else
                /*
                  we store cur_e's index in the embedding in twin's label
                */
            {
                int      twin;

                twin = embedg_VES_get_twin_edge(embed_graph, n, cur_e);
                embed_graph[twin].label = index_embed;
            }

            /*
              so the only thing we couldn't update yet is
              (*embedding)[index_embed].prev, cur_e previous edge in the list

              but we can do this for next_e
            */
            (*embedding)[index_embed + 1].prev = index_embed;

            /*
              we check if there are any multiple edges or loops
              to embed
            */
            w = embed_graph[cur_e].neighbour;
            mult = embed_graph[cur_e].mult - 1;
            /*
              one was for the TE or BE edge
            */

            if (index_embed == (*vertices)[v_l].first_edge)
                /*
                  when looking for multiple edges/loops
                  we must temporarily "close" this ordered
                  list of vertices when in presence of the first
                  edge in the list:

                  not doing this would mean that
                  (*embedding)[(*vertices)[v_l].first_edge].prev
                  contains some irrelevant value which may cause
                  (major) trouble when embedding inverses of
                  multiple edges...
                */
            {
                (*embedding)[(*vertices)[v_l].first_edge].prev = index_embed;
            }

            embedg_recover_embedding_embed_mult(mult_edges, *embedding,
                                                nbr_e, v, w, mult,
                                                &index_embed, &set_next,
                                                &new_first_edge);
            embedg_recover_embedding_embed_loops(mult_edges, *embedding,
                                                 nbr_e, v, &index_embed,
                                                 &set_next);
            set_next = TRUE;

            /*
              yes, it may be the case that (*vertices)[v_l].first_edge
              change while in embedg_recover_embedding_embed_mult
              -- see that function for more
            */
            (*vertices)[v_l].first_edge = new_first_edge == NIL ?
                (*vertices)[v_l].first_edge : new_first_edge;

            /*
              that's all, we proceed to read a new edge in the list
            */
            index_embed += 1;
            cur_e = next_e;
        }

        /*
          now next_e = v so that cur_e is the last edge in v's adjacency list
          we must deal with this case separately
        */

        /*
          fix cur_e in embedding (and its twin)
        */
        (*embedding)[index_embed].in_adjl = embed_graph[cur_e].in_adjl;

        /*
          we temporarily set next of cur_e in to index_embed + 1
        */
        (*embedding)[index_embed].next = index_embed + 1;
        (*embedding)[index_embed].mark = NIL;  /* mark */

        /*
          fix cur_e's twin
        */
        if (embed_graph[cur_e].label != NIL)
        {
            (*embedding)[index_embed].inv = embed_graph[cur_e].label;
            (*embedding)[embed_graph[cur_e].label].inv = index_embed;
            ASSERT((*embedding)[embed_graph[cur_e].label].in_adjl ==
                   embed_graph[cur_e].twin_in_adjl);
        }
        else
        {
            int      twin;

            twin = embedg_VES_get_twin_edge(embed_graph, n, cur_e);
            embed_graph[twin].label = index_embed;
        }

        /*
          we temporarily set the next record's prev field:
          but we can do that only if we haven't processed
          all the edges yet
        */
        if (index_embed < 2 * nbr_e - 1)
        {
            (*embedding)[index_embed + 1].prev = index_embed;

            /*
              again, check if there are any multiple edges/loops
              to embed
            */
            w = embed_graph[cur_e].neighbour;
            mult = embed_graph[cur_e].mult - 1;
            /*
              one was for the TE or BE edge
            */
            v_w_in_embed = index_embed;

            if (index_embed == (*vertices)[v_l].first_edge)
                /*
                  same comment as above
                */
            {
                (*embedding)[(*vertices)[v_l].first_edge].prev = index_embed;
            }

            embedg_recover_embedding_embed_mult(mult_edges, *embedding,
                                                nbr_e, v, w, mult,
                                                &index_embed, &set_next,
                                                &new_first_edge);
            embedg_recover_embedding_embed_loops(mult_edges, *embedding,
                                                 nbr_e, v, &index_embed,
                                                 &set_next);

            /*
              same comment as above
            */
             (*vertices)[v_l].first_edge = new_first_edge == NIL ?
                (*vertices)[v_l].first_edge : new_first_edge;
         }

        /*
          to finish off, we must set:

          cur_e's next field:
          next of cur_e in the list is ... vertices[v_l].first_edge

          cur_e's next's previous field...
        */
        if (set_next)
            /*
              set_next (poorly named) is used to indicate which
              edges must be updated to "close off" the list:

              if set_next is TRUE, we are in the standard case
              where the last edge in the ordered adj. list
              is at index_embed

              if set_next is FALSE, the last edge in the ordered adj. list
              is at v_w_in_embed: because it could have happened
              (in embedg_recover_embedding_embed_mult only)
              that the edges have been "wedged" between
              v_w_in_embed.prev and v_w_in_embed,
              leaving v_w_in_embed the last in the list
            */
        {
            (*embedding)[index_embed].next = (*vertices)[v_l].first_edge;
            (*embedding)[(*vertices)[v_l].first_edge].prev = index_embed;
        }
        else
        {
            (*embedding)[v_w_in_embed].next = (*vertices)[v_l].first_edge;
            (*embedding)[(*vertices)[v_l].first_edge].prev = v_w_in_embed;
        }
        set_next = TRUE;

        /*
          a simple check
        */
        ASSERT(embedg_dlcl_is_empty(mult_edges[v]));

        /*
          we can process another vertex
        */
        index_embed += 1;
    }
    /*
      when this is done there are a few things that must hold
    */
    ASSERT(index_embed == 2 * nbr_e);
}


static void
embedg_recover_embedding_embed_mult (t_dlcl **mult_edges,
	t_embed_sparse_rep *embedding, int nbr_e, int v, int w,
	int mult, int *index_embed, boolean *set_next, int *first_edge)
    /*
      see if the directed edge [v, w] is multiple: if so embed it
      in embedding

      moreover if there are any [v, v] loops do that too
    */
{
    /*
      we take care of multiple edges: for tree edges and back
      edges their multiplicity is indicated by the
      embed_graph[cur_e].mult field (which records the number
      of undirected edges)

      for loops hovewer this information is stored in the mult
      field of the FIRST encountered neighbour v in v's neighbour
      list
    */
    t_dlcl      *p;
    int         v_w_in_embed, v_w_prev;
    boolean     do_twins, start, do_first_edge;

    IF_DEB_EMBED_MULT(
           fprintf(stdout, "in recover emb. mult, v %d w %d mult %d\n",
                   v, w, mult);
           )

    /*
      the current index_embed value is the edge [v, w]:
      I must record this value as it will be needed
      later
    */
    v_w_in_embed = *index_embed;
    start = TRUE;
    *set_next = TRUE;
    do_twins = FALSE;
    *first_edge = NIL;
    do_first_edge = FALSE;
    v_w_prev = NIL;
    while (mult > 0)
    {
        ASSERT(!embedg_dlcl_is_empty(mult_edges[v]));
        p = embedg_dlcl_find(mult_edges[v], w);
        /*
          note that using embedg_dlcl_find to always find
          the first in the list with p->info == w
          is ok here since any previous such records would
          have been deleted/removed from the list
        */
        ASSERT(p != NP);
        /*
          otherwise we couldn't have mult > 0 !
        */

        *index_embed += 1;

        /*
          once again I must use a similar sort of trick as in the
          main function to deal with the inverse edge:

          the inverse edge is to be found in mult_edges[w]:
          if p->twin_in_adjl (which was initialised to NIL
          and has NOT been set in the DFS preprocessing),
          if p->twin_in_adjl != NIL, then
          a. its inverse in mult_edges[w] has already been embedded
          in *embedding
          b. its index there is stored in p->twin_in_adjl
          precisely
         */
        if (p->twin_in_adjl != NIL)
        {
            if (! start)
                /*
                  if the first the multiple edges' inverse is already
                  stored, then this is true for ALL of them
                */
            {
                ASSERT(do_twins == TRUE);
            }
            do_twins = TRUE;
        }
        else
            /*
              similarly, if the first the multiple edges' inverse is
              not already stored, then this is true for ALL of them
            */
        {
            ASSERT(do_twins == FALSE);
        }

        embedding[*index_embed].in_adjl = p->in_adjl;
        embedding[*index_embed].mark = NIL;

        /*
          as we will see do_twins has to be treated differently
        */
        if (!do_twins)
            /*
              this is pretty standard as works as the
              main recover function
            */
        {
            t_dlcl      *i_m_l, *i_p;

            embedding[*index_embed].next = *index_embed + 1;

            /*
              we store the current index in the embedding in
              the twin/inverse's twin_in_adjl field
            */
            i_p = i_m_l = mult_edges[w];
            ASSERT(!embedg_dlcl_is_empty(i_m_l));
            i_p = embedg_dlcl_find_with_NIL_twin_in_adjl(i_m_l, v);
            ASSERT(i_p != NP);
            ASSERT(i_p->twin_in_adjl == NIL);

            i_p->twin_in_adjl = *index_embed;

             /*
              to finish off this bit we set embedding[*index_embed + 1].prev

              but I can only set this prev field if I haven't reached
              the end of the embedding[] array: this is why we needed
              nbr_e (total number of edges to embed) as input
             */

            if (*index_embed < 2 * nbr_e - 1)
            {
                embedding[*index_embed + 1].prev = *index_embed;
            }
        }
        else
            /*
              how to insert the inverses of multiple edges already
              in the embedding:

              if one studies how the twin_in_adjl field has been
              set while dealing with the inverses of the
              present multiple edges one sees that
              the latter must be inserted in counter clockwise
              order (assuming that the inverses were inserted
              in clockwise order)

              this is necessariy to ensure a correct matching between
              the edge and its inverse
            */
        {

            embedding[*index_embed].inv = p->twin_in_adjl;

            /*
              fix the twin by the same token
            */
            embedding[p->twin_in_adjl].inv = *index_embed;

            /*
              general (reverse) insertion for these edges
            */
            embedding[*index_embed].prev = *index_embed + 1;
            embedding[*index_embed].next = *index_embed - 1;

            /*
              ok, that was the easy bit, things are a bit more complicated
              below...
            */
            if (start)
                /*
                  the edges are "wedged" between
                  embedding[v_w_in_embed].prev and v_w_in_embed,

                  hence the following
                */
            {
                v_w_prev = embedding[v_w_in_embed].prev;
                if (v_w_prev == v_w_in_embed)
                    /*
                      in this case the first edge in the adj. list
                      of the vertex whose first_edges is v_w_in_embed
                      will be changed
                      (because we insert in reverse order)
                    */
                {
                    do_first_edge = TRUE;
                }

                embedding[*index_embed].next = v_w_in_embed;
                embedding[v_w_in_embed].prev = *index_embed;

                ASSERT(embedding[embedding[*index_embed].inv].prev ==
                       embedding[v_w_in_embed].inv);
                ASSERT(embedding[embedding[v_w_in_embed].inv].next ==
                       embedding[*index_embed].inv);
            }

            if (mult == 1)
                /*
                  last inv. edge in this list to add
                */
            {
                ASSERT(v_w_prev != NIL);

                /*
                  must fix embedding[v_w_prev].next appropriately
                  (and embedding[*index_embed].prev)

                  this may be overwritten later on, but not necessarily so

                  the next_set flag will enable us to decide
                  which edge ends this adjacency list: see above
                */

                embedding[*index_embed].prev = v_w_prev;
                embedding[v_w_prev].next = *index_embed;
                *set_next = FALSE;

                ASSERT(embedding[embedding[*index_embed].inv].prev ==
                       embedding[*index_embed - 1].inv);
                ASSERT(embedding[embedding[*index_embed - 1].inv].next ==
                       embedding[*index_embed].inv);

                if (do_first_edge)
                    /*
                      the first edge is the last one added
                    */
                {
                    *first_edge = *index_embed;
                }

                embedding[v_w_in_embed].next = *index_embed + 1;
                if (*index_embed < 2 * nbr_e - 1)
                {
                   embedding[*index_embed + 1].prev = v_w_in_embed;
                }
            }

            ASSERT(embedding[embedding[*index_embed].inv].prev ==
                   embedding[embedding[*index_embed].next].inv);
        }

        /*
          to finish off this bit we delete the p record from m_l
          and set embedding[*index_embed + 1].prev
        */
        mult_edges[v] = embedg_dlcl_delete_rec(mult_edges[v], p);

        mult--;
        start = FALSE;
    }
    /*
      conclusion: sevral days to get this working! *sigh*
    */
}




static void
embedg_recover_embedding_embed_loops (t_dlcl **mult_edges,
	t_embed_sparse_rep *embedding, int nbr_e, int v,
	int *index_embed, boolean *set_next)
    /*
      embed the [v, v] loops
    */
{
    /*
      the loops' multiplicity is stored in the mult
      field of the FIRST encountered neighbour v in v's neighbour
      list
    */
    t_dlcl      *p;
    int         nbr_loops;

    /*
      have a look if there are any [v. v] loops
    */
    p = embedg_dlcl_find(mult_edges[v], v);
    if (p == NP)
    {
        return;
    }

    /*
      when there are loops to add to the adjaceny list,
      edge insertion resume in the "normal" clockwaise saya, way:
      so we reset set_next to true
    */
    *set_next = TRUE;

    nbr_loops = p->mult;
    ASSERT(nbr_loops % 2 == 0);
    /*
      we counted directed edges
    */
    nbr_loops /= 2;

    IF_DEB_EMBED_LOOPS(
           fprintf(stdout, "in recover emb. loops, nbr_loops [v, v] %d\n",
                   nbr_loops);
           )

    while (nbr_loops > 0)
        /*
          a loop requires to embed two directed edges
        */
    {
        p = embedg_dlcl_find(mult_edges[v], v);
        ASSERT(p != NP);

        *index_embed += 1;

        embedding[*index_embed].in_adjl = p->in_adjl;
        embedding[*index_embed].next = *index_embed + 1;
        embedding[*index_embed].mark = NIL;
        embedding[*index_embed].inv = *index_embed + 1;
        embedding[*index_embed + 1].prev = *index_embed;

        mult_edges[v] = embedg_dlcl_delete_rec(mult_edges[v], p);

        IF_DEB_EMBED_LOOPS(
           fprintf(stdout, "in recover emb. loops, mid\n");
           embedg_dlcl_print(mult_edges[v]);
           );

        /*
          now do the "inverse" loop
        */
        p = embedg_dlcl_find(mult_edges[v], v);
        ASSERT(p != NP);

        *index_embed += 1;

        embedding[*index_embed].in_adjl = p->in_adjl;
        embedding[*index_embed].next = *index_embed + 1;
        embedding[*index_embed].mark = NIL;
        embedding[*index_embed].inv = *index_embed - 1;

        if (*index_embed < 2 * nbr_e - 1)
        {
            embedding[*index_embed + 1].prev = *index_embed;
        }
        mult_edges[v] = embedg_dlcl_delete_rec(mult_edges[v], p);

        nbr_loops--;

        IF_DEB_EMBED_LOOPS(
           fprintf(stdout, "in recover emb. loops, end\n");
           embedg_dlcl_print(mult_edges[v]);
           );
    }
}




void
embedg_recov_embed_walk_proper_face (int n, int e, t_adjl_sparse_rep *A,
	t_embed_sparse_rep *embedding, boolean MARK, int mark)
    /*
      do a proper face walk in the recovered embedding starting
      at index e in the embedding
    */
{
    int          cur, next;

    IF_DEB_FACES(
                 fprintf(stdout, "recov. emb. proper face walk\n");
                 fprintf(stdout, "[-, %d] ",
                         A[embedding[e].in_adjl].end_vertex);
                 )

    cur = e;
    next = NIL;
    while (next != e)
        /*
          to get the next in a proper face traversal:
          get the previous of the cur's inverse
        */
    {
        int     inv;

        inv = embedding[cur].inv;
        next = embedding[inv].prev;

        ASSERT(embedding[next].mark != mark);

        if (MARK)
        {
            embedding[next].mark = mark;
        }

        cur = next;
        IF_DEB_FACES(
                     fprintf(stdout, "[-, %d] ",
                             A[embedding[cur].in_adjl].end_vertex);
                     )
    }
    IF_DEB_FACES(
                 fprintf(stdout, "\n");
                 )
}



boolean
embedg_check_recov_embedding (int n, int nbr_e, int nbr_comp,
	t_ver_sparse_rep *vertices, t_adjl_sparse_rep *A,
	t_embed_sparse_rep *embedding)
    /*
      check if the recovered embedding is a valid embedding
      SHOULD ONLY be use after creation, that is, after having
      recovered the embedding from the VES structure
      (because of the mark MIN_EMBED_MARK we use)
    */
{
    int          v, e, f;

    f = 0;
    /*
      do all the edges in embedding:
      careful: we have 2 * nbr_e to visit (the edge and its inverse!)
    */
    for (e = 0; e < 2 * nbr_e; e++)
    {
        /*
          we check if the current edge is marked: if not, we
          traverse a proper face bordered by this edge
        */
        if (embedding[e].mark != MIN_EMBED_MARK)
            /*
              we --hopefully-- perform this check only after creation
              where mark == NIL
            */
        {
            embedg_recov_embed_walk_proper_face(n, e, A, embedding,
                                                TRUE, MIN_EMBED_MARK);
            f++;
        }
    }

    /*
      must also count a face for each isolated vertex
    */
    for (v = 0; v < n; v++)
    {
        if (vertices[v].first_edge == NIL)
            f++;
    }

    IF_DEB_CHECK_EMBED(
                       fprintf(stdout, "recovered embedding, n: %d\t e: %d\t C: %d\t f: %d\n",
                               n, nbr_e, nbr_comp, f);
                       )

    return f == 2 * nbr_comp + nbr_e - n ? TRUE : FALSE;
}


t_dlcl **
embedg_recover_obstruction (t_ver_edge *embed_graph, int n, minor m, int *nbr_e)
    /*
      recover the obstruction as a t_dlcl * structure:
      and return the number of edges: lets say we agree on returning
      the number of undirected edges
      -- I don't know yet which way to do, directed or undirected???

      so far in the algorithm we only dealt with DFIs,
      but now, we retrieve the obstruction not wrt DFIs but
      wrt the vertices' labels
    */
{
    /*
      so I am looking, in embed_graph, for the vertices and edges
      marked MARK_MINORS(n)
    */

    int          v;
    t_dlcl       **obs;

    obs = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);
    for (v = 0; v < n; v++)
        obs[v] = NP;

    *nbr_e = 0;
    for (v = 0; v < 2*n; v++)
        /*
          must check real vertices as well as virtual vertices
        */
    {
        int      e;

        if (embed_graph[v].link[0] == v)
            /*
              isolated vertex case
            */
        {
            ASSERT(embed_graph[v].link[1] == v);
            continue;
        }

        e = embed_graph[v].link[0];
        while (e != v)
        {
            ASSERT(embedg_VES_is_edge(n, e));
            if (embed_graph[e].visited == MARK_MINORS(n))
            {
                int        cur_v, neigh;

                /*
                  virtual vertices may still hang around
                */
                /*
                  let's get the "actual" v:
                  note that the statement below is safe since if v were
                  not a valid virtual vertex (ie [v - n].DFS_parent = n)
                  it would have an empty
                  adjacency list and we wouldn't be there anyway
                */
                cur_v = embedg_VES_get_ver(embed_graph, n, v);

                neigh = embedg_VES_get_ver(embed_graph, n,
                                           embed_graph[e].neighbour);

                /*
                  again, cur_v and neigh are DFIs,
                  we want vertex labels at this stage
                */
                cur_v = embed_graph[cur_v].label;
                neigh = embed_graph[neigh].label;
                sparseg_dlcl_append_to_neigh_list(obs, n, cur_v, neigh,
                                                  embed_graph[e].in_adjl);
                (*nbr_e)++;
            }
            e = embed_graph[e].link[0];
        }
    }

    IF_DEB_OBS(
               fprintf(stdout, "recovering the obstruction\n");
               sparseg_dlcl_print(obs, n);
    );

    ASSERT(*nbr_e % 2 == 0);
    *nbr_e /= 2;

    return obs;
}


static t_dlcl **
embedg_get_reduced_obs (t_dlcl **obs, int n)
    /*
      reduce the obstruction by removing all degree 2 vertices
      (so that they become isolated vertices)
    */
{
    t_dlcl       **reduced;
    int          v;

    reduced =  (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);
    for (v = 0; v < n; v++)
    {
        reduced[v] = embedg_dlcl_copy(obs[v]);
    }

    for (v = 0; v < n; v++)
    {
        t_dlcl   *n_l, *n_l_b, *p, *new_n_v, *n_l_x, *b_in_n_x;
        int      a, b, n_x;

        n_l = reduced[v];
        while (!embedg_dlcl_is_empty(n_l)
                && embedg_dlcl_list_last(n_l) == embedg_dlcl_list_next(n_l))
            /*
              pick out which  vertices have deg 2
            */
        {
            a = n_l->info;
            b = embedg_dlcl_list_next(n_l)->info;
            /*
              we remove the edge (v, b), or rather, we identify v and b:
              b will then be an isolated vertex

              fix v's neighbour list: all of b's neighbours
              are now v's neighbours
            */
            reduced[v] = n_l =
                embedg_dlcl_delete_rec(n_l, embedg_dlcl_list_last(n_l));

            p = n_l_b = reduced[b];
            ASSERT(!embedg_dlcl_is_empty(n_l_b));
            n_x = p->info;
            if (n_x != v)
            {
                new_n_v = embedg_dlcl_rec_new(n_x);
                reduced[v] = n_l = embedg_dlcl_cat(n_l, new_n_v);

                /*
                  and in n_x neighbour list, we must replace b by v
                */
                n_l_x = reduced[n_x];
                b_in_n_x = embedg_dlcl_find(n_l_x, b);
                b_in_n_x->info = v;
            }
            /*
              and do this for all of b's neighbours
            */
            p = embedg_dlcl_list_next(p);
            while (p != n_l_b)
            {
                n_x = p->info;
                if (n_x != v)
                {
                    new_n_v = embedg_dlcl_rec_new(n_x);
                    reduced[v] = n_l = embedg_dlcl_cat(n_l, new_n_v);
                    n_l_x = reduced[n_x];
                    b_in_n_x = embedg_dlcl_find(n_l_x, b);
                    b_in_n_x->info = v;
                }
                p = embedg_dlcl_list_next(p);
            }
            embedg_dlcl_delete(reduced[b]);
            reduced[b] = NP;
        }
    }

    IF_DEB_CHECK_OBS(
                     fprintf(stdout, "reducing the obstruction\n");
                     sparseg_dlcl_print(reduced, n);
                     )

    /*
      now check no degree 2 vertices are left
    */
    for (v = 0; v < n; v++)
    {
        t_dlcl   *n_l;

        n_l = reduced[v];
        if (!embedg_dlcl_is_empty(n_l))
        {
            ASSERT(embedg_dlcl_list_last(n_l) != embedg_dlcl_list_next(n_l));
        }
    }

    return reduced;
}

static boolean
embedg_is_red_obs_K33 (t_dlcl **reduced, int n)
    /*
      check if the (reduced) obstruction is indeed K33
    */
{
    int          v, order, vs[6], i, b1[3];

    /*
      check that order == 6 and that the obstruction is cubic
    */
    order = 0;
    for (v = 0; v < n; v++)
    {
        if (!embedg_dlcl_is_empty(reduced[v]))
        {
            if (order == 6)
            {
                return FALSE;
            }
            order++;
            vs[order - 1] = v;

            if (embedg_dlcl_length(reduced[v]) != 3)
            {
                return FALSE;
            }
        }
    }
    if (order != 6)
    {
        return FALSE;
    }

    /*
      check if bipartite
    */
    v = vs[0];
    ASSERT(!embedg_dlcl_is_empty(reduced[v]));
    b1[0] = reduced[v]->info;
    b1[1] = embedg_dlcl_list_next(reduced[v])->info;
    b1[2] = embedg_dlcl_list_prev(reduced[v])->info;

    for (i = 1; i < 6; i++)
    {
        t_dlcl      *n_v;

        v = vs[i];
        n_v = reduced[v];
        ASSERT(!embedg_dlcl_is_empty(n_v));
        if (n_v->info == b1[0]
            || embedg_dlcl_list_next(n_v)->info == b1[0]
            || embedg_dlcl_list_prev(n_v)->info == b1[0])
        {
            if ((n_v->info != b1[1]
                 && embedg_dlcl_list_next(n_v)->info != b1[1]
                 && embedg_dlcl_list_prev(n_v)->info != b1[1])
                &&
                (n_v->info != b1[2]
                 && embedg_dlcl_list_next(n_v)->info != b1[2]
                 && embedg_dlcl_list_prev(n_v)->info != b1[2]))
            {
                return FALSE;
            }
        }
        else
        {
            if ((n_v->info == b1[1]
                 || embedg_dlcl_list_next(n_v)->info == b1[1]
                 || embedg_dlcl_list_prev(n_v)->info == b1[1])
                ||
                (n_v->info == b1[2]
                 || embedg_dlcl_list_next(n_v)->info == b1[2]
                 || embedg_dlcl_list_prev(n_v)->info == b1[2]))
            {
                return FALSE;
            }
        }
    }

    return TRUE;
}


static boolean
embedg_is_red_obs_K5 (t_dlcl **reduced, int n)
    /*
      check if the (reduced) obstruction is indeed K5
    */
{
    int          v, order;

    /*
      check that order == 5 and that the obstruction is quadric
    */
    order = 0;
    for (v = 0; v < n; v++)
    {
        if (!embedg_dlcl_is_empty(reduced[v]))
        {
            if (order == 5)
            {
                return FALSE;
            }
            order++;

            if (embedg_dlcl_length(reduced[v]) != 4)
            {
                return FALSE;
            }
        }
    }

    return TRUE;
}


boolean
embedg_check_recov_obs (t_dlcl **obs, int n, minor m)
    /*
      check if the recovered obstruction is one of K33 or K5
    */
{
    t_dlcl      **reduced;
    boolean     ans;

    reduced = embedg_get_reduced_obs(obs, n);
    if (m != MINOR_E5)
    {
        ans = embedg_is_red_obs_K33(reduced, n);
    }
    else
    {
        ans = embedg_is_red_obs_K5(reduced, n);
    }

    sparseg_dlcl_delete(reduced, n);
    return ans;
}
/*
 *  obstruction.c
 */

/*
  What:
  *****

  Implementing:

  The graph is not planar: we recover the obstruction from the VES structure
  and check it as well.
  (Some of these checks will disappear later)



  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_OBS(x) {}
#define IF_DEB_CHECK_OBS(x) {}
#define IF_CPU(x) {}
#define IF_DEB_MINOR(x) {}


/* aproto: header embed_graph_protos.h */

void
embedg_obstruction (
    t_ver_sparse_rep *V,
    t_adjl_sparse_rep *A,       /* the input graph as a sparse graph */
    t_dlcl **dfs_tree,      /* a sparse graph rep. for the dfs tree
                                      -- vertices are as DFIs
                                      -- and children are ordered wrt
                                      lowpoint value
                                  */
    t_dlcl **back_edges,    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      (vertices are given as DFIs)
                                  */
    t_ver_edge *embed_graph,    /* output of tester */
    int n,               /* size of the graph */
    int *edge_pos,       /* pos. in embed_graph for addition
                                     of the next edge */
    int v,
    int w_in,         /* the unembedded directed back edge
                                     [w_in, v]
                                   */
    t_ver_sparse_rep **OV,      /* the obstruction as an adjacency list */
    t_adjl_sparse_rep **OA,
    int *nbr_e_obs      /* obstruction's #edges */
)

    /*
      the graph is non planar: we must mark & recover the K33 or K5
      homeomorph
    */
{
    int          *ver_orient;
    minor        m;
    t_dlcl       **obs;

    /*
      this is magma code - must be removed
    */
    float      sttime, time_to_now;

 IF_CPU(
    sttime = time_current_user();
       )

    /*
      we will NOT remove the short-cut edges at this stage:
      we'll have to perform another walkdown in embedg_iso_is_minor_A
      so
      1. saves time when looking for ext. active vertices
      2. more importantly this enables us to ascertain that the number of
         edges in embed_graph (even after completing whichever obstruction
         applying in this case) will NEVER be > 3*n - 5!!!
      3. SCEs are then removed in embedg_iso_is_minor_A
         (obligatory path for every possible case)
    */

    /*
      we must compute each vertex's orientation (wrt flipped bicomps)
      and set the edges' orientation:

      the other day I was wondering why this was necessary in this
      instance (because after all we won't get an embedding):
      orientation is required bacause later in the piece we
      do a proper face traversal (I guess for Minor C testing)
    */
    ver_orient = embedg_vertices_orientation(embed_graph, n);
    embedg_VES_set_orientation(embed_graph, n, ver_orient);
    mem_free(ver_orient);

    m = embedg_mark_obstruction(dfs_tree, back_edges,
                                embed_graph, n, edge_pos, v, w_in);

    /*
      get the obstruction
    */
    obs = embedg_recover_obstruction(embed_graph, n, m, nbr_e_obs);

    /*
      and check it
    */
    if (!embedg_check_recov_obs(obs, n, m))
    {
        sparseg_dlcl_delete(obs, n);
        DIE();
    }

    sparseg_dlcl_to_sparseg(obs, n, *nbr_e_obs, OV, OA);
    sparseg_dlcl_delete(obs, n);

    /*
      just for the sake of it, chcek if the obstruction is
      a subgraph of the input graph
    */
    if (!sparseg_adjl_sub(*OV, n, *OA, V, n, A))
    {
        DIE();
    }

    IF_DEB_OBS(
               sparseg_adjl_print(*V, n, *A, FALSE);
               )

    IF_CPU(
           fprintf(stdout, "CPU for obstruction recovering %f\n",
                   (time_current_user() - sttime));
           )
}







minor
embedg_mark_obstruction (
    t_dlcl **dfs_tree,      /* a sparse graph rep. for the dfs tree
                                      -- vertices are as DFIs
                                      -- and children are ordered wrt
                                      lowpoint value
                                  */
    t_dlcl **back_edges,    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      (vertices are given as DFIs)
                                  */
    t_ver_edge *embed_graph,    /* output of tester */
    int n,               /* size of the graph */
    int *edge_pos,       /* pos. in embed_graph for addition
                                     of the next edge */
    int v,
    int w_in         /* the unembedded directed back edge
                                     [w_in, v]
                                   */
)
    /*
      the graph is non planar: we must mark & recover the K33 or K5
      homeomorph
    */
{
    int          c, vr, x, y, w;
    int          *path_v, *path_e, nbr_v, entry_in_path_e;
    boolean      px_attached_high, py_attached_high, is_minor_D;
    minor        m;


  IF_CPU(
    float      sttime; float time_to_now;

    sttime = time_current_user();
        )


    /*
      find c such that v^c is the root of the biconnected
      component on which the walkdown failed
    */
    c = embedg_iso_get_c_of_v(embed_graph, n, v, w_in);

    /*
      now: decide which minor we are dealing with and mark the
      appropriate one (vertices/edges marked as MARK_MINOR(n)
      in embed_graph)
    */
    if (embedg_iso_is_minor_A(embed_graph, n, edge_pos, v, c, &vr))
    {
        embedg_mark_minor_A(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, c, vr);

        IF_DEB_MINOR(
                     fprintf(stdout, "Minor A\n");
                     )

        return MINOR_A;
    }

    /*
      get the externally active vertices x & y and the pertinent w
      on the external face of the bicomp rooted by v^c

      and determine if minor B
    */
    if (embedg_iso_is_minor_B(embed_graph, n, edge_pos, v, c,
                                   &x, &y, &w))
    {
        embedg_mark_minor_B(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, c,
                            x, y, w);
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor B\n");
                     )

        IF_CPU(
               fprintf(stdout, "CPU for obstruction isolation %f\n",
                       time_current_user() - sttime);
               )

        return MINOR_B;
    }

    /*
      the remaining cases: must get the highest x-y path

      it will be containing in path_v (vertices), path_e (edges)
    */
    embedg_iso_get_highest_x_y_path(embed_graph, n, MARK_EXT_FACE(n),
                                    MARK_EXT_FACE_L(n),
                                    MARK_EXT_FACE_R(n),
                                    v, c, x, y, w,
                                    &path_v, &path_e,
                                    &nbr_v, &entry_in_path_e,
                                    &px_attached_high,
                                    &py_attached_high,
                                    &is_minor_D);

    /*
      we are in the minor C case if either one of p_x or p_y
      is attached high
    */
    if (px_attached_high || py_attached_high)
    {
        embedg_mark_minor_C(dfs_tree, back_edges, embed_graph, n, edge_pos,
                            v, c, x, y, w,
                            path_v, path_e, nbr_v,
                            px_attached_high, py_attached_high);
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor C\n");
                     )

        mem_free(path_v);
        mem_free(path_e);

        IF_CPU(
               fprintf(stdout, "CPU for obstruction isolation %f\n",
                       time_current_user() - sttime);
               )

        return MINOR_C;
    }

    if (is_minor_D)
    {
        embedg_mark_minor_D(dfs_tree, back_edges, embed_graph, n, edge_pos,
                            v, c, x, y, w,
                            path_v, path_e, nbr_v, entry_in_path_e);
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor D\n");
                     )

        mem_free(path_v);
        mem_free(path_e);

        IF_CPU(
               fprintf(stdout, "CPU for obstruction isolation %f\n",
                       time_current_user() - sttime);
               )

        return MINOR_D;
    }

    /*
      finally, the minor E case
    */
    m = embedg_mark_minor_E(dfs_tree, back_edges, embed_graph, n, edge_pos,
                            v, c, x, y, w,
                            path_v, path_e, nbr_v);
    switch (m)
    {
    case MINOR_E1:
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor E1\n");
                     )
        break;
    case MINOR_E2:
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor E2\n");
                     )
        break;
    case MINOR_E3:
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor E3\n");
                     )
        break;
    case MINOR_E4:
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor E4\n");
                     )
        break;
    case MINOR_E5:
        IF_DEB_MINOR(
                     fprintf(stdout, "Minor E5\n");
                     )
        break;
    case MINOR_A:
    case MINOR_B:
    case MINOR_C:
    case MINOR_D:
    case MINOR_E:
    case NBR_MINORS:
        break;
    }

    mem_free(path_v);
    mem_free(path_e);

    IF_CPU(
           fprintf(stdout, "CPU (scaled) for obstruction isolation %f\n",
                   (time_current_user() - sttime) / e);
           )

    return m;
}
/*
 *  isolator.c
 */

/*
  What:
  *****

  Implementing:

  The graph is non planar: we isolate the obstruction.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}
#define IF_DEB_EDGES(x) {}
#define IF_CPU(x) {}
/* #define IF_DEB_MINOR(x) {x}  -- Not Used  */


/* aproto: header embed_graph_protos.h */

#ifndef PLANAR_IN_MAGMA
#endif




int
embedg_iso_get_c_of_v (t_ver_edge *embed_graph, int n, int v, int w)
    /*
      the edge [v, w] (w a descendant of v) remains unembedded
      after the walkdown returns

      find c such that v^c is the root of the biconnected
      component on which the walkdown failed
    */
{
    /*
      how to do this??? easy! follow the DFS tree path as given
      by the field DFS_parent
    */

    int           u;

    u = embed_graph[w].DFS_parent;
    while (embed_graph[u].DFS_parent != v)
    {
        u = embed_graph[u].DFS_parent;
    }
    /*
      this is guaranteed to succeed given the structure of the DFS tree
      and the fact that there exists a  back edge [w, v]
    */

    return u;
}


boolean
embedg_iso_is_minor_A (t_ver_edge *embed_graph, int n,
	int *edge_pos, int v, int c, int *vr)
    /*
      determines if the obstruction is a minor A
    */
{
    /*
      to do this we again call the walkdown routine with v^c as input,
      the walkdown routine will fail (since there will be an
      un-embedded back edge incident to v and to a vertex
      in the subtree rooted by v^c)

      the obstruction is a minor A if the merge queue returned by the
      walkdown is non-empty, if this is the case we return
      the bicomp last appended to the queue
    */
    int             vv;
    t_merge_queue   q;

    vv = c + n;

    q = embedg_walkdown(embed_graph, n, edge_pos, vv);
    /*
      we MUST remove the SCEs here: this is the only place where it
      will be done when looking for and recovering an obstruction

      this is safe since this very function applies to ALL cases!
    */
    embedg_remove_SCE(embed_graph, n, *edge_pos);

    if (!embedg_merge_queue_empty(q))
        /*
          the bicomp of interest is the last in the queue
        */
    {
        int         r, rin, vrout;

        embedg_merge_queue_prune(&q, &r, &rin, vr, &vrout);
        embedg_merge_queue_delete(q);
        return TRUE;
    }
    else
    {
        embedg_merge_queue_delete(q);
        return FALSE;
    }
}


void
embedg_iso_get_x_y_w (t_ver_edge *embed_graph, int n, int v, int r,
	int c, int mark, int mark_l, int mark_r, int *x, int *y, int *w)
    /*
      the obstruction is one of minor B, C, D, E.

      get the externally active vertices x & y along the
      external face  paths starting at r^c

      get a pertinent vertex w along the lower external
      face path between x and y

      external activity and pertinence are wrt v

      all the vertices on the external face r^c...x...w
      and r^c...y...w will be marked (the visited field)
    */
{
    int          vr, vrin, x_y[4];
    int          s, sin, cur, curin;

    vr = c + n;

    /*
      find x and y first:

      note that we mark the vertices on the external face r^c...x
      and r^c...y

      more on that below
    */
    embed_graph[vr].visited = mark;
    for (vrin = 0; vrin <= 1; vrin++)
    {
        int      m;

        m = vrin == 0 ? mark_l : mark_r;
        embedg_VES_get_succ_ext_active_on_ext_face(embed_graph, n, v,
                                                        vr, vrin,
                                                        TRUE, m,
                                                        &s, &sin);
        x_y[vrin] = s;
        x_y[vrin + 2] = sin;
        /*
          note the bizarre way I store the active vertex
          and the direction out of which to continue a walk
          on the lower external face as described above
        */
    }
    *x = x_y[0];
    *y = x_y[1];

    /*
      next get the pertinent w on the lower external face from x to y
    */
    cur = x_y[0];
    curin = x_y[2];
    embedg_VES_get_succ_pertinent_on_ext_face(embed_graph, n, v,
                                                   cur, curin,
                                                   TRUE, mark_l, w, &sin);

    /*
      now all the vertices  r^c...x...w and r^c...y have been marked,
      it remains to mark the vertices on the y...w external face path

      (will need to be able to distinguish the external face  later on)

      Note the way the external face is marked (needed when recovering
      the highest x-y path):
      mark_l for the path v^c...x...w
      mark_r for the path v^c...y
      mark for the lower external face y...w
    */
    cur = x_y[1];
    curin = x_y[3];
    s = n;
    while (s != *w)
    {
        embedg_VES_get_succ_pertinent_on_ext_face(embed_graph, n, v,
                                                       cur, curin,
                                                       TRUE, mark, &s, &sin);
        cur = s;
        curin = sin;
    }

    IF_DEB(
           fprintf(stdout, "get x, y & w: the external face\n");
           fprintf(stdout, "%d\t", vr);
           cur = vr;
           curin = 0;
           while (s != vr)
           {
               embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                                    cur, curin,
                                                    FALSE, 0, &s, &sin);
               cur = s;
               curin = sin;
               fprintf(stdout, "%d\t", s);
           }
           fprintf(stdout, "\n");
           )
}




boolean
embedg_iso_is_minor_B (t_ver_edge *embed_graph, int n, int *edge_pos,
	int v, int c, int *x, int *y, int *w)
    /*
      determines if the obstruction is a minor B and return x, y
      (ext. active) and w (pertinent)
    */
{
    /*
      get x & y the ext. active vertices on the (external face)
      path out of v^c,
      and w the pertinent vertex on the lower external face x-y

      PLUS mark the whole external face with MARK_EXT_FACE(n)
    */
    embedg_iso_get_x_y_w(embed_graph, n, v, v, c,
                              MARK_EXT_FACE(n),
                              MARK_EXT_FACE_L(n), MARK_EXT_FACE_R(n),
                              x, y, w);

    if (embedg_dlcl_is_empty(embed_graph[*w].pertinent_bicomp_list))
        /*
          w has no pertinent child bicomp: not a minor B
        */
        return FALSE;
    else
    {
        t_dlcl      *pert_l;
        int         l;

        pert_l = embed_graph[*w].pertinent_bicomp_list;
        l = embedg_dlcl_list_last(pert_l)->info;
        /*
          if w has an ext. active pertinent child bicomp then minor B

          note that we need to know if w has an ext. active AND pertinent
          bicomp child: so it is NOT good enough to test
          w's separated_DFS_child_list as is done in
          embedg_VES_is_ver_ext_active!!!!!!!!!

          PLUS: l is actually a VIRTUAL vertex: to check its lowpoint
          I must take its DFS child l - n !!!!!!!!
        */
        ASSERT(embedg_VES_is_virtual_vertex(n, l));
        l = l - n;
        return embed_graph[l].lowpoint < v ? TRUE : FALSE;
    }
}

void
embedg_iso_get_highest_x_y_path (
    t_ver_edge *embed_graph,
    int n,
    int mark,
    int mark_l,
    int mark_r,
    int v,
    int c,
    int x,
    int y,
    int w,
    int **path_v,     /* stack of vertices in x-y path */
    int **path_e,     /* stack of egdes in x-y path */
    int *nbr_v,         /* number of vertices in path_v */
    int *entry_in_path_e, /* the in direction for the FIRST edge in
                                      path_e: needed later on *sigh*
                                   */
    boolean *px_attached_high,
    boolean *py_attached_high,
    boolean *is_minor_D
)
    /*
      the obstruction is one of minor C, D, E.

      we want to recover the highest x-y path:
      the obstructing path attached to the external faces v^c - x - w
      and v^c - y - w

      while doing all this we also determine if the case is a minor C
      or a minor D
    */
{
    /*
      the path is obtained by walking the proper face starting at v
      where ALL the edges incident to v^c BUT the ones bordering
      the external face have been removed

      I won't I don't think remove these edges, but instead I'll be
      implementing an "avoidance" walk
    */

    int          vv, s, sin, p_x, p_y, cur_v, cur_vin;
    int          e, ein, s_e, s_ein;
    boolean      avoid_vv;

    /*
      must start the walk at edge embed_graph[v^c].link[1 ^ 0],
      (vvin = 0 is in direction of x, see embedg_iso_get_x_y_w)
    */
    vv = c + n;
    e = embed_graph[vv].link[1];
    ein = 0;     /* because of adjacency list consistency */

    *path_v = (int *) mem_malloc(sizeof(int) * n);
    *path_e = (int *) mem_malloc(sizeof(int) * n);
    (*nbr_v) = -1;

    /*
      recall that in embedg_iso_get_x_y_w we did mark
      (with mark, mark_l, mark_r)
      ALL the vertices lying on the external face walk starting
      & ending at v^c: we will use this fact to enable us
      to decide if a vertex is on the external face
      (as opposed to being on the internal face)
    */

    s = embed_graph[e].neighbour;
    ASSERT(embed_graph[s].visited == mark_l);
    /*
       this must be the case since s lies on the external face
       starting at v^c in x's direction
      -- we push s onto the stack
    */
    (*path_v)[++(*nbr_v)] = s;

    /*
      start the proper face walk which "avoids" v^c since the
      internal edges incident to v^c are supposed to have
      been removed

      please read on
    */
    avoid_vv = FALSE;
    while (TRUE)
    {
        boolean      av;

        av =
            embedg_VES_get_succ_on_proper_face_with_avoidance(
                                                          embed_graph, n,
                                                          e, ein, vv,
                                                          FALSE, 0,
                                                          &s, &s_e, &s_ein);
        avoid_vv = av == TRUE ? av : avoid_vv;
        if (embed_graph[s].visited == mark_l)
            /*
              means that s is still on the external face:
              empty the path's stack and push s
            */
        {
            (*nbr_v) = -1;
            (*path_v)[++(*nbr_v)] = s;
            e = s_e;
            ein = s_ein;
        }
        else if (*nbr_v == 0)
            /*
              s is the first encountered vertex after
              path_v[0] which does not
              lie on the external face v^c...c...w

              given the way we pushed things on the vertex stack, path_v[0]
              will be the point of attachement of the x-y path
              on the v^c...x...w external face

              path_e[0] will contain nothing: a dummy

              path_e[1] will be the first edge in the x-y path
              (and entry_in_path will give the in-direction to this edge)

              oh yes!, we break the loop at this point if
              the vertex s lies on the v^c...y...w external face
            */
        {
            ASSERT(embed_graph[(*path_v)[0]].visited == mark_l);
            /*
              the first vertex on the path must be on the
              v^c...x...w external face
            */
            (*path_v)[++(*nbr_v)] = s;
            /*
              and now we also push the edge on the edge stack

              I'll need this later to initiate a proper face walk
              starting at the first vertex/edge in the x-y path,
              which is the same as starting from s_e
            */
            (*path_e)[*nbr_v] = s_e;
            *entry_in_path_e = s_ein;
            e = s_e;
            ein = s_ein;

            /*
              since we are at the start of the path, we must not
              forget to reset avoid_vv
            */
            avoid_vv = FALSE;

            if (embed_graph[s].visited == mark_r
                || embed_graph[s].visited == mark)
                /*
                  we have reached the v^c...y...w external face:
                  we can stop here
                */
            {
                break;
            }

            /*
              if not finished yet,
              we also mark s (and path_v[0]) as visited:
              later on we'll need to recognise which of the vertices
              in path have already been encountered
              (in case of encountering a cut-vertex due to the
              "removal" of the "internal" edges incidnet ot v^c)

              note that we mark s as visited iff s if not already
              on the v^c..y..w external face
            */

            ASSERT(embedg_VES_is_vertex(n, (*path_v)[0]));
            ASSERT(embedg_VES_is_vertex(n, s));

            embed_graph[s].visited = MARK_X_Y_PATH(n);
        }
        else  if (embed_graph[s].visited == MARK_X_Y_PATH(n))
            /*
              this means that s is a cut vertex on the internal
              face walk: pop all the vertices from path
              until s's last occurrence in path
            */
        {
            ASSERT((*nbr_v) >= 0);
            while ((*path_v)[(*nbr_v)] != s)
            {
                (*nbr_v)--;
                ASSERT((*nbr_v) >= 0);
                /*
                  note that s should be somewhere in path!
                */
            }
            /*
              note also that popping from path_v also implies
              popping from path_e
            */
            e = s_e;
            ein = s_ein;
        }
        else
            /*
              we push s and s_e on their respective stacks
            */
        {
            (*path_v)[++(*nbr_v)] = s;
            (*path_e)[*nbr_v] = s_e;
            e = s_e;
            ein = s_ein;

            if (embed_graph[s].visited == mark_r
                || embed_graph[s].visited == mark)
                /*
                  again, s lies on the v^c...y...w external face:
                  we end the walk: path_v now contains the highest x-y path

                  note that there can be no conflict between
                  mark_r or mark and MARK_X_Y_PATH(n) since
                  we mark with MARK_X_Y_PATH iff the vertex
                  is NOT marked with mark_r/mark!
                */
            {
                break;
            }
            else
                /*
                  we must mark this vertex as MARK_X_Y_PATH since we aren't
                  finished yet
                */
            {
                embed_graph[s].visited = MARK_X_Y_PATH(n);
            }
        }
    }

    /*
      there is only one thing remaining to do: see if p_x or
      p_y are attached high
      (ie closer to v^c than x or y resp.)

      we walk the external face starting at v^c in y's direction
      (again see embedg_iso_get_x_y_w)
    */
    *px_attached_high = TRUE;
    p_x = (*path_v)[0];
    /*
      p_y denotes the attachement point of the x-y path
      on the v^c...y...w external face
    */

    s = n;
    cur_v = vv;
    cur_vin = 0;
    while (s != p_x)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                             cur_v, cur_vin,
                                             FALSE, 0, &s, &sin);
        if (s == x)
        {
            *px_attached_high = FALSE;
            break;
        }
        cur_v = s;
        cur_vin = sin;
    }

    *py_attached_high = TRUE;
    p_y = (*path_v)[*nbr_v];
    /*
      p_y denotes the attachement point of the x-y path
      on the v^c...y...w external face
    */

    s = n;
    cur_v = vv;
    cur_vin = 1;
    while (s != p_y)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                             cur_v, cur_vin,
                                             FALSE, 0, &s, &sin);
        if (s == y)
        {
            *py_attached_high = FALSE;
            break;
        }
        cur_v = s;
        cur_vin = sin;
    }

    /*
      now we are in the minor C case if either p_x or p_y are
      attached high

      the minor D case:
      this happens when there is a path v^c - z where z lies
      on the x-y path

      that is, when

      either v^c has been effectively "avoided" within the
      embedg_VES_get_succ_on_proper_face_with_avoidance function
      BUT ONLY if this "avoidance" happened AFTER having
      encountered the very first vertex on the x-y path!

      or when a cut vertex has been encountered on the x-y path:
      separable components on this walk can only occur
      if one walks the face while skipping the edges incident to v^c

      in any case this means that checking the return from
      the embedg_VES_get_succ_on_proper_face_with_avoidance function
      is enough: this is the purpose of avoid_vv.
    */

    *is_minor_D = !(*px_attached_high || *py_attached_high) && avoid_vv;


    IF_DEB(
           int    i;

           fprintf(stdout, "x-y path\t");
           for (i = 0; i <= *nbr_v; i++)
               fprintf(stdout, "%d\t", (*path_v)[i]);
           fprintf(stdout, "\n");
           )
}


/*
 *  embedg_misc.c
 */

/*
  What:
  *****

  Implementing:

  Some high level routinse for the VES structure.
  See VES_misc.c.


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}



/* aproto: header embed_graph_protos.h */

#ifndef PLANAR_IN_MAGMA
#endif




void
embedg_VES_delete (t_ver_edge *embed_graph, int n)
{
    int          i;

    for (i = 0; i < n; i++)
    {
        embedg_dlcl_delete(embed_graph[i].separated_DFS_child_list);
        /*
          embedg_dlcl_delete(embed_graph[i].rep_in_parent_list);

          NO!!! this points to something in separated_DFS_child_list
        */
        embedg_dlcl_delete(embed_graph[i].pertinent_bicomp_list);
    }
    mem_free(embed_graph);
}



void
embedg_VES_print (t_ver_edge *embed_graph, int n)
{
    int          i;

    fprintf(stdout, "vertices\n");
    for (i = 0; i < n; i++)
    {
        t_ver_edge   rec;

        rec = embed_graph[i];

        fprintf(stdout, "\nDFI\t%d\tlabel\t%d\n", i, rec.label);
        fprintf(stdout, "DFS parent\t%d\tleast_a\t%d\tlowpoint\t%d\n",
                rec.DFS_parent, rec.least_ancestor, rec.lowpoint);
        fprintf(stdout, "separated_DFS_child_list\n");
        embedg_dlcl_print(rec.separated_DFS_child_list);
    }

    fprintf(stdout, "\nvirtual vertices\n");
    for (i = n; i < 2*n; i++)
    {
        int          c;

        c = i - n;
        fprintf(stdout, "%d^%d\t", embed_graph[c].DFS_parent, c);
    }
    fprintf(stdout, "\n");

    embedg_VES_print_bigcomps(embed_graph, n);
}


void
embedg_VES_print_bigcomps (t_ver_edge *embed_graph, int n)
    /*
      walking the external faces of all the bicomp; for testing only
    */
{
    int          i;

    fprintf(stdout, "bicomponents\n");
    /*
      to get to the bicomps, it makes sense to start at the
      virtual vertices????
    */
    for (i = n + 1; i < 2*n; i++)
        /*
          a note of caution: there is no virtual vertex at
          embed_graph[n] since that would mean a virtual vertex x^0
          which makes no sense (0 is the root of the dfs_tree)
        */
    {
        embedg_VES_walk_bicomp(embed_graph, n, i, 0);
    }
    fprintf(stdout, "\n");
}
/*
 *  planar_alg_init.c
 */

/*
  What:
  *****

  Implementing:

  Initialising the embed_graph aka VES data structure from the information
  collected from the DFS.

  The embed_graph/VES data structure is an array consisting of vertices,
  virtual vertices and edges;
  vertices, virtual vertices and edges share a common record structure;
  one of the particular features is that any vertex is linked
  together with its incident edges into a doubly circular linked list.

  See also VES_misc.c.

  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/

#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_DFS(x) {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}
#define IF_CPU(x) {}


/* aproto: header embed_graph_protos.h */

/* aproto: beginstatic -- don't touch this!! */
static void embedg_init_insert_TE (t_ver_edge *, int, int *, t_dlcl *);
/* aproto: endstatic -- don't touch this!! */

#ifndef PLANAR_IN_MAGMA
#endif


t_ver_edge *
embedg_planar_alg_init (
    t_ver_sparse_rep *V,
    int n,
    t_adjl_sparse_rep *A,        /* input sparse graph */
    int *nbr_c,        /* size of the graph, #components*/
    int *edge_pos,        /* pos in the struct where the last edge
                                      has been inserted
                                   */
    t_dlcl ***dfs_tree,      /* a sparse graph rep. for the dfs tree
                                      -- vertices are as DFIs
                                   */
    t_dlcl ***back_edges,    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      -- vertices are as DFIs
                                   */
    t_dlcl ***mult_edges    /* for each vertex v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v
                                      -- vertices are as DFIs
                                   */
)
    /*
      initialising embed_graph, the fundamental data structure
      underpinning the tester and obstruction isolator

      from there on, a vertex is exclusively referred to by its DFI!!
      -- so forget about labels
    */
{
    int          *dfs_nbr;        /* dfs numbering for each vertex */
    int          *dfs_order;      /* vertices in dfs order */
    int          *lowpoint;       /* lowpoint value for each DFI */
    int          *dfs_parent;     /* for each DFI, its DFS ancestor
                                     as a DFI (DFS index)
                                  */
    int          *least_a;        /* for each DFI, its least ancestor's DFI
                                     (via a back edge exclusively)
                                  */

    t_ver_edge   *embed_graph;
    int          i;


  IF_CPU(
    float      sttime;  float time_to_now;

    sttime = time_current_user();
       )

    ASSERT(n >= 1);

    /*
      DFS and lowpoint calculations + ordering
    */
    sparseg_adjl_dfs_preprocessing(V, n, A, nbr_c,
                                   &dfs_nbr, &dfs_order, &lowpoint,
                                   dfs_tree, back_edges,
                                   &dfs_parent, &least_a, mult_edges);

    IF_CPU(
           fprintf(stdout, "CPU for DFS only %f\n",
                   (time_current_user() - sttime));
    sttime = time_current_user();
           )

    IF_DEB_DFS(
            fprintf(stdout, "DFS indices\n");
            for (i = 0; i < n; i++)
            fprintf(stdout, "%d ", dfs_nbr[i]);
            fprintf(stdout, "\n");

            fprintf(stdout, "DFS order\n");
            for (i = 0; i < n; i++)
            fprintf(stdout, "%d ", dfs_order[i]);
            fprintf(stdout, "\n");

            fprintf(stdout, "lowpoint values\n");
            for (i = 0; i < n; i++)
            fprintf(stdout, "%d ", lowpoint[i]);
            fprintf(stdout, "\n");
            );

    IF_VERB(
            fprintf(stdout, "DFS parent\n");
            for (i = 0; i < n; i++)
                fprintf(stdout, "%d ", dfs_parent[i]);
            fprintf(stdout, "\n");
            );

    IF_VERB(
            fprintf(stdout, "least ancestors\n");
            for (i = 0; i < n; i++)
                fprintf(stdout, "%d ", least_a[i]);
            fprintf(stdout, "\n");
            );

    IF_VERB(
            for (i = 0; i < n; i++)
            {
                fprintf(stdout, "the list of children ordered by lowpoint for %d\n",
                        i);
                embedg_dlcl_print((*dfs_tree)[i]);
            }
            );

    IF_DEB_DFS(
            fprintf(stdout, "the tree edges\n");
            sparseg_dlcl_print(*dfs_tree, n);

            fprintf(stdout, "the back edges\n");
            sparseg_dlcl_print(*back_edges, n);

            fprintf(stdout, "multiple edges\n");
            sparseg_dlcl_print(*mult_edges, n);
            );

    /*
      create the data structure for the embedded graph:
      it will have (max) size 2*n + 2 * MAXE(n)

      we will see that that number of edges is sufficient
      even when later adding short-cut edges (see embedg_walkdown)
    */
    embed_graph = (t_ver_edge *) mem_malloc(sizeof(t_ver_edge)
                                            * (2*n + 2 * MAXE(n)));
    /*
      initialisation
    */
    for (i = 0; i < 2*n + 2 * MAXE(n); i++)
        /*
          some fields are initialised to n as n is actually
          an "invalid" value
        */
    {
        t_ver_edge   rec;

        rec.label = NIL;
        rec.DFS_parent = n;
        rec.least_ancestor = n;
        rec.lowpoint = n;
        rec.separated_DFS_child_list = NP;
        rec.rep_in_parent_list = NP;
        rec.pertinent_bicomp_list = NP;
        rec.adjacent_to = n;
        rec.visited = n;
        rec.neighbour = n;
        rec.in_adjl = NIL;
        rec.twin_in_adjl = NIL;
        rec.mult = 0;
        rec.type = NIL;
        rec.sign = NILSIGN;
        /*
          make the links refer back to self
        */
        rec.link[0] = rec.link[1] = i;

        embed_graph[i] = rec;
    }

    /*
      embed_graph[0..n-1]: the n vertices
      ATTENTION: the vertices are stored according to their DFS numbering
    */
    for (i = 0; i < n; i++)
    {
        t_ver_edge   rec;

        rec = embed_graph[i];

        rec.label = dfs_order[i];
        rec.DFS_parent = dfs_parent[i];
        rec.least_ancestor = least_a[i];
        rec.lowpoint = lowpoint[i];
        rec.separated_DFS_child_list = embedg_dlcl_copy((*dfs_tree)[i]);

        IF_VERB(
                fprintf(stdout, "the list of children ordered by lowpoint for DFI %d\n",
                        i);
                embedg_dlcl_print(rec.separated_DFS_child_list);
        );

        embed_graph[i] = rec;
    }

    /*
      one more thing to do for these vertices:
      fix the rep_in_parent_list field
    */
    for (i = 1; i < n; i++)
    {
        t_dlcl       *parent_list, *rep;
        int          parent;

        parent = embed_graph[i].DFS_parent; /* careful: this is a DFI  */
        /*
          recall that the vertices in embed_graph are accessed via their DFI
        */

        if (parent != n)
            /*
              when parent == n this means that i the root of a DFS tree
              in the disconnected graph
            */
        {
            parent_list = embed_graph[parent].separated_DFS_child_list;
            rep = embedg_dlcl_find(parent_list, i);
            ASSERT(rep != NP);
            embed_graph[i].rep_in_parent_list = rep;
        }
    }

    /*
      embed_graph[n..2*n-1]: the n virtual vertices
      do I need to do anything here?????

      no - I don't think so

      let's try to explain what virtual vertices are:
      let v^c be a virtual vertex:
      - it is at position  c + n in the array,
      - c is the DFS child of v,
      - v can be retrieved by taking embed_graph[c].DFS_parent,
      - v^c is said virtual as long as the bicomp rooted by v^c is not
        merged with the vertex v
      - once v is merged (identified?) with v^c, then v^c
        is of no relevance anymore

      below we will see that we embed all the tree edges as singleton
      bicomps (bicomponent): (0^1, 1), (1^2, 2) etc...:
      this is what virtual vertices are there for:
      to distinguish them from their "real" counterpart with
      which they will be ultimately merged

      the primary reason for this is:
      while testing for planarity virtual vertices are the roots of bicomps
    */

    /*
      now the edges:
      we actually embed the tree edges so that each tree edge
      forms a (singleton) biconnected component

      embedding an edge in effect means creating the
      doubly linked circular list of [virtual] vertices & the edges incident
      to it

      this list is built using the links 0 & 1 in embed_graph[i]
    */

    /*
      for each tree edge (v,u) we embed (v^u, u) (v^u is the virtual vertex)

      CAREFUL: when talking about vertex v say,
      we mean the vertex with DFI v, and NOT the vertex with label v
      **************************************************************
    */
    *edge_pos = 2*n - 1;
    /*
      edge_pos will tell us where to insert the next edge in embed_graph[]
    */
    for (i = 0; i < n; i++)
    {
        t_dlcl     *te_l, *p;

        te_l = (*dfs_tree)[i];
        p = te_l;

        if (!embedg_dlcl_is_empty(p))
        {
            /*
              the test below is a bit stupid... well...
            */
            ASSERT(embed_graph[p->info].DFS_parent == i);

            embedg_init_insert_TE(embed_graph, n, edge_pos, p);
            p = embedg_dlcl_list_next(p);
            while (p != te_l)
            {
                ASSERT(embed_graph[p->info].DFS_parent == i);
                embedg_init_insert_TE(embed_graph, n, edge_pos, p);

                p = embedg_dlcl_list_next(p);
            }
        }
    }

    mem_free(dfs_nbr);
    mem_free(dfs_order);
    mem_free(lowpoint);

    mem_free(dfs_parent);
    mem_free(least_a);

    IF_CPU(
           fprintf(stdout, "CPU for remainder of initialisation %f\n",
                   (time_current_user() - sttime));
           )

    return embed_graph;
}


static void
embedg_init_insert_TE (t_ver_edge *embed_graph, int n, int *edge_pos, t_dlcl *p)
    /*
      init and insert a tree edge in embed graph:

      the tree edge will form a singleton bicomponent (v^c, c)
      where c is p->info and v is c.DFS_parent
    */
{
    int             c, v;

    c = p->info;
    v = embed_graph[c].DFS_parent;
    ASSERT(v >= 0 && v < n);

    /*
      now (v, c) is a tree edge; embed the directed edge [v^c, c]

      -- and recall that v^c is a virtual vertex, at position  c + n
      in embed_graph, and that vertex c is at position c
    */

    /*
      first, set this edge with the appropriate info
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = c;
    embed_graph[*edge_pos].in_adjl = p->in_adjl;
    embed_graph[*edge_pos].twin_in_adjl = p->twin_in_adjl;

    ASSERT(p->mult % 2 == 0);
    /*
      we want the number of undirected edges
    */
    embed_graph[*edge_pos].mult = p->mult / 2;
    embed_graph[*edge_pos].type = TE;
    embed_graph[*edge_pos].sign = CCLOCKW;

    /*
      link this with vertex v^c in a doubly linked circular list
    */
    embed_graph[c + n].link[0] =
        embed_graph[c + n].link[1] = *edge_pos;
    embed_graph[*edge_pos].link[0] =
        embed_graph[*edge_pos].link[1] = c + n;

    /*
      now create/set the twin edge, the directed edge [c, v^c]
    */
    (*edge_pos)++;
    ASSERT(*edge_pos < 2*n + 2 * MAXE(n));
    embed_graph[*edge_pos].neighbour = c + n;
    embed_graph[*edge_pos].in_adjl = p->twin_in_adjl;
    embed_graph[*edge_pos].twin_in_adjl = p->in_adjl;
    embed_graph[*edge_pos].mult = p->mult / 2;
    embed_graph[*edge_pos].type = TE;
    embed_graph[*edge_pos].sign = CCLOCKW;

    /*
      and link it with vertex c in a doubly linked circular list
    */
    embed_graph[c].link[0] = embed_graph[c].link[1] = *edge_pos;
    embed_graph[*edge_pos].link[0] =
        embed_graph[*edge_pos].link[1] = c;
}
/*
 *  dfs_preprocessing.c
 */

/*
  What:
  *****

  Implementing:

  A DFS as an initialisation step for the planarity tester.
  This is an especially beefed up DFS that collects lots of
  marginal information:

  - a DFS tree as a list of DFS children for each vertex
  - the DFS children are sorted according to their lowpoint value
  - a back_edge structure as a list of descendants v for each
    vertex u such that [v, u] is a back edge
  - a multiple edges structure which stores multiple (directed) edges
    NOT in the DFS tree nor in the back_edge struc, and loops

  - the vertices in DFS order
  - the DFS index (DFI) for each vertex
  - the lowpoint value for each vertex
  - the number of components of the (possibly disconnected) graph
  - for each vertex, its DFS parent
  - for each vertex v, its least ancestor u such that [v, u]
    is a back edge

  ALL info above (except the vertices in DFS order) is given
  in terms of the vertices' DFIs and NOT their labels.



  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


/*
  There are some dodgy things which need some thought; it would be nice
  to fix them so that the code get's cleaner:

  - we do store in_adj (and twin_in_adjl) for each directed edge:

    + this is ONLY needed at the time of recovering the embedding
      (see embedg_recover_embedding) and its sole use is to establish
      a link between an edge in the embedding structure
      t_embed_sparse_rep  *E and the corresponding edge
      in the t_adjl_sparse_rep   *A struc.

    + well, I cannot recall why I thought this correspondence
      was needed in the first place and it might well be the case
      that there is no use for it; in which case recovering the
      embedding is simplified
      (we would store the end-vertex in the embedding's edges instead
      of their index in the adjacency list)

  - there are some non-linear bits in the DFS below: when searching
    for an already existing tree/back/multiple edge.
    I couldn't fix this in less then one hour so I leave it as it is...
    for now.

    This shouldn't be a major issue, overall timings of the planarity
    tester do not show this non-linear "bump"...

  - also, this algorithm has been growing incrementally and I now
    realise that I am using some redundant data structures:
    for example visited[] and the vertex and could be dispensed with...
    ...more things to clean up...

    Paulette  07/02/02
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}


/* aproto: header embed_graph_protos.h */

#ifndef PLANAR_IN_MAGMA
#endif


void
sparseg_adjl_dfs_preprocessing (
    t_ver_sparse_rep *V,
    int n,                /* size of the graph */
    t_adjl_sparse_rep *A,        /* input sparse graph */
    int *c,               /* nbr of components */
    int **dfs_nbr,        /* dfs numbering for each vertex */
    int **dfs_order,      /* vertices in dfs order */
    int **lowpoint,       /* lowpoint value for each DFI */
    t_dlcl ***dfs_tree,      /* a sparse graph rep. for the dfs tree:
                                      for each DFI, a list of its children's
                                      DFI ordered wrt their lowpoint values
                                   */
    t_dlcl ***back_edges,    /* for each DFI  v, a dlcl
                                      of the back edges [v, x] incident to v
                                      where x is a DESCENDANT of v */
    int **dfs_parent,     /* for each DFI its DFS ancestor */
    int **least_a,        /* for each DFI, its least ancestor's DFI
                                      via a back edge exclusively */
    t_dlcl ***mult_edges    /*  for each DFI  v, a dlcl
                                       of the multiple directed
                                       edges NOT included
                                       in either dfs_tree or back_edges
                                   */
)

    /*
      in ALL the returned info above BUT dfs_order[] we store
      the vertices' DFIs (DFS indices) and NOT their labels!

      -- shuffling between labels and vertices can then be done
         via dfs_nbr[] and dfs_order[]
    */
{
    int            pos_v_stack, pos_e_stack, dfs_n;
    int            *visited, *vertex_stack, *edge_stack, *lowpoint_order;
    int            *TE_in_adjl, *TE_twin_in_adjl, *TE_mult;
    int            v, lp, cur, cur_e, next;
    t_dlcl         **temp, *lowpoint_list, **new_dfs_tree;

    /*
      create the dfs tree as a sparse graph
    */
    *dfs_tree = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);
    /*
      the DFS numbering for the vertices
    */
    *dfs_nbr = (int *) mem_malloc(sizeof(int) * n);
    /*
      the vertices as ordered by their DFS index
    */
    *dfs_order = (int *) mem_malloc(sizeof(int) * n);
    /*
      the lowpoint value for each DFI
    */
    *lowpoint = (int *) mem_malloc(sizeof(int) * n);

    /*
      the (directed) back edges
    */
    *back_edges = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);


    /*
      the DFS parent for each DFI
    */
    *dfs_parent = (int *) mem_malloc(sizeof(int) * n);
    /*
      the least ancestor (via a back edge exlusively) for each DFI
    */
    *least_a = (int *) mem_malloc(sizeof(int) * n);

    /*
      the (directed) multiple edges
    */
    *mult_edges = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);

    /*
      the vertices visited while DFS
    */
    visited = (int *) mem_malloc(sizeof(int) * n);
    /*
      stack of vertices: last current vertex
    */
    vertex_stack = (int *) mem_malloc(sizeof(int) * n);
    /*
      stack of (tree) edges: last added tree edge
    */
    edge_stack = (int *) mem_malloc(sizeof(int) * n);

    /*
      the following will be used in order to recreate the dfs_tree
      so that the DFS children of each DFI are ordered
      according to their lowpoint value
    */
    lowpoint_order = (int *) mem_malloc(sizeof(int) * n);
    temp = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);
    new_dfs_tree = (t_dlcl **) mem_malloc(sizeof(t_dlcl *) * n);

    /*
      finally, three more holding arrays: a trick to remember which
      tree edges we are talking about:

      when constructing dfs_tree, back_edges, mult_edges
      - we NEED to record the index in A (the adjacency list)
        of some of the edges and their twins/inverses
        we are currently storing in either of these structures
      - we also need to record the number of multiple (directed)
        edges we encounter  when the graph is not simple

      this is easy to do when storing back edges and multiple edges,
      and tree edges also: but this lattest set of neighbour lists (dfs_tree)
      is subsequently reordered so that DFS children are ordered
      wrt lowpoint values;
      - consequently the info about position in adjacency list
      and edge multiplicity are lost in the ordering process

      the two following arrays will remember the info we'll need later
      - more about this below
    */
    TE_in_adjl = (int *) mem_malloc(sizeof(int) * n);
    TE_twin_in_adjl = (int *) mem_malloc(sizeof(int) * n);
    TE_mult = (int *) mem_malloc(sizeof(int) * n);


    /*
      initialization of the data structures
    */
    for (v = 0; v < n; v++)
    {
        (*dfs_tree)[v] = (*back_edges)[v] = (*mult_edges)[v] = NP;
        visited[v] = TE_mult[v] = 0;
        (*dfs_parent)[v] = (*least_a)[v] = n;
        temp[v] = new_dfs_tree[v] = NP;
        TE_in_adjl[v] = TE_twin_in_adjl[v] = NIL;
        /*
          note that in the 3rd last statement n is considered
          as an "invalid" value;
          will be if importance in the overall algorithm
        */
    }

    /*
      the DFS tree is rooted at vertex 0
    */
    dfs_n = -1;
    pos_v_stack = -1;
    pos_e_stack = -1;
    *c = 0;
    for (v = 0; v < n; v++)
    {
        if (visited[v])
            /*
              we come only at this level when looking for
              a new subtree (when graph is disconnected)
            */
        {
            continue;
        }
        else
        {
            (*c)++;
        }

        cur = v;
        visited[cur] = 1;
        (*dfs_nbr)[cur] = ++dfs_n;
        (*lowpoint)[(*dfs_nbr)[cur]] = dfs_n;
        (*dfs_order)[dfs_n] = cur;

        cur_e = V[cur].first_edge == NIL ? NIL : V[cur].first_edge;
        while (TRUE)
        {
            if (cur_e != NIL)
            {
                t_dlcl        *existing_e;

                next = A[cur_e].end_vertex;
                if (!visited[next])
                    /*
                      adding tree edges (careful: directed edges)

                      AND tree edges are stored as
                      [dfs_nbr[u], dfs_nbr[cv]]
                      instead of [u, cv]: that is we store the edges
                      according to the vertices' DFIs
                    */
                {
                    IF_DEB_TREE(
                                io_printf("add tree edge %d\t%d\n",
                                          cur+1, next+1);
                                );

                    (*dfs_nbr)[next] = ++dfs_n;
                    (*lowpoint)[(*dfs_nbr)[next]] = dfs_n;
                    (*dfs_order)[dfs_n] = next;

                    sparseg_dlcl_append_to_neigh_list(*dfs_tree, n,
                                                      (*dfs_nbr)[cur],
                                                      (*dfs_nbr)[next],
                                                      NIL);
                    TE_in_adjl[(*dfs_nbr)[next]] = cur_e;
                    TE_mult[(*dfs_nbr)[next]]++;

                    /*
                      we push cur and the edge (cur, cur_e) on their
                      respective stacks
                    */
                    vertex_stack[++pos_v_stack] = cur;
                    edge_stack[++pos_e_stack] = cur_e;

                    /*
                      and mark next as visited
                    */
                    visited[next] = 1;

                    /*
                      update dfs_parent (always deal with DFIs rembember!)
                    */
                    (*dfs_parent)[(*dfs_nbr)[next]] = (*dfs_nbr)[cur];

                    /*
                      the DFS goes one level deeper
                    */
                    cur = next;
                    cur_e = V[cur].first_edge == NIL ?
                        NIL : V[cur].first_edge;
                }
                /*
                  the next three tests deal with multiple edges
                  and loops: apart from storing these (DIRECTED) edges
                  in mult_edges, we also need to update
                  the multipliciaty information about these edges
                */
                else if (sparseg_dlcl_is_adjacent(*dfs_tree, n,
                                                  (*dfs_nbr)[cur],
                                                  (*dfs_nbr)[next],
                                                  &existing_e))
                    /*
                      [cur, next] is a tree edge
                    */
                {
                    sparseg_dlcl_append_to_neigh_list(*mult_edges, n,
                                                      (*dfs_nbr)[cur],
                                                      (*dfs_nbr)[next],
                                                      cur_e);
                    TE_mult[(*dfs_nbr)[next]]++;

                    cur_e = A[cur_e].next; /* next in cur's adjacency list */
                }
                else if (sparseg_dlcl_is_adjacent(*back_edges, n,
                                                  (*dfs_nbr)[next],
                                                  (*dfs_nbr)[cur],
                                                  &existing_e))
                    /*
                      [cur, next] is a back edge
                    */
                {
                    sparseg_dlcl_append_to_neigh_list(*mult_edges, n,
                                                      (*dfs_nbr)[cur],
                                                      (*dfs_nbr)[next],
                                                      cur_e);
                    (existing_e->mult)++;

                    cur_e = A[cur_e].next; /* next in cur's adjacency list */
                }
                else if (next == cur)
                    /*
                      the case of a loop
                    */
                {
                    if (sparseg_dlcl_is_adjacent(*mult_edges, n,
                                                  (*dfs_nbr)[next],
                                                  (*dfs_nbr)[cur],
                                                  &existing_e))
                        /*
                          in this case we must update the multiplicity
                          of this edge: note that the elt. in cur's
                          neighbours list that gets updated is the first
                          in the list

                          dodgy??? certainly, but can't think
                          of a better way to do this

                          eventually it will happen that even myself
                          won't understand what I am doing..........
                        */
                    {
                        (existing_e->mult)++;
                    }
                    sparseg_dlcl_append_to_neigh_list(*mult_edges, n,
                                                      (*dfs_nbr)[cur],
                                                      (*dfs_nbr)[next],
                                                      cur_e);

                    cur_e = A[cur_e].next; /* next in cur's adjacency list */
                }
                else if (sparseg_dlcl_is_adjacent(*dfs_tree, n,
                                                  (*dfs_nbr)[next],
                                                  (*dfs_nbr)[cur],
                                                  &existing_e))
                    /*
                      [next, cur] is a tree edge:
                      that is, [cur, next] is [next, cur]'s twin/inverse:

                      1. if it is the first time one encounters
                         [cur, next] (as it would always be the case
                         for a simple graph) then all I need to do
                         is to update the tree edge's multiplicity,
                         and the twin info in TE_[]

                      2. if [cur, next] is actually a multiple edge,
                         then I'll need to store it in mult_edges;
                         and I update the tree edge's multiplicity too.
                         No twin info will be required here.
                         Why? see how recover.c embeds the multiple
                         edges in the planar embedding.

                      3. how do I know it is the first time I encounter
                         [cur, next]?:
                         when TE_twin_in_adjl = NIL

                      4. finally, note that the present counting scheme
                         implies that the mult field always holds
                         the number of directed edges:
                         ie, if [a, b] is a tree edge, [a, b].mult = 2
                         because we would have counted [a, b] and [b, a]

                         this applies to tree edges, back edges, and loops
                    */
                {
                    ASSERT(TE_in_adjl[(*dfs_nbr)[cur]] != NIL);
                    if (TE_twin_in_adjl[(*dfs_nbr)[cur]] == NIL)
                    {
                        TE_twin_in_adjl[(*dfs_nbr)[cur]] = cur_e;
                    }
                    else
                    {
                        sparseg_dlcl_append_to_neigh_list(*mult_edges, n,
                                                          (*dfs_nbr)[cur],
                                                          (*dfs_nbr)[next],
                                                          cur_e);
                    }

                    TE_mult[(*dfs_nbr)[cur]]++;

                    cur_e = A[cur_e].next; /* next in cur's adjacency list */
                }
                else if (sparseg_dlcl_is_adjacent(*back_edges, n,
                                                  (*dfs_nbr)[cur],
                                                  (*dfs_nbr)[next],
                                                  &existing_e))
                    /*
                      [next, cur] is a back edge: [cur, next] is its inverse:
                      we proceed as for the tree edge case above
                    */
                {
                    ASSERT(existing_e->in_adjl != NIL);
                    if (existing_e->twin_in_adjl == NIL)
                    {
                        existing_e->twin_in_adjl = cur_e;
                    }
                    else
                    {
                        sparseg_dlcl_append_to_neigh_list(*mult_edges, n,
                                                          (*dfs_nbr)[cur],
                                                          (*dfs_nbr)[next],
                                                          cur_e);
                    }

                    (existing_e->mult)++;

                    cur_e = A[cur_e].next; /* next in cur's adjacency list */
                }
                /*
                  the next bit concludes the DFS: it deals with the case
                  where a back edge needs to be added
                */
                else
                    /*
                      that is, next is visited and neither
                      the tree edge [next, cur] nor
                      the back edge [next, cur] exist:

                      this implies that [cur, next] is a back edge
                      that must be added to the back_edges structure
                      (with dfs_nbr(next) < dfs_nbr(cur))
                    */
                {
                    IF_DEB_TREE(
                                io_printf("add back edge %d\t%d\n",
                                          cur+1, next+1);
                                );

                    ASSERT(visited[next]);
                    ASSERT((*dfs_nbr)[cur] > (*dfs_nbr)[next]);

                    sparseg_dlcl_append_to_neigh_list(*back_edges, n,
                                                      (*dfs_nbr)[next],
                                                      (*dfs_nbr)[cur],
                                                      cur_e);

                    /*
                      update cur's lowpoint
                    */
                    (*lowpoint)[(*dfs_nbr)[cur]] =
                        (*dfs_nbr)[next] < (*lowpoint)[(*dfs_nbr)[cur]] ?
                        (*dfs_nbr)[next] : (*lowpoint)[(*dfs_nbr)[cur]];

                    /*
                      update least_a (of cur)
                      (always deal with DFIs remember!)
                    */
                    (*least_a)[(*dfs_nbr)[cur]] =
                        (*dfs_nbr)[next] < (*least_a)[(*dfs_nbr)[cur]] ?
                            (*dfs_nbr)[next] : (*least_a)[(*dfs_nbr)[cur]];

                    /*
                      get the next edge in cur's adjacency list
                    */
                    cur_e = A[cur_e].next;
                }
            }

            if (cur_e == NIL)
                /*
                  we are either at a leaf or have finished scanning
                  cur's adjacency list: backtrack
                */
            {
                if (pos_v_stack == -1)      /* no previous vertex */
                {
                    /*
                      no edge left on the stack: DFS ends for
                      this subtree:
                      we visit the next vertex
                    */
                    ASSERT(pos_e_stack == -1);
                    break;
                }
                else
                {
                    int      prev_e;
                    /*
                      Otherwise backtrack and pop cur from the stack
                      as well as the last tree edge  added to the tree.
                      We use next to get a new lowpoint value for cur:
                      This value will be min(lowpoint(cur), lowpoint(next)).
                    */
                    cur = vertex_stack[pos_v_stack--];
                    prev_e = edge_stack[pos_e_stack--];
                    next = A[prev_e].end_vertex;
                    (*lowpoint)[(*dfs_nbr)[cur]] =
                        (*lowpoint)[(*dfs_nbr)[cur]]
                        < (*lowpoint)[(*dfs_nbr)[next]] ?
                        (*lowpoint)[(*dfs_nbr)[cur]]
                        : (*lowpoint)[(*dfs_nbr)[next]];

                    cur_e = A[prev_e].next;
                }
                /*
                  we proceed with DFS
                */
            }
        }
    }
    mem_free(vertex_stack);
    mem_free(edge_stack);

    /*
      just for the sake of it, check that all vertices have
      been visited
    */
#ifdef ASSERTIONS
    for (v = 0; v < n; v++)
    {
        ASSERT(visited[v]);
    }
#endif
    mem_free(visited);

    /*
      we now order the DFIs wrt lowpoint values:
      use bucket sort (linear time)
    */
    /*
      for each lowpoint value, collect the DFIs (in a t_dlcl)
      with that lowpoint value
      (IMPORTANT: we want the DFIs since the aim is to rewrite dfs_tree
      which stores DFIs and not labels!)
    */
    for (v = 0; v < n; v++)
        /*
          v  is taken as a DFI here
        */
    {
        t_dlcl    *r;

        r = embedg_dlcl_rec_new(v);
        temp[(*lowpoint)[v]] =
            embedg_dlcl_rec_append(temp[(*lowpoint)[v]], r);
    }

    /*
      concatenate these lists now
    */
    lowpoint_list = temp[0];
    for (lp = 1; lp < n; lp++)
    {
        lowpoint_list = embedg_dlcl_cat(lowpoint_list, temp[lp]);
    }
    ASSERT(embedg_dlcl_length(lowpoint_list) == n);

    lowpoint_order[0] = lowpoint_list->info;
    for (lp = 1; lp < n; lp++)
    {
        lowpoint_list = embedg_dlcl_list_next(lowpoint_list);
        lowpoint_order[lp] = lowpoint_list->info;
    }
    embedg_dlcl_delete(lowpoint_list);
    mem_free(temp);

    IF_DEB(
           fprintf(stdout, "dfs_preprocessing, lowpoint_order\n");
           for (lp = 0; lp < n; lp++)
           fprintf(stdout, "%d ", lowpoint_order[lp]);
           fprintf(stdout, "\n");
           fprintf(stdout, "dfs_preprocessing, lowpoint\n");
           for (lp = 0; lp < n; lp++)
           fprintf(stdout, "%d ", (*lowpoint)[lp]);
           fprintf(stdout, "\n");
           )

    /*
      we now use this order to rewrite dfs_tree such that
      the DFS children of each vertex are ordered wrt lowpoint values
    */
    for (lp = 0; lp < n; lp ++)
        /*
          for each DFI in lowpoint_order[] I know its DFS_parent
          from dfs_parent[] -- the rest is then trivial
        */
    {
        int       parent;

        v = lowpoint_order[lp];
        /*
          lowpoint_order stores DFIs as does dfs_parent, so the lot
          makes sense
        */
        parent = (*dfs_parent)[v];
        if (parent != n)
            /*
              v may be the root of a DFS tree
            */
        {
            t_dlcl   *temp;

            temp = embedg_dlcl_rec_new(v);

            /*
              this is where the TE_ holding arrays are useful *sigh*
            */
            ASSERT(TE_in_adjl[v] != NIL);
            temp->in_adjl = TE_in_adjl[v];

            ASSERT(TE_twin_in_adjl[v] != NIL);
            temp->twin_in_adjl = TE_twin_in_adjl[v];

            ASSERT(TE_mult[v] != 0 && TE_mult[v] % 2 == 0);
            temp->mult = TE_mult[v];

            new_dfs_tree[parent] =
                embedg_dlcl_rec_append(new_dfs_tree[parent], temp);
        }
    }
    mem_free(lowpoint_order);
    mem_free(TE_in_adjl);
    mem_free(TE_twin_in_adjl);
    mem_free(TE_mult);

    /*
      some checks are in order here
    */
#ifdef ASSERTIONS
    for (v = 0; v < n; v++)
    {
        ASSERT(embedg_dlcl_length((*dfs_tree)[v])
               == embedg_dlcl_length(new_dfs_tree[v]));

        IF_DEB(
               fprintf(stdout, "dfs_preprocessing    dfs_tree for %d\n", v);
               embedg_dlcl_print((*dfs_tree)[v]);
               fprintf(stdout, "dfs_preprocessing    new_dfs_tree for %d\n", v);
               embedg_dlcl_print(new_dfs_tree[v]);
    );
    }
#endif

    sparseg_dlcl_delete(*dfs_tree, n);
    *dfs_tree = new_dfs_tree;
}

/*
 *  embedding.c
 */

/*
  What:
  *****

  Implementing:

  The graph is planar: we recover the embedding from the VES structure
  and check it as well.
  (Some of these checks will disappear later)


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_EMBED(x)    {}
#define IF_DEB_CHECK_EMBED(x)    {}
#define IF_DEB_FACES(x) {}
#define IF_VERB(x)   {}
#define IF_DEB_SCE(x) {}
#define IF_CPU(x) {}


/* aproto: header embed_graph_protos.h */


#ifndef PLANAR_IN_MAGMA
#endif

void
embedg_embedding (t_ver_sparse_rep *V, t_adjl_sparse_rep *A,
	t_ver_edge *embed_graph, int n, int e, int nbr_c,
	int edge_pos, t_dlcl **mult_edges, t_ver_sparse_rep **vertices,
	t_embed_sparse_rep **embedding)
    /*
      recovering the embedding for the (planar) graph

      - the embedding is returned in vertices and embedding, vertices
      indexes embedding, the ordered list of edges
      - edges in the embedding are given as their index in A, the graph's
      adajacency list
      - the nbr of edges in the embedding is given as nbr_e_embed:
      this may be different form the original number of edges when the graph
      iss not simple
    */
{
    int          *ver_orient, nbr_comp, nbr_e_embed;

    IF_CPU(
    float      sttime; float time_to_now;

    sttime = time_current_user();
    )

    IF_DEB(
           fprintf(stdout, "embedding, begin, which edges have been flipped\n");
           embedg_VES_print_flipped_edges(embed_graph, n, edge_pos);
           )

    IF_DEB(
           fprintf(stdout, "embedding, before removing SCE\n");
           embedg_VES_print_bigcomps(embed_graph, n);
           )

    /*
      several things to do:
      1. removing the short-cut edges
    */
    embedg_remove_SCE(embed_graph, n, edge_pos);

    IF_DEB(
           fprintf(stdout, "embedding, after removing SCE\n");
           embedg_VES_print_bigcomps(embed_graph, n);
           )

    /*
      2. computing each vertex's orientation (wrt flipped bicomps)
    */
    ver_orient = embedg_vertices_orientation(embed_graph, n);


    /*
      3. merging the remaining virtual vertices with their
         non-virtual counterpart
    */
    nbr_comp = embedg_merge_remaining_virtual(embed_graph, n);
    /*
      actually there is no need to return the nbr of components
      from the above function
      but let's do it for the sake of it and for possible checking
    */
    ASSERT(nbr_c == nbr_comp);

    IF_DEB(
           fprintf(stdout, "embedding, after merging of remaining vertices\n");
           )

    /*
      4. to be on the safe side: check that the embedding is a valid one

      for now, we DIE if not
    */

    if (!embedg_is_embed_valid(embed_graph, n, nbr_comp, edge_pos,
                               ver_orient, &nbr_e_embed))
    {
        mem_free(ver_orient);
        DIE();
    }
    mem_free(ver_orient);

    ASSERT(nbr_e_embed <= e);
    /*
      when the graph is not simple, multiple edges and loops are
      not in embed_graph[]: they will be added to the final
      embedding in embedg_recover_embedding below
    */

    /*
      5. recover the embedding in preparation for the Magma type,
      and check it as well
    */
    embedg_recover_embedding(V, A, embed_graph, n, e,
                             mult_edges, vertices, embedding);
    if (!embedg_check_recov_embedding(n, e, nbr_comp,
                                      *vertices, A, *embedding))
    {
        mem_free(*vertices);
        mem_free(*embedding);

        IF_CPU(
               fprintf(stdout, "CPU for embedding recovering %f\n",
                       time_current_user() - sttime);
               )

        DIE();
    }

    IF_DEB_EMBED(
                 fprintf(stdout, "embedding, original graph and embedding\n");
                 sparseg_adjl_print(V, n, A, FALSE);
                 fprintf(stdout, "\n");
                 sparseg_adjl_embed_print(*vertices, n, A, *embedding,
                                          FALSE);
                 )

    IF_CPU(
           fprintf(stdout, "CPU for embedding recovering %f\n",
                   time_current_user() - sttime);
           )
}


void
embedg_remove_SCE (t_ver_edge *embed_graph, int n, int edge_pos)
    /*
      remove all the short-cut edges from the embedding
    */
{
    int          i, c;

    c = 0;
    for (i = 2*n; i <= edge_pos; i += 2)
        /*
          and edge and its twin occupy consecutive positions in embed_graph:
          need only to examine one out of two
          (removing an edge also entails removing its twin of course
        */
    {
        if (embedg_VES_is_short_cut_edge(embed_graph, n, i))
        {
            IF_DEB_SCE(
                       fprintf(stdout, "remove SCE\n");
                       embedg_VES_print_edge(embed_graph, n, i);
                       )

            embedg_VES_remove_edge(embed_graph, n, i);
            c++;
        }
    }

    IF_DEB_SCE(
               fprintf(stdout, "nbr of SCE edges removed %d\n", c);
               )
}


int *
embedg_vertices_orientation (t_ver_edge *embed_graph, int n)
    /*
      for each vertex return its orientation from the
      bicomps in embed_graph:
      perform a DFS of each bicomp
    */
{
    int          i, vv, prod_sign;
    int          *stack, *ver_orient, to_prev;

    /*
      the whole lot makes sense iff the adjacency lists are consistent:
      this is a very important issue and it might be the case
      that the ASSERT warrants replacement by a DIE
      (the check is linear - I think)
    */
    ASSERT(embedg_VES_are_adj_lists_consistent(embed_graph, n));

    ver_orient = (int *) mem_malloc(sizeof(int) * n);
    for (i = 0; i < n; i++)
    {
        ver_orient[i] = CCLOCKW;
    }

    /*
      create the stack for the DFS
    */
    stack = (int *) mem_malloc(sizeof(int) * 3*n);
    to_prev = -1;

    IF_DEB(
           fprintf(stdout, "vertex orientation, one line (of vert.) for each bicomp\n");
           )

    /*
      now visit all the bicomps, ie, all the virtual vertices
      in embed_graph
    */
    for (vv = n; vv < 2*n; vv++)
    {
        int      c, cur, cur_e;
        boolean  NEW_BICOMP;

        if (embed_graph[vv].link[0] == vv)
            /*
              means that vv is disabled and is not the root of a bicomp
            */
        {
            continue;
        }

        c = vv - n;
        IF_DEB(
               fprintf(stdout, "%d ", c);
               )
        /*
          orientation for c (vv is as yet unembedded) is CCLOCKW

          now find the orientation of all its DFS descendants
        */

        if (embed_graph[c].DFS_parent == n)
            /*
              this means that actually c is an isolated vertex:
              we initialise the sign to CCLOCKW
            */
        {
            prod_sign = CCLOCKW;
        }
        else
            /*
              we initialise the sign to CCLOCKW to the sign of c's parent
            */
        {
            prod_sign = ver_orient[embed_graph[c].DFS_parent];
        }

        /*
          we must not forget to set c's sign!!
          (won't be done below)
        */
        ver_orient[c] = prod_sign;

        NEW_BICOMP = FALSE;
        cur = c;
        cur_e = embed_graph[cur].link[0];
        ASSERT(embedg_VES_is_edge(n, cur_e));

        ASSERT(to_prev == -1);
        while (TRUE)
        {
            while (!embedg_VES_is_tree_edge(embed_graph, n, cur_e)
                   || !embedg_VES_is_vertex(n,
                                             embed_graph[cur_e].neighbour)
                   || embed_graph[cur_e].neighbour <= cur)
                /*
                  want to find a tree edge [cur, u]
                  where u is a descendant of cur
                */
            {
                cur_e = embed_graph[cur_e].link[0];

                while (cur_e == cur)
                    /*
                      back to the vertex where we started from:
                      no edge has been found:
                      cur is a leaf, backtrack
                    */
                {
                    if (to_prev == -1)
                    {
                        NEW_BICOMP = TRUE;
                        break;
                    }
                    prod_sign = stack[to_prev--];
                    cur_e = stack[to_prev--];
                    /*
                      must advance one more edge
                    */
                    cur_e = embed_graph[cur_e].link[0];
                    cur = stack[to_prev--];
                }
                if (NEW_BICOMP)
                {
                    break;
                }
            }

            if (NEW_BICOMP)
            {
                break;
            }
            else
                /*
                  now cur_e is the edge we were looking for, get its sign
                */
            {
                /*
                  push on stack the current vertex, the edge where we
                  stopped the DFS, AND the sign carried by that vertex

                  and go down one level in the DFS
                */
                stack[++to_prev] = cur;
                stack[++to_prev] = cur_e;
                stack[++to_prev] = prod_sign;

                cur = embed_graph[cur_e].neighbour;
                prod_sign *= embed_graph[cur_e].sign;
                ver_orient[cur] = prod_sign;

                cur_e = embed_graph[cur].link[0];
                ASSERT(embedg_VES_is_edge(n, cur_e));

                IF_DEB(
                       fprintf(stdout, "%d with sign %d\n", cur, prod_sign);
                       )
            }
        }

        IF_DEB(
               fprintf(stdout, "\n");
               )
    }

    IF_DEB(
           fprintf(stdout, "vertex orientation\n");
           for (i = 0; i < n; i++)
           {
               fprintf(stdout, "%d ", ver_orient[i]);
           }
           fprintf(stdout, "\n");
           )

   mem_free(stack);
   return ver_orient;
}


int
embedg_merge_remaining_virtual (t_ver_edge *embed_graph, int n)
    /*
      after the short-cut edges have been removed and the vertices'
      orientation computed, one finishes by merging all
      remaining virtual vertices with their virtual counterpart
      (without flip of course)

      and use this routine to return  the number of disconnected
      components of the graph
    */
{
    /*
      at this stage it is easy to see that all remaining
      virtual vertices are DFS roots (if the graph is not connected)
      or cut vertices
    */

    int          vv, nbr_comp;

    nbr_comp = 0;
    for (vv = n; vv < 2*n; vv++)
    {
        int      v, c;


        c = vv - n;
        v = embed_graph[c].DFS_parent;

        /*
          must fish out which virtual vertices are actual roots
          of DFS trees (esp. for the disconnected graph case):
          roots of DFS trees are those virtual vertices for which
          v = embed_graph[c].DFS_parent = n
        */
        if (v == n)
        {
            nbr_comp++;
            continue;
        }

        if (embed_graph[vv].link[0] == vv)
            /*
              means that vv is disabled and is not the root of a bicomp
            */
        {
            continue;
        }

        embedg_VES_merge_simple_bicomps(embed_graph, n,
                                                   vv, 1, v, 0);
        /*
          note:
          since v is a cut vertex in this intance the bicomp
          rooted by vv will be merged without flip;
          therefore we could have done
          embedg_VES_merge_simple_bicomps(embed_graph, n,
          vv, 0, v, 1)
          as well, the important thing being that vin != vvout
          (see embedg_VES_merge_simple_bicomps)
        */
    }

    return nbr_comp;
}


int
embedg_nbr_faces (t_ver_edge *embed_graph, int n, int edge_pos,
	int *ver_orient, int *nbr_e_embed)
    /*
      count the number of faces and the number of edges of the embedding
    */
{
    int          v, e, f, total_e;

    IF_DEB_FACES(
                 int    v;

                 fprintf(stdout, "nbr of faces, the vertices' adj. lists\n");
                 for (v = 0; v < n; v++)
                     embedg_VES_print_adj_list(embed_graph, n,
                                                          v, TRUE);
                 )

    /*
      the following is no more than a quick check -- certainly
      not very useful -- or could be done elsewhere
    */
    total_e = 0;
    for (e = 2*n; e <= edge_pos; e++)
    {
        if (!embedg_VES_is_short_cut_edge(embed_graph, n, e))
        {
            total_e++;
        }
    }
    ASSERT(total_e % 2 == 0);
    *nbr_e_embed = total_e / 2;

    /*
      I now set each edge's orientation

      QUESTION: do I really need to do this???
      so far, when doing a proper face traversal, the way in which
      the adjacency list of an edge must be traversed is given
      by the vertex's (in that list) orientation...
      So this seems sensible to me huh?
    */
    embedg_VES_set_orientation(embed_graph, n, ver_orient);

    /*
      I will be using the visited field to enable me to check
      if all edges have been traversed

      let's be smart (?!): so far the visited field has been used
      and set in the following circumstances:
      + initialisation: set to n
      + walkup: set to whatever DFI of interest

      so here we set it to MARK_EMBED(n)
    */
    f = 0;
    for (e = 2*n; e <= edge_pos; e++)
    {
        if (!embedg_VES_is_short_cut_edge(embed_graph, n, e)
            /*
              arrghh!!! I must also skip the SCE!!!
            */
            && embed_graph[e].visited != MARK_EMBED(n))
        {
            int          ein;

            IF_DEB_FACES(
                         fprintf(stdout, "nbr of faces, edges not visited\n");
                         embedg_VES_print_edge(embed_graph, n, e);
                         )

            ein = embed_graph[e].sign == CCLOCKW ? 0 : 1;
            /*
              the way I enter e in dependent on its sign:
              all the proper face traversal must obviously be done
              with the same orientation!
            */
            embedg_VES_walk_proper_face(embed_graph, n, e,
                                                       ein,
                                                       TRUE,
                                                       MARK_EMBED(n));
            f++;
        }
    }

    /*
      counting the faces by traversing all the edges does not
      account of the face defined by isolated vertices
      -- we do that now

      we only need to check which vertices refer to self, ie with
      no incident edges
    */
    for (v = 0; v < n; v++)
    {
        if (embed_graph[v].link[0] == v)
        {
            ASSERT(embed_graph[v].link[1] == v);
            f++;
        }
    }

    return f;
}


boolean
embedg_is_embed_valid (t_ver_edge *embed_graph, int n, int nbr_comp,
	int edge_pos, int *ver_orient, int *nbr_e_embed)
    /*
      use Euler's formula to assertain that the embedding is a valid
      embedding:

      f = 2 * nbr_comp + nbr_e_embed - n

    */
{
    int         v, f;

    f = embedg_nbr_faces(embed_graph, n, edge_pos, ver_orient, nbr_e_embed);

    IF_DEB_CHECK_EMBED(
                       fprintf(stdout, "embedding, n: %d\t e: %d\t C: %d\t f: %d\n",
                               n, nbr_e, nbr_comp, f);
                       )

    return f == 2 * nbr_comp + *nbr_e_embed - n ? TRUE : FALSE;
}
/*
 *  ext_face_walk.c
 */

/*
  What:
  *****

  Implementing the external face walk of a bicomponent.
  The concept of an external face --in the context of the VES
  data structure-- makes only sense when talking
  about a bicomp.

  Recall that a vertex is linked together with the edges
  incident from it in a circular (doubly) linked list
  (this is the VES structure).

  One particular feature is that if a vertex v is on
  the external face of a component and if in the list
  we have edges e1, e2 such as e1  -> v -> e2
  then e1 and e2 border the external face.

  In other words, in the circular list of vertex v and edges,
  v is ALWAYS between the two edges bordering the external face

  Of course, when v is (maybe) pushed into the internal face
  (by embedding of some edge) then we don't care about this any more
  (for v that is).



  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}


/* aproto: header embed_graph_protos.h */


void
embedg_VES_get_succ_on_ext_face (t_ver_edge *embed_graph, int n, int v,
	int vin, boolean MARK, int mark, int *s, int *sin)
    /*
      find the successor s of v (entered via vin) on the external face
      -- also return the direction in which s has been entered

      if MARK true mark the succ. vertex and the edges traversed
      with mark (the visited field)
    */
{
    int        e, twin;
    int        vout, ein, eout, tout;

    ASSERT(embedg_VES_is_vertex(n, v)
           || embedg_VES_is_virtual_vertex(n, v));

    IF_DEB(
           fprintf(stdout, "get_succ_on_ext_face, of %d:%d\n", v, vin);
           )

    /*
      find the direction out of the vertex, and get the edge
    */
    vout = vin == 0 ? 1 : 0;
    e = embed_graph[v].link[vout];
    if (embedg_VES_is_virtual_vertex(n, v) && e == v)
        /*
          this can happen if a virtual vertex has been "disabled"

          -- this should not never happen since we can only walk
          on the external face of a bicomp!
        */
    {
        *s = v;
        *sin = vin;
        return;
    }

    /*
      otherwise we must have an edge:
      note that it is entirely irrelevant if I walk SCEs:
      those are precisely there to "jump" over inactive vertices
    */
    ASSERT(embedg_VES_is_edge(n, e));

    /*
      get the twin edge
    */
    twin = embedg_VES_get_twin_edge(embed_graph, n, e);

    IF_DEB(
           fprintf(stdout, "get_succ_on_ext_face, edge [%d, %d]\n",
                   v, embed_graph[e].neighbour);
           fprintf(stdout, "get_succ_on_ext_face, twin edge [%d, %d]\n",
                   embed_graph[e].neighbour, embed_graph[twin].neighbour);
           )
    /*
      find which of twin's link links a vertex
    */
    tout = embedg_VES_is_vertex(n, embed_graph[twin].link[0])
        || embedg_VES_is_virtual_vertex(n,
                                                   embed_graph[twin].link[0])
        ?
        0 : 1;

    /*
      get this vertex: this is v's successor on the external face
    */
    *s = embed_graph[twin].link[tout];

    /*
      one more thing to do: find the direction in which s was entered
    */
    *sin = embed_graph[*s].link[0] == twin ? 0 : 1;

    IF_DEB(
           fprintf(stdout, "get_succ_on_ext_face, succ is %d:%d\n",
                   *s, *sin);
           )
    /*
      a special case: when the bicomp is a singleton bicomp
      (ie a single edge)
    */
    if (embed_graph[*s].link[0] == (embed_graph[*s].link[1]))
    {
        ASSERT(embed_graph[*s].link[0] == twin);
        *sin = vin;
    }

    /*
      finally, mark the vertex and edges if so requested
    */
    if (MARK)
    {
        embed_graph[*s].visited = mark;
        embed_graph[e].visited = mark;
        embed_graph[twin].visited = mark;
    }
}

void
embedg_VES_get_succ_active_on_ext_face (t_ver_edge *embed_graph, int n,
	int v, int w, int win, boolean MARK, int mark, int *s, int *sin)
    /*
      find the ACTIVE (wrt v) successor s of w (entered via win)
      on the external face
      -- also return the direction in which s has been entered

      if MARK true mark the succ. vertex (and the edge)
      with mark (the visited field)
    */
{
    /*
      simply repeatedly calls embedg_VES_get_succ_on_ext_face
      until an active vertex is found
    */
    ASSERT(embedg_VES_is_vertex(n, w)
           || embedg_VES_is_virtual_vertex(n, w));

    embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                         w, win, MARK, mark, s, sin);
    while (embedg_VES_is_ver_inactive(embed_graph, n, v, *s))
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                             *s, *sin, MARK, mark, s, sin);
    }
    ASSERT(!embedg_VES_is_ver_inactive(embed_graph, n, v, *s));
}

void
embedg_VES_get_succ_ext_active_on_ext_face (t_ver_edge *embed_graph, int n,
	int v, int w, int win, boolean MARK, int mark, int *s, int *sin)
    /*
      find the externally active (wrt v) successor s of w (entered via win)
      on the external face
      -- also return the direction in which s has been entered

      if MARK true mark the succ. vertex (and the edge)
      with mark (the visited field)
    */
{
    ASSERT(embedg_VES_is_vertex(n, w)
           || embedg_VES_is_virtual_vertex(n, w));

    embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                         w, win, MARK, mark, s, sin);
    while (!embedg_VES_is_ver_ext_active(embed_graph, n, v, *s))
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                             *s, *sin, MARK, mark, s, sin);
    }
    ASSERT(embedg_VES_is_ver_ext_active(embed_graph, n, v, *s));
}

void
embedg_VES_get_succ_pertinent_on_ext_face (t_ver_edge *embed_graph, int n,
	int v, int w, int win, boolean MARK, int mark, int *s, int *sin)
    /*
      find the pertinent (wrt v) successor s of w (entered via win)
      on the external face
      -- also return the direction in which s has been entered

      if MARK true mark the succ. vertex (and the edge)
      with mark (the visited field)
    */
{
    ASSERT(embedg_VES_is_vertex(n, w)
           || embedg_VES_is_virtual_vertex(n, w));

    embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                         w, win, MARK, mark, s, sin);
    while (!embedg_VES_is_ver_pertinent(embed_graph, n, v, *s))
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                             *s, *sin, MARK, mark, s, sin);
    }
    ASSERT(embedg_VES_is_ver_pertinent(embed_graph, n, v, *s));
}

/*
 *  mark_kur.c
 */

/*
  What:
  *****

  Implementing:

  Marking the Kuratowski obstruction (in the VES structure):
  this we do once we know which minor we are talking about
  (see isolator.c).


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_VERB(x)   {}
#define IF_DEB_TREE(x)    {}
#define IF_DEB_EDGES(x) {}
#define IF_CPU(x) {}



/* aproto: header embed_graph_protos.h */

/* aproto: beginstatic -- don't touch this!! */
static void embedg_VES_walk_mark_part_ext_face (t_ver_edge *, int, int, int, int, int, int);
static void embedg_VES_walk_mark_ext_face (t_ver_edge *, int, int, int);
static void embedg_VES_walk_mark_part_proper_face (t_ver_edge *, int, int, int, int, int);
static boolean embedg_VES_is_part_ext_face_marked (t_ver_edge *, int, int, int, int, int, int);
static void embedg_get_u_x (t_ver_edge *, int, int, int, int *);
static int embedg_get_least_neigh (t_dlcl **, t_dlcl **, int, int, int);
static void embedg_add_mark_u_x (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int *, int);
static void embedg_mark_tree_path (t_ver_edge *, int, int, int, int);
static void embedg_add_mark_v_w (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int);
static void embedg_add_mark_v_w_for_B (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int *, int);
static void embedg_mark_x_y_path (t_ver_edge *, int, int *, int *, int, int);
/* aproto: endstatic -- don't touch this!! */

#ifndef PLANAR_IN_MAGMA
#endif



static void
embedg_VES_walk_mark_part_ext_face (t_ver_edge *embed_graph, int n,
	int v, int vin, int from, int to, int mark)
    /*
      walk & mark the external face:
      walk in the direction vin -> v -> vout and mark <from> <to>
    */
{
    int          cur, curin, next, nextin;

    embed_graph[from].visited = mark;
    embed_graph[to].visited = mark;

    IF_DEB(
           fprintf(stdout, "part. ext face marked\t");
           fprintf(stdout, "%d\t", from);
           )

    next = cur = v;
    curin = vin;
    while (next != from)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n, cur, curin,
                                             FALSE, 0, &next, &nextin);
        cur = next;
        curin = nextin;
    }
    next = n;
    while (next != to)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n, cur, curin,
                                             TRUE, mark, &next, &nextin);
        cur = next;
        curin = nextin;

        IF_DEB(
               fprintf(stdout, "%d\t", next);
               )
    }
    IF_DEB(
           fprintf(stdout, "\n");
           )
}

static void
embedg_VES_walk_mark_ext_face (t_ver_edge *embed_graph, int n, int v, int mark)
    /*
      walk & mark the external face, starting & ending at vertex v
    */
{
    embedg_VES_walk_mark_part_ext_face(embed_graph, n, v, 0, v, v,
                                            mark);
}



static void
embedg_VES_walk_mark_part_proper_face (t_ver_edge *embed_graph, int n,
	int from_e, int from_ein, int to, int mark)
    /*
      walk & mark a proper face starting at EDGE from_e and ending
      at VERTEX to

      walk in the direction from_ein -> from_e -> to and mark
      everything in between
    */
{
    int     s, cur_e, cur_ein, next_e, next_ein;

    next_e = s = n; /* this is an invalid value for an edge/vertex */

    cur_e = from_e;
    cur_ein = from_ein;
    while (s != to)
    {
        ASSERT(embedg_VES_is_edge(n, cur_e));
        ASSERT(!embedg_VES_is_short_cut_edge(embed_graph,
                                                        n, cur_e));

        embedg_VES_get_succ_on_proper_face(embed_graph, n,
                                                cur_e, cur_ein,
                                                TRUE, mark,
                                                &s, &next_e, &next_ein);
        cur_e = next_e;
        cur_ein = next_ein;
    }
}



static boolean
embedg_VES_is_part_ext_face_marked (t_ver_edge *embed_graph, int n, int v,
	int vin, int from, int to, int mark)
    /*
      simple check to see if all the vertices on the external
      face walk starting at vin -> v -> vout <from> <to> are marked
      (with mark)
    */
{
    int          cur, curin, next, nextin;

    if (embed_graph[from].visited != mark || embed_graph[to].visited != mark)
        return FALSE;

    cur = v;
    curin = vin;
    next = n;
    while (next != from)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n, cur, curin,
                                             FALSE, 0, &next, &nextin);
        cur = next;
        curin = nextin;
    }
    while (next != to)
    {
        embedg_VES_get_succ_on_ext_face(embed_graph, n, cur, curin,
                                             FALSE, 0, &next, &nextin);
        if (embed_graph[next].visited != mark)
            return FALSE;

        cur = next;
        curin = nextin;
    }

    return TRUE;
}


boolean
embedg_VES_is_ext_face_marked (t_ver_edge *embed_graph, int n, int v, int mark)
    /*
      simple check to see if all the vertices on the external
      face walk starting/ending at v are marked (with mark)
    */
{
    return embedg_VES_is_part_ext_face_marked(embed_graph, n, v, 0,
                                                   v, v, mark);
}


static void
embedg_get_u_x (t_ver_edge *embed_graph, int n, int v, int x, int *u_x)
    /*
      x is an externally active vertex (wrt v):
      we want u_x, the lowest point of "attachement" for
      the unembedded directed edge [x, u_x]
    */
{
    int          c;
    t_dlcl       *child_list;

    ASSERT(embedg_VES_is_ver_ext_active(embed_graph, n, v, x));
    if (embed_graph[x].least_ancestor < v)
        /*
          then there is a single unembedded back edge (u_x, x),
          u_x an ancestor of v
        */
    {
        *u_x = embed_graph[x].least_ancestor;
        return;
    }

    /*
      else there is a tree path x to d_x and an
      unembedded back edge (u_x, d_x)

      get the lowpoint of the first elt. in separated_DFS_child_list of x
    */
    child_list = embed_graph[x].separated_DFS_child_list;
    ASSERT(!embedg_dlcl_is_empty(child_list));
    c = child_list->info;
    *u_x = embed_graph[c].lowpoint;
}

static int
embedg_get_least_neigh (t_dlcl **dfs_tree, t_dlcl **back_edges,
	int n, int v, int c)
    /*
      get the least neighbour of v >= c, ie a vertex in the sub tree
      rooted by c

      somehow this must always succeed
    */
{
    int          least_n;
    t_dlcl       *tree_l, *back_l, *p;

    /*
      neighbours are found in either dfs_tree[v] or back_edges[v]
    */

    tree_l = dfs_tree[v];
    back_l = back_edges[v];
    ASSERT(!embedg_dlcl_is_empty(tree_l) || !embedg_dlcl_is_empty(back_l));

    least_n = n;  /* ok, invalid value for any neighbour */
    p = tree_l;
    if (!embedg_dlcl_is_empty(p))
    {
        if (p->info >= c)
        {
            least_n = p->info < least_n ? p->info : least_n;
        }
        p = embedg_dlcl_list_next(p);
        while (p != tree_l)
        {
            if (p->info >= c)
            {
                least_n = p->info < least_n ? p->info : least_n;
            }
            p = embedg_dlcl_list_next(p);
        }
    }
    p = back_l;
    if (!embedg_dlcl_is_empty(p))
    {
        if (p->info >= c)
        {
            least_n = p->info < least_n ? p->info : least_n;
        }
        p = embedg_dlcl_list_next(p);
        while (p != back_l)
        {
            if (p->info >= c)
            {
                least_n = p->info < least_n ? p->info : least_n;
            }
            p = embedg_dlcl_list_next(p);
        }
    }

    ASSERT(least_n >= c);
    /*
      this is so because of the context where this function is called from
    */
    return least_n;
}

static void
embedg_add_mark_u_x (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v,
	int x, int *u_x, int mark)
    /*
      marking a Kuratowski homeomorph:

      marking and adding the unembedded dotted edge (u, x),
      x an ext. active vertex wrt v
    */
{
    int          c, d_x;
    t_dlcl       *child_list;

    ASSERT(embedg_VES_is_ver_ext_active(embed_graph, n, v, x));
    if (embed_graph[x].least_ancestor < v)
        /*
          then there is a single unembedded back edge (u_x, x),
          u_x an ancestor of v
        */
    {
        *u_x = embed_graph[x].least_ancestor;
        embed_graph[x].visited = mark;
        embed_graph[*u_x].visited = mark;
        embedg_VES_add_edge(embed_graph, n, edge_pos, *u_x, x,
                                       TRUE, mark);
        return;
    }

    /*
      else there is a tree path x to d_x and an
      unembedded back edge (u_x, d_x)

      get the lowpoint of the first elt. in separated_DFS_child_list of x
    */
    child_list = embed_graph[x].separated_DFS_child_list;
    ASSERT(!embedg_dlcl_is_empty(child_list));
    c = child_list->info;
    *u_x = embed_graph[c].lowpoint;

    /*
      search for the least neighbour of *u_x  >= c,
      that is in the subtree rooted by c
    */
    d_x = embedg_get_least_neigh(dfs_tree, back_edges, n, *u_x, c);
    ASSERT(d_x >= c);
    /*
      this must be true  since u_x is incident to a descendant of x
      (remember: x is externally active)
    */

    /*
      mark the DFS tree path from d_x to x
    */
    embedg_mark_tree_path(embed_graph, n, d_x, x, mark);
    /*
      add the unembedded (u_x, d_x) edge
    */
    embedg_VES_add_edge(embed_graph, n, edge_pos, *u_x, d_x,
                                   TRUE, mark);
}

static void
embedg_mark_tree_path (t_ver_edge *embed_graph, int n, int d_x, int x, int mark)
    /*
      marking the DFS tree path d_x...x where x is an ancestor of d_x
    */
{
    int          cur_v, te, twe;

    ASSERT(d_x >= x);

    cur_v = d_x;

    while (cur_v != x)
    {
        embed_graph[cur_v].visited = mark;
        te = embed_graph[cur_v].link[0];
        ASSERT(embedg_VES_is_edge(n, te));
        while (!embedg_VES_is_tree_edge(embed_graph, n, te)
               || (embed_graph[te].neighbour > cur_v
                   && embed_graph[te].neighbour != cur_v + n))
            /*
              want to find a tree edge incident to an ancestor of d_x:
              given that d_x..x is a tree path, we MUST find such an edge!

              note also that I must take account of the fact that
              [te].neighbour could be a virtual vertex, in which case
              it can only be cur_v + n!
            */
        {
            te = embed_graph[te].link[0];
        }
        ASSERT(embedg_VES_is_tree_edge(embed_graph, n, te));
        ASSERT(embed_graph[te].neighbour == embed_graph[cur_v].DFS_parent
               || embed_graph[te].neighbour == cur_v + n);

        embed_graph[te].visited = mark;
        twe =  embedg_VES_get_twin_edge(embed_graph, n, te);
        embed_graph[twe].visited = mark;

        /*
          want only to deal with real vertices instead of virtual vertices
        */
        cur_v = embed_graph[te].neighbour < cur_v ?
            embed_graph[te].neighbour : embed_graph[cur_v].DFS_parent;
    }
    embed_graph[x].visited = MARK_MINORS(n);
}


static void
embedg_add_mark_v_w (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v, int w, int mark)
    /*
      marking a Kuratowski homeomorph:

      marking and adding the unembedded dotted edge (v, w),
      w is pertinent wrt v
    */
{
    int          vw, c, d_w;
    t_dlcl       *bicomp_list;

    if (embed_graph[w].adjacent_to == v)
        /*
          then there is a single unembedded back edge (v, w)
          w an ancestor of w
        */
    {
        embed_graph[v].visited = mark;
        embed_graph[w].visited = mark;
        embedg_VES_add_edge(embed_graph, n, edge_pos, v, w,
                                       TRUE, mark);
        return;
    }

    /*
      else there is a tree path w to d_w and an
      unembedded back edge (v, d_w)

      get the last elt in w's bicomp list
    */
    bicomp_list = embed_graph[w].pertinent_bicomp_list;
    ASSERT(!embedg_dlcl_is_empty(bicomp_list));
    vw = (embedg_dlcl_list_last(bicomp_list))->info;
    c = vw - n;

    /*
      search for the least neighbour of v >= c,
      that is in the subtree rooted by c
    */
    d_w = embedg_get_least_neigh(dfs_tree, back_edges, n, v, c);
    ASSERT(d_w >= c);
    /*
      this must be true since v is incident to a descendant of w
      (remember: w is pertinent)
    */

    /*
      mark the DFS tree path from d_w to w
    */
    embedg_mark_tree_path(embed_graph, n, d_w, w, mark);
    /*
      add the unembedded (d_w, v) edge
    */
    embedg_VES_add_edge(embed_graph, n, edge_pos, d_w, v,
                                   TRUE, mark);
}


static void
embedg_add_mark_v_w_for_B (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v, int w,
	int *u_z, int mark)
    /*
      marking a Kuratowski homeomorph:

      marking and adding the unembedded dotted edge (v, w) for minor B:
      w is pertinent wrt v
    */
{
    int          vz, z, d_z, d_w;
    t_dlcl       *bicomp_list;

    /*
      get the last elt in w's bicomp list
    */
    bicomp_list = embed_graph[w].pertinent_bicomp_list;
    ASSERT(!embedg_dlcl_is_empty(bicomp_list));
    vz = (embedg_dlcl_list_last(bicomp_list))->info;
    z = vz - n;

    /*
      get the lowpoint of z
    */
    *u_z = embed_graph[z].lowpoint;

    /*
      search for the least neighbour of *u_z  >= z,
      that is in the subtree rooted by c
    */
    d_z = embedg_get_least_neigh(dfs_tree, back_edges, n, *u_z, z);
    ASSERT(d_z >= z);
    /*
      this must be true since u_z is incident to z or a descendant of z
    */

    /*
      now do the same for neighbours of v
    */
    d_w = embedg_get_least_neigh(dfs_tree, back_edges, n, v, z);
    ASSERT(d_w >= z);
    /*
      this must be true since v is incident to a descendant of w
      (remember: w is pertinent)
    */

    /*
      mark the DFS tree path from d_w to w
    */
    embedg_mark_tree_path(embed_graph, n, d_w, w, mark);
    /*
      mark the DFS tree path from d_z to z
    */
    embedg_mark_tree_path(embed_graph, n, d_z, z, mark);
    /*
      add & mark the edges (u_z, d_z), (v, d_w)
    */
    embedg_VES_add_edge(embed_graph, n, edge_pos, *u_z, d_z,
                                   TRUE, mark);
    embedg_VES_add_edge(embed_graph, n, edge_pos, v, d_w,
                                   TRUE, mark);
}

static void
embedg_mark_x_y_path (t_ver_edge *embed_graph, int n, int *path_v,
	int *path_e, int nbr_v, int mark)
{
    int          i;

    /*
      have a look at embedg_iso_get_highest_x_y_path
      to see that path_e[0] is a dummy

      (note: path_v and path_e contain nbr_v + 1 elts!)
    */
    embed_graph[path_v[0]].visited = mark;
    for (i = 1; i <= nbr_v; i++)
    {
        int        e, twin;

        embed_graph[path_v[i]].visited = mark;
        e = path_e[i];
        twin = embedg_VES_get_twin_edge(embed_graph, n, e);
        embed_graph[e].visited =
            embed_graph[twin].visited = mark;
    }
}

void
embedg_mark_minor_A (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v, int c, int vr)
{
    int          r, r_c, x, y, w, u_x, u_y, u;

    ASSERT(embedg_VES_is_virtual_vertex(n, vr));
    r_c = vr - n;
    r = embed_graph[r_c].DFS_parent;

    /*
      find the ext. active x & y, and the pertinent w,
      and mark the external face of the bicomp rooted at vr
    */
    embedg_iso_get_x_y_w(embed_graph, n, v, r, r_c,
                              MARK_MINORS(n),
                              MARK_MINORS(n), MARK_MINORS(n), &x, &y, &w);

    /*
      mark the edges (u, x), (u, y), (v, w)
    */
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, x, &u_x,
                        MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, y, &u_y,
                        MARK_MINORS(n));
    embedg_add_mark_v_w(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, w,
                        MARK_MINORS(n));

    /*
      mark the tree path from r to min(u_x, u_y)
    */
    u = u_x <= u_y ? u_x : u_y;
    embedg_mark_tree_path(embed_graph, n, r, u, MARK_MINORS(n));

    IF_DEB(
           fprintf(stdout, "mark minor A\n");
           fprintf(stdout, "v %d\t c %d\t r %d\t r_c %d\t x %d\t y %d\t w %d\t u_x %d\t u_y %d\n",
                   v, c, r, r_c, x, y, w, u_x, u_y);
           )
}

void
embedg_mark_minor_B (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v,
	int c, int x, int y, int w)
{
    int          vv, u_x, u_y, vz, u_z, u_max, u_min;

    vv = c + n;

    /*
      mark the external face of the bicomp rooted by v^c
    */
    embedg_VES_walk_mark_ext_face(embed_graph, n, vv, MARK_MINORS(n));
    ASSERT(embedg_VES_is_ext_face_marked(embed_graph, n, vv,
                                              MARK_MINORS(n)));

    /*
      mark the edges (u, x), (u, y)
    */
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, x, &u_x,
                        MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, y, &u_y,
                        MARK_MINORS(n));

    /*
      mark the dotted edges (v, w), (v, u)
    */
    embedg_add_mark_v_w_for_B(dfs_tree, back_edges,
                              embed_graph, n, edge_pos, v, w,
                              &u_z, MARK_MINORS(n));

    /*
      mark the tree path from max(u_x, u_y, u_z) to min(u_x, u_y, u_z)
    */
    u_max = u_x > u_y ? u_x : u_y;
    u_max = u_max > u_z ? u_max : u_z;
    u_min = u_x < u_y ? u_x : u_y;
    u_min = u_min < u_z ? u_min : u_z;
    embedg_mark_tree_path(embed_graph, n, u_max, u_min, MARK_MINORS(n));

    IF_DEB(
           fprintf(stdout, "mark minor B\n");
           fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t u_x %d\t u_y %d\t u_z %d\n",
                   v, c, x, y, w, u_x, u_y, u_z);
           )
}

void
embedg_mark_minor_C (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v,
	int c, int x, int y, int w, int *path_v, int *path_e,
	int nbr_v, boolean px_attached_high, boolean py_attached_high)
{
    int          vv, p_x, p_y, u_x, u_y, u;

    vv = c + n;
    p_x = path_v[0];
    p_y = path_v[nbr_v];
    /*
      see embedg_iso_get_highest_x_y_path for the above
    */

    if (px_attached_high)
        /*
          mark the external face:
          - from v^c to p_y if py_attached_high
          - from v^c to y if !py_attached_high

          not too sure about that one....

          from v^c to p_y: so vvin = 0,
          in x's direction
        */
    {
        if (py_attached_high)
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                    vv, p_y, MARK_MINORS(n));
        else
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                    vv, y, MARK_MINORS(n));
    }
    else
        /*
          symmetric case:
          mark the external face from v^c to p_x: so vvin = 1,
          in y's direction
        */
    {
        if (px_attached_high)
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                    vv, p_x, MARK_MINORS(n));
        else
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                    vv, x, MARK_MINORS(n));
    }

    /*
      mark the edges (u, x), (u, y), (v, w)
    */
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, x, &u_x,
                        MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, y, &u_y,
                        MARK_MINORS(n));
    embedg_add_mark_v_w(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, w,
                        MARK_MINORS(n));

    /*
      mark the tree path from v to min(u_x, u_y)
    */
    u = u_x <= u_y ? u_x : u_y;
    embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

    /*
      finally, mark the x-y path, ie the vertices in path_v
      and the edges in path_e
    */
    embedg_mark_x_y_path(embed_graph, n, path_v, path_e, nbr_v,
                         MARK_MINORS(n));

    IF_DEB(
           fprintf(stdout, "mark minor C      p_x high %d\t p_y high %d\n",
                   px_attached_high, py_attached_high);
           fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\n",
                   v, c, x, y, w, p_x, p_y, u_x, u_y);
           )
}

void
embedg_mark_minor_D (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v,
	int c, int x, int y, int w, int *path_v, int *path_e,
	int nbr_v, int entry_in_path_e)
{
    int          i, vv, p_x, p_y, u_x, u_y, u;

    vv = c + n;
    p_x = path_v[0];
    p_y = path_v[nbr_v];
    /*
      see embedg_iso_get_highest_x_y_path for the above
    */

    /*
      mark the lower external face from x to y: we can walk in
      either direction
    */
    embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                            x, y, MARK_MINORS(n));

    /*
      mark the internal path which goes from the x-y path to v
      - since I haven't stored those vertices/edges I assume
      that a proper face walk should suffice

      BUT a walk that say starts at p_x and ends at vv,
      that is, a walk starting at path_e[1] entered from entry_in_path_e
      (recall that path_e[0] is a dummy)
    */
    embedg_VES_walk_mark_part_proper_face(embed_graph, n,
                                               path_e[1], entry_in_path_e,
                                               vv, MARK_MINORS(n));

    /*
      a note of caution here:
      ALWAYS mark external/internal faces before adding any other edges:
      since adding edges destroys the faces' consistency
      (adding edges makes no sense of face since we are in a non-planar
      situation)
    */
    /*
      mark the edges (u, x), (u, y), (v, w)
    */
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, x, &u_x,
                        MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, y, &u_y,
                        MARK_MINORS(n));
    embedg_add_mark_v_w(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, w,
                        MARK_MINORS(n));

    /*
      mark the tree path from v to min(u_x, u_y)
    */
    u = u_x <= u_y ? u_x : u_y;
    embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

    /*
      mark the x-y path, ie the vertices in path_v
      and the edges in path_e
    */
    embedg_mark_x_y_path(embed_graph, n, path_v, path_e, nbr_v,
                         MARK_MINORS(n));

    IF_DEB(
           fprintf(stdout, "mark minor D\n");
           fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\n",
                   v, c, x, y, w, p_x, p_y, u_x, u_y);
           )
}




minor
embedg_mark_minor_E (t_dlcl **dfs_tree, t_dlcl **back_edges,
	t_ver_edge *embed_graph, int n, int *edge_pos, int v,
	int c, int x, int y, int w, int *path_v, int *path_e, int nbr_v)
    /*
      while marking minor E return which of the minors we are dealing with
    */
{
    int          vv, p_x, p_y, u_x, u_y, u_w, u, u_max, u_min;

    vv = c + n;
    p_x = path_v[0];
    p_y = path_v[nbr_v];
    /*
      see embedg_iso_get_highest_x_y_path for the above
    */

    if (!embedg_VES_is_ver_ext_active(embed_graph, n, v, w))
        /*
          minor E1 case: we must find an ext. active z, distinct from w,
          on the external face p_x..w..p_y
        */
    {
        int       s, sin, cur, curin, z, u_z, u_xy;

        s = n;
        /*
          start searching at vv entered from 0 (in x's direction)
          -- we MUST reach p_x - hopefully! :)
        */
        cur = vv;
        curin = 0;
        while (s != p_x)
            /*
              first advance to p_x: we are sure of reaching it
            */
        {
            embedg_VES_get_succ_on_ext_face(embed_graph, n,
                                                 cur, curin,
                                                 FALSE, 0, &s, &sin);
            cur = s;
            curin = sin;
        }

        /*
          continue the walk on the external face:
          stop if either s is ext. active OR s == w

          we'll mark the lot later on
        */
        while (
               !(embedg_VES_is_ver_ext_active(embed_graph, n, v,
                                                         s)
                 && s != p_x)
               && s != w)
        {
            embedg_VES_get_succ_on_ext_face(embed_graph, n, cur, curin,
                                                 FALSE, 0, &s, &sin);
            cur = s;
            curin = sin;
        }
        /*
          now we must decide which symmetry we are in
        */
        if (embedg_VES_is_ver_ext_active(embed_graph, n, v, s))
            /*
              z is between x and w (recall that w is NOT ext. active)
            */
        {
            z = s;
            ASSERT(z != w);

            /*
              mark the external face from v^c to y in x's direction
            */
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                    vv, y, MARK_MINORS(n));
            /*
              add/mark dotted edge (u, y)
            */
            embedg_add_mark_u_x(dfs_tree, back_edges,
                                embed_graph, n, edge_pos,
                                v, y, &u_xy, MARK_MINORS(n));
        }
        else
            /*
              this is the symmetric case: must find z between w and p_y
            */
        {
            ASSERT(s == w);
            embedg_VES_get_succ_ext_active_on_ext_face(embed_graph, n,
                                                            v, cur, curin,
                                                            FALSE, 0,
                                                            &s, &sin);
            /*
              and z is distinct from p_y!
            */
            z = s;
            ASSERT(z != p_y);

            /*
              mark the external face from v^c to x in y's direction
            */
            embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                    vv, x, MARK_MINORS(n));
            /*
              add/mark dotted edge (u, x)
            */
            embedg_add_mark_u_x(dfs_tree, back_edges,
                                embed_graph, n, edge_pos,
                                v, x, &u_xy, MARK_MINORS(n));
        }
        /*
          now the marked bits which are common to both cases:
          dotted edges (u, z), (v, w), the x-y path,
          the tree path (v, min(u_xy, u_z))
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, z, &u_z, MARK_MINORS(n));
        embedg_add_mark_v_w(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, w,
                            MARK_MINORS(n));

        embedg_mark_x_y_path(embed_graph, n, path_v, path_e, nbr_v,
                             MARK_MINORS(n));

        u = u_z <= u_xy ? u_z : u_xy;
        embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E1\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t z %d\t w %d\t p_x %d\t p_y %d\t u_xy %d\t u_z %d\n",
                       v, c, x, y, z, w, p_x, p_y, u_xy, u_z);
           )

        return MINOR_E1;
    }

    /*
      in all other cases we get u_x, u_y, u_w back
      from the ext. active vertices x, y, w resp.

      again, I CANNOT embed these edges now since that would destroy
      my external/internal faces
    */

    embedg_get_u_x(embed_graph, n, v, x, &u_x);
    embedg_get_u_x(embed_graph, n, v, y, &u_y);
    embedg_get_u_x(embed_graph, n, v, w, &u_w);

    if (u_w > u_x && u_w > u_y)
        /*
          minor E2 case:
          we mark the whole external face rooted by v^c
          and the tree path (v, min(u_x, u_y))
        */
    {
        embedg_VES_walk_mark_ext_face(embed_graph, n, vv,
                                           MARK_MINORS(n));
        u = u_x <= u_y ? u_x : u_y;
        embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

        /*
          embed dotted edges (u, x), (u, y) & (u, w)
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, x, &u_x, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, y, &u_y, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, w, &u_w, MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E2\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                       v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

        return MINOR_E2;
    }

    /*
      two more things common to all remaining cases:

      mark the dotted edge (v, w) (but we MUST do that later)

      mark the x-y path
    */
    embedg_mark_x_y_path(embed_graph, n, path_v, path_e, nbr_v,
                         MARK_MINORS(n));

    if (u_x < u_y && u_w < u_y)
        /*
          minor E3 case: one of the symmetric cases:
          the external face rooted at v_c from vv to x (in x's direction)
          the external face rooted at v_c from y to w (in y's direction)
          the (v, min(u_w, u_x)) tree path
        */
    {
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                vv, p_x, MARK_MINORS(n));
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                y, w, MARK_MINORS(n));

        u = u_x <= u_w ? u_x : u_w;
        embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

        /*
          embed dotted edges (u, x), (u, y), (u, w), (v, w)
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, x, &u_x, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, y, &u_y, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, w, &u_w, MARK_MINORS(n));
        embedg_add_mark_v_w(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, w,
                            MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E3/a\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                       v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

        return MINOR_E3;
    }
    if (u_y < u_x && u_w < u_x)
        /*
          minor E3 case: the other symmetric case:
          the external face rooted at v_c from vv to y (in y's direction)
          the external face rooted at v_c from x to w (in x's direction)
          the (v, min(u_w, u_y)) tree path
        */
    {
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                vv, p_y, MARK_MINORS(n));
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                x, w, MARK_MINORS(n));

        u = u_y <= u_w ? u_y : u_w;
        embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

        /*
          embed dotted edges (u, x), (u, y), (u, w), (v, w)
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, x, &u_x, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, y, &u_y, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, w, &u_w, MARK_MINORS(n));
        embedg_add_mark_v_w(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, w,
                            MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E3/b\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                       v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

        return MINOR_E3;
    }

    if (p_x != x)
        /*
          minor E4 case: one of the symmetric cases:
          the external face rooted at v_c from vv to w (in x's direction)
          the external face rooted at v_c from vv to p_y (in y's direction)
          the tree path from max(u_x, u_y, u_w) to min(u_x, u_y, u_w)
        */
    {
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                vv, w, MARK_MINORS(n));
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                vv, p_y, MARK_MINORS(n));

        u_max = u_x > u_y ? u_x : u_y;
        u_max = u_max > u_w ? u_max : u_w;
        u_min = u_x < u_y ? u_x : u_y;
        u_min = u_min < u_w ? u_min : u_w;
        embedg_mark_tree_path(embed_graph, n, u_max, u_min, MARK_MINORS(n));

        /*
          embed dotted edges (u, x), (u, y), (u, w), (v, w)
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, x, &u_x, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, y, &u_y, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, w, &u_w, MARK_MINORS(n));
        embedg_add_mark_v_w(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, w,
                            MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E4/a\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                       v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

        return MINOR_E4;
    }
    if (p_y != y)
        /*
          minor E4 case: the other symmetric case:
          the external face rooted at v_c from vv to w (in y's direction)
          the external face rooted at v_c from vv to x (in x's direction)
          (here p_x = x!)
          the tree path from max(u_x, u_y, u_w) to min(u_x, u_y, u_w)
        */
    {
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 1,
                                                vv, w, MARK_MINORS(n));
        embedg_VES_walk_mark_part_ext_face(embed_graph, n, vv, 0,
                                                vv, x, MARK_MINORS(n));

        u_max = u_x > u_y ? u_x : u_y;
        u_max = u_max > u_w ? u_max : u_w;
        u_min = u_x < u_y ? u_x : u_y;
        u_min = u_min < u_w ? u_min : u_w;
        embedg_mark_tree_path(embed_graph, n, u_max, u_min, MARK_MINORS(n));

        /*
          embed dotted edges (u, x), (u, y), (u, w), (v, w)
        */
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, x, &u_x, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, y, &u_y, MARK_MINORS(n));
        embedg_add_mark_u_x(dfs_tree, back_edges,
                            embed_graph, n, edge_pos,
                            v, w, &u_w, MARK_MINORS(n));
        embedg_add_mark_v_w(dfs_tree, back_edges,
                            embed_graph, n, edge_pos, v, w,
                            MARK_MINORS(n));

        IF_DEB(
               fprintf(stdout, "mark minor E$/b\n");
               fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                       v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

        return MINOR_E4;
    }

    /*
      this is the last case for minor E: when the homeomorph is K5

      mark the whole external face rooted at v^c
      mark the tree path from v to min(u_x, u_y, u_w)
    */

    embedg_VES_walk_mark_ext_face(embed_graph, n, vv, MARK_MINORS(n));

    u = u_x < u_y ? u_x : u_y;
    u = u < u_w ? u : u_w;
    embedg_mark_tree_path(embed_graph, n, v, u, MARK_MINORS(n));

    /*
      embed dotted edges (u, x), (u, y), (u, w), (v, w)
    */
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos,
                        v, x, &u_x, MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos,
                        v, y, &u_y, MARK_MINORS(n));
    embedg_add_mark_u_x(dfs_tree, back_edges,
                        embed_graph, n, edge_pos,
                        v, w, &u_w, MARK_MINORS(n));
    embedg_add_mark_v_w(dfs_tree, back_edges,
                        embed_graph, n, edge_pos, v, w,
                        MARK_MINORS(n));

    IF_DEB(
           fprintf(stdout, "mark minor E5\n");
           fprintf(stdout, "v %d\t c %d\t x %d\t y %d\t w %d\t p_x %d\t p_y %d\t u_x %d\t u_y %d\t u_w %d\n",
                   v, c, x, y, w, p_x, p_y, u_x, u_y, u_w);
           )

    return MINOR_E5;
}
/*
 *  proper_face_walk.c
 */

/*
  What:
  *****

  Implementing a proper face walk within the VES structure.
  This is obviously not the same as an external face walk,
  but is simply the standard face walk in a planar embedding.

  Not much to say, if only to emphasize that for our
  purposes here we assume:

  1. the short-cut edges have been removed from the VES structure
  2. each vertex/edge has been given its orientation
  2. the adjacency lists (vertex + plus its incident edges)
     are consistent:  (and this is IMPORTANT)
     that is, the way to traverse an adj. list (ie what
     constitute previous and next in the list which actually
     is a planar embedding at this stage) is indicated
     by the vertex/edge's orientation


     try to explain this better another time.... sorry...



  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  from

  Simplified O(n) Planarity Algorithms  (draft)
  ************************************

  John Boyer      JBoyer@PureEdge.com, jboyer@acm.org
  Wendy Myrvold   wendym@csr.uvic.ca


  ++++++++++++++++++++++++++++++++++++++++++++++++++++++
  authors:
  ********

  Paulette Lieby (Magma), Brendan McKay (ANU)

  Started October 2001
*/


#include "planarity.h"

#define IF_DEB(x)    {}
#define IF_DEB_PROPER_FACE(x)    {}
#define IF_VERB(x)   {}



/* aproto: header embed_graph_protos.h */




boolean
embedg_VES_get_succ_on_proper_face_with_avoidance (t_ver_edge *embed_graph,
	int n, int e, int ein, int a, boolean MARK, int mark, int *s,
	int *next_e, int *next_ein)
    /*
      find the successor s of embed_graph[e].neighbour
      (entered via ein) on a proper face traversal
      which avoids (the vertex) a if a != n

      also returns the edge next_e such that
      embed_graph[next_e].neighbour = s (to allow for continuation
      of the walk)

      assumes that short-cut edges have been removed and that each
      edge/vertex has been given its orientation

      and (more importantly) assumes that adjacency lists are consistent

      this function has been written especially to retrieve the highest
      x-y path for the isolator;
      (see embedg_iso_get_highest_x_y_path)
      but as I discovered later (when marking an internal face
      as for minor D) this function is general purpose

      PLUS: return true if the proper face walk has to skip an edge
      incident to a (ie had to "avoid" a)

      PLUS: mark s & next_e if so requested
    */
{
    int            eout;
    int            twin, twinout;
    boolean        avoid_a;

    ASSERT(embedg_VES_is_edge(n, e));
    ASSERT(!embedg_VES_is_short_cut_edge(embed_graph, n, e));

    IF_DEB(
           fprintf(stdout, "get_succ_on_proper_face, \n");
           )

    avoid_a = FALSE;
    /*
      find the direction out of the edge
    */
    eout = 1 ^ ein;

    /*
      get the twin edge
    */
    twin = embedg_VES_get_twin_edge(embed_graph, n, e);

    /*
      for each edge we must set the way to get to the next
      in the adjacency list:
      adjacency lists are traversed according to the vertex/edges
      orientation (one unique orientation per list of course)
    */
    if (embed_graph[e].sign != embed_graph[twin].sign)
        /*
          invert traversal
        */
    {
        twinout = 1 ^ eout;
    }
    else
        /*
          traversal is identical
        */
    {
        twinout = eout;
    }

    /*
      now, we want the edge previous to twin in twin's adjacency list,
      ie link[1 ^ twinout]
    */
    *next_e = embed_graph[twin].link[1 ^ twinout];
    /*
      next_e could be a vertex, I need an edge
    */
    if (embedg_VES_is_vertex(n, *next_e)
        || embedg_VES_is_virtual_vertex(n, *next_e))
        /*
          at this stage all virtual vertices should have
          been disabled BUT the vertices rooting the bicomps!!!
        */
    {
        *next_e = embed_graph[*next_e].link[1 ^ twinout];
    }
    ASSERT(embedg_VES_is_edge(n, *next_e));
    ASSERT(!embedg_VES_is_short_cut_edge(embed_graph, n, e));
    *s = embed_graph[*next_e].neighbour;

    if (*s == a)
        /*
          want to avoid this vertex, so must get yet previous
          edge in adjacency list
        */
    {
        avoid_a = TRUE;

        *next_e = embed_graph[*next_e].link[1 ^ twinout];
        if (embedg_VES_is_vertex(n, *next_e)
            || embedg_VES_is_virtual_vertex(n, *next_e))
        {
            *next_e = embed_graph[*next_e].link[1 ^ twinout];
        }
        ASSERT(embedg_VES_is_edge(n, *next_e));
        ASSERT(!embedg_VES_is_short_cut_edge(embed_graph, n, e));
    }
    *s = embed_graph[*next_e].neighbour;
    ASSERT(*s != a);

    /*
      finally (again, because lists  are consistent)
    */
    *next_ein = 1 ^ twinout;

    /*
      now mark s and next_e if required
    */
    if (MARK)
    {
        embed_graph[*s].visited =
            embed_graph[*next_e].visited = mark;
        /*
          ouuh... must mark the twin as well....
          but ONLY when we mark the minors....
          that is poor design, can we do better????
          -- don't think so...

          (when we mark when counting the faces, we MUST only
          mark the edge and NOT its twin)
        */
        if (mark == MARK_MINORS(n))
        {
            twin =
                embedg_VES_get_twin_edge(embed_graph, n, *next_e);
            embed_graph[twin].visited = mark;
        }
    }

    return avoid_a;
}



void
embedg_VES_get_succ_on_proper_face (t_ver_edge *embed_graph, int n, int e,
	int ein, int MARK, int mark, int *s, int *next_e, int *next_ein)
    /*
      same as above but without avoidance
    */
{
    boolean  avoid;

    avoid =
        embedg_VES_get_succ_on_proper_face_with_avoidance(
                                                       embed_graph, n,
                                                       e, ein, n,
                                                       MARK, mark,
                                                       s, next_e, next_ein);
    ASSERT(avoid == FALSE);
}


void
embedg_VES_walk_proper_face (t_ver_edge *embed_graph, int n, int e,
	int ein, boolean MARK, int mark)
    /*
      traversing a proper face starting at edge e which has been entered
      via ein

      -- we mark the visited edges with mark if so requested

      assumes that short-cut edges have been removed and that each
      edge/vertex has been given its orientation
    */
{
    int     s, cur_e, cur_ein, next_e, next_ein;

    next_e = n; /* this is an invalid value for an edge */

    IF_DEB_PROPER_FACE(
                       fprintf(stdout, "proper face traversal\n");
                       )

    cur_e = e;
    cur_ein = ein;
    while (next_e != e)
    {
        ASSERT(embedg_VES_is_edge(n, cur_e));
        ASSERT(!embedg_VES_is_short_cut_edge(embed_graph,
                                                        n, cur_e));
        IF_DEB_PROPER_FACE(
                           embedg_VES_print_edge(embed_graph, n, cur_e);
                           )

        embedg_VES_get_succ_on_proper_face(embed_graph, n,
                                                cur_e, cur_ein,
                                                MARK, mark,
                                                &s, &next_e, &next_ein);
        cur_e = next_e;
        cur_ein = next_ein;
    }

    /*
      note that by doing so we would have marked e and the first of e's
      endpoints since by exiting the loop e = next_e and s is the
      actual starting vertex of the walk
    */
}