Source code for Creator

from typing import Dict, Set, List, Tuple

import networkx
from random import randint

[docs]class Creator: """ Static class that works with creating graph objects from given specifications. Can either create a random unassigned graph with given nodes or a graph with edges from given parameters. """
[docs] @staticmethod def from_random(node_count: int, area_dimension: int = None) -> networkx.Graph: """ Creates an unassigned graph with nodes of random position. The work area corresponds to the node count squared. :rtype: networkx.Graph :param node_count: The number of nodes to create a graph from. :param area_dimension: The size of the area to put nodes in. Defaults to the node count. :return: An unassigned graph with nodes with random position. """ if area_dimension is None: area_dimension = node_count # If the area is smaller than the node count it won't be able to create a graph. if (area_dimension*area_dimension) < node_count: raise ValueError("area_dimension must be at least the size of sqrt(node_count)") nxg: networkx.Graph = networkx.Graph() node_set: Set[str] = set() for node_id in range(0, node_count): coord_x = None coord_y = None # Keep finding new coordinates until a new one is found while coord_x is None or coord_y is None or str((coord_x, coord_y)) in node_set: coord_x = randint(0, area_dimension-1) coord_y = randint(0, area_dimension-1) nxg.add_node(node_id, x=coord_x, y=coord_y) node_set.add(str((coord_x, coord_y))) return nxg
[docs] @staticmethod def from_spec(v: Dict[int, Tuple[int, int]], e: Dict[int, List[int]]) -> networkx.Graph: """ Creates a graph from given parameters, that also assigns weighted edges based on a neighbour list. :param v: Nodes in the graph. Should be a dict with the format { node_1: (x, y), node_2: (x, y)... } :param e: Edges that connects the nodes.Should be a dict with the format { node_1: [dest_1, dest_2, ...], node_2: [dest_3, dest_4, ...] } :return: A graph with assigned nodes and weighted edges. :rtype: networkx.Graph """ nxg = networkx.Graph() for node_id, node in v.items(): nxg.add_node(node_id, x=node[0], y=node[1]) for origin, destinations in e.items(): for destination in destinations: Creator.add_weighted_edge(nxg, origin, destination) return nxg
[docs] @staticmethod def add_weighted_edge(nxg: networkx.Graph, origin: int, destination: int, ignore_validity: bool = False) -> bool: """ Adds a bidirectional edge between 2 nodes with weight corresponding to the distance between the nodes squared. :param nxg: The graph to add an edge to. :param origin: First node id to add the edge from :param destination: Second node id to add the edge to. :param ignore_validity: Whether to skip the validity check when adding the edge :return: True if the edge was added, otherwise false if the edge already existed. """ if ignore_validity is False: if nxg.has_edge(origin, destination): return False # Find start and end coordinates start_coord = (nxg.node[origin]['x'], nxg.node[origin]['y']) destination_coord = (nxg.node[destination]['x'], nxg.node[destination]['y']) # Subtract the coordinate values of the two points delta = tuple(map(lambda n: pow(n[0] - n[1], 2), zip(start_coord, destination_coord))) # Extract values from delta tuple delta_x, delta_y = delta # Cost is the summation of the difference in x and y of the two coordinates weight = delta_x + delta_y # Add edge to graph with its corresponding weight nxg.add_edge(origin, destination, weight=weight) return True