from typing import List, Tuple, Dict, Set class DirectedGraph: def __init__(self, list_edges: List[Tuple[str, str]] ): """ We consider that the graph possesses only one attribute, corresponding to its list of edges. Each edge is a tuple (node_1, node_2) where each node is a string. If the tuple (node_1, node_2) appears in the list of edges, it means that there is an edge that GOES FROM node_1 TO node_2 (and not the other way round) Example 1: The graph below contains 3 nodes ("A", "B" and "C"), and 3 edges: - ("A", "B") - ("B", "C") - ("A", "C") +-------+ +-------+ +-------+ | | | | | | | "A" +--------->+ "B" +------->+ "C" | | | | | | | +-------+ +-------+ +-------+ | ^ | | | | +----------------------------------+ The list of nodes of the graph can be deduced from its list of edges. :param list_edges: list of tuples (str, str) defining the nodes of the graph """ self._list_edges = list_edges def get_list_nodes(self) -> List[str]: """ :return: List of nodes in the Graph (without any duplicates) For example, for the graph in example 1, a possible result would be ["A", "C", "B"] """ # TODO def number_edges(self) -> int: """ :return: the number of edges in the graph For example, for the graph in example 1, the result should be 3. """ def number_nodes(self) -> int: """ :return: the number of nodes in the graph For example, for the graph in example 1, the result should be 3 (the 3 nodes are A, B and C) """ def remove_edge(self, edge: Tuple[str, str]) -> None: """ delete the edge from the graph (if it exists in the graph) """ def remove_node(self, node: str) -> None: """ delete the node from the graph (if it exists in the graph) Warning: you will also have to delete all the edges that are attached to that node! For example, if we delete node "A" from example 1 we get: +-------+ +-------+ | | | | | "B" +------->+ "C" | | | | | +-------+ +-------+ (node A, and the edges (A,B) and (A,C) have been deleted) """ def add_edges(self, *edges: Tuple[str, str] ) -> None: """ :param edges: edges to be added to the graph; each edge is a tuple (node_1, node_2) """ # TODO def get_dict_graph(self) -> Dict[str, List[str]]: """ :return: A dictionary where: - each key represents a node X - each value is the list of the nodes reachable from X via an edge. For example, one possible result with Example 1 is: { "A": ["B", "C"], "B": ["C"], "C": [], } """ # TODO def get_list_nodes_directly_reachable(self, node_start: str, ) -> List[str]: """ :param node_start: a node in the Graph :return: the list of nodes directly reachable from node_start via an edge Example 2: +----------------------------------------------------+ | | | +-------+ | | | | | | | "G" | | | | | | | +---+---+ | | ^ | | | | v | | +---+---+ +---+---+ +-------+ +---+---+ +-------+ | | | | | | | | | | | "A" +--------->+ "B" +------->+ "C" +------->+ "D" +<---+ "E" | | | | | | | | | | | +---+---+ +-------+ +--+----+ +-------+ +-------+ | ^ | | +-------+ | | | | +----------------------------------+ | "F" | | | +-------+ In example 2, get_list_nodes_directly_reachable("A") should return ["B", "C"] (or ["C", "B"]) """ # TODO def depth_first_search(self, node_start: str, nodes_already_visited: List[str]=None, ) -> List[str]: """ CHALLENGING EXERCISE :param node_start: a node in the Graph :param nodes_already_visited: a list of all the nodes that have been visited so far during the search :return: A list of ALL the nodes that are ultimately reachable from node_start, via a depth-first search. Description of a depth first search algorithm starting from "A" in example 2: 1. We start from "A" -> nodes_already_visited=["A"] -> Nodes reachable from A = ["B", "C"], we will visit starting from "B" (step 2) THEN "C" (step 6) | ----------> 2. We are at "B" | -> nodes_already_visited=["A", "B"] | -> Nodes reachable from B = ["C", "G"], we will visit starting from "C" (step 3) THEN "G" (step 5) | | | ----------> 3. We are at "C" | | -> nodes_already_visited=["A", "B", "C"] | | -> Nodes reachable from C = ["D"], we choose "D" for the next step | | | | | --------> 4. We are at "D" | | -> nodes_already_visited=["A", "B", "C", "D"] | | -> Nodes reachable from D = ["A"], BUT "A" is already in nodes_already_visited so we do not consider it. | | | ---------> 5. we are at "G" | -> nodes_already_visited=["A", "B", "C", "D", "G"] | -> Nodes reachable from G = [] -> nothing to do | ---------> 6. We are at "C" -> nodes_already_visited=["A", "B", "C", "D", "G"] -> "C" is in the list of nodes_already_visited -> do not do anything. 7. End of the recursion -> so the result of the depth first search starting from "A" is: ["A", "B", "C", "D", "G"] HINT: Implement a recursive function, in which you incrementally update nodes_already_visited at each step: - On "A" we launch a recursion starting from "B" (see step 2), then we update nodes_already_visited then we launch it starting from "C" (see step 6) - On "B" we launch a recursion starting from "C" (see step 3), then we update nodes_already_visited then we launch it starting from "G" (see step 5) """ # TODO def exists_path_between(self, node_start: str, node_end: str ) -> bool: """ REQUIRES depth_first_search :param node_start: node in the Graph :param node_end: node in the Graph :return: true if and only if there is a path in the graph that goes from node_start to node_end """ # TODO class UndirectedGraph(DirectedGraph): def __init__(self, list_edges: List[Tuple[str, str]]): """ An Undirected Graph is a special kind of Directed Graph in which all the edges are BIDIRECTIONAL. So each time an edge (node_1, node_2) is in the graph, its inverse edge (node_2, node_1) is ALSO in the Graph. Consequently, there are no arrows in the representation of an Undirected Graph: Example 3: +-------+ +-------+ +-------+ +-------+ +-------+ | | | | | | | | | | | "A" +----------+ "B" +--------+ "C" | | "D" +-----+ "E" | | | | | | | | | | | +---+---+ +-------+ +--+----+ +-------+ +-------+ | | | | | | +----------------------------------+ The graph above contains the following edges: - (A, B) and (B, A) - (A, C) and (C, A) - (B, C) and (C, B) - (D, E) and (E, D) So, each time we add an edge to the graph, its inverse should also be added to the graph! That is why in this class you should always TAKE INTO ACCOUNT BOTH: - the edges in list_edges - the INVERSE of all these edges :param list_edges: list of tuples (node_1, node_2) Remark: As explained before, an undirected graph can be seen as a special kind of directed graph. That is why we make this class inherit from DirectedGraph. """ super().__init__([]) self.add_edges(*list_edges) # Adding list_edges manually def add_edges(self, *edges: Tuple[str, str] ) -> None: """ :param edges: UNDIRECTED edges to be added to the graph; each edge is a tuple (node_1, node_2) (do not forget to also add the reversed edge as well if it is not already in the graph) """ # TODO def number_edges(self) -> int: """ :return: the number of UNDIRECTED edges in the graph For example, for the graph in example 3, the result should be 4. There are 4 undirected edges: - (A, B) - (A, C) - (B, C) - (D, E) """ # TODO def remove_edge(self, edge: Tuple[str, str]) -> None: """ delete the UNDIRECTED edge from the graph (if it exists in the graph) (do not forget to also delete the reversed edge as well) """ # TODO def is_fully_connected(self) -> bool: """ :return: true if and only if any node can be reached from any other node in the graph. For example, in example 3, the graph is not fully connected. In example 4 (see below), the graph is fully connected. Example 4: +-------+ +-------+ +-------+ +-------+ +-------+ | | | | | | | | | | | "A" +----------+ "B" +--------+ "C" +----+ "D" +-----+ "E" | | | | | | | | | | | +---+---+ +-------+ +--+----+ +-------+ +-------+ | | | | | | +----------------------------------+ """ # TODO def get_all_clusters(self) -> List[Set[str]]: """ :return: a list of sets of nodes, each set representing a cluster of nodes. With example 3, the result should be: [{"A", "B", "C"}, {"D", "E"}] With example 4, the result should be: [{"A", "B", "C", "D", "E"}] """ # TODO def merge_graphs(*graphs: DirectedGraph) -> DirectedGraph: """ :param graphs: Graph (which can be directed or Undirected) :return: A Graph that combines all the edges and nodes from all the graphs in parameters For example, if we merge this graph: +-------+ +-------+ +-------+ | | | | | | | "A" +--------->+ "B" +------->+ "C" | | | | | | | +-------+ +-------+ +-------+ | ^ | | | | +----------------------------------+ with this other graph +-------+ +-------+ | | | | | "C" +--------->+ "D" + | | | | +-------+ +-------+ we should get: +-------+ +-------+ +-------+ +-------+ | | | | | | | | | "A" +--------->+ "B" +------->+ "C" |------->+ "D" | | | | | | | | | +-------+ +-------+ +-------+ +-------+ | ^ | | | | +----------------------------------+ """ # TODO