Quelle planar.c Sprache: C

/********************************************************************************
**
*A  planar.c               Planarity testing
**
**
**  Copyright (C) 2018 - J. D. Mitchell
**
**  This file is free software, see the digraphs/LICENSE.
**
********************************************************************************/

#include "planar.h"

// C headers
#include <limits.h>   // for INT_MAX
#include <stdbool.h>  // for true and false

// Digraphs package headers
#include "digraphs-config.h"  // for DIGRAPHS_WITH_INCLUDED_PLANARITY
#include "digraphs-debug.h"   // for DIGRAPHS_ASSERT
#include "digraphs.h"         // for DigraphNrVertices, DigraphNrEdges, . . .
#include "gap-includes.h"     // for Fail, False, True

// edge-addition-planarity-suite headers
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored \
    "-Wincompatible-pointer-types-discards-qualifiers"
#pragma clang diagnostic ignored "-Wstrict-prototypes"
#elif defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstrict-prototypes"
#pragma GCC diagnostic ignored "-Wswitch-default"
#endif
#ifdef DIGRAPHS_WITH_INCLUDED_PLANARITY
#include "c/graph.h"
#include "c/graphLib/homeomorphSearch/graphK23Search.h"
#include "c/graphLib/homeomorphSearch/graphK33Search.h"
#include "c/graphLib/homeomorphSearch/graphK4Search.h"
#else
#include "planarity/graph.h"
#include "planarity/c/graphLib/homeomorphSearch/graphK23Search.h"
#include "planarity/c/graphLib/homeomorphSearch/graphK33Search.h"
#include "planarity/c/graphLib/homeomorphSearch/graphK4Search.h"
#endif
#if defined(__clang__)
#pragma clang diagnostic pop
#elif defined(__GNUC__)
#pragma GCC diagnostic pop
#endif

// Forward declaration of the main function in this file.
Obj trivial_planarity_output(Int V, bool krtwsk);

// Forward declaration of the main function in this file.
Obj boyers_planarity_check(Obj digraph, int flags, bool krtwsk);

// GAP level functions
Obj FuncIS_PLANAR(Obj self, Obj digraph) {
  return boyers_planarity_check(digraph, EMBEDFLAGS_PLANAR, false);
}

