from typing import Any, List, FrozenSet, Set
from MDP import State, MDP
class ConnectedComponent:
def __init__(self, states: List[State], children: Set[Any]) -> None:
self.states_ = states
self.children_ = children
def states(self) -> List[State]:
return self.states_
def children(self) -> List[Any]:
return self.children_
class CCGraph:
def __init__(self) -> None:
self.roots_ = set() # all connected components can be reached from the roots
def add_connected_component(self, cc: ConnectedComponent) -> None:
self.roots_ = self.roots_.difference(cc.children())
self.roots_.add(cc)
def roots(self) -> Set[ConnectedComponent]:
return self.roots_
def print(self) -> None:
todo = set()
node_to_int = {}
nb_nodes = 0
for node in self.roots_:
node_to_int[node] = nb_nodes
nb_nodes += 1
todo.add(node)
while todo:
node = todo.pop()
for next in node.children():
if not next in node_to_int:
node_to_int[next] = nb_nodes
nb_nodes += 1
todo.add(next)
print(f'{node_to_int[node]} -> { [node_to_int[next] for next in node.children()] }’)
# print(node.states())
def nb_components(self) -> int:
open = set()
closed = set()
for cc in self.roots():
open.add(cc)
closed.add(cc)
result = 0
while open:
cc = open.pop()
result += 1
for child in cc.children():
if child in closed:
continue
open.add(child)
closed.add(child)
return result
def compute_connected_components(mdp: MDP) -> CCGraph:
pass
# eof