API

Travelling Salesman Problem with Profits library

Alpha

Bases: IntEnum

Ratio between profit/cost limit and profit/cost of TSP solution

Source code in tspwplib/types.py

class Alpha(IntEnum):
    """Ratio between profit/cost limit and profit/cost of TSP solution"""

    fifty = 50

BaseTSP

Bases: BaseModel

A pydantic model for tsplib95.

Each field is validated with type hinting.

Source code in tspwplib/problem.py

class BaseTSP(pydantic.BaseModel):
    """A pydantic model for tsplib95.

    Each field is validated with type hinting.
    """

    # pylint: disable=too-many-arguments

    capacity: Optional[Union[int, float]] = None
    comment: str
    demands: Optional[VertexFunction]
    depots: VertexList
    dimension: int
    display_data: Optional[NodeCoords] = None
    display_data_type: DisplayDataType
    edge_data: SimpleEdgeList
    edge_data_format: EdgeDataFormat
    edge_weights: Optional[SimpleEdgeFunction] = None
    edge_weight_format: EdgeWeightFormat
    edge_weight_type: EdgeWeightType
    fixed_edges: SimpleEdgeList
    name: str
    node_coords: Optional[NodeCoords] = None
    node_coord_type: NodeCoordType
    problem_type: str
    tours: Optional[List[VertexList]] = None

    # pydantic model config
    model_config = {"arbitrary_types_allowed": True}

    @classmethod
    def from_networkx(
        cls,
        name: str,
        comment: str,
        problem_type: str,
        G: nx.Graph,
        capacity: Optional[Union[int, float]] = None,
        display_data: Optional[NodeCoords] = None,
        display_data_type: DisplayDataType = DisplayDataType.NO_DISPLAY,
        edge_weight_format: EdgeWeightFormat = EdgeWeightFormat.FULL_MATRIX,
        weight_attr_name: str = "weight",
    ):
        """Get a base TSP model from a networkx graph"""
        edge_attr_names = edge_attribute_names(G)
        node_attr_names = node_attribute_names(G)
        if weight_attr_name not in edge_attr_names:
            message = f"{weight_attr_name} is required to be an edge attribute, "
            message += "but was not found in graph. "
            message += "This function only supports an explicit weight function. "
            raise NotImplementedError(message)
        is_2d = "x" in node_attr_names and "y" in node_attr_names
        is_3d = is_2d and "z" in node_attr_names
        if is_3d:
            raise NotImplementedError("3D coords are not supported")
            # node_coord_type = NodeCoordType.THREED_COORDS
            # node_coords = {
            #     node: (float(data["x"]), float(data["y"]), float(data["z"]))
            #     for node, data in G.nodes(data=True)
            # }
        if is_2d:
            node_coord_type = NodeCoordType.TWOD_COORDS
            node_coords = {
                node: (float(data["x"]), float(data["y"]))
                for node, data in G.nodes(data=True)
            }
        else:
            node_coord_type = NodeCoordType.NO_COORDS
            node_coords = {}

        demands = None
        if "demand" in node_attr_names:
            demands = nx.get_node_attributes(G, "demand")
        if display_data_type == DisplayDataType.COORD_DISPLAY:
            display_data = node_coords

        fixed_edges = []
        if "is_fixed" in edge_attr_names:
            fixed_edges = [
                (u, v) for u, v, data in G.edges(data=True) if data["is_fixed"]
            ]

        depots = []
        if "is_depot" in node_attr_names:
            depots = [node for node, data in G.nodes(data=True) if data["is_depot"]]
        edge_data = list(G.edges())
        edge_weights = nx.get_edge_attributes(G, weight_attr_name)
        return cls(
            capacity=capacity,
            comment=comment,
            demands=demands,
            depots=depots,
            dimension=G.number_of_nodes(),
            display_data=display_data,
            display_data_type=display_data_type,
            edge_data=edge_data,
            edge_data_format=EdgeDataFormat.EDGE_LIST,
            edge_weights=edge_weights,
            edge_weight_format=edge_weight_format,
            edge_weight_type=EdgeWeightType.EXPLICIT,
            fixed_edges=fixed_edges,
            name=name,
            node_coords=node_coords,
            node_coord_type=node_coord_type,
            problem_type=problem_type,
            tours=None,
        )

    @classmethod
    def from_dataframes(
        cls,
        name: str,
        comment: str,
        problem_type: str,
        edges_df: pd.DataFrame,
        nodes_df: pd.DataFrame,
        capacity: Optional[Union[int, float]] = None,
        display_data: Optional[NodeCoords] = None,
        display_data_type: DisplayDataType = DisplayDataType.NO_DISPLAY,
        edge_weight_format: EdgeWeightFormat = EdgeWeightFormat.FULL_MATRIX,
    ):
        """Get a TSP base model from edge and node dataframes

        Notes:
            Essential edge columns: [source, target, weight].
            Optional edge columns: [is_fixed].
            Essential node columns: [node, is_depot].
            Optional node columns: [x, y, z, demand].
            The edge weight function is explicitly given by the 'weight' column.
        """
        if "weight" not in edges_df:
            message = "'weight' is not a column in edges_df. "
            message += "This function only supports an explicit weight function. "
            message += "If you have a column that can be used as the weight function, "
            message += "please rename the column to 'weight'."
            raise NotImplementedError(message)
        is_2d = "x" in nodes_df.columns and "y" in nodes_df.columns
        is_3d = is_2d and "z" in nodes_df.columns
        if is_3d:
            raise NotImplementedError("3D coords not supported")
        if is_2d:
            node_coord_type = NodeCoordType.TWOD_COORDS
            node_coords = dict(zip(nodes_df["node"], zip(nodes_df["x"], nodes_df["y"])))
        else:
            node_coord_type = NodeCoordType.NO_COORDS
            node_coords = {}

        demands = None
        if "demand" in nodes_df.columns:
            demands = dict(zip(nodes_df["node"], nodes_df["demand"]))

        if display_data_type == DisplayDataType.COORD_DISPLAY:
            display_data = node_coords

        fixed_edges = []
        if "is_fixed" in edges_df.columns:
            fixed_edges_df = edges_df.loc[edges_df["is_fixed"]]
            fixed_edges = list(zip(fixed_edges_df["source"], fixed_edges_df["target"]))

        depots = nodes_df.loc[nodes_df["is_depot"]]["node"].to_list()
        edge_data = list(zip(edges_df["source"], edges_df["target"]))
        edge_weights = dict(zip(edge_data, edges_df["weight"]))
        return cls(
            capacity=capacity,
            comment=comment,
            demands=demands,
            depots=depots,
            dimension=len(nodes_df["node"]),
            display_data=display_data,
            display_data_type=display_data_type,
            edge_data=edge_data,
            edge_data_format=EdgeDataFormat.EDGE_LIST,
            edge_weights=edge_weights,
            edge_weight_format=edge_weight_format,
            edge_weight_type=EdgeWeightType.EXPLICIT,
            fixed_edges=fixed_edges,
            name=name,
            node_coords=node_coords,
            node_coord_type=node_coord_type,
            problem_type=problem_type,
            tours=None,
        )

    @classmethod
    def from_tsplib95(cls, problem: tsplib95.models.StandardProblem):
        """Get a TSP base model from a StandardProblem object"""

        display_data_type = (
            problem.display_data_type
            if problem.display_data_type
            else DisplayDataType.NO_DISPLAY
        )
        edge_data_format = (
            problem.edge_data_format
            if problem.edge_data_format
            else EdgeDataFormat.EDGE_LIST
        )
        edge_weight_type = problem.edge_weight_type

        # edge weight format
        edge_weight_format = problem.edge_weight_format
        if edge_weight_type == EdgeWeightType.UNIFORM_RANDOM:
            edge_weight_format = EdgeWeightFormat.FUNCTION
            weights = uniform_random_cost(list(problem.get_edges()))
        elif (
            not edge_weight_format
            and edge_weight_type in EdgeWeightType.__members__
            and edge_weight_type != EdgeWeightType.EXPLICIT
        ):
            edge_weight_format = EdgeWeightFormat.FUNCTION
            weights = {(i, j): problem.get_weight(i, j) for i, j in problem.get_edges()}
        elif not edge_weight_format and edge_weight_type == EdgeWeightType.EXPLICIT:
            raise ValueError(
                "Edge weight type is set to EXPLICIT but no edge weight format is given"
            )
        elif not edge_weight_format:
            raise ValueError(
                "Edge weight format in StandardProblem is not set - cannot assign edge weights."
            )
        else:
            weights = {(i, j): problem.get_weight(i, j) for i, j in problem.get_edges()}

        node_coord_type = (
            problem.node_coord_type
            if problem.node_coord_type
            else NodeCoordType.NO_COORDS
        )
        node_coords = None
        if node_coord_type == NodeCoordType.TWOD_COORDS:
            node_coords = {i: problem.node_coords.get(i) for i in problem.get_nodes()}
        elif node_coord_type == NodeCoordType.THREED_COORDS:
            raise NotImplementedError("3D coords not yet supported")

        return cls(
            capacity=problem.capacity,
            comment=problem.comment if problem.comment else "",
            demands=problem.demands,
            depots=problem.depots,
            dimension=problem.dimension,
            display_data=problem.display_data,
            display_data_type=display_data_type,
            edge_data=list(problem.get_edges()),
            edge_data_format=edge_data_format,
            edge_weights=weights,
            edge_weight_format=edge_weight_format,
            edge_weight_type=edge_weight_type,
            fixed_edges=problem.fixed_edges,
            name=problem.name,
            node_coords=node_coords,
            node_coord_type=node_coord_type,
            problem_type=problem.type,
            tours=problem.tours,
        )

    @no_type_check
    def to_tsplib95(self) -> tsplib95.models.StandardProblem:
        """Convert to a tsplib95 standard model"""
        weights = None
        if self.edge_weight_type == EdgeWeightType.EXPLICIT:
            weights = self.get_weighted_full_matrix()

        optional_kwargs = {}
        if not self.capacity is None:
            optional_kwargs["capacity"] = self.capacity
        if self.display_data:
            optional_kwargs["display_data"] = self.display_data
        if self.fixed_edges:
            optional_kwargs["fixed_edges"] = self.fixed_edges
        if self.tours:
            optional_kwargs["tours"] = self.tours
        return tsplib95.models.StandardProblem(
            comment=self.comment,
            demands=self.demands,
            depots=self.depots,
            dimension=self.dimension,
            display_data_type=self.display_data_type,
            edge_data=self.edge_data,
            edge_data_format=self.edge_data_format,
            edge_weights=weights,
            edge_weight_format=self.edge_weight_format,
            edge_weight_type=self.edge_weight_type,
            name=self.name,
            node_coords=self.node_coords,
            node_coord_type=self.node_coord_type,
            type=self.problem_type,
            **optional_kwargs,
        )

    @classmethod
    def from_yaml(cls, yaml_filepath: Path):
        """Load from a yaml file"""
        with open(yaml_filepath, "r", encoding="utf-8") as yaml_file:
            yaml_dict = yaml.load(yaml_file, Loader=yaml.FullLoader)
        edge_data = edge_list_from_adjacency_list(yaml_dict.pop("edge_data"))
        edge_weights = edge_dict_from_adjacency_weights(yaml_dict.pop("edge_weights"))
        fixed_edges = edge_list_from_adjacency_list(yaml_dict.pop("fixed_edges"))
        return cls(
            **yaml_dict,
            edge_data=edge_data,
            edge_weights=edge_weights,
            fixed_edges=fixed_edges,
        )

    def to_yaml(self, yaml_filepath: Path) -> None:
        """Dump the TSP to a YAML file"""
        yaml_dict = dict(
            comment=self.comment,
            demands=self.demands,
            depots=self.depots,
            dimension=self.dimension,
            display_data_type=self.display_data_type.value,
            edge_data=adjacency_list_from_edge_list(self.edge_data),
            edge_data_format=self.edge_data_format.value,
            edge_weight_format=self.edge_weight_format.value,
            edge_weight_type=self.edge_weight_type.value,
            fixed_edges=adjacency_list_from_edge_list(self.fixed_edges),
            name=self.name,
            node_coords=self.node_coords,
            node_coord_type=self.node_coord_type.value,
            problem_type=self.problem_type,
            tours=self.tours,
        )
        if self.edge_weights:
            weights: AdjWeights = adjacency_weights_from_edge_dict(self.edge_weights)
            yaml_dict["edge_weights"] = weights  # type: ignore
        else:
            yaml_dict["edge_weights"] = None
        with open(yaml_filepath, "w", encoding="utf-8") as yaml_file:
            yaml.dump(yaml_dict, yaml_file)

    def get_weighted_full_matrix(self) -> npt.NDArray[np.int_]:
        """Get a square weighted adjacency matrix, sorted by node ID"""
        # create a graph
        G = self.get_graph()
        # sort the node list (ascending)
        sorted_node_list = list(G.nodes())
        sorted_node_list.sort()
        # then get the weighted adjacency matrix
        return nx.to_numpy_array(
            G, nodelist=sorted_node_list, weight="weight", dtype=int
        )

    def __set_graph_attributes(self, graph: nx.Graph) -> None:
        """Set graph attributes such as 'name' and 'comment'"""
        graph.graph["name"] = self.name
        graph.graph["comment"] = self.comment
        graph.graph["problem_type"] = self.problem_type
        graph.graph["dimension"] = self.dimension
        if not self.capacity is None:
            graph.graph["capacity"] = self.capacity

    def __set_node_attributes(self, graph: nx.Graph) -> None:
        """Set node attributes"""
        for vertex in graph.nodes():
            graph.nodes[vertex]["is_depot"] = vertex in self.depots
            if self.demands:
                graph.nodes[vertex]["demand"] = self.demands[vertex]
            if self.display_data:
                graph.nodes[vertex]["display"] = self.display_data[vertex]
            if self.node_coords:
                coords = self.node_coords[vertex]
                graph.nodes[vertex]["x"] = coords[0]
                graph.nodes[vertex]["y"] = coords[1]

    def __add_edges(self, graph: nx.Graph) -> None:
        """Add edges from edge data

        Args:
            graph: Input graph
        """
        for edge in self.edge_data:
            graph.add_edge(edge[0], edge[1])

    def __set_edge_attributes(self, graph: nx.Graph) -> None:
        """Set edge attributes for 'weight' and 'is_fixed'

        Args:
            graph: Input graph
        """
        nx.set_edge_attributes(graph, self.edge_weights, name="weight")
        fixed = {(u, v): (u, v) in self.fixed_edges for u, v in graph.edges()}
        nx.set_edge_attributes(graph, fixed, name="is_fixed")

    def get_graph(self) -> nx.Graph:
        """Get a networkx graph

        Returns:
            Undirected networkx graph with node attributes such as 'is_depot'
            and edge attributes such as 'weight' and 'is_fixed'.
        """
        G = nx.Graph()
        self.__set_graph_attributes(G)
        self.__add_edges(G)
        self.__set_edge_attributes(G)
        self.__set_node_attributes(G)
        return G

