Select Git revision
graph_3.py 6.95 KiB
import itertools
from abc import ABCMeta
from typing import Iterator, Dict, Set, Sequence, Union, Tuple
class Graph(metaclass=ABCMeta):
def __init__(self):
self.nodes: set[Node] = set()
self.vertices: Dict[Node: set[Node]]
def add_node(self):
pass
def del_node(self):
pass
class NDGraph:
"""
To handle Non Directed Graph
A graph is a collection of Nodes linked by edges
there are basically to way to implement a graph
- The graph handles Nodes, each nodes know it's neighbors
- The graph handles nodes and the edges between nodes
below I implemented the 2nd version.
"""
def __init__(self, nodes: Sequence['Node']) -> None:
self.nodes: Set['Node'] = {n for n in nodes}
self.vertices: Dict['Node': Set['Node']] = {n: set() for n in self.nodes}
def add_node(self, node: 'Node') -> None:
"""
Add a node to the graph
:param node: the node to add
:type node: :class:`Node`
:return: None
"""
self.nodes.add(node)
if node not in self.vertices:
self.vertices[node] = set()
def del_node(self, node: 'Node') -> None:
"""
Remove Node from Graph
:param node: the node to add
:type node: :class:`Node`
:return: None
"""
self.nodes.remove(node)
neighbors = self.vertices[node]
for nbh in neighbors:
self.vertices[nbh].remove(node)
del self.vertices[node]
def add_edge(self, node_1: 'Node', nodes: Sequence['Node']):
"""
Add vertice between node1 and all nodes in nodes
:param node_1: the reference node
:type node_1: :class:`Node`
:param nodes: the nodes connected to node_1
:type nodes: Sequence of :class:`Node`
:return: Node
"""
if node_1 not in self.nodes:
raise ValueError("the node_1 must be in Graph")
for n in nodes:
if n not in self.nodes:
raise ValueError("node must be add to Graph before creating edge")
self.vertices[node_1].add(n)
self.vertices[n].add(node_1)
def neighbors(self, node: 'Node') -> Set['Node']:
"""
return the nodes connected to node
:param node: the reference node
:type node: :class:`Node`
:return: a set of :class:`Node`
"""
return {n for n in self.vertices[node]}
def get_weight(self, node_1, node_2):
"""
:param node_1:
:param node_2:
:return:
"""
return 1
class Node:
_id = itertools.count(0)
def __init__(self) -> None:
self.id: int = next(self._id)
def __hash__(self) -> int:
# to be usable in set an object must be hashable
# so we need to implement __hash__
# which must return an int unique per object
# here we ad the identifier of the Node
return self.id
def __str__(self):
return f"node_{self.id}"
def __repr__(self):
return str(self)
class Edge:
def __init__(self, src, target, weight):
self.src = src
self.target = target
self.weight = weight
class NDWGraph:
"""
To handle Non Directed Graph
A graph is a collection of Nodes linked by edges
there are basically to way to implement a graph
- The graph handles Nodes, each nodes know it's neighbors
- The graph handles nodes and the edges between nodes
below I implemented the 2nd version.
"""
def __init__(self, node) -> None:
self.nodes: Set[Node] = {}
def add_node(self, node: Node) -> None:
"""
Add a node to the graph
:param node: the node to add
:type node: :class:`Node`
:return: None
"""
if node not in self.nodes:
self.nodes[node] = {}
def del_node(self, node: Node) -> None:
"""
Remove Node from Graph
:param node: the node to add
:type node: :class:`Node`
:return: None
"""
neighbors = self.nodes[node]
for nbh in neighbors:
del self.vertices[nbh][node]
del self.nodes[node]
def add_edge(self, node_1: Node, node_2: Node, weight: Union[int, float]):
"""
Add vertex between node1 and all nodes in nodes
:param node_1: the reference node
:param node_2: the nodes connected to node_1
:param weight: the weight of the edge between node_1 and node_2
:return: Node
"""
for n in node_1, node_2:
if n not in self.nodes:
raise ValueError(f"node {n.id} not found in Graph. The node must be in Graph.")
self.nodes[node_1][node_2] = weight
self.nodes[node_2][node_1] = weight
def neighbors(self, node):
"""
return the nodes connected to node
:param node: the reference node
:type node: :class:`Node`
:return: a set of :class:`Node`
"""
return {n for n, w in self.nodes[node].items()}
def get_weight(self, node_1, node_2):
"""
:param node_1:
:param node_2:
:return:
"""
return self.nodes[node_1][node_2]
def DFS(graph: NDGraph, node: Node) -> Iterator[Node]:
"""
**D**epth **F**irst **S**earch.
We start the path from the node given as argument,
This node is labeled as 'visited'
The neighbors of this node which have not been already 'visited' nor 'to visit' are labelled as 'to visit'
We pick the last element to visit and visit it
(The neighbors of this node which have not been already 'visited' nor 'to visit' are labelled as 'to visit').
on so on until there no nodes to visit anymore.
:param graph:
:param node:
:return:
"""
to_visit = [node]
visited = set()
while to_visit:
n = to_visit.pop(-1)
visited.add(n)
new_to_visit = graph.neighbors(n) - visited - set(to_visit)
to_visit.extend(new_to_visit)
yield n
def BFS(graph: NDGraph, node: Node) -> Iterator[Node]:
"""
**B**readth **F**irst **s**earch
We start the path from the node given as argument,
This node is labeled as 'visited'
The neighbors of this node which have not been already 'visited' nor 'to visit' are labelled as 'to visit'
we pick the **first** element of the nodes to visit and visit it.
(The neighbors of this node which have not been already 'visited' nor 'to visit' are labelled as 'to visit')
on so on until there no nodes to visit anymore.
:param graph:
:param node:
:return:
"""
to_visit = [node]
visited = set()
parent = None
while to_visit:
n = to_visit.pop(0)
visited.add(n)
new_to_visit = graph.neighbors(n) - visited - set(to_visit)
to_visit.extend(new_to_visit)
if not parent:
weight = 0
else:
weight = graph.get_weight(parent, n)
parent = n
yield n, weight