graphNonplanar.c

Go to the documentation of this file.

/* Copyright (c) 2005 by John M. Boyer, All Rights Reserved.  Please see
 * License.txt for use and redistribution license. */
/* Copyright (c) 1997-2003 by John M. Boyer, All Rights Reserved.
        This code may not be reproduced or disseminated in whole or in part 
        without the written permission of the author. */

#define GRAPHNONPLANAR_C

#include "graph_boyer.h"

/* Imported functions */
extern void _ClearIsolatorContext (graphP theGraph);
extern void _FillVisitedFlags (graphP,
                               int);
extern void _FillVisitedFlagsInBicomp (graphP theGraph,
                                       int BicompRoot,
                                       int FillValue);
extern void _SetVertexTypeInBicomp (graphP theGraph,
                                    int BicompRoot,
                                    int theType);
extern int _GetNextVertexOnExternalFace (graphP theGraph,
                                         int curVertex,
                                         int *pPrevLink);
extern int _GetPertinentChildBicomp (graphP theGraph,
                                     int W);
extern void _WalkDown (graphP theGraph,
                       int I,
                       int RootVertex);
extern void _OrientVerticesInEmbedding (graphP theGraph);
extern void _OrientVerticesInBicomp (graphP theGraph,
                                     int BicompRoot,
                                     int PreserveSigns);

/* Private functions (exported to system) */
int _ChooseTypeOfNonplanarityMinor (graphP theGraph,
                                    int I,
                                    int R);
int _InitializeNonplanarityContext (graphP theGraph,
                                    int I,
                                    int R);
int _FindNonplanarityBicompRoot (graphP theGraph);
void _FindActiveVertices (graphP theGraph,
                          int R,
                          int *pX,
                          int *pY);
int _FindPertinentVertex (graphP theGraph);
void _PopAndUnmarkVerticesAndEdges (graphP theGraph,
                                    int Z);
int _MarkHighestXYPath (graphP theGraph);
int _MarkZtoRPath (graphP theGraph);
int _FindExtActivityBelowXYPath (graphP theGraph);

/****************************************************************************
 _ChooseTypeOfNonplanarityMinor()
 ****************************************************************************/
int _ChooseTypeOfNonplanarityMinor (graphP theGraph,
                                    int I,
                                    int R)
{
  int N,
    X,
    Y,
    W,
    Px,
    Py,
    Z,
    DFSChild,
    RootId;

/* Create the initial non-planarity minor state in the isolator context */
  if (_InitializeNonplanarityContext (theGraph, I, R) != OK)
    return NOTOK;
  N = theGraph->N;
  R = theGraph->IC.r;
  X = theGraph->IC.x;
  Y = theGraph->IC.y;
  W = theGraph->IC.w;

/* If the root copy is not a root copy of the current vertex I,
        then the Walkdown terminated because it couldn't find 
        a viable path along a child bicomp, which is Minor A. */
  if (theGraph->V[R - N].DFSParent != I)

  {
    theGraph->IC.minorType |= FLAGS_MINOR_A;
    return OK;
  }

/* If W has an externally active pertinent child bicomp, then
     we've found Minor B */
  if (theGraph->V[W].pertinentBicompList != NIL)

  {
    RootId =
      LCGetPrev (theGraph->BicompLists, theGraph->V[W].pertinentBicompList,
                 NIL);
    DFSChild = RootId;
    if (theGraph->V[DFSChild].Lowpoint < I)

    {
      theGraph->IC.minorType |= FLAGS_MINOR_B;
      return OK;
    }
  }

/* Find the highest obstructing X-Y path */
  if (_MarkHighestXYPath (theGraph) != OK)
    return NOTOK;
  Px = theGraph->IC.px;
  Py = theGraph->IC.py;

/* If either point of attachment is 'high' (P_x closer to R than X
     or P_y closer to R than Y along external face), then we've
     matched Minor C. */
  if (theGraph->G[Px].type == VERTEX_HIGH_RXW
      || theGraph->G[Py].type == VERTEX_HIGH_RYW)

  {
    theGraph->IC.minorType |= FLAGS_MINOR_C;
    return OK;
  }

/* For Minor D, we search for a path from an internal
     vertex Z along the X-Y path up to the root R of the bicomp. */
  if (_MarkZtoRPath (theGraph) == NOTOK)
    return NOTOK;
  if (theGraph->IC.z != NIL)

  {
    theGraph->IC.minorType |= FLAGS_MINOR_D;
    return OK;
  }

/* For Minor E, we search for an externally active vertex Z
     below the points of attachment of the X-Y path */
  Z = _FindExtActivityBelowXYPath (theGraph);
  if (Z != NIL)

  {
    theGraph->IC.z = Z;
    theGraph->IC.minorType |= FLAGS_MINOR_E;
    return OK;
  }
  return NOTOK;
}


