graphlang/

graphoperations.rs

use log::{debug, trace};
use rand::seq::IteratorRandom;
use rand::seq::SliceRandom;
use rand::thread_rng;

use crate::primitives::{Index, Label};
use crate::{Graph, Isomorphism, Node};
// TODO: Graph::neigbours(&Node<I,NL>)
// TODO: Isomorphism::can_be_safely_merged(&Isomorphism<I>)

/// Tries to find an partial isomorphism from `subgraph` to `graph`. `subgraph` can be a
/// disconnected graph. If `None` is returned if there is no mapping.
#[must_use]
pub fn match_subgraph<I: Index, NL: Label, EL: Label>(
    graph: &Graph<I, NL, EL>,
    subgraph: &Graph<I, NL, EL>,
) -> Option<Isomorphism<I>> {
    custom(graph, subgraph)
}

fn custom<I: Index, NL: Label, EL: Label>(
    graph: &Graph<I, NL, EL>,
    subgraph: &Graph<I, NL, EL>,
) -> Option<Isomorphism<I>> {
    // Random starting node from q_s
    let q_s = subgraph.nodes.iter().choose(&mut thread_rng())?;
    trace!("Starting matching with query node: {:?}", &q_s);
    // For every possible start ...
    for g_s in graph.nodes.iter().filter(|g| g.is_isomorph_to(q_s)) {
        trace!("Starting matching with graph node: {:?}", &g_s);
        let ret = custom_with_initial_nodes_2(graph, subgraph, q_s, g_s, &Isomorphism::default());
        if ret.is_some() {
            return ret;
        }
    }
    debug!("No partial isomorphism found");
    None
}

/// Combines two lists of nodes and returns all possible mappings, but neglect all nodes,
/// that are alerdy mapped (i.e. that are in isomorphism).
fn combine_neighbours<I: Index, NL: Label>(
    graph: &[Node<I, NL>],
    query: &[Node<I, NL>],
    isomorphism: &Isomorphism<I>,
) -> Isomorphism<I> {
    let mut iso = Isomorphism::default();
    for q in query {
        for g in graph {
            if q.is_isomorph_to(g)
                && !isomorphism.contains_nodeid_on_lhs(&q.id)
                && !isomorphism.contains_nodeid_on_rhs(&g.id)
            {
                iso.0.insert(q.id.clone(), g.id.clone());
            }
        }
    }
    iso
}

#[test]
fn combine_neighbours_simple() {
    let q = vec![Node {
        id: 1u32,
        label: "a",
    }];
    let g = vec![
        Node {
            id: 1u32,
            label: "a",
        },
        Node { id: 3, label: "a" },
    ];
    let possible_matches = combine_neighbours(&g, &q, &Isomorphism::default());
    let reference: Isomorphism<u32> = (&[(1, 1), (1, 3)]).into();
    assert_eq!(reference, possible_matches);
}

#[test]
fn combine_neighbours_with_filter() {
    let g = vec![
        Node {
            id: 1u32,
            label: "a",
        },
        Node { id: 3, label: "a" },
    ];
    let q = vec![Node {
        id: 1u32,
        label: "a",
    }];

    let possible_isomorphisms: Isomorphism<u32> = (&[(2, 0)]).into();

    let possible_matches = combine_neighbours(&g, &q, &possible_isomorphisms);
    let reference: Isomorphism<u32> = (&[(1, 1), (1, 3)]).into();
    assert_eq!(reference, possible_matches);

    let possible_matches = combine_neighbours(&q, &g, &possible_isomorphisms);
    let reference: Isomorphism<u32> = (&[(1, 1), (3, 1)]).into();
    assert_eq!(reference, possible_matches);
}

#[test]
fn combine_neighbours_with_filter_2() {
    let g: Vec<Node<u32, _>> = vec![
        Node { id: 0, label: "a" },
        Node { id: 2, label: "a" },
        Node { id: 3, label: "a" },
    ];
    let q: Vec<Node<u32, _>> = vec![Node { id: 0, label: "a" }, Node { id: 2, label: "a" }];

    let possible_isomorphisms: Isomorphism<u32> = (&[(1, 1)]).into();
    let possible_matches = combine_neighbours(&g, &q, &possible_isomorphisms);

    let reference: Isomorphism<u32> = (&[(0, 0), (0, 2), (0, 3), (2, 0), (2, 2), (2, 3)]).into();
    assert_eq!(reference, possible_matches);
}

