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.