/****************************************************************************
 _InitializeNonplanarityContext()
 ****************************************************************************/
int _InitializeNonplanarityContext (graphP theGraph,
                                    int I,
                                    int R)
{
  int e,
    X,
    Y,
    W,
    Z,
    ZPrevLink,
    ZType;
  int singleBicompMode = (R == NIL) ? 0 : 1;

/* For the embedding or in a given bicomp, orient the vertices, 
    and clear the visited members of all vertex and edge records. */
  if (!singleBicompMode)

  {
    _OrientVerticesInEmbedding (theGraph);
    _FillVisitedFlags (theGraph, 0);
  }

  else

  {
    _OrientVerticesInBicomp (theGraph, R, 1);
    _FillVisitedFlagsInBicomp (theGraph, R, 0);
  }

/* Blank out the isolator context, then assign the input graph reference
     and the current vertext I into the context. */
  _ClearIsolatorContext (theGraph);
  theGraph->IC.v = I;

/* Now we find a root copy R of the current vertex on which the Walkdown failed
   (i.e. there is an unembedded back edge between an ancestor of the current
   vertex and descendant of the current vertex in the subtree rooted by
   the DFS child C=R-N. */
  R = _FindNonplanarityBicompRoot (theGraph);
  if (R == NIL)
    return NOTOK;

/* Now we find the active vertices along both external face paths extending 
     from R. If either is not a stopping vertex, then we call Walkdown to
     reconstruct the stack to the root of the descendant bicomp that blocked 
     the Walkdown. Otherwise, R is the desired root. Either way, the stopping
     vertices x and y are calculated. */
  _FindActiveVertices (theGraph, R, &X, &Y);
  if (theGraph->V[X].pertinentBicompList != NIL
      || theGraph->V[Y].pertinentBicompList != NIL)

  {

    /* We are dealing with minor A, which has a main bicomp rooted by
     * a descendant of R.  So we put the bicomp rooted by R back
     * the way we found it. */
    if (singleBicompMode)
      _OrientVerticesInBicomp (theGraph, R, 1);

    /* Now we do the Walkdown to find the descendant bicomp. */
    _WalkDown (theGraph, I, R);
    if (sp_IsEmpty (theGraph->theStack))
      return NOTOK;
    sp_Pop2 (theGraph->theStack, R, e);

    /* Now we give the proper orientation to the descendant bicomp, 
     * but we make it reversible (last param=1) to make processing
     * easier for the K3,3 search, which simply reinitializes
     * everything when it finds minor A. */
    if (singleBicompMode)
      _OrientVerticesInBicomp (theGraph, R, 1);

    /* Now we find the stopping vertices along the external face
     * paths of the descendant bicomp. */
    _FindActiveVertices (theGraph, R, &X, &Y);
  }

/* We store the info we have gathered so far in the isolator context */
  theGraph->IC.r = R;
  theGraph->IC.x = X;
  theGraph->IC.y = Y;

/* Now, we obtain the pertinent vertex W on the lower external face
    path between X and Y (that path that does not include R). */
  theGraph->IC.w = W = _FindPertinentVertex (theGraph);

/* In the current bicomp, we clear the type flags */

/* Now we can classify the vertices along the external face of the bicomp
    rooted at R as 'high RXW', 'low RXW', 'high RXY', 'low RXY' */
  _SetVertexTypeInBicomp (theGraph, R, TYPE_UNKNOWN);
  ZPrevLink = 1;
  Z = _GetNextVertexOnExternalFace (theGraph, R, &ZPrevLink);
  ZType = VERTEX_HIGH_RXW;
  while (Z != W)

  {
    if (Z == X)
      ZType = VERTEX_LOW_RXW;
    theGraph->G[Z].type = ZType;
    Z = _GetNextVertexOnExternalFace (theGraph, Z, &ZPrevLink);
  }
  ZPrevLink = 0;
  Z = _GetNextVertexOnExternalFace (theGraph, R, &ZPrevLink);
  ZType = VERTEX_HIGH_RYW;
  while (Z != W)

  {
    if (Z == Y)
      ZType = VERTEX_LOW_RYW;
    theGraph->G[Z].type = ZType;
    Z = _GetNextVertexOnExternalFace (theGraph, Z, &ZPrevLink);
  }

/* All work is done, so return success */
  return OK;
}


