from _typeshed import Incomplete, Unused
from collections.abc import Generator, Iterable, Mapping, MutableSet, Reversible
from decimal import Decimal
from typing import NoReturn

from networkx.classes.digraph import DiGraph
from networkx.classes.graph import Graph, _EdgeData, _EdgePlus, _Node, _NodeData
from networkx.utils.backends import _dispatchable

__all__ = ["check_planarity", "is_planar", "PlanarEmbedding"]

@_dispatchable
def is_planar(G: Graph[_Node]) -> bool: ...
@_dispatchable
def check_planarity(G: Graph[_Node], counterexample: bool = False): ...
@_dispatchable
def get_counterexample(G: Graph[_Node, _NodeData, _EdgeData]) -> Graph[_Node, _NodeData, _EdgeData]: ...
@_dispatchable
def get_counterexample_recursive(G: Graph[_Node, _NodeData, _EdgeData]) -> Graph[_Node, _NodeData, _EdgeData]: ...

class Interval:
    low: Incomplete
    high: Incomplete

    def __init__(self, low=None, high=None) -> None: ...
    def empty(self): ...
    def copy(self): ...
    def conflicting(self, b, planarity_state): ...

class ConflictPair:
    left: Incomplete
    right: Incomplete

    def __init__(self, left=..., right=...) -> None: ...
    def swap(self) -> None: ...
    def lowest(self, planarity_state): ...

class LRPlanarity:
    __slots__ = [
        "G",
        "roots",
        "height",
        "lowpt",
        "lowpt2",
        "nesting_depth",
        "parent_edge",
        "DG",
        "adjs",
        "ordered_adjs",
        "ref",
        "side",
        "S",
        "stack_bottom",
        "lowpt_edge",
        "left_ref",
        "right_ref",
        "embedding",
    ]
    G: Incomplete
    roots: Incomplete
    height: Incomplete
    lowpt: Incomplete
    lowpt2: Incomplete
    nesting_depth: Incomplete
    parent_edge: Incomplete
    DG: Incomplete
    adjs: Incomplete
    ordered_adjs: Incomplete
    ref: Incomplete
    side: Incomplete
    S: Incomplete
    stack_bottom: Incomplete
    lowpt_edge: Incomplete
    left_ref: Incomplete
    right_ref: Incomplete
    embedding: Incomplete

    def __init__(self, G: Graph[_Node]) -> None: ...
    def lr_planarity(self) -> PlanarEmbedding[Incomplete] | None: ...
    def lr_planarity_recursive(self): ...
    def dfs_orientation(self, v): ...
    def dfs_orientation_recursive(self, v) -> None: ...
    def dfs_testing(self, v): ...
    def dfs_testing_recursive(self, v): ...
    def add_constraints(self, ei, e): ...
    def remove_back_edges(self, e) -> None: ...
    def dfs_embedding(self, v): ...
    def dfs_embedding_recursive(self, v) -> None: ...
    def sign(self, e): ...
    def sign_recursive(self, e): ...

# NOTE: Graph subclasses relationships are so complex
# we're only overriding methods that differ in signature from the base classes
# to use inheritance to our advantage and reduce complexity
class PlanarEmbedding(DiGraph[_Node]):
    def get_data(self) -> dict[_Node, list[_Node]]: ...
    def set_data(self, data: Mapping[_Node, Reversible[_Node]]) -> None: ...
    def neighbors_cw_order(self, v: _Node) -> Generator[_Node]: ...
    def add_half_edge(self, start_node: _Node, end_node: _Node, *, cw: _Node | None = None, ccw: _Node | None = None): ...
    def check_structure(self) -> None: ...
    def add_half_edge_ccw(self, start_node: _Node, end_node: _Node, reference_neighbor: _Node) -> None: ...
    def add_half_edge_cw(self, start_node: _Node, end_node: _Node, reference_neighbor: _Node) -> None: ...
    def connect_components(self, v: _Node, w: _Node) -> None: ...
    def add_half_edge_first(self, start_node: _Node, end_node: _Node) -> None: ...
    def next_face_half_edge(self, v: _Node, w: _Node) -> tuple[_Node, _Node]: ...
    def traverse_face(
        self, v: _Node, w: _Node, mark_half_edges: MutableSet[tuple[_Node, _Node]] | None = None
    ) -> list[_Node]: ...
    # Overriden in __init__ to always raise
    def add_edge(self, u_of_edge: _Node, v_of_edge: _Node, **attr: Unused) -> NoReturn: ...
    def add_edges_from(self, ebunch_to_add: Iterable[_EdgePlus[_Node]], **attr: Unused) -> NoReturn: ...
    def add_weighted_edges_from(
        self, ebunch_to_add: Iterable[tuple[_Node, _Node, float | Decimal | None]], weight: str = "weight", **attr: Unused
    ) -> NoReturn: ...