__add_edges(graph)

Add edges from edge data

Parameters:

Name	Type	Description	Default
graph	Graph	Input graph	required

Source code in tspwplib/problem.py

def __add_edges(self, graph: nx.Graph) -> None:
    """Add edges from edge data

    Args:
        graph: Input graph
    """
    for edge in self.edge_data:
        graph.add_edge(edge[0], edge[1])

__set_edge_attributes(graph)

Set edge attributes for 'weight' and 'is_fixed'

Parameters:

Name	Type	Description	Default
graph	Graph	Input graph	required

Source code in tspwplib/problem.py

def __set_edge_attributes(self, graph: nx.Graph) -> None:
    """Set edge attributes for 'weight' and 'is_fixed'

    Args:
        graph: Input graph
    """
    nx.set_edge_attributes(graph, self.edge_weights, name="weight")
    fixed = {(u, v): (u, v) in self.fixed_edges for u, v in graph.edges()}
    nx.set_edge_attributes(graph, fixed, name="is_fixed")

__set_graph_attributes(graph)

Set graph attributes such as 'name' and 'comment'

Source code in tspwplib/problem.py

def __set_graph_attributes(self, graph: nx.Graph) -> None:
    """Set graph attributes such as 'name' and 'comment'"""
    graph.graph["name"] = self.name
    graph.graph["comment"] = self.comment
    graph.graph["problem_type"] = self.problem_type
    graph.graph["dimension"] = self.dimension
    if not self.capacity is None:
        graph.graph["capacity"] = self.capacity

__set_node_attributes(graph)

Set node attributes

Source code in tspwplib/problem.py

def __set_node_attributes(self, graph: nx.Graph) -> None:
    """Set node attributes"""
    for vertex in graph.nodes():
        graph.nodes[vertex]["is_depot"] = vertex in self.depots
        if self.demands:
            graph.nodes[vertex]["demand"] = self.demands[vertex]
        if self.display_data:
            graph.nodes[vertex]["display"] = self.display_data[vertex]
        if self.node_coords:
            coords = self.node_coords[vertex]
            graph.nodes[vertex]["x"] = coords[0]
            graph.nodes[vertex]["y"] = coords[1]

from_dataframes(name, comment, problem_type, edges_df, nodes_df, capacity=None, display_data=None, display_data_type=DisplayDataType.NO_DISPLAY, edge_weight_format=EdgeWeightFormat.FULL_MATRIX) classmethod

Get a TSP base model from edge and node dataframes

Notes

Essential edge columns: [source, target, weight]. Optional edge columns: [is_fixed]. Essential node columns: [node, is_depot]. Optional node columns: [x, y, z, demand]. The edge weight function is explicitly given by the 'weight' column.

Source code in tspwplib/problem.py

@classmethod
def from_dataframes(
    cls,
    name: str,
    comment: str,
    problem_type: str,
    edges_df: pd.DataFrame,
    nodes_df: pd.DataFrame,
    capacity: Optional[Union[int, float]] = None,
    display_data: Optional[NodeCoords] = None,
    display_data_type: DisplayDataType = DisplayDataType.NO_DISPLAY,
    edge_weight_format: EdgeWeightFormat = EdgeWeightFormat.FULL_MATRIX,
):
    """Get a TSP base model from edge and node dataframes

    Notes:
        Essential edge columns: [source, target, weight].
        Optional edge columns: [is_fixed].
        Essential node columns: [node, is_depot].
        Optional node columns: [x, y, z, demand].
        The edge weight function is explicitly given by the 'weight' column.
    """
    if "weight" not in edges_df:
        message = "'weight' is not a column in edges_df. "
        message += "This function only supports an explicit weight function. "
        message += "If you have a column that can be used as the weight function, "
        message += "please rename the column to 'weight'."
        raise NotImplementedError(message)
    is_2d = "x" in nodes_df.columns and "y" in nodes_df.columns
    is_3d = is_2d and "z" in nodes_df.columns
    if is_3d:
        raise NotImplementedError("3D coords not supported")
    if is_2d:
        node_coord_type = NodeCoordType.TWOD_COORDS
        node_coords = dict(zip(nodes_df["node"], zip(nodes_df["x"], nodes_df["y"])))
    else:
        node_coord_type = NodeCoordType.NO_COORDS
        node_coords = {}

    demands = None
    if "demand" in nodes_df.columns:
        demands = dict(zip(nodes_df["node"], nodes_df["demand"]))

    if display_data_type == DisplayDataType.COORD_DISPLAY:
        display_data = node_coords

    fixed_edges = []
    if "is_fixed" in edges_df.columns:
        fixed_edges_df = edges_df.loc[edges_df["is_fixed"]]
        fixed_edges = list(zip(fixed_edges_df["source"], fixed_edges_df["target"]))

    depots = nodes_df.loc[nodes_df["is_depot"]]["node"].to_list()
    edge_data = list(zip(edges_df["source"], edges_df["target"]))
    edge_weights = dict(zip(edge_data, edges_df["weight"]))
    return cls(
        capacity=capacity,
        comment=comment,
        demands=demands,
        depots=depots,
        dimension=len(nodes_df["node"]),
        display_data=display_data,
        display_data_type=display_data_type,
        edge_data=edge_data,
        edge_data_format=EdgeDataFormat.EDGE_LIST,
        edge_weights=edge_weights,
        edge_weight_format=edge_weight_format,
        edge_weight_type=EdgeWeightType.EXPLICIT,
        fixed_edges=fixed_edges,
        name=name,
        node_coords=node_coords,
        node_coord_type=node_coord_type,
        problem_type=problem_type,
        tours=None,
    )

from_networkx(name, comment, problem_type, G, capacity=None, display_data=None, display_data_type=DisplayDataType.NO_DISPLAY, edge_weight_format=EdgeWeightFormat.FULL_MATRIX, weight_attr_name='weight') classmethod

Get a base TSP model from a networkx graph

Source code in tspwplib/problem.py

@classmethod
def from_networkx(
    cls,
    name: str,
    comment: str,
    problem_type: str,
    G: nx.Graph,
    capacity: Optional[Union[int, float]] = None,
    display_data: Optional[NodeCoords] = None,
    display_data_type: DisplayDataType = DisplayDataType.NO_DISPLAY,
    edge_weight_format: EdgeWeightFormat = EdgeWeightFormat.FULL_MATRIX,
    weight_attr_name: str = "weight",
):
    """Get a base TSP model from a networkx graph"""
    edge_attr_names = edge_attribute_names(G)
    node_attr_names = node_attribute_names(G)
    if weight_attr_name not in edge_attr_names:
        message = f"{weight_attr_name} is required to be an edge attribute, "
        message += "but was not found in graph. "
        message += "This function only supports an explicit weight function. "
        raise NotImplementedError(message)
    is_2d = "x" in node_attr_names and "y" in node_attr_names
    is_3d = is_2d and "z" in node_attr_names
    if is_3d:
        raise NotImplementedError("3D coords are not supported")
        # node_coord_type = NodeCoordType.THREED_COORDS
        # node_coords = {
        #     node: (float(data["x"]), float(data["y"]), float(data["z"]))
        #     for node, data in G.nodes(data=True)
        # }
    if is_2d:
        node_coord_type = NodeCoordType.TWOD_COORDS
        node_coords = {
            node: (float(data["x"]), float(data["y"]))
            for node, data in G.nodes(data=True)
        }
    else:
        node_coord_type = NodeCoordType.NO_COORDS
        node_coords = {}

    demands = None
    if "demand" in node_attr_names:
        demands = nx.get_node_attributes(G, "demand")
    if display_data_type == DisplayDataType.COORD_DISPLAY:
        display_data = node_coords

    fixed_edges = []
    if "is_fixed" in edge_attr_names:
        fixed_edges = [
            (u, v) for u, v, data in G.edges(data=True) if data["is_fixed"]
        ]

    depots = []
    if "is_depot" in node_attr_names:
        depots = [node for node, data in G.nodes(data=True) if data["is_depot"]]
    edge_data = list(G.edges())
    edge_weights = nx.get_edge_attributes(G, weight_attr_name)
    return cls(
        capacity=capacity,
        comment=comment,
        demands=demands,
        depots=depots,
        dimension=G.number_of_nodes(),
        display_data=display_data,
        display_data_type=display_data_type,
        edge_data=edge_data,
        edge_data_format=EdgeDataFormat.EDGE_LIST,
        edge_weights=edge_weights,
        edge_weight_format=edge_weight_format,
        edge_weight_type=EdgeWeightType.EXPLICIT,
        fixed_edges=fixed_edges,
        name=name,
        node_coords=node_coords,
        node_coord_type=node_coord_type,
        problem_type=problem_type,
        tours=None,
    )

from_tsplib95(problem) classmethod

Get a TSP base model from a StandardProblem object

Source code in tspwplib/problem.py

@classmethod
def from_tsplib95(cls, problem: tsplib95.models.StandardProblem):
    """Get a TSP base model from a StandardProblem object"""

    display_data_type = (
        problem.display_data_type
        if problem.display_data_type
        else DisplayDataType.NO_DISPLAY
    )
    edge_data_format = (
        problem.edge_data_format
        if problem.edge_data_format
        else EdgeDataFormat.EDGE_LIST
    )
    edge_weight_type = problem.edge_weight_type

    # edge weight format
    edge_weight_format = problem.edge_weight_format
    if edge_weight_type == EdgeWeightType.UNIFORM_RANDOM:
        edge_weight_format = EdgeWeightFormat.FUNCTION
        weights = uniform_random_cost(list(problem.get_edges()))
    elif (
        not edge_weight_format
        and edge_weight_type in EdgeWeightType.__members__
        and edge_weight_type != EdgeWeightType.EXPLICIT
    ):
        edge_weight_format = EdgeWeightFormat.FUNCTION
        weights = {(i, j): problem.get_weight(i, j) for i, j in problem.get_edges()}
    elif not edge_weight_format and edge_weight_type == EdgeWeightType.EXPLICIT:
        raise ValueError(
            "Edge weight type is set to EXPLICIT but no edge weight format is given"
        )
    elif not edge_weight_format:
        raise ValueError(
            "Edge weight format in StandardProblem is not set - cannot assign edge weights."
        )
    else:
        weights = {(i, j): problem.get_weight(i, j) for i, j in problem.get_edges()}

    node_coord_type = (
        problem.node_coord_type
        if problem.node_coord_type
        else NodeCoordType.NO_COORDS
    )
    node_coords = None
    if node_coord_type == NodeCoordType.TWOD_COORDS:
        node_coords = {i: problem.node_coords.get(i) for i in problem.get_nodes()}
    elif node_coord_type == NodeCoordType.THREED_COORDS:
        raise NotImplementedError("3D coords not yet supported")

    return cls(
        capacity=problem.capacity,
        comment=problem.comment if problem.comment else "",
        demands=problem.demands,
        depots=problem.depots,
        dimension=problem.dimension,
        display_data=problem.display_data,
        display_data_type=display_data_type,
        edge_data=list(problem.get_edges()),
        edge_data_format=edge_data_format,
        edge_weights=weights,
        edge_weight_format=edge_weight_format,
        edge_weight_type=edge_weight_type,
        fixed_edges=problem.fixed_edges,
        name=problem.name,
        node_coords=node_coords,
        node_coord_type=node_coord_type,
        problem_type=problem.type,
        tours=problem.tours,
    )

from_yaml(yaml_filepath) classmethod

Load from a yaml file

Source code in tspwplib/problem.py

@classmethod
def from_yaml(cls, yaml_filepath: Path):
    """Load from a yaml file"""
    with open(yaml_filepath, "r", encoding="utf-8") as yaml_file:
        yaml_dict = yaml.load(yaml_file, Loader=yaml.FullLoader)
    edge_data = edge_list_from_adjacency_list(yaml_dict.pop("edge_data"))
    edge_weights = edge_dict_from_adjacency_weights(yaml_dict.pop("edge_weights"))
    fixed_edges = edge_list_from_adjacency_list(yaml_dict.pop("fixed_edges"))
    return cls(
        **yaml_dict,
        edge_data=edge_data,
        edge_weights=edge_weights,
        fixed_edges=fixed_edges,
    )