/****************************************************************************
 _FindNonplanarityBicompRoot()

 This procedure finds the root copy R of the current vertex on which the
 Walkdown failed (whether it failed while traversing the bicomp rooted by
 R or some descendant bicomp is determined later).

 We iterate the forward cycle edges of the vertex I looking for a forward 
 edge (I, W) that was not embedded.  Once it is found, we figure out which 
 bicomp rooted by a root copy of I contains W or contains a DFS ancestor of W.

 This turns out to be an easy test.  The desired bicomp is rooted by the DFS
 tree edge (I, C) with the largest value of C that does not exceed W.  C is
 a DFS ancestor of Z.

 Return: The desired root copy, or NIL on error.
 ****************************************************************************/
int _FindNonplanarityBicompRoot (graphP theGraph)
{
  int R,
    tempChild,
    fwdArc,
    W = NIL,
    C = NIL,
    I = theGraph->IC.v;

/* Obtain the forward arc of an unembedded back edge from I to one of its
    descendants (edges are removed from the forward arc list as they are
    embedded, so the list will be empty if all edges were embedded). */
  if ((fwdArc = theGraph->V[I].fwdArcList) == NIL)
    return NIL;
  W = theGraph->G[fwdArc].v;

/* Find the greatest DFS child C of I that is less than W.  This will
    give us the ancestor of W that is a child of I.  Since the
    ancestors of I have not been processed by the planarity algorithm,
    the separatedDFSChildList of I contains all the children of I. */
  tempChild = theGraph->V[I].separatedDFSChildList;
  while (tempChild != NIL)

  {
    if (tempChild > C && tempChild < W)
      C = tempChild;
    tempChild =
      LCGetNext (theGraph->DFSChildLists, theGraph->V[I].separatedDFSChildList,
                 tempChild);
  }
  if (C == NIL)
    return NIL;

/* The root vertex of a bicomp rooted by edge (I, C) is located at
        position C+N in our data structures */
  R = C + theGraph->N;
  return R;
}


/****************************************************************************
 _FindStoppingVertices()

 Descends from the root of a bicomp R in both the link[0] and link[1] 
 directions, returning the first active vertex appearing in either direction.
 ****************************************************************************/
void _FindActiveVertices (graphP theGraph,
                          int R,
                          int *pX,
                          int *pY)
{
  int XPrevLink = 1,
    YPrevLink = 0,
    I = theGraph->IC.v;
  *pX = _GetNextVertexOnExternalFace (theGraph, R, &XPrevLink);
  *pY = _GetNextVertexOnExternalFace (theGraph, R, &YPrevLink);
  while (_VertexActiveStatus (theGraph, *pX, I) == VAS_INACTIVE)
    *pX = _GetNextVertexOnExternalFace (theGraph, *pX, &XPrevLink);
  while (_VertexActiveStatus (theGraph, *pY, I) == VAS_INACTIVE)
    *pY = _GetNextVertexOnExternalFace (theGraph, *pY, &YPrevLink);
}


/****************************************************************************
 _FindPertinentVertex()

 Get the first vertex after x. Since x was obtained using a prevlink of 1 on r,
 we use the same prevlink so we don't go back to r (works because all vertices
 have the same orientation).
 Then, we proceed around the lower path until we find a vertex W that either
 has pertinent child bicomps or is directly adjacent to the current vertex I.
 ****************************************************************************/
int _FindPertinentVertex (graphP theGraph)
{
  int W = theGraph->IC.x,
    WPrevLink = 1,
    I = theGraph->IC.v;
  W = _GetNextVertexOnExternalFace (theGraph, W, &WPrevLink);
  while (W != theGraph->IC.y)

  {
    if (PERTINENT (theGraph, W, I))
      return W;
    W = _GetNextVertexOnExternalFace (theGraph, W, &WPrevLink);
  }
  return NIL;
}


