mis.shared.graphs

source module mis.shared.graphs

Functions

• calculate_weight — Calculates the total weight of a set of nodes in a given MISInstance

• is_independent — Checks if the node set is an independent set (no edges between them).

• remove_neighborhood — Removes a node and all its neighbors from the graph.

source calculate_weight(graph: nx.Graph, nodes: list[int]) → float

Calculates the total weight of a set of nodes in a given MISInstance

Parameters

• graph : nx.Graph — The graph to check.

• nodes : list[int] — List of node indices.

Returns

• float — Total weight as a float.

source is_independent(graph: nx.Graph, nodes: list[int]) → bool

Checks if the node set is an independent set (no edges between them).

Parameters

• graph : nx.Graph — The graph to check.

• nodes : list[int] — The set of nodes.

Returns

• bool — True if independent, False otherwise.

source remove_neighborhood(graph: nx.Graph, nodes: list[int]) → nx.Graph

Removes a node and all its neighbors from the graph.

Parameters

• graph : nx.Graph — The graph to modify.

• nodes : list[int] — List of nodes to remove.

Returns

• nx.Graph — The reduced graph.