Struct MaximumCommonEdgeSubgraph 

pub struct MaximumCommonEdgeSubgraph { /* private fields */ }

The Maximum Common Edge Subgraph problem.

Given two finite directed edge-labelled graphs G1 = (V1, E1) and G2 = (V2, E2), find a partial injective map f: U1 -> V2 with U1 subset.eq V1 that maximizes

|{(u, lambda, v) in E1 : u, v in U1 and (f(u), lambda, f(v)) in E2}|.

Configuration encoding

dims() returns vec![graph_2.num_vertices + 1; graph_1.num_vertices]. For each source vertex u in V1, config[u] is either an index in 0..graph_2.num_vertices (the matched target vertex) or the sentinel value graph_2.num_vertices denoting bottom (unmatched). Feasibility requires the matched values (everything not equal to the sentinel) to be pairwise distinct.

Implementations

impl MaximumCommonEdgeSubgraph

pub fn new(graph_1: LabelledDigraph, graph_2: LabelledDigraph) -> Self

Construct a new instance from two labelled digraphs.

pub fn graph_1(&self) -> &LabelledDigraph

Source graph G1.

pub fn graph_2(&self) -> &LabelledDigraph

Target graph G2.

pub fn num_vertices_1(&self) -> usize

Number of vertices in G1: |V1|.

pub fn num_vertices_2(&self) -> usize

Number of vertices in G2: |V2|.

pub fn num_arcs_1(&self) -> usize

Number of labelled arcs in G1: |E1|.

pub fn num_arcs_2(&self) -> usize

Number of labelled arcs in G2: |E2|.

pub fn bottom_index(&self) -> usize

Sentinel value encoding bottom (unmatched) for any config[u].

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

Check that config describes a partial injective map.

Validity requires: config.len() == |V1|, every entry lies in 0..=|V2| (with |V2| denoting bottom), and all entries strictly less than |V2| are pairwise distinct.

pub fn preserved_arc_count(&self, config: &[usize]) -> Option<usize>

Count the labelled arcs in G1 that are preserved by the partial injective map config. Returns None if config is infeasible.

Trait Implementations

impl Clone for MaximumCommonEdgeSubgraph

fn clone(&self) -> MaximumCommonEdgeSubgraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MaximumCommonEdgeSubgraph

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MaximumCommonEdgeSubgraph

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for MaximumCommonEdgeSubgraph

fn eq(&self, other: &MaximumCommonEdgeSubgraph) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Problem for MaximumCommonEdgeSubgraph

const NAME: &'static str = "MaximumCommonEdgeSubgraph"

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

type Value = Max<i64>

The evaluation value type.

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

Returns variant attributes derived from type parameters.

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

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

fn evaluate(&self, config: &[usize]) -> Max<i64>

Evaluate the problem on a configuration.

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 MaximumCommonEdgeSubgraph

type Result = ReductionMCESToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for MaximumCommonEdgeSubgraph

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 MaximumCommonEdgeSubgraph

impl Eq for MaximumCommonEdgeSubgraph

impl StructuralPartialEq for MaximumCommonEdgeSubgraph