get_graph()

Get a networkx graph

Returns:

Type	Description
Graph	Undirected networkx graph with node attributes such as 'is_depot'
Graph	and edge attributes such as 'weight' and 'is_fixed'.

Source code in tspwplib/problem.py

def get_graph(self) -> nx.Graph:
    """Get a networkx graph

    Returns:
        Undirected networkx graph with node attributes such as 'is_depot'
        and edge attributes such as 'weight' and 'is_fixed'.
    """
    G = nx.Graph()
    self.__set_graph_attributes(G)
    self.__add_edges(G)
    self.__set_edge_attributes(G)
    self.__set_node_attributes(G)
    return G

get_weighted_full_matrix()

Get a square weighted adjacency matrix, sorted by node ID

Source code in tspwplib/problem.py

def get_weighted_full_matrix(self) -> npt.NDArray[np.int_]:
    """Get a square weighted adjacency matrix, sorted by node ID"""
    # create a graph
    G = self.get_graph()
    # sort the node list (ascending)
    sorted_node_list = list(G.nodes())
    sorted_node_list.sort()
    # then get the weighted adjacency matrix
    return nx.to_numpy_array(
        G, nodelist=sorted_node_list, weight="weight", dtype=int
    )

to_tsplib95()

Convert to a tsplib95 standard model

Source code in tspwplib/problem.py

@no_type_check
def to_tsplib95(self) -> tsplib95.models.StandardProblem:
    """Convert to a tsplib95 standard model"""
    weights = None
    if self.edge_weight_type == EdgeWeightType.EXPLICIT:
        weights = self.get_weighted_full_matrix()

    optional_kwargs = {}
    if not self.capacity is None:
        optional_kwargs["capacity"] = self.capacity
    if self.display_data:
        optional_kwargs["display_data"] = self.display_data
    if self.fixed_edges:
        optional_kwargs["fixed_edges"] = self.fixed_edges
    if self.tours:
        optional_kwargs["tours"] = self.tours
    return tsplib95.models.StandardProblem(
        comment=self.comment,
        demands=self.demands,
        depots=self.depots,
        dimension=self.dimension,
        display_data_type=self.display_data_type,
        edge_data=self.edge_data,
        edge_data_format=self.edge_data_format,
        edge_weights=weights,
        edge_weight_format=self.edge_weight_format,
        edge_weight_type=self.edge_weight_type,
        name=self.name,
        node_coords=self.node_coords,
        node_coord_type=self.node_coord_type,
        type=self.problem_type,
        **optional_kwargs,
    )

to_yaml(yaml_filepath)

Dump the TSP to a YAML file

Source code in tspwplib/problem.py

def to_yaml(self, yaml_filepath: Path) -> None:
    """Dump the TSP to a YAML file"""
    yaml_dict = dict(
        comment=self.comment,
        demands=self.demands,
        depots=self.depots,
        dimension=self.dimension,
        display_data_type=self.display_data_type.value,
        edge_data=adjacency_list_from_edge_list(self.edge_data),
        edge_data_format=self.edge_data_format.value,
        edge_weight_format=self.edge_weight_format.value,
        edge_weight_type=self.edge_weight_type.value,
        fixed_edges=adjacency_list_from_edge_list(self.fixed_edges),
        name=self.name,
        node_coords=self.node_coords,
        node_coord_type=self.node_coord_type.value,
        problem_type=self.problem_type,
        tours=self.tours,
    )
    if self.edge_weights:
        weights: AdjWeights = adjacency_weights_from_edge_dict(self.edge_weights)
        yaml_dict["edge_weights"] = weights  # type: ignore
    else:
        yaml_dict["edge_weights"] = None
    with open(yaml_filepath, "w", encoding="utf-8") as yaml_file:
        yaml.dump(yaml_dict, yaml_file)

EdgeFunctionName

Bases: StrEnumMixin, str, Enum

Valid names of functions on edges

Source code in tspwplib/types.py

class EdgeFunctionName(StrEnumMixin, str, Enum):
    """Valid names of functions on edges"""

    cost = "cost"
    weight = "weight"

EdgeNotFoundException

Bases: NetworkXException

An edge could not be found in the graph

Source code in tspwplib/exception.py

class EdgeNotFoundException(ex.NetworkXException):
    """An edge could not be found in the graph"""

EdgeWeightType

Bases: StrEnumMixin, str, Enum

Specifies how the edge weights (or distances) are given

Source code in tspwplib/types.py

class EdgeWeightType(StrEnumMixin, str, Enum):
    """Specifies how the edge weights (or distances) are given"""

    EXPLICIT = "EXPLICIT"  # Weights are listed explicitly in the corresponding section
    EUC_2D = "EUC_2D"  # Weights are Euclidean distances in 2-D
    EUC_3D = "EUC_3D"  # Weights are Euclidean distances in 3-D
    MAX_2D = "MAX_2D"  # Weights are maximum distances in 2-D
    MAX_3D = "MAX_3D"  # Weights are maximum distances in 3-D
    MAN_2D = "MAN_2D"  # Weights are Manhattan distances in 2-D
    MAN_3D = "MAN_3D"  # Weights are Manhattan distances in 3-D
    CEIL_2D = "CEIL_2D"  # Weights are Euclidean distances in 2-D rounded up
    GEO = "GEO"  # Weights are geographical distances
    ATT = "ATT"  # Special distance function for problems att48 and att532
    XRAY1 = (
        "XRAY1"  # Special distance function for crystallography problems (Version 1)
    )
    XRAY2 = (
        "XRAY2"  # Special distance function for crystallography problems (Version 2)
    )
    SPECIAL = "SPECIAL"  # There is a special distance function documented elsewhere
    UNIFORM_RANDOM = "UNIFORM_RANDOM"
    MST = "MST"
    SEMI_MST = "SEMI_MST"

EdgesNotAdjacentException

Bases: AmbiguousSolution

An edge list has been given non-adjacent edges which is ambiguous

Source code in tspwplib/exception.py

class EdgesNotAdjacentException(ex.AmbiguousSolution):
    """An edge list has been given non-adjacent edges which is ambiguous"""

Generation

Bases: StrEnumMixin, str, Enum

Generations of TSPwP problem instances

Source code in tspwplib/types.py

class Generation(StrEnumMixin, str, Enum):
    """Generations of TSPwP problem instances"""

    gen1 = "gen1"
    gen2 = "gen2"
    gen3 = "gen3"

GraphName

Bases: StrEnumMixin, str, Enum

Names of TSPlib instances

Source code in tspwplib/types.py

class GraphName(StrEnumMixin, str, Enum):
    """Names of TSPlib instances"""

    a280 = "a280"
    ali535 = "ali535"
    att48 = "att48"
    att532 = "att532"
    bayg29 = "bayg29"
    bays29 = "bays29"
    berlin52 = "berlin52"
    bier127 = "bier127"
    brazil58 = "brazil58"
    brd14051 = "brd14051"
    brg180 = "brg180"
    burma14 = "burma14"
    ch130 = "ch130"
    ch150 = "ch150"
    d198 = "d198"
    d493 = "d493"
    d657 = "d657"
    d1291 = "d1291"
    d1655 = "d1655"
    d2103 = "d2103"
    d15112 = "d15112"
    d18512 = "d18512"
    dantzig42 = "dantzig42"
    dsj1000 = "dsj1000"
    eil51 = "eil51"
    eil76 = "eil76"
    eil101 = "eil101"
    fl417 = "fl417"
    fl1400 = "fl1400"
    fl1577 = "fl1577"
    fl3795 = "fl3795"
    fnl4461 = "fnl4461"
    fri26 = "fri26"
    gil262 = "gil262"
    gr17 = "gr17"
    gr21 = "gr21"
    gr24 = "gr24"
    gr48 = "gr48"
    gr96 = "gr96"
    gr120 = "gr120"
    gr137 = "gr137"
    gr202 = "gr202"
    gr229 = "gr229"
    gr431 = "gr431"
    gr666 = "gr666"
    hk48 = "hk48"
    kroA100 = "kroA100"
    kroB100 = "kroB100"
    kroC100 = "kroC100"
    kroD100 = "kroD100"
    kroE100 = "kroE100"
    kroA150 = "kroA150"
    kroB150 = "kroB150"
    kroA200 = "kroA200"
    kroB200 = "kroB200"
    lin105 = "lin105"
    lin318 = "lin318"
    linhp318 = "linhp318"
    nrw1379 = "nrw1379"
    p654 = "p654"
    pa561 = "pa561"
    pcb442 = "pcb442"
    pcb1173 = "pcb1173"
    pcb3038 = "pcb3038"
    pla7397 = "pla7397"
    pla33810 = "pla33810"
    pla85900 = "pla85900"
    pr76 = "pr76"
    pr107 = "pr107"
    pr124 = "pr124"
    pr136 = "pr136"
    pr144 = "pr144"
    pr152 = "pr152"
    pr226 = "pr226"
    pr264 = "pr264"
    pr299 = "pr299"
    pr439 = "pr439"
    pr1002 = "pr1002"
    pr2392 = "pr2392"
    rat99 = "rat99"
    rat195 = "rat195"
    rat575 = "rat575"
    rat783 = "rat783"
    rd100 = "rd100"
    rd400 = "rd400"
    rl1304 = "rl1304"
    rl1323 = "rl1323"
    rl1889 = "rl1889"
    rl5915 = "rl5915"
    rl5934 = "rl5934"
    rl11849 = "rl11849"
    si175 = "si175"
    si535 = "si535"
    si1032 = "si1032"
    st70 = "st70"
    swiss42 = "swiss42"
    ts225 = "ts225"
    tsp225 = "tsp225"
    u159 = "u159"
    u574 = "u574"
    u724 = "u724"
    u1060 = "u1060"
    u1432 = "u1432"
    u1817 = "u1817"
    u2152 = "u2152"
    u2319 = "u2319"
    ulysses16 = "ulysses16"
    ulysses22 = "ulysses22"
    usa13509 = "usa13509"
    vm1084 = "vm1084"
    vm1748 = "vm1748"

LondonaqGraphName

Bases: StrEnumMixin, str, Enum

Names of graphs with London air quality forecasts

Source code in tspwplib/types.py

class LondonaqGraphName(StrEnumMixin, str, Enum):
    """Names of graphs with London air quality forecasts"""

    laqkxA = "laqkxA"
    laqtinyA = "laqtinyA"
    laqbbA = "laqbbA"
    laqidA = "laqidA"
    laqwsA = "laqwsA"

LondonaqLocation

Bases: StrEnumMixin, str, Enum

Names of locations that the London air quality graph is centered upon

Source code in tspwplib/types.py

class LondonaqLocation(StrEnumMixin, str, Enum):
    """Names of locations that the London air quality graph is centered upon"""

    bb = "Big Ben"
    kx = "King's Cross"
    tiny = "Camden Town"
    id = "Isle of Dogs"
    ws = "Wembley Stadium"

LondonaqLocationShort

Bases: StrEnumMixin, str, Enum

Short codes for londonaq locations

Source code in tspwplib/types.py

class LondonaqLocationShort(StrEnumMixin, str, Enum):
    """Short codes for londonaq locations"""

    bb = "bb"
    kx = "kx"
    tiny = "tiny"
    id = "id"
    ws = "ws"

LondonaqTimestamp

Bases: Enum

Timestamps of the forecasts for London air quality forecasts

Source code in tspwplib/types.py

class LondonaqTimestamp(Enum):
    """Timestamps of the forecasts for London air quality forecasts"""

    A = datetime.datetime(2021, 10, 13, 8, 0, 0, tzinfo=datetime.UTC)  # 9am BST

LondonaqTimestampId

Bases: StrEnumMixin, str, Enum

Timestamp IDs for CLI

Source code in tspwplib/types.py

class LondonaqTimestampId(StrEnumMixin, str, Enum):
    """Timestamp IDs for CLI"""

    A = "A"

NotSimpleCycleException

Bases: NotSimpleException

The walk was not a simple cycle

Source code in tspwplib/exception.py

class NotSimpleCycleException(NotSimpleException):
    """The walk was not a simple cycle"""

NotSimpleException

Bases: NetworkXException

A path, cycle or walk is not simple

Source code in tspwplib/exception.py

class NotSimpleException(ex.NetworkXException):
    """A path, cycle or walk is not simple"""

NotSimplePathException

Bases: NotSimpleException

The walk was not a simple path

Source code in tspwplib/exception.py

class NotSimplePathException(NotSimpleException):
    """The walk was not a simple path"""

OptimalSolutionTSP

Bases: IntEnum

Value of optimal solutions to TSP instances

Source code in tspwplib/types.py

