Quelle  planarity.c   Sprache: 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(
--> --------------------

--> maximum size reached

--> --------------------