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: Returns nodes on the face that belong to the half-edge (v, w).
  
  The face that is traversed lies to the right of the half-edge (in an
  orientation where v is below w).
  
  Optionally it is possible to pass a set to which all encountered half
  edges are added. Before calling this method, this set must not include
  any half-edges that belong to the face.
  
  Parameters
  ----------
  v : node
      Start node of half-edge.
  w : node
      End node of half-edge.
  mark_half_edges: set, optional
      Set to which all encountered half-edges are added.
  
  Returns
  -------
  face : list
      A list of nodes that lie on this face.
docstr_tok: ["Returns","nodes","on","the","face","that","belong","to","the","half-edge","(","v",",","w",")",".","The","face","that","is","traversed","lies","to","the","right","of","the","half-edge","(","in","an","orientation","where","v","is","below","w",")",".","Optionally","it","is","possible","to","pass","a","set","to","which","all","encountered","half","edges","are","added",".","Before","calling","this","method",",","this","set","must","not","include","any","half-edges","that","belong","to","the","face",".","Parameters","--","--","--","--","--","v",":","node","Start","node","of","half-edge",".","w",":","node","End","node","of","half-edge",".","mark_half_edges",":","set",",","optional","Set","to","which","all","encountered","half-edges","are","added",".","Returns","--","--","--","-","face",":","list","A","list","of","nodes","that","lie","on","this","face","."]
code: def traverse_face(self, v, w, mark_half_edges=None):
      """Returns nodes on the face that belong to the half-edge (v, w).
  
      The face that is traversed lies to the right of the half-edge (in an
      orientation where v is below w).
  
      Optionally it is possible to pass a set to which all encountered half
      edges are added. Before calling this method, this set must not include
      any half-edges that belong to the face.
  
      Parameters
      ----------
      v : node
          Start node of half-edge.
      w : node
          End node of half-edge.
      mark_half_edges: set, optional
          Set to which all encountered half-edges are added.
  
      Returns
      -------
      face : list
          A list of nodes that lie on this face.
      """
      if mark_half_edges is None:
          mark_half_edges = set()
  
      face_nodes = [v]
      mark_half_edges.add((v, w))
      prev_node = v
      cur_node = w
      # Last half-edge is (incoming_node, v)
      incoming_node = self[v][w]["cw"]
  
      while cur_node != v or prev_node != incoming_node:
          face_nodes.append(cur_node)
          prev_node, cur_node = self.next_face_half_edge(
              prev_node, cur_node
          )
          if (prev_node, cur_node) in mark_half_edges:
              raise nx.NetworkXException(
                  "Bad planar embedding. Impossible face."
              )
          mark_half_edges.add((prev_node, cur_node))
  
      return face_nodes
  
imports: from collections import defaultdict
  import networkx
label_desc: Use image node_id 17 for calling the PlanarEmbedding obj's underlying member method code with example usage: obj.traverse_face(v, w, mark_half_edges) and returns: face_nodes