class OptimalSolutionTSP(IntEnum):
    """Value of optimal solutions to TSP instances"""

    a280 = 2579
    ali535 = 202339
    att48 = 10628
    att532 = 27686
    bayg29 = 1610
    bays29 = 2020
    berlin52 = 7542
    bier127 = 118282
    brazil58 = 25395
    brd14051 = 469385
    brg180 = 1950
    burma14 = 3323
    ch130 = 6110
    ch150 = 6528
    d198 = 15780
    d493 = 35002
    d657 = 48912
    d1291 = 50801
    d1655 = 62128
    d2103 = 80450
    d15112 = 1573084
    d18512 = 645238
    dantzig42 = 699
    dsj1000 = 18659688  # (EUC_2D)
    # dsj1000 = 18660188 # (CEIL_2D)    # NOTE breaks keys
    eil51 = 426
    eil76 = 538
    eil101 = 629
    fl417 = 11861
    fl1400 = 20127
    fl1577 = 22249
    fl3795 = 28772
    fnl4461 = 182566
    fri26 = 937
    gil262 = 2378
    gr17 = 2085
    gr21 = 2707
    gr24 = 1272
    gr48 = 5046
    gr96 = 55209
    gr120 = 6942
    gr137 = 69853
    gr202 = 40160
    gr229 = 134602
    gr431 = 171414
    gr666 = 294358
    hk48 = 11461
    kroA100 = 21282
    kroB100 = 22141
    kroC100 = 20749
    kroD100 = 21294
    kroE100 = 22068
    kroA150 = 26524
    kroB150 = 26130
    kroA200 = 29368
    kroB200 = 29437
    lin105 = 14379
    lin318 = 42029
    linhp318 = 41345
    nrw1379 = 56638
    p654 = 34643
    pa561 = 2763
    pcb442 = 50778
    pcb1173 = 56892
    pcb3038 = 137694
    pla7397 = 23260728
    pla33810 = 66048945
    pla85900 = 142382641
    pr76 = 108159
    pr107 = 44303
    pr124 = 59030
    pr136 = 96772
    pr144 = 58537
    pr152 = 73682
    pr226 = 80369
    pr264 = 49135
    pr299 = 48191
    pr439 = 107217
    pr1002 = 259045
    pr2392 = 378032
    rat99 = 1211
    rat195 = 2323
    rat575 = 6773
    rat783 = 8806
    rd100 = 7910
    rd400 = 15281
    rl1304 = 252948
    rl1323 = 270199
    rl1889 = 316536
    rl5915 = 565530
    rl5934 = 556045
    rl11849 = 923288
    si175 = 21407
    si535 = 48450
    si1032 = 92650
    st70 = 675
    swiss42 = 1273
    ts225 = 126643
    tsp225 = 3916
    u159 = 42080
    u574 = 36905
    u724 = 41910
    u1060 = 224094
    u1432 = 152970
    u1817 = 57201
    u2152 = 64253
    u2319 = 234256
    ulysses16 = 6859
    ulysses22 = 7013
    usa13509 = 19982859
    vm1084 = 239297
    vm1748 = 336556

ProfitsProblem

Bases: StandardProblem

TSP with Profits Problem

Source code in tspwplib/problem.py

class ProfitsProblem(tsplib95.models.StandardProblem):
    """TSP with Profits Problem"""

    # overwrite edge data to fix bugs
    edge_data = TempEdgeDataField("EDGE_DATA")
    # Maximum distance of the total route in a OP.
    cost_limit = tsplib95.fields.IntegerField("COST_LIMIT")
    # The scores of the nodes of a OP are given in the form (per line)
    node_score = tsplib95.fields.DemandsField("NODE_SCORE_SECTION")
    # The optimal solution to the TSP
    tspsol = tsplib95.fields.IntegerField("TSPSOL")

    def __init__(self, special=None, **data):
        super().__init__(special=special, **data)

    def __set_edge_attributes(self, graph: nx.Graph, names: VertexLookup) -> None:
        """Set edge attributes"""
        # add every edge with some associated metadata
        for edge in self.get_edges():
            cost: int = self.get_weight(edge[0], edge[1])
            # pylint: disable=unsupported-membership-test
            # is_fixed: bool = (u, v) in self.fixed_edges
            graph.add_edge(names[edge[0]], names[edge[1]], cost=cost)

    def __set_graph_attributes(self, graph: nx.Graph) -> None:
        """Set attributes of the graph such as the name"""
        graph.graph["name"] = self.name
        graph.graph["comment"] = self.comment
        graph.graph["type"] = self.type
        graph.graph["dimension"] = self.dimension
        graph.graph["capacity"] = self.capacity
        graph.graph["root"] = self.get_root_vertex()

    def __set_node_attributes(self, graph: nx.Graph, names: VertexLookup) -> None:
        """Add node attributes"""
        node_score = self.get_node_score()
        for vertex in list(self.get_nodes()):
            # pylint: disable=unsupported-membership-test,no-member
            is_depot = vertex in self.depots
            graph.add_node(
                names[vertex],
                prize=node_score[vertex],
                is_depot=is_depot,
            )
            demand: int = self.demands.get(vertex)
            display = self.display_data.get(vertex)
            if not demand is None:
                graph[vertex]["demand"] = demand
            if not display is None:
                graph[vertex]["display"] = display
            if self.node_coords:
                coord = self.node_coords.get(vertex)
                graph.nodes[names[vertex]]["x"] = coord[0]
                graph.nodes[names[vertex]]["y"] = coord[1]

    def get_weight(self, start: int, end: int) -> int:
        """Return the weight of the edge between start and end.

        This method provides a single way to obtain edge weights regardless of
        whether the problem uses an explicit matrix or a distance function.

        Args:
            start: starting node index
            end: ending node index

        Returns:
            Weight of edge

        Notes:
            Over-rides euclidean weight to ensure the costs are metric
        """
        if self.edge_weight_type == EdgeWeightType.EUC_2D:
            return tsplib95.distances.euclidean(
                self.node_coords.get(start), self.node_coords.get(end), round=math.ceil
            )
        return super().get_weight(start, end)

    def get_graph(self, normalize: bool = False) -> nx.Graph:
        """Return a networkx graph instance representing the problem.

        Args:
            normalize: rename nodes to be zero-indexed
        """
        # directed graphs are fundamentally different
        graph: nx.Graph = nx.Graph() if self.is_symmetric() else nx.DiGraph()

        # set up a map from original node name to new node name
        nodes: List[Vertex] = list(self.get_nodes())
        if normalize:
            names = {n: i for i, n in enumerate(nodes)}
        else:
            names = {n: n for n in nodes}

        self.__set_node_attributes(graph, names)
        self.__set_edge_attributes(graph, names)

        # add basic graph metadata
        self.__set_graph_attributes(graph)
        return graph

    def get_total_prize(self) -> int:
        """Get the sum of prize over all vertices

        Returns:
            Total prize
        """
        # pylint: disable=no-member
        return sum([value for _, value in self.get_node_score().items()])

    def get_quota(self, alpha: int) -> int:
        """The quota is alpha percent of the total prize

        Args:
            alpha: Percent of the total prize

        Returns:
            quota
        """
        return get_quota_from_alpha(alpha, self.get_total_prize())

    def number_of_nodes(self) -> int:
        """Get the number of nodes in the problem

        Returns:
            Number of nodes in graph
        """
        return len(list(self.get_nodes()))

    def get_cost_limit(self) -> int:
        """Get the cost limit for a TSP with Profits problem

        Returns:
            Cost limit
        """
        return self.cost_limit

    def get_node_score(self) -> VertexLookup:
        """Get the node scores (profits)

        Returns:
            Mapping from node to node score (profit)
        """
        score_dict: VertexLookup = {}
        for key, value in self.node_score.items():  # pylint: disable=no-member
            score_dict[key] = value
        return score_dict

    def get_tsp_optimal_value(self) -> int:
        """Get the value of the optimal solution to TSP

        Returns:
            TSP optimal value
        """
        return self.tspsol

    def get_root_vertex(self, normalize: bool = False) -> Vertex:
        """Get the root vertex

        Args:
            normalize: If true, vertices start at index 0

        Returns:
            The first depot in the list

        Raises:
            ValueError: If the list of depots is empty
        """
        nodes: List[Vertex] = list(self.get_nodes())
        if normalize:
            names = {n: i for i, n in enumerate(nodes)}
        else:
            names = {n: n for n in nodes}
        try:
            # pylint: disable=unsubscriptable-object
            return names[self.depots[0]]
        except KeyError as key_error:
            raise ValueError("The list of depots is empty") from key_error

    # pylint: disable=arguments-differ
    def get_edges(self, normalize: bool = False) -> EdgeList:
        """Get a list of edges in the graph

        Args:
            normalize: If true use the normalized vertex ids

        Returns:
            List of edges in the graph
        """
        if normalize:
            raise NotImplementedError("Normalizing edges not yet implemented")
        return list(super().get_edges())

__set_edge_attributes(graph, names)

Set edge attributes

Source code in tspwplib/problem.py

def __set_edge_attributes(self, graph: nx.Graph, names: VertexLookup) -> None:
    """Set edge attributes"""
    # add every edge with some associated metadata
    for edge in self.get_edges():
        cost: int = self.get_weight(edge[0], edge[1])
        # pylint: disable=unsupported-membership-test
        # is_fixed: bool = (u, v) in self.fixed_edges
        graph.add_edge(names[edge[0]], names[edge[1]], cost=cost)

__set_graph_attributes(graph)

Set attributes of the graph such as the name

Source code in tspwplib/problem.py

def __set_graph_attributes(self, graph: nx.Graph) -> None:
    """Set attributes of the graph such as the name"""
    graph.graph["name"] = self.name
    graph.graph["comment"] = self.comment
    graph.graph["type"] = self.type
    graph.graph["dimension"] = self.dimension
    graph.graph["capacity"] = self.capacity
    graph.graph["root"] = self.get_root_vertex()

__set_node_attributes(graph, names)

Add node attributes

Source code in tspwplib/problem.py

def __set_node_attributes(self, graph: nx.Graph, names: VertexLookup) -> None:
    """Add node attributes"""
    node_score = self.get_node_score()
    for vertex in list(self.get_nodes()):
        # pylint: disable=unsupported-membership-test,no-member
        is_depot = vertex in self.depots
        graph.add_node(
            names[vertex],
            prize=node_score[vertex],
            is_depot=is_depot,
        )
        demand: int = self.demands.get(vertex)
        display = self.display_data.get(vertex)
        if not demand is None:
            graph[vertex]["demand"] = demand
        if not display is None:
            graph[vertex]["display"] = display
        if self.node_coords:
            coord = self.node_coords.get(vertex)
            graph.nodes[names[vertex]]["x"] = coord[0]
            graph.nodes[names[vertex]]["y"] = coord[1]

get_cost_limit()

Get the cost limit for a TSP with Profits problem

Returns:

Type	Description
int	Cost limit

Source code in tspwplib/problem.py

def get_cost_limit(self) -> int:
    """Get the cost limit for a TSP with Profits problem

    Returns:
        Cost limit
    """
    return self.cost_limit

get_edges(normalize=False)

Get a list of edges in the graph

Parameters:

Name	Type	Description	Default
normalize	bool	If true use the normalized vertex ids	False

Returns:

Type	Description
EdgeList	List of edges in the graph

Source code in tspwplib/problem.py

def get_edges(self, normalize: bool = False) -> EdgeList:
    """Get a list of edges in the graph

    Args:
        normalize: If true use the normalized vertex ids

    Returns:
        List of edges in the graph
    """
    if normalize:
        raise NotImplementedError("Normalizing edges not yet implemented")
    return list(super().get_edges())

get_graph(normalize=False)

Return a networkx graph instance representing the problem.

Parameters:

Name	Type	Description	Default
normalize	bool	rename nodes to be zero-indexed	False

Source code in tspwplib/problem.py

def get_graph(self, normalize: bool = False) -> nx.Graph:
    """Return a networkx graph instance representing the problem.

    Args:
        normalize: rename nodes to be zero-indexed
    """
    # directed graphs are fundamentally different
    graph: nx.Graph = nx.Graph() if self.is_symmetric() else nx.DiGraph()

    # set up a map from original node name to new node name
    nodes: List[Vertex] = list(self.get_nodes())
    if normalize:
        names = {n: i for i, n in enumerate(nodes)}
    else:
        names = {n: n for n in nodes}

    self.__set_node_attributes(graph, names)
    self.__set_edge_attributes(graph, names)

    # add basic graph metadata
    self.__set_graph_attributes(graph)
    return graph

get_node_score()

Get the node scores (profits)

Returns:

Type	Description
VertexLookup	Mapping from node to node score (profit)

Source code in tspwplib/problem.py

def get_node_score(self) -> VertexLookup:
    """Get the node scores (profits)

    Returns:
        Mapping from node to node score (profit)
    """
    score_dict: VertexLookup = {}
    for key, value in self.node_score.items():  # pylint: disable=no-member
        score_dict[key] = value
    return score_dict

get_quota(alpha)

The quota is alpha percent of the total prize

Parameters:

Name	Type	Description	Default
alpha	int	Percent of the total prize	required

Returns:

Type	Description
int	quota

Source code in tspwplib/problem.py

def get_quota(self, alpha: int) -> int:
    """The quota is alpha percent of the total prize

    Args:
        alpha: Percent of the total prize

    Returns:
        quota
    """
    return get_quota_from_alpha(alpha, self.get_total_prize())

get_root_vertex(normalize=False)

Get the root vertex

Parameters:

Name	Type	Description	Default
normalize	bool	If true, vertices start at index 0	False

Returns:

Type	Description
Vertex	The first depot in the list

Raises:

Type	Description
ValueError	If the list of depots is empty

Source code in tspwplib/problem.py