/// For every mapping in the isomorphism the possible matches are explored
fn custom_explore_all_options_2<I: Index, NL: Label, EL: Label>(
    graph: &Graph<I, NL, EL>,
    subgraph: &Graph<I, NL, EL>,
    isomorphism: &Isomorphism<I>,
) -> Option<Isomorphism<I>> {
    //let (q_s, g_s) = possibilities.iter().choose(&mut thread_rng())?;
    let mut keys = isomorphism.0.keys().collect::<Vec<_>>();
    keys.shuffle(&mut thread_rng());

    let mut number_of_hopless_nodes = 0;
    for q in &keys {
        let q = *q;
        let g = isomorphism.0.get(q).unwrap();
        let g_potentials = graph.neighbours(g);
        let q_potentials = subgraph.neighbours(q);
        trace!("");
        trace!("     Used mapping {:?}", (&q, &g));
        trace!("      g neigbours {:?}", &g_potentials);
        trace!("      q neigbours {:?}", &q_potentials);
        trace!("limiting mappings {:?}", &isomorphism);
        let possible_matches = combine_neighbours(&g_potentials, &q_potentials, isomorphism);
        trace!(" possible_matches {:?}", &possible_matches);
        for (q_s, g_s) in &possible_matches.0 {
            let q_s = subgraph.get_node_by_id(q_s)?;
            let g_s = graph.get_node_by_id(g_s)?;
            let ret = custom_with_initial_nodes_2(graph, subgraph, q_s, g_s, isomorphism);
            if ret.is_some() {
                return ret;
            }
        }
        // It could also be a weird start
        if possible_matches.0.is_empty() {
            number_of_hopless_nodes += 1;
        }
    }
    if number_of_hopless_nodes != isomorphism.0.len() {
        return None;
    }
    // The query graph must be disconnected!

    // No connection possible -> Has to be disconnected ...
    let nodes_to_remove = isomorphism.0.keys().cloned().collect::<Vec<_>>();
    let reduced_query: Graph<I, NL, EL> = subgraph - &nodes_to_remove[..];
    if reduced_query.nodes.is_empty() {
        // ... or there is no isomorphism.
        trace!("This doesn't lead to anything ... we should go back.");
        return None;
    }
    trace!("Match found for connected subgraph, but the following graph'island' is still unmapped:\n{:?}", &reduced_query);
    // Find a new random start:
    let q_s = reduced_query.nodes.iter().choose(&mut thread_rng())?;
    let mut isomorphism = isomorphism.clone();
    for g_s in graph.nodes.iter().filter(|g| g.is_isomorph_to(q_s)) {
        let iso = Isomorphism::default();
        let ret = custom_with_initial_nodes_2(graph, &reduced_query, q_s, g_s, &iso)?;
        if isomorphism.can_be_safely_merged(&ret) {
            isomorphism.0.extend(ret.0);
            return Some(isomorphism.clone());
        }
    }
    // Still doesnt work. We are out of luck.
    trace!("Disconnected islands don't match. Back we go ...");
    None
}

fn custom_with_initial_nodes_2<I: Index, NL: Label, EL: Label>(
    graph: &Graph<I, NL, EL>,
    subgraph: &Graph<I, NL, EL>,
    q_s: &Node<I, NL>,
    g_s: &Node<I, NL>,
    isomorphism: &Isomorphism<I>,
) -> Option<Isomorphism<I>> {
    let mut isomorphism = isomorphism.clone();
    isomorphism.0.insert(q_s.id.clone(), g_s.id.clone());
    trace!("The current isomorphism reads       : {:?}", &isomorphism);
    if isomorphism.0.len() == subgraph.nodes.len() {
        debug!("(Sub-)Match found!");
        return Some(isomorphism);
    }

    custom_explore_all_options_2(graph, subgraph, &isomorphism)
}

