Module RelayModel.Validation
Expand source code
from RelayModel.SortedListNode import SortedListNode
def check_sorted_list_node_is_valid(node: SortedListNode, node_ids, should_be_connected=False):
"""Checks if a given SortedListNode is valid.
The function checks if the given Node is valid. That means they have to be connected if they are staying and should
not be connected to other nodes if they are leaving.
Furthermore it checks if the connections are direct and if the connections are to the right node.
Args:
node (SortedListNode): The node that should be checked as a SortedListNode object.
node_ids (list): Defines a list of all staying node ids in the system. This list should be sorted.
should_be_connected (bool, optional): Defines if a node should be connected or not. By default this is set to
False. This should be set to True if a staying node is checked and False otherwise.
Returns:
bool: True if the given node is a valid SortedListNode, False otherwise.
"""
if node.left is None and node.right is None:
return not should_be_connected
elif not should_be_connected:
return False
elif node.left is None:
if not node.right.direct:
return False
if node_ids.index(node.node_id) != 0:
return False
sink_id = node.right.sink_rid.node_id
if node.node_id < node.right.sink_rid.node_id and sink_id in node_ids\
and node_ids.index(node.node_id) + 1 == node_ids.index(node.right.sink_rid.node_id):
return True
else:
return False
elif node.right is None:
if not node.left.direct:
return False
if node_ids.index(node.node_id) < len(node_ids) - 1:
return False
sink_id = node.left.sink_rid.node_id
if node.node_id > node.left.sink_rid.node_id and sink_id in node_ids \
and node_ids.index(node.node_id) == node_ids.index(node.left.sink_rid.node_id) + 1:
return True
else:
return False
elif node.left.sink_rid.node_id in node_ids and node.right.sink_rid.node_id in node_ids:
order = node.left.sink_rid.node_id < node.node_id < node.right.sink_rid.node_id
is_valid_linked_list_left = node_ids.index(node.left.sink_rid.node_id) + 1 == node_ids.index(node.node_id)
is_valid_linked_list_right = node_ids.index(node.right.sink_rid.node_id) == node_ids.index(node.node_id) + 1
direct = node.left.direct and node.right.direct
return direct and order and is_valid_linked_list_left and is_valid_linked_list_right
else:
return False
def check_weak_connectivity(nodes):
"""Checks a system of nodes for weakly connectivity.
The function takes a dict of nodes where the key is the node id and the value is the node itself.
Then it creates a adjacency matrix with the relays in the node and checks the weakly connectivity with the BFS
function.
Args:
nodes (dict): The nodes dict where the key is the node id and the value the node object.
Returns:
bool: True if the nodes are weakly connected. False otherwise.
"""
node_count = len(nodes.keys())
if node_count == 1:
return True
index = 0
id_index_mapping = {}
for node_id, node in nodes.items():
id_index_mapping[node_id] = index
index += 1
adjacency_matrix = [[0] * node_count for i in range(node_count)]
for node_id, node in nodes.items():
if node.left is not None and node.left.sink_rid.node_id in id_index_mapping:
left_id = id_index_mapping[node.left.sink_rid.node_id]
index = id_index_mapping[node_id]
adjacency_matrix[index][left_id] = 1
adjacency_matrix[left_id][index] = 1
if node.right is not None and node.right.sink_rid.node_id in id_index_mapping:
right_id = id_index_mapping[node.right.sink_rid.node_id]
index = id_index_mapping[node_id]
adjacency_matrix[index][right_id] = 1
adjacency_matrix[right_id][index] = 1
for relay in node.relays:
if relay.alive and relay != node.right and relay != node.left \
and relay.relay_id.layer_id.node_id in id_index_mapping \
and relay.sink_rid.node_id in id_index_mapping:
con_id = id_index_mapping[relay.sink_rid.node_id]
index = id_index_mapping[node_id]
adjacency_matrix[index][con_id] = 1
adjacency_matrix[con_id][index] = 1
visited_nodes = [0] * node_count
BFS(visited_nodes, adjacency_matrix)
count = 0
for visited in visited_nodes:
if visited == 2:
count += 1
if count == len(nodes.keys()):
return True
else:
return False
def BFS(visited_nodes, adjacency):
"""Breadth first search algorithm.
The function takes a list of visiting information where the index defines a node and the value defines the visited
information. Zero stands for not visited. One stands for queued but not visited yet. Two stands for visited.
It also takes a adjacency matrix to go along edges.
The method writes the results directly in the visited nodes variable given in the parameters.
Args:
visited_nodes (list): A list of visited information for each node.
adjacency (list): A adjacency matrix.
"""
queue = [0]
while len(queue) != 0:
u = queue.pop()
for v, has_edge in enumerate(adjacency[u]):
if has_edge == 1:
if visited_nodes[v] == 0:
visited_nodes[v] = 1
queue.insert(0, v)
visited_nodes[u] = 2
def system_has_valid_state(nodes, logger):
"""Checks a system of nodes if the system is in a valid state.
The method takes a dictionary of nodes. Every value of the dict should be a Node object.
It checks every node if they are stopped when they are leaving and if they are running if they stay.
Also it checks if every node is a valid sorted list node with the `check_sorted_list_node_is_valid` function.
If one condition fails it returns False. Only if all nodes are valid it checks if all staying nodes form a weakly
connected graph. If that is given it returns True otherwise False.
To log the validation process a logger can be passed to the function.
Args:
nodes (dict): The node dict where every value is a Node object.
logger (logging.Logger): A logger object to log some results of the validation process.
Returns:
bool: True if system of nodes is valid False otherwise.
"""
check_nodes = {}
node_ids = [node.node_id for node in nodes.values() if not node.leaving]
node_ids.sort()
for node in nodes.values():
if not node.leaving and not node.running:
logger.debug("Node should not be stopped {}".format(node.node_id))
return False
if node.leaving and node.running:
logger.debug("Node should be stopped {}".format(node.node_id))
return False
if not check_sorted_list_node_is_valid(node, node_ids, not node.leaving):
logger.debug(
f"Not valid third for node {node.node_id} left "
f"{node.left.sink_rid if node.left is not None else 'None'} and right "
f"{node.right.sink_rid if node.right is not None else 'None'} ")
logger.debug(str(node_ids))
return False
# else:
# logger.debug(
# f"Valid third for node {node.node_id} left {node.left.sink_rid if node.left is not None else 'None'} and right {node.right.sink_rid if node.right is not None else 'None'} ")
if not node.leaving or node.running:
check_nodes[node.node_id] = node
valid = check_weak_connectivity(check_nodes)
if not valid:
logger.warning("Not weak connected")
return valid
Functions
def BFS(visited_nodes, adjacency)-
Breadth first search algorithm.
The function takes a list of visiting information where the index defines a node and the value defines the visited information. Zero stands for not visited. One stands for queued but not visited yet. Two stands for visited. It also takes a adjacency matrix to go along edges. The method writes the results directly in the visited nodes variable given in the parameters.
Args
visited_nodes:list- A list of visited information for each node.
adjacency:list- A adjacency matrix.
Expand source code
def BFS(visited_nodes, adjacency): """Breadth first search algorithm. The function takes a list of visiting information where the index defines a node and the value defines the visited information. Zero stands for not visited. One stands for queued but not visited yet. Two stands for visited. It also takes a adjacency matrix to go along edges. The method writes the results directly in the visited nodes variable given in the parameters. Args: visited_nodes (list): A list of visited information for each node. adjacency (list): A adjacency matrix. """ queue = [0] while len(queue) != 0: u = queue.pop() for v, has_edge in enumerate(adjacency[u]): if has_edge == 1: if visited_nodes[v] == 0: visited_nodes[v] = 1 queue.insert(0, v) visited_nodes[u] = 2 def check_sorted_list_node_is_valid(node: SortedListNode, node_ids, should_be_connected=False)-
Checks if a given SortedListNode is valid.
The function checks if the given Node is valid. That means they have to be connected if they are staying and should not be connected to other nodes if they are leaving. Furthermore it checks if the connections are direct and if the connections are to the right node.
Args
node:SortedListNode- The node that should be checked as a SortedListNode object.
node_ids:list- Defines a list of all staying node ids in the system. This list should be sorted.
should_be_connected:bool, optional- Defines if a node should be connected or not. By default this is set to False. This should be set to True if a staying node is checked and False otherwise.
Returns
bool- True if the given node is a valid SortedListNode, False otherwise.
Expand source code
def check_sorted_list_node_is_valid(node: SortedListNode, node_ids, should_be_connected=False): """Checks if a given SortedListNode is valid. The function checks if the given Node is valid. That means they have to be connected if they are staying and should not be connected to other nodes if they are leaving. Furthermore it checks if the connections are direct and if the connections are to the right node. Args: node (SortedListNode): The node that should be checked as a SortedListNode object. node_ids (list): Defines a list of all staying node ids in the system. This list should be sorted. should_be_connected (bool, optional): Defines if a node should be connected or not. By default this is set to False. This should be set to True if a staying node is checked and False otherwise. Returns: bool: True if the given node is a valid SortedListNode, False otherwise. """ if node.left is None and node.right is None: return not should_be_connected elif not should_be_connected: return False elif node.left is None: if not node.right.direct: return False if node_ids.index(node.node_id) != 0: return False sink_id = node.right.sink_rid.node_id if node.node_id < node.right.sink_rid.node_id and sink_id in node_ids\ and node_ids.index(node.node_id) + 1 == node_ids.index(node.right.sink_rid.node_id): return True else: return False elif node.right is None: if not node.left.direct: return False if node_ids.index(node.node_id) < len(node_ids) - 1: return False sink_id = node.left.sink_rid.node_id if node.node_id > node.left.sink_rid.node_id and sink_id in node_ids \ and node_ids.index(node.node_id) == node_ids.index(node.left.sink_rid.node_id) + 1: return True else: return False elif node.left.sink_rid.node_id in node_ids and node.right.sink_rid.node_id in node_ids: order = node.left.sink_rid.node_id < node.node_id < node.right.sink_rid.node_id is_valid_linked_list_left = node_ids.index(node.left.sink_rid.node_id) + 1 == node_ids.index(node.node_id) is_valid_linked_list_right = node_ids.index(node.right.sink_rid.node_id) == node_ids.index(node.node_id) + 1 direct = node.left.direct and node.right.direct return direct and order and is_valid_linked_list_left and is_valid_linked_list_right else: return False def check_weak_connectivity(nodes)-
Checks a system of nodes for weakly connectivity.
The function takes a dict of nodes where the key is the node id and the value is the node itself. Then it creates a adjacency matrix with the relays in the node and checks the weakly connectivity with the BFS function.
Args
nodes:dict- The nodes dict where the key is the node id and the value the node object.
Returns
bool- True if the nodes are weakly connected. False otherwise.
Expand source code
def check_weak_connectivity(nodes): """Checks a system of nodes for weakly connectivity. The function takes a dict of nodes where the key is the node id and the value is the node itself. Then it creates a adjacency matrix with the relays in the node and checks the weakly connectivity with the BFS function. Args: nodes (dict): The nodes dict where the key is the node id and the value the node object. Returns: bool: True if the nodes are weakly connected. False otherwise. """ node_count = len(nodes.keys()) if node_count == 1: return True index = 0 id_index_mapping = {} for node_id, node in nodes.items(): id_index_mapping[node_id] = index index += 1 adjacency_matrix = [[0] * node_count for i in range(node_count)] for node_id, node in nodes.items(): if node.left is not None and node.left.sink_rid.node_id in id_index_mapping: left_id = id_index_mapping[node.left.sink_rid.node_id] index = id_index_mapping[node_id] adjacency_matrix[index][left_id] = 1 adjacency_matrix[left_id][index] = 1 if node.right is not None and node.right.sink_rid.node_id in id_index_mapping: right_id = id_index_mapping[node.right.sink_rid.node_id] index = id_index_mapping[node_id] adjacency_matrix[index][right_id] = 1 adjacency_matrix[right_id][index] = 1 for relay in node.relays: if relay.alive and relay != node.right and relay != node.left \ and relay.relay_id.layer_id.node_id in id_index_mapping \ and relay.sink_rid.node_id in id_index_mapping: con_id = id_index_mapping[relay.sink_rid.node_id] index = id_index_mapping[node_id] adjacency_matrix[index][con_id] = 1 adjacency_matrix[con_id][index] = 1 visited_nodes = [0] * node_count BFS(visited_nodes, adjacency_matrix) count = 0 for visited in visited_nodes: if visited == 2: count += 1 if count == len(nodes.keys()): return True else: return False def system_has_valid_state(nodes, logger)-
Checks a system of nodes if the system is in a valid state.
The method takes a dictionary of nodes. Every value of the dict should be a Node object. It checks every node if they are stopped when they are leaving and if they are running if they stay. Also it checks if every node is a valid sorted list node with the
check_sorted_list_node_is_valid()function.If one condition fails it returns False. Only if all nodes are valid it checks if all staying nodes form a weakly connected graph. If that is given it returns True otherwise False.
To log the validation process a logger can be passed to the function.
Args
nodes:dict- The node dict where every value is a Node object.
logger:logging.Logger- A logger object to log some results of the validation process.
Returns
bool- True if system of nodes is valid False otherwise.
Expand source code
def system_has_valid_state(nodes, logger): """Checks a system of nodes if the system is in a valid state. The method takes a dictionary of nodes. Every value of the dict should be a Node object. It checks every node if they are stopped when they are leaving and if they are running if they stay. Also it checks if every node is a valid sorted list node with the `check_sorted_list_node_is_valid` function. If one condition fails it returns False. Only if all nodes are valid it checks if all staying nodes form a weakly connected graph. If that is given it returns True otherwise False. To log the validation process a logger can be passed to the function. Args: nodes (dict): The node dict where every value is a Node object. logger (logging.Logger): A logger object to log some results of the validation process. Returns: bool: True if system of nodes is valid False otherwise. """ check_nodes = {} node_ids = [node.node_id for node in nodes.values() if not node.leaving] node_ids.sort() for node in nodes.values(): if not node.leaving and not node.running: logger.debug("Node should not be stopped {}".format(node.node_id)) return False if node.leaving and node.running: logger.debug("Node should be stopped {}".format(node.node_id)) return False if not check_sorted_list_node_is_valid(node, node_ids, not node.leaving): logger.debug( f"Not valid third for node {node.node_id} left " f"{node.left.sink_rid if node.left is not None else 'None'} and right " f"{node.right.sink_rid if node.right is not None else 'None'} ") logger.debug(str(node_ids)) return False # else: # logger.debug( # f"Valid third for node {node.node_id} left {node.left.sink_rid if node.left is not None else 'None'} and right {node.right.sink_rid if node.right is not None else 'None'} ") if not node.leaving or node.running: check_nodes[node.node_id] = node valid = check_weak_connectivity(check_nodes) if not valid: logger.warning("Not weak connected") return valid