class_docstr: Represents a planar graph with its planar embedding.
  
  The planar embedding is given by a `combinatorial embedding
  <https://en.wikipedia.org/wiki/Graph_embedding#Combinatorial_embedding>`_.
  
  .. note:: `check_planarity` is the preferred way to check if a graph is planar.
  
  **Neighbor ordering:**
  
  In comparison to a usual graph structure, the embedding also stores the
  order of all neighbors for every vertex.
  The order of the neighbors can be given in clockwise (cw) direction or
  counterclockwise (ccw) direction. This order is stored as edge attributes
  in the underlying directed graph. For the edge (u, v) the edge attribute
  'cw' is set to the neighbor of u that follows immediately after v in
  clockwise direction.
  
  In order for a PlanarEmbedding to be valid it must fulfill multiple
  conditions. It is possible to check if these conditions are fulfilled with
  the method :meth:`check_structure`.
  The conditions are:
  
  * Edges must go in both directions (because the edge attributes differ)
  * Every edge must have a 'cw' and 'ccw' attribute which corresponds to a
    correct planar embedding.
  
  As long as a PlanarEmbedding is invalid only the following methods should
  be called:
  
  * :meth:`add_half_edge`
  * :meth:`connect_components`
  
  Even though the graph is a subclass of nx.DiGraph, it can still be used
  for algorithms that require undirected graphs, because the method
  :meth:`is_directed` is overridden. This is possible, because a valid
  PlanarGraph must have edges in both directions.
  
  **Half edges:**
  
  In methods like `add_half_edge` the term "half-edge" is used, which is
  a term that is used in `doubly connected edge lists
  <https://en.wikipedia.org/wiki/Doubly_connected_edge_list>`_. It is used
  to emphasize that the edge is only in one direction and there exists
  another half-edge in the opposite direction.
  While conventional edges always have two faces (including outer face) next
  to them, it is possible to assign each half-edge *exactly one* face.
  For a half-edge (u, v) that is oriented such that u is below v then the
  face that belongs to (u, v) is to the right of this half-edge.
  
  See Also
  --------
  is_planar :
      Preferred way to check if an existing graph is planar.
  
  check_planarity :
      A convenient way to create a `PlanarEmbedding`. If not planar,
      it returns a subgraph that shows this.
  
  Examples
  --------
  
  Create an embedding of a star graph (compare `nx.star_graph(3)`):
  
  >>> G = nx.PlanarEmbedding()
  >>> G.add_half_edge(0, 1)
  >>> G.add_half_edge(0, 2, ccw=1)
  >>> G.add_half_edge(0, 3, ccw=2)
  >>> G.add_half_edge(1, 0)
  >>> G.add_half_edge(2, 0)
  >>> G.add_half_edge(3, 0)
  
  Alternatively the same embedding can also be defined in counterclockwise
  orientation. The following results in exactly the same PlanarEmbedding:
  
  >>> G = nx.PlanarEmbedding()
  >>> G.add_half_edge(0, 1)
  >>> G.add_half_edge(0, 3, cw=1)
  >>> G.add_half_edge(0, 2, cw=3)
  >>> G.add_half_edge(1, 0)
  >>> G.add_half_edge(2, 0)
  >>> G.add_half_edge(3, 0)
  
  After creating a graph, it is possible to validate that the PlanarEmbedding
  object is correct:
  
  >>> G.check_structure()