Obj FuncKURATOWSKI_PLANAR_SUBGRAPH(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_PLANAR, true);
  return (ELM_PLIST(res, 1) == False ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncPLANAR_EMBEDDING(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_PLANAR, true);
  return (ELM_PLIST(res, 1) == True ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncIS_OUTER_PLANAR(Obj self, Obj digraph) {
  return boyers_planarity_check(digraph, EMBEDFLAGS_OUTERPLANAR, false);
}

Obj FuncKURATOWSKI_OUTER_PLANAR_SUBGRAPH(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_OUTERPLANAR, true);
  return (ELM_PLIST(res, 1) == False ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncOUTER_PLANAR_EMBEDDING(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_OUTERPLANAR, true);
  return (ELM_PLIST(res, 1) == True ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncSUBGRAPH_HOMEOMORPHIC_TO_K23(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_SEARCHFORK23, true);
  return (ELM_PLIST(res, 1) == False ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncSUBGRAPH_HOMEOMORPHIC_TO_K33(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_SEARCHFORK33, true);
  return (ELM_PLIST(res, 1) == False ? ELM_PLIST(res, 2) : Fail);
}

Obj FuncSUBGRAPH_HOMEOMORPHIC_TO_K4(Obj self, Obj digraph) {
  Obj res = boyers_planarity_check(digraph, EMBEDFLAGS_SEARCHFORK4, true);
  return (ELM_PLIST(res, 1) == False ? ELM_PLIST(res, 2) : Fail);
}

// The implementation of the main functions in this file.

Obj trivial_planarity_output(Int V, bool krtwsk) {
  Obj res;
  if (krtwsk) {
    Obj subgraph = NEW_PLIST_IMM(T_PLIST, V);
    SET_LEN_PLIST(subgraph, V);
    for (int i = 1; i <= V; ++i) {
      Obj list = NEW_PLIST_IMM(T_PLIST, 0);
      SET_LEN_PLIST(list, 0);
      SET_ELM_PLIST(subgraph, i, list);
      CHANGED_BAG(subgraph);
    }
    res = NEW_PLIST_IMM(T_PLIST, 2);
    SET_LEN_PLIST(res, 2);
    SET_ELM_PLIST(res, 1, True);
    SET_ELM_PLIST(res, 2, subgraph);
    CHANGED_BAG(res);
  } else {
    res = True;
  }
  return res;
}

// This function only accepts digraphs without multiple edges

Obj boyers_planarity_check(Obj digraph, int flags, bool krtwsk) {
  DIGRAPHS_ASSERT(flags == EMBEDFLAGS_PLANAR || flags == EMBEDFLAGS_OUTERPLANAR
                  || flags == EMBEDFLAGS_SEARCHFORK23
                  || flags == EMBEDFLAGS_SEARCHFORK4
                  || flags == EMBEDFLAGS_SEARCHFORK33);

  if (CALL_1ARGS(IsDigraph, digraph) != True) {
    ErrorQuit("Digraphs: boyers_planarity_check (C): the 1st argument must be "
              "a digraph, not %s",
              (Int) TNAM_OBJ(digraph),
              0L);
  }
  if (CALL_1ARGS(IsMultiDigraph, digraph) == True) {
    ErrorQuit("expected a digraph without multiple edges!", 0L, 0L);
  }

  Int V = DigraphNrVertices(digraph);
  if (V == 0) {
    return trivial_planarity_output(0, krtwsk);
  }

  Int E = DigraphNrAdjacenciesWithoutLoops(digraph);
  if (E == 0) {
    return trivial_planarity_output(V, krtwsk);
  }
  if (V > INT_MAX) {
    // Cannot currently test this, it might always be true, depending on the
    // definition of Int.
    ErrorQuit("Digraphs: boyers_planarity_check (C): the maximum number of "
              "nodes is %d, found %d",
              INT_MAX,
              V);
    return 0L;
  } else if (2 * E > INT_MAX) {
    // Cannot currently test this
    ErrorQuit("Digraphs: boyers_planarity_check (C): the maximum number of "
              "edges is %d, found %d",
              INT_MAX / 2,
              E);
    return 0L;
  }

  graphP theGraph = gp_New();

  if (gp_InitGraph(theGraph, V) != OK) {
    gp_Free(&theGraph);
    ErrorQuit("Digraphs: boyers_planarity_check (C): invalid number of nodes!",
              0L,
              0L);
    return 0L;
  } else if (gp_EnsureArcCapacity(theGraph, 2 * E) != OK) {
    gp_Free(&theGraph);
    ErrorQuit("Digraphs: boyers_planarity_check (C): invalid number of edges!",
              0L,
              0L);
    return 0L;
  }

  switch (flags) {
    case EMBEDFLAGS_SEARCHFORK33:
      gp_AttachK33Search(theGraph);
      break;
    case EMBEDFLAGS_SEARCHFORK23:
      gp_AttachK23Search(theGraph);
      break;
    case EMBEDFLAGS_SEARCHFORK4:
      gp_AttachK4Search(theGraph);
      break;
    default:
      break;
  }

  int       status;
  Obj const out = FuncOutNeighbours(0L, digraph);

  // Construct the antisymmetric digraph with no loops
  for (Int v = 1; v <= LEN_LIST(out); ++v) {
    DIGRAPHS_ASSERT(gp_VertexInRange(theGraph, v));
    gp_SetVertexIndex(theGraph, v, v);
    Obj const out_v = ELM_LIST(out, v);
    for (Int w = 1; w <= LEN_LIST(out_v); ++w) {
      DIGRAPHS_ASSERT(gp_VertexInRange(theGraph, w));
      Int u = INT_INTOBJ(ELM_LIST(out_v, w));
      if (v < u
          || CALL_3ARGS(IsDigraphEdge, digraph, INTOBJ_INT(u), INTOBJ_INT(v))
                 == False) {
        status = gp_AddEdge(theGraph, v, 0, u, 0);
        if (status != OK) {
          // Cannot currently test this, i.e. it shouldn't happen (and
          // currently there is no example where it does happen)
          gp_Free(&theGraph);
          ErrorQuit("Digraphs: boyers_planarity_check (C): internal error, "
                    "can't add edge from %d to %d",
                    (Int) v,
                    (Int) u);
          return 0L;
        }
      }
    }
  }

  status = gp_Embed(theGraph, flags);
  if (status == NOTOK) {
    // Cannot currently test this, i.e. it shouldn't happen (and
    // currently there is no example where it does happen)
    gp_Free(&theGraph);
    ErrorQuit("Digraphs: boyers_planarity_check (C): status is not ok", 0L, 0L);
  }

  // Construct the return value
  Obj res;
  if (krtwsk) {
    // Kuratowski subgraph isolator
    gp_SortVertices(theGraph);
    Obj subgraph = NEW_PLIST_IMM(T_PLIST, theGraph->N);
    SET_LEN_PLIST(subgraph, theGraph->N);
    for (int i = 1; i <= theGraph->N; ++i) {
      int nr   = 0;
      Obj list = NEW_PLIST(T_PLIST, 0);
      int j    = theGraph->V[i].link[1];
      while (j) {
        if (CALL_3ARGS(IsDigraphEdge,
                       digraph,
                       INTOBJ_INT((Int) i),
                       INTOBJ_INT((Int) theGraph->E[j].neighbor))
            == True) {
          AssPlist(list, ++nr, INTOBJ_INT(theGraph->E[j].neighbor));
        }
        j = theGraph->E[j].link[1];
      }
      if (nr == 0) {
        SET_LEN_PLIST(list, 0);
      }
      MakeImmutable(list);
      SET_ELM_PLIST(subgraph, i, list);
      CHANGED_BAG(subgraph);
    }
    res = NEW_PLIST_IMM(T_PLIST, 2);
    SET_LEN_PLIST(res, 2);
    SET_ELM_PLIST(res, 1, (status == NONEMBEDDABLE ? False : True));
    SET_ELM_PLIST(res, 2, subgraph);
    CHANGED_BAG(res);
  } else if (status == NONEMBEDDABLE) {
    res = False;
  } else {
    res = True;
  }
  gp_Free(&theGraph);
  return res;
}

quality91%

¤ Dauer der Verarbeitung: 0.26 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.