/****************************************************************************
 _PopAndUnmarkVerticesAndEdges()

 Pop all vertex/edge pairs from the top of the stack up to a terminating
 vertex Z and mark as unvisited.  If Z is NIL, then all vertex/edge pairs
 are popped and marked as unvisited.
 ****************************************************************************/
void _PopAndUnmarkVerticesAndEdges (graphP theGraph,
                                    int Z)
{
  int V,
    e;
  while (sp_NonEmpty (theGraph->theStack))

  {
    sp_Pop (theGraph->theStack, e);

    /* If we popped a vertex other than the termination vertex Z, then
     * we also pop the edge we pushed, and we clear the visited flags
     * for the vertex and the edge's two edge records. */
    if (e < 2 * theGraph->N && e != Z)

    {
      V = e;
      sp_Pop (theGraph->theStack, e);
      theGraph->G[V].visited = 0;
      theGraph->G[e].visited = 0;
      theGraph->G[gp_GetTwinArc (theGraph, e)].visited = 0;
    }

    /* If we popped an edge or the terminating vertex Z, then put it
     * back and break */

    else

    {
      sp_Push (theGraph->theStack, e);
      break;
    }
  }
}


/****************************************************************************
 _MarkHighestXYPath()

 An X-Y path in the bicomp rooted by R is a path attached to the external
 face at points Px and Py that separates W from R such that a back edge (R, W)
 cannot be embedded within the bicomp. Recall that R is a root copy of I, so
 (R, W) is the representative of (I, W).  Also, note that W is pertinent if
 either W *or* one of its descendants in a separate bicomp has, in the input 
 graph, a back edge to I.

 If no X-Y path separating W from R is found, then NOTOK is returned because
 this procedure is only called once an X-Y path is guaranteed (by our proof
 of correctness) to exist.

 The desired output is to set the 'visited' flags of the X-Y path with
 highest points of attachment to the external face (i.e. the points of
 attachment that are closest to R along the external face).  This includes
 marking both the vertices and edges along the X-Y path.

 As a function of initialization, the vertices along the external face
 (other than R and W) have been classified as 'high RXW', 'low RXW', 'high RXY', 
 or 'low RXY'. Once the vertices have been categorized, we proceed with trying 
 to set the visitation flags in the way described above.  To do this, we first 
 remove all edges incident to R except the two edges that join R to the external 
 face. The result is that R and its two remaining edges are a 'corner' in the
 external face but also in a single proper face whose boundary includes the
 X-Y path with the highest attachment points. Thus, we simply need to walk
 this proper face to find the desired X-Y path. Note, however, that the
 resulting face boundary may have attached cut vertices.  Any such separable
 component contains a vertex neighbor of R, but the edge to R has been
 temporarily removed.  The algorithm removes loop of vertices and edges along
 the proper face so that only a path is identified.

 To walk the proper face containing R, we begin with its link[0] successor,
 then take the link[1] corner at every subsequent turn.  For each vertex,
 we mark as visited the vertex as well as the edge used to enter the vertex
 (except for the edge used to enter the RXW vertex).  We also push the visited
 vertices and edges onto a stack.

 As we walk the proper face, we keep track of the last vertex P_x we visited of
 type RXW (high or low).  Each time we encounter a vertex of type RXW (high or
 low), we pop the stack and unmark all of the edges and vertices visited because
 they were part of a path parallel to the external face that does not obstruct
 W from reaching R within the bicomp.  If we encounter vertex W, then there is
 no obstructing X-Y path since we removed only edges incident to R, so we pop
 the stack unmarking everything then return NOTOK as stated above.  If we
 encounter a vertex Z previously visited, then we pop the stack, unmarking the
 vertices and edges popped, until we find the prior occurence of Z on the stack.

 Otherwise, the first time we encounter a vertex P_y of type 'RYW', we stop
 because the obstructing X-Y path has been marked visited and its points of
 connection P_x and P_y have been found.

 Once the X-Y path is identified, we restore the edges incident to R.

 The stack space used is no greater than 3N.  The first N accounts for removing
 the edges incident to R.  The other 2N accounts for the fact that each
 iteration of the main loop visits a vertex, pushing its index and the
 location of an edge record.  If a vertex is encountered that is already
 on the stack, then it is not pushed again (and in fact part of the stack
 is removed). 
 ****************************************************************************/
