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