Test instance creation for the GCP

create_GCP_test_instance.py

import numpy as np
from typing import Union

def create_test_instance(
    num_nodes: int, 
    edge_density_power_exponent: float, 
    edge_density_lb: float, 
    edge_density_ub: float, 
    seed: Union[int, None] = None, 
    verbose: bool=False
) -> np.array:
    
    """
    Create test instances of the GCP using a power distribution and some bounds.
    For each node, sample from the power distribution (with bounds), then set the
    node to be connected to that proportion of the other nodes.
    """
    
    def unique2d(a: np.array) -> np.array:
        """
        Ensure the rows of inputted 2d array are unique.
        """
        order = np.lexsort(a.T)
        a = a[order]
        diff = np.diff(a, axis=0)
        ui = np.ones(len(a), 'bool')
        ui[1:] = (diff != 0).any(axis=1) 
        return a[ui]
    
    # intialise an edge array and index array for the nodes
    edge_array = np.empty((0,2), int)
    all_nodes = np.arange(num_nodes)
    
    if seed is not None:
        np.random.seed(seed)
    else:
        np.random.seed()
    
    # we don't need to process the final node since all its edges  
    # will be added when we process the first n-1 nodes
    for node_index in range(num_nodes-1):
        # get the proportion of the total nodes that the current node should connect to
        # by sampling a power distribution and bounding the output 
        edge_density = np.random.power(edge_density_power_exponent)
        edge_density = max(min(edge_density, edge_density_ub), edge_density_lb)
        # translate the proportion to the number of node edges
        num_occurences_so_far = (edge_array == node_index).sum()
        # we want to discount the edges that already exist to the node
        # we also want to make sure that each node is connected to at least one other node
        num_node_edges = max(int(edge_density * num_nodes-1) - num_occurences_so_far, 1) 
        # choose the nodes to conenct to from the remaining nodes that haven't been processed
        remaining_nodes=np.arange(node_index+1, num_nodes)
        chosen_nodes = np.random.choice(remaining_nodes, size=min(len(remaining_nodes),num_node_edges), replace=False)
        if verbose:
            print(f'node_index {node_index}')
            print(f'edge_density {edge_density}')
            print(f'num_node_edges {num_node_edges}')
            print(f'chosen_nodes {chosen_nodes}')
            print(' ')
        # add the new edges to the edge array
        for chosen_node_index in chosen_nodes:
            edge_array = np.vstack((edge_array, np.sort([node_index, chosen_node_index])))
       
    # remove any repeated edges
    edge_array = unique2d(edge_array)
            
    return edge_array