Skip to content

Results are limited to Maximum Independent Set v0.2.3

Product news
You are reading Maximum Independent Set v0.2.3, an older version of this documentation. Go to the latest version (v0.3.2)

mis.coloring

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.

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.

method
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.

method
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.

method
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.

method
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.

method
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.