propositions.reductions module¶

Reduction between computational search problems.

propositions.reductions.Graph¶

A graph on a vertex set of the form (1,…,n_vertices), represented by the number of vertices n_vertices and a set of edges over the vertices.

alias of Tuple[int, AbstractSet[Tuple[int, int]]]

propositions.reductions.is_graph(graph)¶

Checks if the given data structure is a valid representation of a graph.

Parameters: graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – data structure to check.
Return type: bool
Returns: True if the given data structure is a valid representation of a graph, False otherwise.

propositions.reductions.is_valid_3coloring(graph, coloring)¶

Checks whether the given coloring is a valid coloring of the given graph by the colors 1, 2, and 3.

Parameters

graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph to check.
coloring (Mapping[int, int]) – mapping from the vertices of the given graph to colors, to check.

Return type

bool

Returns

True if the given coloring is a valid coloring of the given graph by the colors 1, 2, and 3; False otherwise.

propositions.reductions.graph3coloring_to_formula(graph)¶

Efficiently reduces the 3-coloring problem of the given graph into a satisfiability problem.

Parameters: graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph whose 3-coloring problem to reduce.
Return type: Formula
Returns: A propositional formula that is satisfiable if and only if the given graph is 3-colorable.

propositions.reductions.assignment_to_3coloring(graph, assignment)¶

Efficiently transforms an assignment to the formula corresponding to the 3-coloring problem of the given graph, to a 3-coloring of the given graph so that the 3-coloring is valid if and only if the given assignment is satisfying.

Parameters

graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph to produce a 3-coloring for.
assignment (Mapping[str, bool]) – assignment to the variable names of the formula returned by graph3coloring_to_formula(graph).

Return type

Mapping[int, int]

Returns

A 3-coloring of the given graph by the colors 1, 2, and 3 that is valid if and only if the given assignment satisfies the formula graph3coloring_to_formula(graph).

propositions.reductions.tricolor_graph(graph)¶

Computes a 3-coloring of the given graph.

Parameters: graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph to 3-color.
Return type: Optional[Mapping[int, int]]
Returns: An arbitrary 3-coloring of the given graph if it is 3-colorable, None otherwise.