int _MarkHighestXYPath (graphP theGraph)
{
  int J,
    Z,
    e;
  int R,
    X,
    Y,
    W;

/* Initialization */
  R = theGraph->IC.r;
  X = theGraph->IC.x;
  Y = theGraph->IC.y;
  W = theGraph->IC.w;
  theGraph->IC.px = theGraph->IC.py = NIL;
  sp_ClearStack (theGraph->theStack);

/* Remove the internal edges incident to vertex R */
  J = theGraph->G[R].link[0];
  J = theGraph->G[J].link[0];
  while (J != theGraph->G[R].link[1])

  {
    sp_Push (theGraph->theStack, J);
    gp_HideEdge (theGraph, J);
    J = theGraph->G[J].link[0];
  }

/* Walk the proper face containing R to find and mark the highest
        X-Y path. Note that if W is encountered, then there is no
        intervening X-Y path, so we would return NOTOK. */
  Z = R;
  J = theGraph->G[R].link[1];
  while (theGraph->G[Z].type != VERTEX_HIGH_RYW
         && theGraph->G[Z].type != VERTEX_LOW_RYW)

  {

    /* Advance J and Z along the proper face containing R */
    J = theGraph->G[J].link[1];
    if (J < 2 * theGraph->N)
      J = theGraph->G[J].link[1];
    Z = theGraph->G[J].v;
    J = gp_GetTwinArc (theGraph, J);

    /* If Z is already visited, then pop everything since the last time
     * we visited Z because its all part of a separable component. */
    if (theGraph->G[Z].visited)

    {
      _PopAndUnmarkVerticesAndEdges (theGraph, Z);
    }

    /* If we have not visited this vertex before... */

    else

    {

      /* If we found another vertex along the RXW path, then blow off
       * all the vertices we visited so far because they're not part of
       * the obstructing path */
      if (theGraph->G[Z].type == VERTEX_HIGH_RXW
          || theGraph->G[Z].type == VERTEX_LOW_RXW)

      {
        theGraph->IC.px = Z;
        _PopAndUnmarkVerticesAndEdges (theGraph, NIL);
      }

      /* Push the current vertex onto the stack of vertices visited
       * since the last RXW vertex was encountered */
      sp_Push (theGraph->theStack, J);
      sp_Push (theGraph->theStack, Z);

      /* Mark the vertex Z as visited as well as its edge of entry
       * (except the entry edge for P_x). */
      theGraph->G[Z].visited = 1;
      if (Z != theGraph->IC.px)

      {
        theGraph->G[J].visited = 1;
        theGraph->G[gp_GetTwinArc (theGraph, J)].visited = 1;
      }

      /* If we found an RYW vertex, then we have successfully finished
       * identifying the highest X-Y path, so we record the point of
       * attachment and break the loop. */
      if (theGraph->G[Z].type == VERTEX_HIGH_RYW
          || theGraph->G[Z].type == VERTEX_LOW_RYW)

      {
        theGraph->IC.py = Z;
        break;
      }
    }
  }

/* Restore the internal edges incident to R that were previously removed,
        ignoring any leftover vertices that might be on the stack. */
  while (sp_NonEmpty (theGraph->theStack))

  {
    sp_Pop (theGraph->theStack, e);
    if (e < 2 * theGraph->N)
      sp_Pop (theGraph->theStack, e);

    else
      gp_RestoreEdge (theGraph, e);
  }

/* Return the result */
  return theGraph->IC.py == NIL ? NOTOK : OK;
}