def get_root_vertex(self, normalize: bool = False) -> Vertex:
    """Get the root vertex

    Args:
        normalize: If true, vertices start at index 0

    Returns:
        The first depot in the list

    Raises:
        ValueError: If the list of depots is empty
    """
    nodes: List[Vertex] = list(self.get_nodes())
    if normalize:
        names = {n: i for i, n in enumerate(nodes)}
    else:
        names = {n: n for n in nodes}
    try:
        # pylint: disable=unsubscriptable-object
        return names[self.depots[0]]
    except KeyError as key_error:
        raise ValueError("The list of depots is empty") from key_error

get_total_prize()

Get the sum of prize over all vertices

Returns:

Type	Description
int	Total prize

Source code in tspwplib/problem.py

def get_total_prize(self) -> int:
    """Get the sum of prize over all vertices

    Returns:
        Total prize
    """
    # pylint: disable=no-member
    return sum([value for _, value in self.get_node_score().items()])

get_tsp_optimal_value()

Get the value of the optimal solution to TSP

Returns:

Type	Description
int	TSP optimal value

Source code in tspwplib/problem.py

def get_tsp_optimal_value(self) -> int:
    """Get the value of the optimal solution to TSP

    Returns:
        TSP optimal value
    """
    return self.tspsol

get_weight(start, end)

Return the weight of the edge between start and end.

This method provides a single way to obtain edge weights regardless of whether the problem uses an explicit matrix or a distance function.

Parameters:

Name	Type	Description	Default
start	int	starting node index	required
end	int	ending node index	required

Returns:

Type	Description
int	Weight of edge

Notes

Over-rides euclidean weight to ensure the costs are metric

Source code in tspwplib/problem.py

def get_weight(self, start: int, end: int) -> int:
    """Return the weight of the edge between start and end.

    This method provides a single way to obtain edge weights regardless of
    whether the problem uses an explicit matrix or a distance function.

    Args:
        start: starting node index
        end: ending node index

    Returns:
        Weight of edge

    Notes:
        Over-rides euclidean weight to ensure the costs are metric
    """
    if self.edge_weight_type == EdgeWeightType.EUC_2D:
        return tsplib95.distances.euclidean(
            self.node_coords.get(start), self.node_coords.get(end), round=math.ceil
        )
    return super().get_weight(start, end)

number_of_nodes()

Get the number of nodes in the problem

Returns:

Type	Description
int	Number of nodes in graph

Source code in tspwplib/problem.py

def number_of_nodes(self) -> int:
    """Get the number of nodes in the problem

    Returns:
        Number of nodes in graph
    """
    return len(list(self.get_nodes()))

VertexFunctionName

Bases: StrEnumMixin, str, Enum

Valid names of functions on vertices

Source code in tspwplib/types.py

class VertexFunctionName(StrEnumMixin, str, Enum):
    """Valid names of functions on vertices"""

    demand = "demand"
    prize = "prize"

asymmetric_from_directed(G)

Create asymmetric directed graph from directed graph

Split every node u two nodes u1 and u2. We add a directed arc between u1 and u2. Any previous inward edge v->u is now v->u1 and any outward edge from u is now u2->v.

Parameters:

Name	Type	Description	Default
G	DiGraph	Directed graph	required

Returns:

Type	Description
DiGraph	Directed asymmetric graph

Source code in tspwplib/converter.py

def asymmetric_from_directed(G: nx.DiGraph) -> nx.DiGraph:
    """Create asymmetric directed graph from directed graph

    Split every node u two nodes u1 and u2.
    We add a directed arc between u1 and u2.
    Any previous inward edge v->u is now v->u1 and any outward edge from u is now u2->v.

    Args:
        G: Directed graph

    Returns:
        Directed asymmetric graph
    """
    asymmetric_graph = nx.DiGraph()
    nodes_for_adding: List[Tuple[Vertex, Dict]] = []
    edges_for_adding: List[Tuple[Vertex, Vertex, Dict]] = []
    # deepcopy when not a view
    asymmetric_graph.graph.update(deepcopy(G.graph))

    # find the id of the biggest vertex
    biggest_vertex = biggest_vertex_id_from_graph(G)

    for vertex, data in G.nodes(data=True):
        # split the vertex into two
        head = split_head(biggest_vertex, vertex)
        tail = split_tail(biggest_vertex, vertex)

        # the data is copied to both vertices
        tail_data = data.copy()
        head_data = data.copy()

        # split the value of the prize
        prize: int = data.get(VertexFunctionName.prize, 0)
        tail_data[VertexFunctionName.prize] = tail_prize(prize)
        head_data[VertexFunctionName.prize] = head_prize(prize)

        # add vertex to asymmetric graph with new data
        nodes_for_adding.append((head, head_data))
        nodes_for_adding.append((tail, tail_data))

        # add zero-cost edge from tail to head
        edge = (tail, head, {EdgeFunctionName.cost.value: 0})
        edges_for_adding.append(edge)

    for u, v, edge_data in G.edges(data=True):
        # add edge from head of u to tail of v with data
        u_head = split_head(biggest_vertex, u)
        v_tail = split_tail(biggest_vertex, v)
        edge_uv = (u_head, v_tail, edge_data)
        edges_for_adding.append(edge_uv)

    # add nodes and edges then return graph
    asymmetric_graph.add_nodes_from(nodes_for_adding)
    asymmetric_graph.add_edges_from(edges_for_adding)
    return asymmetric_graph

asymmetric_from_undirected(G)

Create asymmetric directed graph from undirected graph

Parameters:

Name	Type	Description	Default
G	Graph	Undirected graph	required

Returns:

Type	Description
DiGraph	Directed asymmetric graph

Source code in tspwplib/converter.py

def asymmetric_from_undirected(G: nx.Graph) -> nx.DiGraph:
    """Create asymmetric directed graph from undirected graph

    Args:
        G: Undirected graph

    Returns:
        Directed asymmetric graph
    """
    directed_graph = G.to_directed()
    return asymmetric_from_directed(directed_graph)

biggest_vertex_id_from_graph(G)

Return the vertex with the largest integer id

Parameters:

Name	Type	Description	Default
G	Graph	Graph	required

Returns:

Type	Description
Vertex	Vertex with biggest id

Source code in tspwplib/converter.py

def biggest_vertex_id_from_graph(G: nx.Graph) -> Vertex:
    """Return the vertex with the largest integer id

    Args:
        G: Graph

    Returns:
        Vertex with biggest id
    """
    return max(G)

build_path_to_londonaq_instance(londonaq_root, name)

Build a filepath to a londonaq instance

Parameters:

Name	Type	Description	Default
londonaq_root	Path	Root directory of the londonaq dataset	required
name	LondonaqGraphName	Londonaq graph name	required

Returns:

Type	Description
Path	Filepath to the londonaq txt

Source code in tspwplib/utils.py

def build_path_to_londonaq_instance(
    londonaq_root: Path,
    name: LondonaqGraphName,
) -> Path:
    """Build a filepath to a londonaq instance

    Args:
        londonaq_root: Root directory of the londonaq dataset
        name: Londonaq graph name

    Returns:
        Filepath to the londonaq txt
    """
    return londonaq_root / name.value / f"{name.value}.txt"

build_path_to_londonaq_yaml(londonaq_root, name)

Build a filepath to the londonaq yaml file

Parameters:

Name	Type	Description	Default
londonaq_root	Path	Root directory of the londonaq dataset	required
name	LondonaqGraphName	Londonaq graph name	required

Returns:

Type	Description
Path	Filepath to the londonaq yaml file

Source code in tspwplib/utils.py

def build_path_to_londonaq_yaml(londonaq_root: Path, name: LondonaqGraphName) -> Path:
    """Build a filepath to the londonaq yaml file

    Args:
        londonaq_root: Root directory of the londonaq dataset
        name: Londonaq graph name

    Returns:
        Filepath to the londonaq yaml file
    """
    return londonaq_root / name.value / f"{name.value}.yaml"

build_path_to_oplib_instance(oplib_root, generation, name, alpha=Alpha.fifty.value)

Build a filepath to a oplib instance

Parameters:

Name	Type	Description	Default
oplib_root	Path	The directory of the clones oplib	required
generation	Generation	Generation of OPLib instance	required
name	GraphName	Graph instance name	required
alpha	int	Percent of the total cost to set the cost limit to. Not useful for instances of Prize-collecting TSPs. Default is 50. Note if you change to a different value, make sure the file exists	value

Returns:

Type	Description
Path	Path to the OPLib instance

Source code in tspwplib/utils.py

def build_path_to_oplib_instance(
    oplib_root: Path,
    generation: Generation,
    name: GraphName,
    alpha: int = Alpha.fifty.value,
) -> Path:
    """Build a filepath to a oplib instance

    Args:
        oplib_root: The directory of the clones oplib
        generation: Generation of OPLib instance
        name: Graph instance name
        alpha: Percent of the total cost to set the cost limit to.
            Not useful for instances of Prize-collecting TSPs.
            Default is 50.
            Note if you change to a different value, make sure the file exists

    Returns:
        Path to the OPLib instance
    """
    filename: str = name + "-" + generation.value + "-" + str(alpha) + ".oplib"
    return oplib_root / "instances" / generation.value / filename

build_path_to_tsplib_instance(tsplib_root, name)

Build a filepath to a tsplib instance

Parameters:

Name	Type	Description	Default
tsplib_root	Path	Directory containing TSP txt instances	required
name	GraphName	Name of the instance	required

Returns:

Type	Description
Path	Filepath to the TSP instance

Source code in tspwplib/utils.py

def build_path_to_tsplib_instance(tsplib_root: Path, name: GraphName) -> Path:
    """Build a filepath to a tsplib instance

    Args:
        tsplib_root: Directory containing TSP txt instances
        name: Name of the instance

    Returns:
        Filepath to the TSP instance
    """
    filename = name.value + ".tsp"
    return tsplib_root / filename

edge_list_from_walk(walk)

Get ordered list of edges from an ordered list of vertices

Parameters:

Name	Type	Description	Default
walk	VertexList	Ordered list of vertices that represent a walk in the graph	required

Returns:

Type	Description
EdgeList	List of edges in the same order as the walk

Source code in tspwplib/walk.py

def edge_list_from_walk(walk: VertexList) -> EdgeList:
    """Get ordered list of edges from an ordered list of vertices

    Args:
        walk: Ordered list of vertices that represent a walk in the graph

    Returns:
        List of edges in the same order as the walk
    """
    edge_list: EdgeList = []
    if len(walk) <= 1:
        return edge_list
    for i in range(len(walk) - 1):
        vertex = walk[i]
        next_vertex = walk[i + 1]
        edge_list.append((vertex, next_vertex))
    return edge_list

get_original_from_split_vertex(biggest_vertex, split_vertex)

Return the original vertex id given a split vertex (may be head or tail)

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
split_vertex	Vertex	A split vertex in asymmetric graph	required

Returns:

Type	Description
Vertex	ID of the vertex in the original graph

Source code in tspwplib/converter.py

def get_original_from_split_vertex(
    biggest_vertex: Vertex, split_vertex: Vertex
) -> Vertex:
    """Return the original vertex id given a split vertex (may be head or tail)

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        split_vertex: A split vertex in asymmetric graph

    Returns:
        ID of the vertex in the original graph
    """
    if is_vertex_split_head(biggest_vertex, split_vertex):
        return split_vertex - 2 * (biggest_vertex + 1)
    # else split tail
    return split_vertex - biggest_vertex - 1

get_original_path_from_split_path(biggest_vertex, split_path)

Get the path in the original graph given a path of split vertices in the asymmetric graph

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
split_path	VertexList	A path of split vertices in the asymmetric directed graph	required

Returns:

Type	Description
VertexList	A path of vertices in the original graph

Source code in tspwplib/converter.py

def get_original_path_from_split_path(
    biggest_vertex: Vertex, split_path: VertexList
) -> VertexList:
    """Get the path in the original graph given a path of split vertices in the asymmetric graph

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        split_path: A path of split vertices in the asymmetric directed graph

    Returns:
        A path of vertices in the original graph
    """
    original_path = []
    previous_vertex = -1
    for split_vertex in split_path:
        original_vertex = get_original_from_split_vertex(biggest_vertex, split_vertex)
        if is_vertex_split_tail(biggest_vertex, split_vertex):
            original_path.append(original_vertex)
        elif (
            is_vertex_split_head(biggest_vertex, split_vertex)
            and previous_vertex != original_vertex
        ):
            original_path.append(original_vertex)
        previous_vertex = original_vertex
    return original_path

get_quota_from_alpha(alpha, total_prize)

The quota is alpha percent of the total prize

Parameters:

Name	Type	Description	Default
alpha	int	Percent of the total prize	required
total_prize	int	Total prize of the graph	required

Returns:

Type	Description
int	quota as an integer

Source code in tspwplib/problem.py

def get_quota_from_alpha(alpha: int, total_prize: int) -> int:
    """The quota is alpha percent of the total prize

    Args:
        alpha: Percent of the total prize
        total_prize: Total prize of the graph

    Returns:
        quota as an integer
    """
    if alpha > 100:
        raise ValueError("Cannot have a percent over 100 for alpha")
    if alpha < 0:
        raise ValueError("Cannot have a negative percent for alpha")
    return int(float(alpha * total_prize) / 100.0)

head_prize(prize)

Get the prize of the split head

Parameters:

Name	Type	Description	Default
prize	int	The prize of a vertex	required

Returns Split head prize

Source code in tspwplib/converter.py

def head_prize(prize: int) -> int:
    """Get the prize of the split head

    Args:
        prize: The prize of a vertex

    Returns
        Split head prize
    """
    if prize % 2 == 1:
        return math.ceil(prize / 2.0)
    return int(prize / 2)

