mis.shared.graphs

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.

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.

classmethod

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

classmethod

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

classmethod

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

classmethod

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

classmethod

for_weighting (weighting: Weighting) → type[BaseWeightPicker]

Pick a cost picker for an objective.

class

WeightedPicker ()

Bases : BaseWeightPicker

Methods

• node_weight

• set_node_weight

• subgraph_weight

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

classmethod

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

classmethod

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

classmethod

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

classmethod

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.

class

UnweightedPicker ()

Bases : BaseWeightPicker

Methods

• node_weight

• set_node_weight

• subgraph_weight

classmethod

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

classmethod

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

Raises

• NotImplementedError

classmethod

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

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

Return the list of closed neighbours of a node.

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.

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.