mis.shared.graphs

source module mis.shared.graphs

Classes

• BaseWeightPicker — Utility class to pick the weight of a node.

• WeightedPicker

• UnweightedPicker

Functions

• closed_neighborhood — Return the list of closed neighbours of a node.

• 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 class BaseWeightPicker()

Bases : ABC

Utility class to pick the weight of a node.

Unweighted implementations optimize the methods into trivial operations.

Methods

• node_weight — Get the weight of a node.

• set_node_weight — Set the weight of a node.

• node_delta — Apply a delta to the weight of a node.

• subgraph_weight — Get the weight of a subraph.

• for_weighting — Pick a cost picker for an objective.

source classmethod BaseWeightPicker.node_weight(graph: nx.Graph, node: int) → float

Get the weight of a node.

For a weighted cost picker, this returns attribute weight of the node, or 1. if the node doesn't specify a weight.

For an unweighted cost picker, this always returns 1.

Raises

• NotImplementedError

source classmethod BaseWeightPicker.set_node_weight(graph: nx.Graph, node: int, weight: float) → None

Set the weight of a node.

For a weighted cost picker, this returns attribute weight of the node, or 1. if the node doesn't specify a weight.

For an unweighted cost picker, raise an error.

Raises

• NotImplementedError

source classmethod BaseWeightPicker.node_delta(graph: nx.Graph, node: int, delta: float) → float

Apply a delta to the weight of a node.

Raises an error in an unweighted cost picker.

Raises

• NotImplementedError

source classmethod BaseWeightPicker.subgraph_weight(graph: nx.Graph, nodes: typing.Iterable[int]) → float

Get the weight of a subraph.

See node_weight for the definition of weight.

For an unweighted cost picker, this always returns len(nodes).

Raises

• NotImplementedError

source classmethod BaseWeightPicker.for_weighting(weighting: Weighting) → type[BaseWeightPicker]

Pick a cost picker for an objective.

source class WeightedPicker()

Bases : BaseWeightPicker

Methods

• node_weight

• set_node_weight

• subgraph_weight

• node_delta — Apply a delta to the weight of a node.

source classmethod WeightedPicker.node_weight(graph: nx.Graph, node: int) → float

source classmethod WeightedPicker.set_node_weight(graph: nx.Graph, node: int, weight: float) → None

source classmethod WeightedPicker.subgraph_weight(graph: nx.Graph, nodes: typing.Iterable[int]) → float

source classmethod WeightedPicker.node_delta(graph: nx.Graph, node: int, delta: float) → float

Apply a delta to the weight of a node.

Raises an error in an unweighted cost picker.

source class UnweightedPicker()

Bases : BaseWeightPicker

Methods

• node_weight

• set_node_weight

• subgraph_weight

source classmethod UnweightedPicker.node_weight(graph: nx.Graph, node: int) → float

source classmethod UnweightedPicker.set_node_weight(graph: nx.Graph, node: int, weight: float) → None

Raises

• NotImplementedError

source classmethod UnweightedPicker.subgraph_weight(graph: nx.Graph, nodes: typing.Iterable[int]) → float

source closed_neighborhood(graph: nx.Graph, node: int) → list[int]

Return the list of closed neighbours of a node.

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.