is_complete(G)

Check if the graph is complete

Parameters:

Name	Type	Description	Default
G	Graph	Simple graph	required

Returns:

Type	Description
bool	True if the graph is complete, false otherwise

Note

Assumes no self loops

Source code in tspwplib/complete.py

def is_complete(G: nx.Graph) -> bool:
    """Check if the graph is complete

    Args:
        G: Simple graph

    Returns:
        True if the graph is complete, false otherwise

    Note:
        Assumes no self loops
    """
    for u in G:
        for v in G:
            if not G.has_edge(u, v) and u != v:
                return False
    return True

is_complete_with_self_loops(G)

Check if the graph is complete, and every vertex has a self loop

Parameters:

Name	Type	Description	Default
G	Graph	Simple graph	required

Returns:

Type	Description
bool	True if the graph is complete, false otherwise

Source code in tspwplib/complete.py

def is_complete_with_self_loops(G: nx.Graph) -> bool:
    """Check if the graph is complete, and every vertex has a self loop

    Args:
        G: Simple graph

    Returns:
        True if the graph is complete, false otherwise
    """
    for u in G:
        if not G.has_edge(u, u):
            return False
    return is_complete(G)

is_pctsp_yes_instance(graph, quota, root_vertex, edge_list)

Returns true if the list of edges is a solution to the instance of the Prize collecting Travelling Salesman Problem.

Parameters:

Name	Type	Description	Default
graph	Graph	Undirected graph with cost function on edges and prize function on vertices	required
quota	int	The salesman must collect at least the quota in prize money	required
root_vertex	Vertex	Start and finish vertex of the tour	required
edge_list	EdgeList	Edges in the solution of the instance	required

Returns:

Type	Description
bool	True if the total prize of the tour is at least the quota and the tour is a simple
bool	cycle that starts and ends at the root vertex. False otherwise.

Source code in tspwplib/problem.py

def is_pctsp_yes_instance(
    graph: nx.Graph, quota: int, root_vertex: Vertex, edge_list: EdgeList
) -> bool:
    """Returns true if the list of edges is a solution to the instance
    of the Prize collecting Travelling Salesman Problem.

    Args:
        graph: Undirected graph with cost function on edges and prize function on vertices
        quota: The salesman must collect at least the quota in prize money
        root_vertex: Start and finish vertex of the tour
        edge_list: Edges in the solution of the instance

    Returns:
        True if the total prize of the tour is at least the quota and the tour is a simple
        cycle that starts and ends at the root vertex. False otherwise.
    """
    if len(edge_list) < 3:
        return False
    walk = walk_from_edge_list(edge_list)
    vertex_set = set(walk)
    return (
        is_simple_cycle(graph, walk)
        and total_prize(
            nx.get_node_attributes(graph, VertexFunctionName.prize.value), vertex_set
        )
        >= quota
        and root_vertex == walk[0]
        and root_vertex == walk[len(walk) - 1]
    )

is_simple_cycle(G, cycle)

Is the cycle simple in the graph?

Parameters:

Name	Type	Description	Default
G	Graph	input graph	required
cycle	VertexList	Ordered sequence of vertices	required

Returns:

Type	Description
bool	True if the cycle is simple in the graph

Source code in tspwplib/walk.py

def is_simple_cycle(G: nx.Graph, cycle: VertexList) -> bool:
    """Is the cycle simple in the graph?

    Args:
        G: input graph
        cycle: Ordered sequence of vertices

    Returns:
        True if the cycle is simple in the graph
    """
    cycle_length = len(cycle)
    if cycle_length <= 1:
        return True
    return (
        is_walk(G, cycle)
        and cycle_length == len(set(cycle)) + 1
        and cycle[0] == cycle[cycle_length - 1]
    )

is_simple_path(G, path)

Is the path simple in the graph?

Parameters:

Name	Type	Description	Default
G	Graph	input graph	required
path	VertexList	Ordered sequence of vertices	required

Returns:

Type	Description
bool	True if the path is simple in the graph

Source code in tspwplib/walk.py

def is_simple_path(G: nx.Graph, path: VertexList) -> bool:
    """Is the path simple in the graph?

    Args:
        G: input graph
        path: Ordered sequence of vertices

    Returns:
        True if the path is simple in the graph
    """
    return is_walk(G, path) and len(path) == len(set(path))

is_split_vertex_pair(biggest_vertex, tail, head)

Does the arc (tail, head) represent a split vertex in the original graph?

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
tail	Vertex	Tail of edge in directed graph	required
head	Vertex	Head of edge in directed graph	required

Returns:

Type	Description
bool	True if the arc (tail, head) represents a split vertex in the original graph

Source code in tspwplib/converter.py

def is_split_vertex_pair(biggest_vertex: Vertex, tail: Vertex, head: Vertex) -> bool:
    """Does the arc (tail, head) represent a split vertex in the original graph?

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        tail: Tail of edge in directed graph
        head: Head of edge in directed graph

    Returns:
        True if the arc (tail, head) represents a split vertex in the original graph
    """
    return (
        head - tail == biggest_vertex + 1
        and is_vertex_split_head(biggest_vertex, head)
        and is_vertex_split_tail(biggest_vertex, tail)
    )

is_vertex_split_head(biggest_vertex, split_vertex)

Is the vertex a head in the asymmetric graph?

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
split_vertex	Vertex	A potential head of an edge in directed graph	required

Returns:

Type	Description
bool	True if the vertex is a head

Source code in tspwplib/converter.py

def is_vertex_split_head(biggest_vertex: Vertex, split_vertex: Vertex) -> bool:
    """Is the vertex a head in the asymmetric graph?

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        split_vertex: A potential head of an edge in directed graph

    Returns:
        True if the vertex is a head
    """
    return 2 * (biggest_vertex + 1) <= split_vertex < 3 * (biggest_vertex + 1)

is_vertex_split_tail(biggest_vertex, vertex)

Is the vertex a tail in the asymmetric graph?

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
vertex	Vertex	A potential tail of an edge in directed graph	required

Returns:

Type	Description
bool	True if the vertex is a tail

Source code in tspwplib/converter.py

def is_vertex_split_tail(biggest_vertex: Vertex, vertex: Vertex) -> bool:
    """Is the vertex a tail in the asymmetric graph?

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        vertex: A potential tail of an edge in directed graph

    Returns:
        True if the vertex is a tail
    """
    return biggest_vertex + 1 <= vertex < 2 * (biggest_vertex + 1)

is_walk(G, walk)

Is the walk a sequence of adjacent vertices in the graph?

Parameters:

Name	Type	Description	Default
G	Graph	input graph	required
walk	VertexList	Ordered sequence of vertices	required

Returns:

Type	Description
bool	True if all vertices are adjacent in the graph

Source code in tspwplib/walk.py

def is_walk(G: nx.Graph, walk: VertexList) -> bool:
    """Is the walk a sequence of adjacent vertices in the graph?

    Args:
        G: input graph
        walk: Ordered sequence of vertices

    Returns:
        True if all vertices are adjacent in the graph
    """
    edge_list = edge_list_from_walk(walk)
    return all(G.has_edge(edge[0], edge[1]) for edge in edge_list)

londonaq_comment(location_id, timestamp_id)

Get a comment for a londonaq dataset

Source code in tspwplib/utils.py

def londonaq_comment(
    location_id: LondonaqLocation, timestamp_id: LondonaqTimestamp
) -> str:
    """Get a comment for a londonaq dataset"""
    comment = f"A London air quality dataset starting at {location_id.value}. "
    comment += f"The UTC timestamp for the air quality forecast is {timestamp_id.value.isoformat()}"
    return comment

londonaq_graph_name(location_id, timestamp_id)

Get a londonaq graph name

Source code in tspwplib/utils.py

def londonaq_graph_name(
    location_id: LondonaqLocation, timestamp_id: LondonaqTimestamp
) -> LondonaqGraphName:
    """Get a londonaq graph name"""
    return LondonaqGraphName["laq" + location_id.name + timestamp_id.name]

metricness(graph, cost_attr='cost')

Measures how metric a cost function is

Parameters:

Name	Type	Description	Default
graph	Graph	Must be undirected, connected and not a tree	required
cost_attr	str	Name of cost attribute	'cost'

Returns:

Type	Description
float	If a cost function is metric, return 1.0.
float	If n-1 edges are metric and the remaining edges are non-metric, return 0.0.

Raises:

Type	Description
NotConnectedException	If the graph is not connected
NoTreesException	If the graph is a tree

Notes

Self loops are ignored from the metricness

Source code in tspwplib/metric.py

def metricness(graph: nx.Graph, cost_attr: str = "cost") -> float:
    """Measures how metric a cost function is

    Args:
        graph: Must be undirected, connected and not a tree
        cost_attr: Name of cost attribute

    Returns:
        If a cost function is metric, return 1.0.
        If n-1 edges are metric and the remaining edges are non-metric, return 0.0.

    Raises:
        NotConnectedException: If the graph is not connected
        NoTreesException: If the graph is a tree

    Notes:
        Self loops are ignored from the metricness
    """
    if not nx.is_connected(graph):
        raise NotConnectedException("Make sure your graph is connected")
    if nx.is_tree(graph):
        raise NoTreesException("Make sure your graph is not a tree")
    path_cost = dict(nx.all_pairs_bellman_ford_path_length(graph, weight=cost_attr))
    num_metric = 0
    num_non_metric = 0
    num_self_loops = 0
    for (u, v), cost in nx.get_edge_attributes(graph, cost_attr).items():
        if u == v:
            num_self_loops += 1
        elif cost <= path_cost[u][v]:
            num_metric += 1
        else:
            num_non_metric += 1
    print(num_metric, "metric edges and", num_non_metric, "non metric edges")
    numerator = (float)(num_metric - graph.number_of_nodes() + 1)
    denominator = (float)(
        graph.number_of_edges() - graph.number_of_nodes() - num_self_loops + 1
    )
    return numerator / denominator

mst_cost(G, cost_attr='cost')

Find the minimum spanning tree of G. The cost of edges in the tree remains unchanged. The cost of edges not in the tree is equal to the cost of the minimum spanning tree plus the original cost of the edges.

Parameters:

Name	Type	Description	Default
G	Graph	Undirected, simple graph	required
cost_attr	str	Name of the cost attribute of edges	'cost'

Returns A new cost function

Source code in tspwplib/metric.py

def mst_cost(G: nx.Graph, cost_attr: str = "cost") -> SimpleEdgeFunction:
    """Find the minimum spanning tree of G.
    The cost of edges in the tree remains unchanged.
    The cost of edges not in the tree is equal to the cost of the minimum spanning tree
    plus the original cost of the edges.

    Args:
        G: Undirected, simple graph
        cost_attr: Name of the cost attribute of edges

    Returns
        A new cost function
    """
    # find the cost of the minimum spanning tree in G
    T = nx.minimum_spanning_tree(G, weight=cost_attr)
    tree_cost = dict(nx.all_pairs_bellman_ford_path_length(T, weight=cost_attr))

    # set the cost of the new edges
    new_cost: SimpleEdgeFunction = {}
    for (u, v), cost in nx.get_edge_attributes(G, cost_attr).items():
        if T.has_edge(u, v):
            new_cost[(u, v)] = cost
        else:
            new_cost[(u, v)] = cost + tree_cost[u][v]
    return new_cost

order_edge_list(unordered_edges)

Given a list of unordered edges, return an ordered edge list such that every two adjacent edge in the list are also adjacent in the input graph.

Note that the list of edges should form a simple path or cycle.

Parameters:

Name	Type	Description	Default
unordered_edges	EdgeList	List of unique edges in no particular order	required

Returns:

Type	Description
EdgeList	List of unique edges that are adjacent in the graph

Raises:

Type	Description
NotSimpleException	If the list of edges is not a simple path or cycle

Source code in tspwplib/walk.py

def order_edge_list(unordered_edges: EdgeList) -> EdgeList:
    """Given a list of unordered edges, return an ordered edge list
    such that every two adjacent edge in the list are also adjacent in
    the input graph.

    Note that the list of edges should form a simple path or cycle.

    Args:
        unordered_edges: List of unique edges in no particular order

    Returns:
        List of unique edges that are adjacent in the graph

    Raises:
        NotSimpleException: If the list of edges is not a simple path or cycle
    """
    if not unordered_edges:
        return []
    # create a lookup table of the first and second occurence of each vertex in the edge list
    first_occurence: VertexLookup = {}
    second_occurence: VertexLookup = {}
    for i, edge in enumerate(unordered_edges):
        __add_vertex_to_occurence(first_occurence, second_occurence, edge[0], i)
        __add_vertex_to_occurence(first_occurence, second_occurence, edge[1], i)

    for u in first_occurence:
        if u not in second_occurence:
            message = f"Vertex {u} does not appear in two edges. Walk must be closed."
            raise NotSimpleCycleException(message)

    # use the lookup tables to place the edges in the correct order in the edge list
    ordered_edges = []
    j = 0
    target_index = -1
    found_source = False
    first_vertex = 0
    for i, edge in enumerate(unordered_edges):
        u = edge[0]
        v = edge[1]
        if not found_source and u not in second_occurence:
            j = i
            found_source = True
        elif found_source and u not in second_occurence:
            target_index = i
            break
        elif not found_source and v not in second_occurence:
            j = i
            found_source = True
            first_vertex = 1
        elif found_source and v not in second_occurence:
            target_index = i
            break
    prev = unordered_edges[j][first_vertex]
    visited = [False] * len(unordered_edges)

    for i in range(len(unordered_edges)):
        edge = unordered_edges[j]
        if visited[j]:
            raise NotSimpleException()
        visited[j] = True
        u = edge[0]
        v = edge[1]
        ordered_edges.append(edge)
        if j == target_index:
            break

        # if u == prev then follow v
        if u == prev and j == first_occurence[v]:
            j = second_occurence[v]
            prev = v
        elif u == prev and j == second_occurence[v]:
            j = first_occurence[v]
            prev = v
        # if v == prev then follow u
        elif v == prev and j == first_occurence[u]:
            j = second_occurence[u]
            prev = u
        elif v == prev and j == second_occurence[u]:
            j = first_occurence[u]
            prev = u

    return ordered_edges

