Skip to content

mis.coloring

source package mis.coloring

Classes

  • GraphColoringSolver GraphColoringSolver class to solve the graph coloring problem for antennas using the Maximum Independent Set (MIS) approach. Given the coordinates of antennas and a specified antenna range, it finds a coloring of the graph such that no two antennas in the range of each other share the same color.

source class GraphColoringSolver(loader: DataLoader, antenna_range: float, config: SolverConfig = SolverConfig())

Bases : BaseSolver

GraphColoringSolver class to solve the graph coloring problem for antennas using the Maximum Independent Set (MIS) approach. Given the coordinates of antennas and a specified antenna range, it finds a coloring of the graph such that no two antennas in the range of each other share the same color.

Initialize the GraphColoringSolver with a DataLoader instance and antenna range. Args: loader (DataLoader): An instance of DataLoader to load antenna coordinates. antenna_range (float): The maximum distance within which antennas can interfere with each other. config (SolverConfig): Configuration for the MIS solver, including backend and other settings.

Attributes

  • loader : DataLoader An instance of DataLoader to load antenna coordinates.

  • antenna_range : float The maximum distance within which antennas can interfere with each other.

  • colors : list[int] A list where the index represents the antenna and the value represents its color.

  • colors_count : int The total number of colors used in the solution.

  • solver_config : SolverConfig Configuration for the MIS solver, including backend and other settings.

Methods

  • solve Solve the graph coloring problem by finding a maximum independent set for the given antenna range and coloring the antennas accordingly.

  • split_antennas_by_degree Splits the antennas into two sets based on a threshold of the degree of the node. Antennas with a degree less than or equal to the threshold will be grouped together.

  • reduce_colors Attempts to reduce the number of colors used in the solution by trying to reassign every node of some color. Returns : list[int]: A list of colors for each antenna, where the index represents the antenna.

  • check_solution Check if the solution is valid by ensuring that no two antennas in the same color are within the antenna range of each other.

  • visualize_solution Visualize the solution by plotting the antennas on a 2D plane. Each antenna is represented by a point, and antennas that are in the same independent set (i.e., do not interfere with each other) are colored the same.

source method GraphColoringSolver.solve(antennas: set[int] = None, is_second_coloring: bool = False)Execution[list[MISSolution]]

Solve the graph coloring problem by finding a maximum independent set for the given antenna range and coloring the antennas accordingly.

Parameters

  • antennas : set[int] A set of antenna indices to consider for coloring. If empty, all antennas in the dataset will be considered.

  • is_second_coloring : bool If True, the solver will not reset the colors count and will continue coloring from the last used color.

Returns

  • Execution[list[MISSolution]] An execution object containing the nodes of each color in the solution.

source method GraphColoringSolver.split_antennas_by_degree(threshold: int)list[set[int]]

Splits the antennas into two sets based on a threshold of the degree of the node. Antennas with a degree less than or equal to the threshold will be grouped together.

Parameters

  • threshold : int The degree threshold for splitting antennas.

Returns

  • list[set[int]] A list of sets, where the first set contains antennas with a degree less than or equal to the threshold, and the second set contains the rest.

source method GraphColoringSolver.reduce_colors()list[int]

Attempts to reduce the number of colors used in the solution by trying to reassign every node of some color. Returns : list[int]: A list of colors for each antenna, where the index represents the antenna.

source method GraphColoringSolver.check_solution()bool

Check if the solution is valid by ensuring that no two antennas in the same color are within the antenna range of each other.

Returns

  • bool True if the solution is valid, False otherwise.

source method GraphColoringSolver.visualize_solution()plt

Visualize the solution by plotting the antennas on a 2D plane. Each antenna is represented by a point, and antennas that are in the same independent set (i.e., do not interfere with each other) are colored the same.

Returns

  • plt A matplotlib plot object showing the antenna coverage solution.