Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Wrapper for Boyer's (C) planarity algorithm. """
cdef extern from "planarity/graph.h": ctypedef struct vertexRec: int link[2] int index ctypedef vertexRec * vertexRecP
ctypedef struct edgeRec: int link[2] int neighbor ctypedef edgeRec * edgeRecP
ctypedef struct BM_graph: vertexRecP V edgeRecP E int N ctypedef BM_graph * graphP
cdef int OK, EMBEDFLAGS_PLANAR, NONEMBEDDABLE, NOTOK
cdef graphP gp_New() cdef void gp_Free(graphP *pGraph) cdef int gp_InitGraph(graphP theGraph, int N) cdef int gp_AddEdge(graphP theGraph, int u, int ulink, int v, int vlink) cdef int gp_Embed(graphP theGraph, int embedFlags) cdef int gp_SortVertices(graphP theGraph)
""" Calls Boyer's planarity algorithm to determine whether g is planar. If kuratowski is False, returns True if g is planar, False otherwise. If kuratowski is True, returns a tuple, first entry is a boolean (whether or not the graph is planar) and second entry is a Kuratowski subgraph, i.e. an edge subdivision of `K_5` or `K_{3,3}` (if not planar) or ``None`` (if planar). Also, will set an ``_embedding`` attribute for the graph ``g`` if ``set_embedding`` is set to True.
INPUT:
- ``kuratowski`` -- If ``True``, return a tuple of a boolean and either ``None`` or a Kuratowski subgraph (i.e. an edge subdivision of `K_5` or `K_{3,3}`)
- ``set_pos`` -- if ``True``, uses Schnyder's algorithm to determine positions
- ``set_embedding`` -- if ``True``, records the combinatorial embedding returned (see g.get_embedding())
- ``circular`` -- if ``True``, test for circular planarity
EXAMPLES::
sage: G = graphs.DodecahedralGraph() sage: from sage.graphs.planarity import is_planar sage: is_planar(G) True sage: Graph('@').is_planar() True
TESTS:
We try checking the planarity of all graphs on 7 or fewer vertices. In fact, to try to track down a segfault, we do it twice. ::
sage: import networkx.generators.atlas # long time sage: atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()] # long time sage: a = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time sage: b = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time sage: a == b # long time True
There were some problems with ``set_pos`` stability in the past, so let's check if this runs without exception::
sage: for i, g in enumerate(atlas_graphs): # long time ....: if (not g.is_connected() or i == 0): ....: continue ....: _ = g.is_planar(set_embedding=True, set_pos=True) """ raise ValueError("is_planar() cannot set vertex positions for a disconnected graph")
# First take care of a trivial cases g._pos = { u: [0,0], v: [0,1] }
# create to and from mappings to relabel vertices to the set {1,...,n} # (planarity 3 uses 1-based array indexing, with 0 representing NIL) cdef int i
cdef graphP theGraph cdef int status raise RuntimeError("gp_InitGraph status is not ok.") raise RuntimeError("gp_AddEdge status is not ok.") # We now know that the graph is nonplanar. if not kuratowski: return False # With just the current edges, we have a nonplanar graph, # so to isolate a kuratowski subgraph, just keep going. break
# use to and from mappings to relabel vertices back from the set {1,...,n}
raise RuntimeError("Status is not ok.") # Kuratowski subgraph isolator else: else: #for i in range(theGraph.N): g.set_planar_positions() else: # Take counter-clockwise embedding if circular planar test # Also, pos must be set after removing extra vertex and edges
# This is separated out here for now because in the circular case, # setting positions would have to come into play while the extra # "wheel" or "star" is still part of the graph.
#for i in range(theGraph.N): else: |