class_docstr_tok: ["Represents","a","planar","graph","with","its","planar","embedding",".","The","planar","embedding","is","given","by","a","`","combinatorial","embedding","<","https",":","\/\/en.wikipedia.org\/wiki\/Graph_embedding","#","Combinatorial_embedding",">","`","_",".","..","note",":",":","`","check_planarity","`","is","the","preferred","way","to","check","if","a","graph","is","planar",".","*","*","Neighbor","ordering",":","*","*","In","comparison","to","a","usual","graph","structure",",","the","embedding","also","stores","the","order","of","all","neighbors","for","every","vertex",".","The","order","of","the","neighbors","can","be","given","in","clockwise","(","cw",")","direction","or","counterclockwise","(","ccw",")","direction",".","This","order","is","stored","as","edge","attributes","in","the","underlying","directed","graph",".","For","the","edge","(","u",",","v",")","the","edge","attribute","'cw","'","is","set","to","the","neighbor","of","u","that","follows","immediately","after","v","in","clockwise","direction",".","In","order","for","a","PlanarEmbedding","to","be","valid","it","must","fulfill","multiple","conditions",".","It","is","possible","to","check","if","these","conditions","are","fulfilled","with","the","method",":","meth",":","`","check_structure","`",".","The","conditions","are",":","*","Edges","must","go","in","both","directions","(","because","the","edge","attributes","differ",")","*","Every","edge","must","have","a","'cw","'","and","'ccw","'","attribute","which","corresponds","to","a","correct","planar","embedding",".","As","long","as","a","PlanarEmbedding","is","invalid","only","the","following","methods","should","be","called",":","*",":","meth",":","`","add_half_edge","`","*",":","meth",":","`","connect_components","`","Even","though","the","graph","is","a","subclass","of","nx.DiGraph",",","it","can","still","be","used","for","algorithms","that","require","undirected","graphs",",","because","the","method",":","meth",":","`","is_directed","`","is","overridden",".","This","is","possible",",","because","a","valid","PlanarGraph","must","have","edges","in","both","directions",".","*","*","Half","edges",":","*","*","In","methods","like","`","add_half_edge","`","the","term","``","half-edge","''","is","used",",","which","is","a","term","that","is","used","in","`","doubly","connected","edge","lists","<","https",":","\/\/en.wikipedia.org\/wiki\/Doubly_connected_edge_list",">","`","_",".","It","is","used","to","emphasize","that","the","edge","is","only","in","one","direction","and","there","exists","another","half-edge","in","the","opposite","direction",".","While","conventional","edges","always","have","two","faces","(","including","outer","face",")","next","to","them",",","it","is","possible","to","assign","each","half-edge","*","exactly","one","*","face",".","For","a","half-edge","(","u",",","v",")","that","is","oriented","such","that","u","is","below","v","then","the","face","that","belongs","to","(","u",",","v",")","is","to","the","right","of","this","half-edge",".","See","Also","--","--","--","--","is_planar",":","Preferred","way","to","check","if","an","existing","graph","is","planar",".","check_planarity",":","A","convenient","way","to","create","a","`","PlanarEmbedding","`",".","If","not","planar",",","it","returns","a","subgraph","that","shows","this",".","Examples","--","--","--","--","Create","an","embedding","of","a","star","graph","(","compare","`","nx.star_graph","(","3",")","`",")",":",">",">",">","G","=","nx.PlanarEmbedding","(",")",">",">",">","G.add_half_edge","(","0",",","1",")",">",">",">","G.add_half_edge","(","0",",","2",",","ccw=1",")",">",">",">","G.add_half_edge","(","0",",","3",",","ccw=2",")",">",">",">","G.add_half_edge","(","1",",","0",")",">",">",">","G.add_half_edge","(","2",",","0",")",">",">",">","G.add_half_edge","(","3",",","0",")","Alternatively","the","same","embedding","can","also","be","defined","in","counterclockwise","orientation",".","The","following","results","in","exactly","the","same","PlanarEmbedding",":",">",">",">","G","=","nx.PlanarEmbedding","(",")",">",">",">","G.add_half_edge","(","0",",","1",")",">",">",">","G.add_half_edge","(","0",",","3",",","cw=1",")",">",">",">","G.add_half_edge","(","0",",","2",",","cw=3",")",">",">",">","G.add_half_edge","(","1",",","0",")",">",">",">","G.add_half_edge","(","2",",","0",")",">",">",">","G.add_half_edge","(","3",",","0",")","After","creating","a","graph",",","it","is","possible","to","validate","that","the","PlanarEmbedding","object","is","correct",":",">",">",">","G.check_structure","(",")"]
docstr: Runs without exceptions if this object is valid.
  
  Checks that the following properties are fulfilled:
  
  * Edges go in both directions (because the edge attributes differ).
  * Every edge has a 'cw' and 'ccw' attribute which corresponds to a
    correct planar embedding.
  
  Running this method verifies that the underlying Graph must be planar.
  
  Raises
  ------
  NetworkXException
      This exception is raised with a short explanation if the
      PlanarEmbedding is invalid.
docstr_tok: ["Runs","without","exceptions","if","this","object","is","valid",".","Checks","that","the","following","properties","are","fulfilled",":","*","Edges","go","in","both","directions","(","because","the","edge","attributes","differ",")",".","*","Every","edge","has","a","'cw","'","and","'ccw","'","attribute","which","corresponds","to","a","correct","planar","embedding",".","Running","this","method","verifies","that","the","underlying","Graph","must","be","planar",".","Raises","--","--","--","NetworkXException","This","exception","is","raised","with","a","short","explanation","if","the","PlanarEmbedding","is","invalid","."]
code: def check_structure(self):
      """Runs without exceptions if this object is valid.
  
      Checks that the following properties are fulfilled:
  
      * Edges go in both directions (because the edge attributes differ).
      * Every edge has a 'cw' and 'ccw' attribute which corresponds to a
        correct planar embedding.
  
      Running this method verifies that the underlying Graph must be planar.
  
      Raises
      ------
      NetworkXException
          This exception is raised with a short explanation if the
          PlanarEmbedding is invalid.
      """
      # Check fundamental structure
      for v in self:
          try:
              sorted_nbrs = set(self.neighbors_cw_order(v))
          except KeyError as err:
              msg = f"Bad embedding. Missing orientation for a neighbor of {v}"
              raise nx.NetworkXException(msg) from err
  
          unsorted_nbrs = set(self[v])
          if sorted_nbrs != unsorted_nbrs:
              msg = (
                  "Bad embedding. Edge orientations not set correctly."
              )
              raise nx.NetworkXException(msg)
          for w in self[v]:
              # Check if opposite half-edge exists
              if not self.has_edge(w, v):
                  msg = "Bad embedding. Opposite half-edge is missing."
                  raise nx.NetworkXException(msg)
  
      # Check planarity
      counted_half_edges = set()
      for component in nx.connected_components(self):
          if len(component) == 1:
              # Don't need to check single node component
              continue
          num_nodes = len(component)
          num_half_edges = 0
          num_faces = 0
          for v in component:
              for w in self.neighbors_cw_order(v):
                  num_half_edges += 1
                  if (v, w) not in counted_half_edges:
                      # We encountered a new face
                      num_faces += 1
                      # Mark all half-edges belonging to this face
                      self.traverse_face(v, w, counted_half_edges)
          num_edges = num_half_edges // 2  # num_half_edges is even
          if num_nodes - num_edges + num_faces != 2:
              # The result does not match Euler's formula
              msg = "Bad embedding. The graph does not match Euler's formula"
              raise nx.NetworkXException(msg)
  
imports: from collections import defaultdict
  import networkx
label_desc: Use image node_id 9 for calling the PlanarEmbedding obj's underlying member method code with example usage: obj.check_structure() without return types