reoptimization_algorithms.utils.graph.pvc.PVCUtils

class PVCUtils

Bases: object

Utility class for Path vertex cover problem

static is_k_pvc(graph: reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph, vertices: Set[str], k: int) → bool

Checks if the given candidate vertices are k path vertex cover for the graph

Parameters

  • graph (UndirectedGraph) – Undirected graph

  • vertices (Set['str']) – Vertices to check if they form k path cover

  • k (int) – length of paths which should be covered

Returns

Boolean

Example

import reoptimization_algorithms as ra

graph = (ra.UndirectedGraph().add_edge("4", "5").add_edge("40", "50")
         .add_vertex("6").add_edge("4", "8").add_vertex("99"))
print(ra.PVCUtils.is_k_pvc(graph, {"4"}, 3)) # True
static is_path(graph: reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph, path: Union[List[str], Tuple[str]]) → bool

Checks if the path exists in the graph

Parameters

  • graph (UndirectedGraph) – Undirected graph

  • path (Union[List['str'], Tuple['str']]) – Path as a list of vertices

Returns

Boolean

Example

from reoptimization_algorithms import PVCUtils, UndirectedGraph

graph = (UndirectedGraph().add_edge("4", "5").add_edge("40", "50")
        .add_vertex("6").add_edge("4", "8").add_vertex("99"))
print(PVCUtils.is_path(graph, ["4"])) # True
static is_vertex_set_path(graph: reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph, vertices: Iterable[str]) → bool

Checks if the vertices form a path of length \(k\) in graph

Parameters

  • graph (UndirectedGraph) – Undirected graph

  • vertices (Set['str']) – Vertices to check if they form k path cover

Returns

Boolean

Example

from reoptimization_algorithms import PVCUtils, UndirectedGraph

graph = (UndirectedGraph().add_edge("4", "5").add_edge("40", "50")
         .add_vertex("6").add_edge("4", "8").add_vertex("99"))
print(PVCUtils.is_vertex_set_path(graph, {"4", "5", "8"})) # True