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: Optional[set[int]] = None, is_second_coloring: bool = False) → 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.