remove_self_loops_from_edge_list(edge_list)

Return a new edge list with no self loops

Parameters:

Name	Type	Description	Default
edge_list	EdgeList	List of edges	required

Returns:

Type	Description
EdgeList	Edge list with no self loops

Source code in tspwplib/walk.py

def remove_self_loops_from_edge_list(edge_list: EdgeList) -> EdgeList:
    """Return a new edge list with no self loops

    Args:
        edge_list: List of edges

    Returns:
        Edge list with no self loops
    """
    return [edge for edge in edge_list if edge[0] != edge[1]]

rename_edge_attributes(graph, renaming, copy_graph=False, del_old_attr=False)

Rename edge attributes

Parameters:

Name	Type	Description	Default
graph	Graph	Networkx graph	required
renaming	Dict[str, str]	Keys are current attribute names. Values are new attribute names.	required
copy_graph	bool	If true, copy the graph before renaming attributes.	False
del_old_attr	bool	If true, delete the old edge attribute.	False

Returns:

Type	Description
Graph	Graph with renamed attributes. If copy_graph is True, then the copied graph is returned.
Graph	Otherwise the original graph is returned.

Source code in tspwplib/utils.py

def rename_edge_attributes(
    graph: nx.Graph,
    renaming: Dict[str, str],
    copy_graph: bool = False,
    del_old_attr: bool = False,
) -> nx.Graph:
    """Rename edge attributes

    Args:
        graph: Networkx graph
        renaming: Keys are current attribute names. Values are new attribute names.
        copy_graph: If true, copy the graph before renaming attributes.
        del_old_attr: If true, delete the old edge attribute.

    Returns:
        Graph with renamed attributes. If `copy_graph` is `True`, then the copied graph is returned.
        Otherwise the original graph is returned.
    """
    G = graph.copy() if copy_graph else graph
    for u, v, data in G.edges(data=True):
        for old_name, new_name in renaming.items():
            G.edges[u, v][new_name] = data[old_name]
            if del_old_attr:  # delete the old attribute
                data.pop(old_name)
    return G

rename_node_attributes(graph, renaming, copy_graph=False, del_old_attr=False)

Rename node attributes

Parameters:

Name	Type	Description	Default
graph	Graph	Networkx graph	required
renaming	Dict[str, str]	Keys are current attribute names. Values are new attribute names.	required
copy_graph	bool	If true, copy the graph before renaming attributes.	False
del_old_attr	bool	If true, delete the old node attribute.	False

Returns:

Type	Description
Graph	Graph with renamed attributes. If copy_graph is True, then the copied graph is returned.
Graph	Otherwise the original graph is returned.

Source code in tspwplib/utils.py

def rename_node_attributes(
    graph: nx.Graph,
    renaming: Dict[str, str],
    copy_graph: bool = False,
    del_old_attr: bool = False,
) -> nx.Graph:
    """Rename node attributes

    Args:
        graph: Networkx graph
        renaming: Keys are current attribute names. Values are new attribute names.
        copy_graph: If true, copy the graph before renaming attributes.
        del_old_attr: If true, delete the old node attribute.

    Returns:
        Graph with renamed attributes. If `copy_graph` is `True`, then the copied graph is returned.
        Otherwise the original graph is returned.
    """
    G = graph.copy() if copy_graph else graph
    for u, data in G.nodes(data=True):
        for old_name, new_name in renaming.items():
            G.nodes[u][new_name] = data[old_name]
            if del_old_attr:  # delete the old attribute
                data.pop(old_name)
    return G

reorder_edge_list_from_root(edge_list, root)

Reorder a list of edges such that the root vertex is in the first (and last) edge

Parameters:

Name	Type	Description	Default
edge_list	EdgeList	List of unique, adjacent edges	required
root	Vertex	Root vertex	required

Returns:

Type	Description
EdgeList	List of edges. The first (and last) edge will contain the root vertex.

Raises:

Type	Description
NodeNotFound	If the root vertex is not in any edges.

Source code in tspwplib/walk.py

def reorder_edge_list_from_root(edge_list: EdgeList, root: Vertex) -> EdgeList:
    """Reorder a list of edges such that the root vertex is in the first (and last) edge

    Args:
        edge_list: List of unique, adjacent edges
        root: Root vertex

    Returns:
        List of edges. The first (and last) edge will contain the root vertex.

    Raises:
        nx.NodeNotFound: If the root vertex is not in any edges.
    """
    root_index = -1
    not_found = nx.NodeNotFound(f"Root vertex {root} not found in edge list")
    n = len(edge_list)
    if n == 0:
        raise not_found
    if n > 1 and root in edge_list[0] and root in edge_list[n - 1]:
        return edge_list
    for i in range(n):
        edge = edge_list[i]
        if root in edge:
            root_index = i
    if root_index == -1:
        raise not_found
    reordered_edges = edge_list[root_index:] + edge_list[:root_index]
    return reordered_edges

semi_mst_cost(G, cost_attr='cost', seed=0)

Half of the non-MST-tree edges are left unchanged. The other half are assigned cost as described in mst_cost.

The half of edges are chosen with uniform and independent probability.

Parameters:

Name	Type	Description	Default
G	Graph	Undirected, simple graph	required
cost_attr	str	Name of the cost attribute of edges	'cost'
seed	int	Set the seed of the random number generator	0

Returns A new cost function

Source code in tspwplib/metric.py

def semi_mst_cost(
    G: nx.Graph, cost_attr: str = "cost", seed: int = 0
) -> SimpleEdgeFunction:
    """Half of the non-MST-tree edges are left unchanged.
    The other half are assigned cost as described in mst_cost.

    The half of edges are chosen with uniform and independent probability.

    Args:
        G: Undirected, simple graph
        cost_attr: Name of the cost attribute of edges
        seed: Set the seed of the random number generator

    Returns
        A new cost function
    """
    # find the cost of the minimum spanning tree in G
    T = nx.minimum_spanning_tree(G, weight=cost_attr)
    tree_cost = dict(nx.all_pairs_bellman_ford_path_length(T, weight=cost_attr))

    # get edges not in the tree
    non_tree_edges = [(u, v) for u, v in G.edges() if not T.has_edge(u, v)]
    num_non_tree_edges = len(non_tree_edges)

    gen = np.random.default_rng(seed=seed)
    donot_change_edge_cost = set()
    while len(non_tree_edges) >= float(num_non_tree_edges) * 0.5:
        index = gen.integers(0, len(non_tree_edges) - 1)  # get random index
        donot_change_edge_cost.add(
            non_tree_edges.pop(index)
        )  # remove item at random index, add to set

    # set the cost of the new edges
    new_cost: SimpleEdgeFunction = {}
    for (u, v), cost in nx.get_edge_attributes(G, cost_attr).items():
        if (
            T.has_edge(u, v)
            or (u, v) in donot_change_edge_cost
            or (v, u) in donot_change_edge_cost
        ):
            new_cost[(u, v)] = cost
        else:
            new_cost[(u, v)] = cost + tree_cost[u][v]
    return new_cost

sparsify_by_cost(G, kappa, cost_attr='cost', seed=0, remove_self_loops=False)

Given vertex i, remove an edge e=(i,j) with probability P[i,j] where the probability function is weighted according to the cost function:

$P[i,j] = c(i,j) / C_i$

where $C_i$ is the total cost of all edges adjacent to vertex i.

Parameters:

Name	Type	Description	Default
G	Graph	Graph	required
kappa	int	Parameter independent of the input size	required
cost_attr	str	Name of the cost attribute on edges	'cost'
remove_self_loops	bool	Should self loops have a change of being removed?	False
seed	int	Set the random seed for reproducibility of graphs	0

Returns:

Type	Description
Graph	A deep copy of the original graph with edges removed

Source code in tspwplib/sparse.py

def sparsify_by_cost(
    G: nx.Graph,
    kappa: int,
    cost_attr: str = "cost",
    seed: int = 0,
    remove_self_loops: bool = False,
) -> nx.Graph:
    """Given vertex i, remove an edge e=(i,j) with probability P[i,j]
    where the probability function is weighted according to the cost function:

    $P[i,j] = c(i,j) / C_i$

    where $C_i$ is the total cost of all edges adjacent to vertex i.

    Args:
        G: Graph
        kappa: Parameter independent of the input size
        cost_attr: Name of the cost attribute on edges
        remove_self_loops: Should self loops have a change of being removed?
        seed: Set the random seed for reproducibility of graphs

    Returns:
        A deep copy of the original graph with edges removed
    """
    random.seed(seed)
    graph_copy = deepcopy(G)
    vertex_list = list(graph_copy.nodes())
    while graph_copy.number_of_edges() > graph_copy.number_of_nodes() * kappa:
        # choose vertex randomly
        u = random.choice(vertex_list)
        u_has_self_loop = graph_copy.has_edge(u, u)
        u_neighbors = list(graph_copy.neighbors(u))
        if u_has_self_loop and not remove_self_loops:
            u_neighbors.remove(u)
        if len(u_neighbors) > 0:
            # draw a random number from uniform and independent distribution (UID)
            threshold = random.random()

            # the total cost of all adjacent edges is the denominator
            cost_of_edges = float(
                total_cost_of_adjacent_edges(graph_copy, u, cost_attr=cost_attr)
            )
            chosen_vertex = None

            if u_has_self_loop and not remove_self_loops:
                cost_of_edges -= graph_copy.get_edge_data(u, u)[cost_attr]

            if cost_of_edges == 0:
                chosen_vertex = random.choice(u_neighbors)

            else:
                # iterate over neighbors to check if the edge has been selected
                probability_so_far = 0.0
                for v in u_neighbors:
                    # weight probability of choosing an edges by the cost
                    edge_prob = (
                        float(graph_copy.get_edge_data(u, v)[cost_attr]) / cost_of_edges
                    )
                    if probability_so_far + edge_prob >= threshold and (
                        remove_self_loops or u != v
                    ):
                        # edge found! break here
                        chosen_vertex = v
                        break
                    probability_so_far += edge_prob
            graph_copy.remove_edge(u, chosen_vertex)
    return graph_copy

sparsify_uid(G, kappa, remove_self_loops=False, seed=0)

Remove edges with uniform and independent (uid) probability until the number of edges equals kappa * number of nodes

Parameters:

Name	Type	Description	Default
G	Graph	Graph	required
kappa	int	Parameter independent of the input size	required
remove_self_loops	bool	Should self loops have a change of being removed?	False
seed	int	Set the random seed	0

Returns:

Type	Description
Graph	Graph with kappa * V edges where V is the number of nodes

Notes

A copy of the graph is made and returned. The original graph is unedited.

Source code in tspwplib/sparse.py

def sparsify_uid(
    G: nx.Graph,
    kappa: int,
    remove_self_loops: bool = False,
    seed: int = 0,
) -> nx.Graph:
    """Remove edges with uniform and independent (uid) probability until
    the number of edges equals kappa * number of nodes

    Args:
        G: Graph
        kappa: Parameter independent of the input size
        remove_self_loops: Should self loops have a change of being removed?
        seed: Set the random seed

    Returns:
        Graph with kappa * V edges where V is the number of nodes

    Notes:
        A copy of the graph is made and returned. The original graph is unedited.
    """
    random.seed(seed)
    graph_copy = deepcopy(G)
    vertex_list = list(graph_copy.nodes())
    while graph_copy.number_of_edges() > graph_copy.number_of_nodes() * kappa:
        # choose vertex randomly
        u = random.choice(vertex_list)
        if graph_copy.degree(u) > 0:
            # choose a neighbor randomly
            v = random.choice(list(graph_copy.neighbors(u)))
            # remove edge if it is not a self loop
            if remove_self_loops or u != v:
                graph_copy.remove_edge(u, v)
    return graph_copy

split_graph_from_properties(edge_properties, edge_attr_to_split='cost', edge_attr_to_vertex='length', new_vertex_attr='prize', old_edge_attr='old_edge')

Split edges with properties and create undirected simple graph.

Parameters:

Name	Type	Description	Default
edge_properties	EdgeProperties	Keys are edges. Values are dicts of edge attributes.	required
edge_attr_to_split	str	Name of edge attribute. Assign half the value to each split edge.	'cost'
edge_attr_to_vertex	str	Name of edge attribute. Assign edge value to a new vertex attribute.	'length'
new_vertex_attr	str	Name of the newly created vertex attribute.	'prize'
old_edge_attr	str	Name of the newly created attribute for the old edge ID.	'old_edge'

Returns:

Type	Description
Graph	Undirected simple graph with edge attributes for cost, prize and old_edge

Notes

To get the original_edge that a split edge represents, access the 'old_edge' attribute

Source code in tspwplib/converter.py