/// Checks if the two given graphs are (totally) isomorphic to each other, by checking if there
/// exists a partial isomorphism from lhs to rhs and in the other direcetion. This function is
/// *very* expensive.
///
/// # Examples
///
/// ```
/// use graphlang::{Node,Edge,Graph,are_graphs_isomorph};
/// let graph_a = Graph {
///         nodes: vec![ Node::new(0u32, "a"), Node::new(1, "a") ],
///         edges: vec![ Edge::new_unlabeled(0, 1), ] };
/// let graph_b = Graph {
///         nodes: vec![ Node::new(10u32, "a"), Node::new(11, "a") ],
///         edges: vec![ Edge::new_unlabeled(10, 11), ] };
/// assert!(are_graphs_isomorph(&graph_a, &graph_b));
/// ```
#[must_use]
pub fn are_graphs_isomorph<I: Index, NL: Label, EL: Label>(
    lhs: &Graph<I, NL, EL>,
    rhs: &Graph<I, NL, EL>,
) -> bool {
    crate::match_subgraph(lhs, rhs).is_some() && crate::match_subgraph(rhs, lhs).is_some()
}

#[cfg(test)]
mod tests {
    //#[allow()]
    use super::*;
    use crate::Edge;

    #[test]
    fn simple_unique_match() {
        let _ = pretty_env_logger::try_init_timed();
        let graph = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let query = graph.clone();
        let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![(&[(0, 0), (1, 1)]).into()];
        let custom_iso =
            match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
        assert!(possible_isomorphisms.contains(&custom_iso));
    }

    #[test]
    fn trivial_disconnected_graphs() {
        let _ = pretty_env_logger::try_init_timed();
        let graph = Graph::<_, _, &str> {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
            edges: vec![],
        };
        let query = Graph::<_, _, &str> {
            nodes: vec![Node::new(10u32, "a"), Node::new(11, "b")],
            edges: vec![],
        };
        let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![(&[(10, 0), (11, 1)]).into()];
        let custom_iso =
            match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
        assert!(possible_isomorphisms.contains(&custom_iso));
    }

    #[test]
    fn simple_nonunique_match() {
        let _ = pretty_env_logger::try_init_timed();
        let graph = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "a"), Node::new(2, "b")],
            edges: vec![Edge::new_unlabeled(0, 2), Edge::new_unlabeled(1, 2)],
        };
        let query = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let possible_isomorphisms: Vec<Isomorphism<u32>> =
            vec![(&[(0, 0), (1, 2)]).into(), (&[(0, 1), (1, 2)]).into()];
        let custom_iso =
            match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
        assert!(possible_isomorphisms.contains(&custom_iso));
    }

    #[test]
    fn nonunique_match_with_cycles() {
        let graph = Graph {
            nodes: vec![
                Node::new(0u32, "a"),
                Node::new(1, "a"),
                Node::new(2, "a"),
                Node::new(3, "a"),
            ],
            edges: vec![
                Edge::new_unlabeled(0, 1),
                Edge::new_unlabeled(1, 2),
                Edge::new_unlabeled(1, 3),
                Edge::new_unlabeled(3, 0),
            ],
        };
        let query = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "a"), Node::new(2, "a")],
            edges: vec![Edge::new_unlabeled(0, 1), Edge::new_unlabeled(1, 2)],
        };
        let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![
            // Path connecting to 2
            (&[(0, 0), (1, 1), (2, 2)]).into(),
            (&[(0, 2), (1, 1), (2, 0)]).into(),
            // Circular path 1 - 2 - 3
            (&[(0, 0), (1, 1), (2, 3)]).into(),
            (&[(0, 1), (1, 3), (2, 0)]).into(),
            (&[(0, 3), (1, 0), (2, 1)]).into(),
            // Circular path 1 - 2 - 3 in other direction
            (&[(0, 3), (1, 1), (2, 0)]).into(),
            (&[(0, 0), (1, 3), (2, 1)]).into(),
            (&[(0, 1), (1, 0), (2, 3)]).into(),
        ];
        for _ in 0..60 {
            let custom_iso =
                match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
            log::info!("Found isormorphism  : {:#?}", custom_iso);
            assert!(possible_isomorphisms.contains(&custom_iso));
        }
    }
}