Skip to content

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.