def split_graph_from_properties(
    edge_properties: EdgeProperties,
    edge_attr_to_split: str = "cost",
    edge_attr_to_vertex: str = "length",
    new_vertex_attr: str = "prize",
    old_edge_attr: str = "old_edge",
) -> nx.Graph:
    """Split edges with properties and create undirected simple graph.

    Args:
        edge_properties: Keys are edges. Values are dicts of edge attributes.
        edge_attr_to_split: Name of edge attribute. Assign half the value to each split edge.
        edge_attr_to_vertex: Name of edge attribute. Assign edge value to a new vertex attribute.
        new_vertex_attr: Name of the newly created vertex attribute.
        old_edge_attr: Name of the newly created attribute for the old edge ID.

    Returns:
        Undirected simple graph with edge attributes for cost, prize and old_edge

    Notes:
        To get the original_edge that a split edge represents, access the 'old_edge' attribute
    """
    # check that every edge has an attribute to split and an attr to move to vertex
    is_edge_attr_to_split = True
    is_edge_attr_to_vertex = True
    for data in edge_properties.values():
        if not edge_attr_to_split in data:
            is_edge_attr_to_split = False
        if not edge_attr_to_vertex in data:
            is_edge_attr_to_vertex = False

    # split edges and create lookups
    edge_list = list(edge_properties.keys())
    splits = split_edges(edge_list)
    to_split = lookup_to_split(edge_list, splits)
    from_split = lookup_from_split(edge_list, splits)

    # create graph and assign prizes and costs
    G = nx.Graph()
    G.add_edges_from(splits)
    if is_edge_attr_to_vertex:
        prize = prize_from_weighted_edges(
            {edge: item[edge_attr_to_vertex] for edge, item in edge_properties.items()},
            to_split,
        )
        nx.set_node_attributes(G, 0.0, name=new_vertex_attr)
        nx.set_node_attributes(G, prize, name=new_vertex_attr)

    if is_edge_attr_to_split:
        cost = split_edge_cost(
            {edge: item[edge_attr_to_split] for edge, item in edge_properties.items()},
            to_split,
        )
        nx.set_edge_attributes(G, 0.0, name=edge_attr_to_split)
        nx.set_edge_attributes(G, cost, name=edge_attr_to_split)
    nx.set_edge_attributes(G, from_split, name=old_edge_attr)
    return G

split_head(biggest_vertex, original_vertex)

Get the split head of the vertex

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
original_vertex	Vertex	Vertex in the original graph	required

Returns:

Type	Description
Vertex	New split vertex that is a head of all arcs in the asymmetric graph

Source code in tspwplib/converter.py

def split_head(biggest_vertex: Vertex, original_vertex: Vertex) -> Vertex:
    """Get the split head of the vertex

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        original_vertex: Vertex in the original graph

    Returns:
        New split vertex that is a head of all arcs in the asymmetric graph
    """
    return 2 * (biggest_vertex + 1) + original_vertex

split_tail(biggest_vertex, original_vertex)

Get the split tail of the vertex

Parameters:

Name	Type	Description	Default
biggest_vertex	Vertex	The vertex with the biggest id in the original graph	required
original_vertex	Vertex	Vertex in the original graph	required

Returns:

Type	Description
Vertex	New split vertex that is a tail of all arcs in the asymmetric graph

Source code in tspwplib/converter.py

def split_tail(biggest_vertex: Vertex, original_vertex: Vertex) -> Vertex:
    """Get the split tail of the vertex

    Args:
        biggest_vertex: The vertex with the biggest id in the original graph
        original_vertex: Vertex in the original graph

    Returns:
        New split vertex that is a tail of all arcs in the asymmetric graph
    """
    return biggest_vertex + 1 + original_vertex

tail_prize(prize)

Get the prize of the split tail

Parameters:

Name	Type	Description	Default
prize	int	The prize of a vertex	required

Returns Split tail prize

Source code in tspwplib/converter.py

def tail_prize(prize: int) -> int:
    """Get the prize of the split tail

    Args:
        prize: The prize of a vertex

    Returns
        Split tail prize
    """
    return math.floor(prize / 2.0)

to_simple_undirected(G)

Given an undirected multigraph, multi edges to create a simple undirected graph.

Parameters:

Name	Type	Description	Default
G	MultiGraph	Undirected networkx multi graph.	required

Returns:

Type	Description
Graph	Undirected networkx simple graph with no multi edges.

Notes

Assumes the vertex ids are integers.

Source code in tspwplib/converter.py

def to_simple_undirected(G: nx.MultiGraph) -> nx.Graph:
    """Given an undirected multigraph, multi edges to create a simple undirected graph.

    Args:
        G: Undirected networkx multi graph.

    Returns:
        Undirected networkx simple graph with no multi edges.

    Notes:
        Assumes the vertex ids are integers.
    """
    if not isinstance(G, nx.MultiGraph) and isinstance(G, nx.Graph):
        return G
    if isinstance(G, nx.DiGraph):
        raise TypeError("Directed graphs are not valid for this method")
    simple_graph = nx.Graph()

    # copy graph attributes to new graph
    for key, value in simple_graph.graph.items():
        simple_graph.graph[key] = value

    # copy vertex attributes
    for v, data in G.nodes(data=True):
        simple_graph.add_node(v, **data)

    biggest = biggest_vertex_id_from_graph(G)

    for u, v, k, data in G.edges.data(keys=True):
        if u == v and k > 0:
            message = "Self loop found with key greater than zero: "
            message += "implies there is more than one self loop on this vertex."
            raise UnexpectedSelfLoopException(message)

        # the first multi edge - add all data to new graph edge
        if k == 0:
            simple_graph.add_edge(u, v, **data)

        # multi edge - create new vertex for the source if it does not yet exist
        elif k > 0:
            vertex_data = G.nodes[u]
            dummy = new_dummy_vertex(u, k, biggest)
            simple_graph.add_node(dummy, **vertex_data)
            simple_graph.add_edge(u, dummy, **data)
            simple_graph.add_edge(dummy, v, **data)
        else:
            raise ValueError("Negative key for edge.")

    return simple_graph

to_vertex_dataframe(graph)

Convert graph vertices to pandas dataframe

Parameters:

Name	Type	Description	Default
graph	Graph	Input graph	required

Returns:

Type	Description
DataFrame	pandas dataframe with vertex set as index

Source code in tspwplib/converter.py

def to_vertex_dataframe(graph: nx.Graph) -> pd.DataFrame:
    """Convert graph vertices to pandas dataframe

    Args:
        graph: Input graph

    Returns:
        pandas dataframe with vertex set as index
    """
    vertex_data = list(map(lambda x: dict(vertex=x[0], **x[1]), graph.nodes(data=True)))
    vertex_df = pd.DataFrame(vertex_data)
    vertex_df = vertex_df.set_index("vertex")
    return vertex_df

total_cost(costs, edges)

Total cost of edges

Parameters:

Name	Type	Description	Default
costs	EdgeFunction	Mapping from edges to costs	required
edges	EdgeList	List of edges	required

Returns:

Type	Description
int	Total cost of edges

Source code in tspwplib/walk.py

def total_cost(costs: EdgeFunction, edges: EdgeList) -> int:
    """Total cost of edges

    Args:
        costs: Mapping from edges to costs
        edges: List of edges

    Returns:
        Total cost of edges
    """
    sum_cost = 0
    for edge in edges:
        try:
            sum_cost += costs[edge]
        except KeyError:
            try:
                u = edge[0]
                v = edge[1]
                sum_cost += costs[(v, u)]
            except KeyError as second_key_error:
                raise KeyError(
                    "Edge ({u},{v}) or ({v},{u}) do not exist in costs map".format(
                        u=u, v=v
                    )
                ) from second_key_error
        except Exception as error:
            raise KeyError(f"{edge} does not exist in cost map") from error
    return sum_cost

total_cost_networkx(graph, walk)

Get the total cost of edges in a walk of the networkx graph

Parameters:

Name	Type	Description	Default
graph	Graph	Undirected input graph with cost attribute	required
walk	VertexList	A sequence of adjacent vertices	required

Returns:

Type	Description
int	Total cost of edges in the walk

Source code in tspwplib/walk.py

def total_cost_networkx(graph: nx.Graph, walk: VertexList) -> int:
    """Get the total cost of edges in a walk of the networkx graph

    Args:
        graph: Undirected input graph with cost attribute
        walk: A sequence of adjacent vertices

    Returns:
        Total cost of edges in the walk
    """
    edges_in_tour = edge_list_from_walk(walk)
    cost_attr = nx.get_edge_attributes(graph, EdgeFunctionName.cost.value)
    return total_cost(cost_attr, edges_in_tour)

total_prize(prizes, vertices)

Total prize of vertices

Parameters:

Name	Type	Description	Default
prizes	Mapping[Vertex, int]	A mapping from vertices to prizes, e.g. dict, property map	required
vertices	Iterable[Vertex]	List of vertices in the prizes map	required

Returns:

Type	Description
int	Total prize of vertices

Source code in tspwplib/walk.py

def total_prize(prizes: Mapping[Vertex, int], vertices: Iterable[Vertex]) -> int:
    """Total prize of vertices

    Args:
        prizes: A mapping from vertices to prizes, e.g. dict, property map
        vertices: List of vertices in the prizes map

    Returns:
        Total prize of vertices
    """
    sum_prize: int = 0
    for vertex in vertices:
        sum_prize += prizes[vertex]
    return sum_prize

total_prize_of_tour(prizes, tour)

Total prize of unique vertices in the tour

Parameters:

Name	Type	Description	Default
prizes	Mapping[Vertex, int]	A mapping from vertices to prizes, e.g. dict, property map	required
tour	VertexList	List of vertices in the prizes map	required

Returns:

Type	Description
int	Total prize of the tour

Source code in tspwplib/walk.py

def total_prize_of_tour(prizes: Mapping[Vertex, int], tour: VertexList) -> int:
    """Total prize of unique vertices in the tour

    Args:
        prizes: A mapping from vertices to prizes, e.g. dict, property map
        tour: List of vertices in the prizes map

    Returns:
        Total prize of the tour
    """
    return total_prize(prizes, set(tour))

uniform_random_cost(edge_list, min_value=1, max_value=100, seed=0)

Generate a cost function for each edge drawn from a uniform and independant probability

Parameters:

Name	Type	Description	Default
edge_list	SimpleEdgeList	List of edges in graph	required
min_value	int	Minimum value the cost can take (inclusive)	1
max_value	int	Maximum value the cost can take (inclusive)	100
seed	int	Set the seed of the random number generator	0

Returns:

Type	Description
SimpleEdgeFunction	Edge cost function

Source code in tspwplib/metric.py

def uniform_random_cost(
    edge_list: SimpleEdgeList, min_value: int = 1, max_value: int = 100, seed: int = 0
) -> SimpleEdgeFunction:
    """Generate a cost function for each edge drawn from a uniform and independant probability

    Args:
        edge_list: List of edges in graph
        min_value: Minimum value the cost can take (inclusive)
        max_value: Maximum value the cost can take (inclusive)
        seed: Set the seed of the random number generator

    Returns:
        Edge cost function
    """
    cost: SimpleEdgeFunction = {}
    random.seed(seed)
    for u, v in edge_list:
        cost[(u, v)] = random.randint(min_value, max_value)
    return cost

vertex_set_from_edge_list(edge_list)

Get a set of vertices from a list of edges

Parameters:

Name	Type	Description	Default
edge_list	EdgeList	List of edges	required

Returns:

Type	Description
Set[Vertex]	Set of vertices in the edge list

Source code in tspwplib/walk.py

def vertex_set_from_edge_list(edge_list: EdgeList) -> Set[Vertex]:
    """Get a set of vertices from a list of edges

    Args:
        edge_list: List of edges

    Returns:
        Set of vertices in the edge list
    """
    return set(itertools.chain.from_iterable(edge_list))

walk_from_edge_list(edge_list)

Get a walk from a list of unique, adjacent edges

Parameters:

Name	Type	Description	Default
edge_list	EdgeList	List of unique edges that are adjacent in the graph	required

Returns:

Type	Description
VertexList	List of vertices in walk of edges

Raises:

Type	Description
EdgesNotAdjacentException	When two edges in the walk are not adjacent

Source code in tspwplib/walk.py

def walk_from_edge_list(edge_list: EdgeList) -> VertexList:
    """Get a walk from a list of unique, adjacent edges

    Args:
        edge_list: List of unique edges that are adjacent in the graph

    Returns:
        List of vertices in walk of edges

    Raises:
        EdgesNotAdjacentException: When two edges in the walk are not adjacent
    """
    walk: VertexList = []
    if len(edge_list) == 0:
        return walk

    first_edge = edge_list[0]
    if len(edge_list) == 1:
        walk.append(first_edge[0])
        walk.append(first_edge[1])
        return walk

    second_edge = edge_list[1]
    if first_edge[0] == second_edge[0] or first_edge[0] == second_edge[1]:
        current = first_edge[0]
        walk.append(first_edge[1])
    else:
        current = first_edge[1]
        walk.append(first_edge[0])

    for i in range(1, len(edge_list)):
        walk.append(current)
        edge = edge_list[i]
        u = edge[0]
        v = edge[1]
        if u == current:
            current = v
        elif v == current:
            current = u
        else:
            message = f"Edges in the edge list must be adjacent, but edge {u} - {v}"
            message += (
                f" is not adjacent to vertex {current} from previous edge in list."
            )
            raise EdgesNotAdjacentException(message)
    walk.append(current)
    return walk