Struct SubgraphIsomorphism 

pub struct SubgraphIsomorphism { /* private fields */ }

The Subgraph Isomorphism problem.

Given a host graph G = (V_1, E_1) and a pattern graph H = (V_2, E_2), determine whether there exists an injective function f: V_2 -> V_1 such that for every edge {u,v} in E_2, {f(u), f(v)} is an edge in E_1.

This is a satisfaction (decision) problem: the metric is bool.

Configuration

A configuration is a vector of length |V_2| where each entry is a value in {0, …, |V_1|-1} representing the host vertex that each pattern vertex maps to. The configuration is valid (true) if:

1. All mapped host vertices are distinct (injective mapping)
2. Every edge in the pattern graph maps to an edge in the host graph

Example

use problemreductions::models::graph::SubgraphIsomorphism;
use problemreductions::topology::SimpleGraph;
use problemreductions::{Problem, Solver, BruteForce};

// Host: K4 (complete graph on 4 vertices)
let host = SimpleGraph::new(4, vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]);
// Pattern: triangle (K3)
let pattern = SimpleGraph::new(3, vec![(0,1),(0,2),(1,2)]);
let problem = SubgraphIsomorphism::new(host, pattern);

// Mapping [0, 1, 2] means pattern vertex 0->host 0, 1->1, 2->2
assert!(problem.evaluate(&[0, 1, 2]));

let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl SubgraphIsomorphism

pub fn new(host_graph: SimpleGraph, pattern_graph: SimpleGraph) -> Self

Create a new SubgraphIsomorphism problem.

Arguments

• host_graph - The host graph to search in
• pattern_graph - The pattern graph to find as a subgraph

pub fn host_graph(&self) -> &SimpleGraph

Get a reference to the host graph.

pub fn pattern_graph(&self) -> &SimpleGraph

Get a reference to the pattern graph.

pub fn num_host_vertices(&self) -> usize

Get the number of vertices in the host graph.

pub fn num_host_edges(&self) -> usize

Get the number of edges in the host graph.

pub fn num_pattern_vertices(&self) -> usize

Get the number of vertices in the pattern graph.

pub fn num_pattern_edges(&self) -> usize

Get the number of edges in the pattern graph.

pub fn is_valid_solution(&self, config: &[usize]) -> bool

Check if a configuration represents a valid subgraph isomorphism.

Trait Implementations

impl Clone for SubgraphIsomorphism

fn clone(&self) -> SubgraphIsomorphism

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SubgraphIsomorphism

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SubgraphIsomorphism

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for SubgraphIsomorphism

const NAME: &'static str = "SubgraphIsomorphism"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Or

The evaluation value type.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Or

Evaluate the problem on a configuration.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for SubgraphIsomorphism

type Result = ReductionSubIsoToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<SubgraphIsomorphism> for KClique<SimpleGraph>

type Result = ReductionKCliqueToSubIso

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl Serialize for SubgraphIsomorphism

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for SubgraphIsomorphism