# Path: py_algorithms/graph/adt/edge.py
# class Edge:
#     __slots__ = '_origin', '_destination', '_element'
# 
#     def __init__(self, origin: Vertex, destination: Vertex, element: Any):
#         self._element = element
#         self._destination = destination
#         self._origin = origin
# 
#     def endpoints(self) -> Tuple[Any, Any]:
#         return self._origin, self._destination
# 
#     def opposite(self, v) -> Union[None, Vertex]:
#         return self._destination if v is self._origin else self._origin
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self):
#         return hash((self._origin, self._destination,))
# 
#     def __repr__(self):
#         return "#<{}({}) ({},{})>" \
#             .format(self.__class__.__name__,
#                     self.element(),
#                     self._origin.element(),
#                     self._destination.element())
# 
# Path: py_algorithms/graph/adt/graph.py
# class Graph:
#     def __init__(self, directed: bool = False):
#         self._outgoing = {}
#         self._incoming = {} if directed else self._outgoing
# 
#     def is_directed(self) -> bool:
#         return self._incoming is not self._outgoing
# 
#     def vertex_count(self) -> int:
#         return len(self._outgoing)
# 
#     def vertices(self) -> List[Vertex]:
#         return list(self._outgoing.keys())
# 
#     def edge_count(self) -> int:
#         total = sum(len(self._outgoing[v]) for v in self._outgoing)
#         return total if self.is_directed() else total // 2
# 
#     def edges(self) -> Set[Edge]:
#         result = set()
#         for sub_map in self._outgoing.values():
#             result.update(sub_map.values())
#         return result
# 
#     def get_edge(self, u, v) -> Union[None, Edge]:
#         return self._outgoing[u].get(v)
# 
#     def degree(self, v: Vertex, outgoing: bool = True) -> int:
#         adj = self._outgoing if outgoing else self._incoming
#         return len(adj[v])
# 
#     def incident_edges(self,
#                        v: Vertex,
#                        outgoing: bool = True) -> Iterator[Edge]:
#         adj = self._outgoing if outgoing else self._incoming
#         for edge in adj[v].values():
#             yield edge
# 
#     def insert_vertex(self, element: Any = None) -> Vertex:
#         v = Vertex(element)
#         self._outgoing[v] = {}
#         if self.is_directed():
#             self._incoming[v] = {}
#         return v
# 
#     def insert_edge(self, origin: Vertex, destination: Vertex,
#                     element: Any) -> Edge:
#         e = Edge(origin, destination, element)
#         self._outgoing[origin][destination] = e
#         self._incoming[destination][origin] = e
#         return e
# 
# Path: py_algorithms/graph/adt/vertex.py
# class Vertex:
#     __slots__ = '_element'
# 
#     def __init__(self, element: Any):
#         self._element = element
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self) -> int:
#         return hash(id(self))
# 
#     def __repr__(self):
#         return "#<{}({})>" \
#             .format(self.__class__.__name__, self.element())


from typing import Dict
from .adt.edge import Edge
from .adt.graph import Graph
from .adt.vertex import Vertex



class ReconstructDijkstraPathTree:
    @classmethod
    def apply(cls, graph: Graph, source: Vertex, dst: Dict[Vertex, int]) -> Dict[Vertex, Edge]:
        tree = {}

        for v in dst:
            if v is not source:
                for e in graph.incident_edges(v, False):
                    u = e.opposite(v)
                    w = e.element()
                    if dst[v] == dst[u] + w:
                        tree[v] = e

# Path: py_algorithms/graph/adt/edge.py
# class Edge:
#     __slots__ = '_origin', '_destination', '_element'
# 
#     def __init__(self, origin: Vertex, destination: Vertex, element: Any):
#         self._element = element
#         self._destination = destination
#         self._origin = origin
# 
#     def endpoints(self) -> Tuple[Any, Any]:
#         return self._origin, self._destination
# 
#     def opposite(self, v) -> Union[None, Vertex]:
#         return self._destination if v is self._origin else self._origin
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self):
#         return hash((self._origin, self._destination,))
# 
#     def __repr__(self):
#         return "#<{}({}) ({},{})>" \
#             .format(self.__class__.__name__,
#                     self.element(),
#                     self._origin.element(),
#                     self._destination.element())
# 
# Path: py_algorithms/graph/adt/graph.py
# class Graph:
#     def __init__(self, directed: bool = False):
#         self._outgoing = {}
#         self._incoming = {} if directed else self._outgoing
# 
#     def is_directed(self) -> bool:
#         return self._incoming is not self._outgoing
# 
#     def vertex_count(self) -> int:
#         return len(self._outgoing)
# 
#     def vertices(self) -> List[Vertex]:
#         return list(self._outgoing.keys())
# 
#     def edge_count(self) -> int:
#         total = sum(len(self._outgoing[v]) for v in self._outgoing)
#         return total if self.is_directed() else total // 2
# 
#     def edges(self) -> Set[Edge]:
#         result = set()
#         for sub_map in self._outgoing.values():
#             result.update(sub_map.values())
#         return result
# 
#     def get_edge(self, u, v) -> Union[None, Edge]:
#         return self._outgoing[u].get(v)
# 
#     def degree(self, v: Vertex, outgoing: bool = True) -> int:
#         adj = self._outgoing if outgoing else self._incoming
#         return len(adj[v])
# 
#     def incident_edges(self,
#                        v: Vertex,
#                        outgoing: bool = True) -> Iterator[Edge]:
#         adj = self._outgoing if outgoing else self._incoming
#         for edge in adj[v].values():
#             yield edge
# 
#     def insert_vertex(self, element: Any = None) -> Vertex:
#         v = Vertex(element)
#         self._outgoing[v] = {}
#         if self.is_directed():
#             self._incoming[v] = {}
#         return v
# 
#     def insert_edge(self, origin: Vertex, destination: Vertex,
#                     element: Any) -> Edge:
#         e = Edge(origin, destination, element)
#         self._outgoing[origin][destination] = e
#         self._incoming[destination][origin] = e
#         return e
# 
# Path: py_algorithms/graph/adt/vertex.py
# class Vertex:
#     __slots__ = '_element'
# 
#     def __init__(self, element: Any):
#         self._element = element
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self) -> int:
#         return hash(id(self))
# 
#     def __repr__(self):
#         return "#<{}({})>" \
#             .format(self.__class__.__name__, self.element())


# Path: py_algorithms/graph/reconstruct_dijkstra_path_tree.py
from typing import Dict
from .adt.edge import Edge
from .adt.graph import Graph
from .adt.vertex import Vertex




class ReconstructDijkstraPathTree:
    @classmethod
    def apply(cls, graph: Graph, source: Vertex, dst: Dict[Vertex, int]) -> Dict[Vertex, Edge]:
        tree = {}

        for v in dst:
            if v is not source:
                for e in graph.incident_edges(v, False):
                    u = e.opposite(v)
                    w = e.element()
                    if dst[v] == dst[u] + w:
                        tree[v] = e

        return tree