/****************************************************************************
 _MarkZtoRPath()

 This function assumes that _MarkHighestXYPath() has already been called,
 which marked as visited the vertices and edges along the X-Y path.

 We begin at the point of attachment P_x and traverse its link[1] edge records
 until we find one marked visited, which leads to the first internal vertex
 along the X-Y path.  We begin with this vertex (and its edge of entry), and
 we run until we find P_y.  For each internal vertex Z and its edge of entry
 ZPrevArc, we take the link[1] successor edge record of ZPrevArc (skipping Z
 if it intervenes).  This is called ZNextArc.  If ZNextArc is marked visited
 then it is along the X-Y path, so we use it to exit Z and go to the next
 vertex on the X-Y path.

 If ZNextArc is not visited, then when _MarkHighestXYPath() ran, it exited
 Z from ZNextArc, then eventually reentered Z.  In other words, Z became a
 cut vertex when we removed the internal edges incident to R. Thus, ZNextArc
 indicates the first edge in an internal path to R.

 When we find an unvisited ZNextArc, we stop running the X-Y path and instead
 begin marking the Z to R path.  We move to successive vertices using a
 twin arc then a link[1] successor edge record, only this time we have not
 removed the internal edges incident to R, so this technique does eventually
 lead us all the way to R.

 If we do not find an unvisited ZNextArc for any vertex Z on the X-Y path and
 inside the bicomp, then there is no Z to R path, so we return.
 ****************************************************************************/
int _MarkZtoRPath (graphP theGraph)
{
  int ZPrevArc,
    ZNextArc,
    Z,
    R,
    Px,
    Py;

/* Initialize */
  R = theGraph->IC.r;
  Px = theGraph->IC.px;
  Py = theGraph->IC.py;
  theGraph->IC.z = NIL;

/* Begin at Px and search its adjacency list for the edge leading to
   the first internal vertex of the X-Y path. */
  Z = Px;
  ZNextArc = theGraph->G[Z].link[1];
  while (ZNextArc != theGraph->G[Z].link[0])

  {
    if (theGraph->G[ZNextArc].visited)
      break;
    ZNextArc = theGraph->G[ZNextArc].link[1];
  }
  if (!theGraph->G[ZNextArc].visited)
    return NOTOK;

/* For each internal vertex Z, determine whether it has a path to root. */
  while (theGraph->G[ZNextArc].visited)

  {
    ZPrevArc = gp_GetTwinArc (theGraph, ZNextArc);
    ZNextArc = theGraph->G[ZPrevArc].link[1];
    if (ZNextArc < 2 * theGraph->N)
      ZNextArc = theGraph->G[ZNextArc].link[1];
  }
  ZPrevArc = gp_GetTwinArc (theGraph, ZNextArc);
  Z = theGraph->G[ZPrevArc].v;

/* If there is no Z to R path, return */
  if (Z == Py)
    return OK;

/* Otherwise, store Z in the isolation context */
  theGraph->IC.z = Z;

/* Walk the proper face starting with (Z, ZNextArc) until we reach R, marking
        the vertices and edges encountered along the way, then Return OK. */
  while (Z != R)

  {

    /* If we ever encounter a non-internal vertex (other than the root R),
     * then corruption has occured, so we return NOTOK */
    if (theGraph->G[Z].type != TYPE_UNKNOWN)
      return NOTOK;

    /* Go to the next vertex indicated by ZNextArc */
    Z = theGraph->G[ZNextArc].v;

    /* Mark the next vertex and the edge leading to it as visited. */
    theGraph->G[ZNextArc].visited = 1;
    theGraph->G[ZPrevArc].visited = 1;
    theGraph->G[Z].visited = 1;

    /* Go to the next edge in the proper face */
    ZNextArc = theGraph->G[ZPrevArc].link[1];
    if (ZNextArc < 2 * theGraph->N)
      ZNextArc = theGraph->G[ZNextArc].link[1];
    ZPrevArc = gp_GetTwinArc (theGraph, ZNextArc);
  }

/* Found Z to R path, so indicate as much to caller */
  return OK;
}


/****************************************************************************
 _FindExtActivityBelowXYPath()

 Get an externally active vertex along the lower external face path between
 the points of attachment P_x and P_y of a 'low' X-Y Path.
 NOTE: By the time this function is called, Px and Py have already been found
        to be at or below X and Y.
 ****************************************************************************/
int _FindExtActivityBelowXYPath (graphP theGraph)
{
  int Z = theGraph->IC.px,
    ZPrevLink = 1,
    Py = theGraph->IC.py,
    I = theGraph->IC.v;
  Z = _GetNextVertexOnExternalFace (theGraph, Z, &ZPrevLink);
  while (Z != Py)

  {
    if (_VertexActiveStatus (theGraph, Z, I) == VAS_EXTERNAL)
      return Z;
    Z = _GetNextVertexOnExternalFace (theGraph, Z, &ZPrevLink);
  }
  return NIL;
}

---