ratio_graph/

mdm.rs

//! # Multi-domain matrix module
//!
//! ## License
//!
//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
//! If a copy of the MPL was not distributed with this file,
//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
//!
//! **Code examples both in the docstrings and rendered documentation are free to use.**

use std::collections::{BTreeMap, BTreeSet};

use snafu::{OptionExt, ResultExt, Snafu};
use uuid::Uuid;

use crate::{EdgeStore, Graph, Meta, MetadataFilter, Node, NodeStore};

/// Multi-domain matrix error.
#[derive(Clone, Debug, Snafu)]
pub enum MdmError {
    /// No node on MDM with this id: {id}.
    NodeNotOnAxis { id: Uuid },
    /// NodeStore error.
    NodeStore { source: crate::node::NodeStoreError },
    /// EdgeStore error.
    EdgeStore { source: crate::edge::EdgeStoreError },
}

/// Whether any node of any kind should be selected independently or they should at least share one
/// edge with a supplied node kind.
#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum NodeSelectionMode {
    #[default]
    Independent,
    Dependent(BTreeSet<String>),
}

/// What to display for edges.
#[derive(Copy, Clone, Default, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum EdgeDisplayMode {
    #[default]
    Binary,
    Kinds,
    Labels,
    Weights,
}

/// How to divide the piecharts per edge.
#[derive(Copy, Clone, Default, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum EdgeDivisionMode {
    Absolute,
    #[default]
    Equal,
    Relative,
}

/// Node IDs as they should be displayed on the axis of an MDM for the given filters and settings.
pub fn mdm_axis_nodes(
    graph: &Graph,
    node_filter: &MetadataFilter,
    edge_filter: &MetadataFilter,
    root_ids: Option<&Vec<Uuid>>,
    node_depth: Option<usize>,
    node_selection_mode: &NodeSelectionMode,
) -> Result<Vec<Uuid>, MdmError> {
    let root_ids = root_ids
        .cloned()
        .unwrap_or_else(|| graph.root_ids().map(|id| id.to_owned()).collect());

    let node_kinds_vec = node_filter.kinds.clone().unwrap_or_else(|| {
        graph
            .node_aggregate()
            .kinds
            .keys()
            .map(|x| x.to_owned())
            .collect::<Vec<_>>()
    });
    let node_kind_order = node_kinds_vec
        .into_iter()
        .enumerate()
        .map(|(i, kind)| (kind, i))
        .collect::<BTreeMap<String, usize>>();

    // Split independent roots from dependent roots and sort them.
    let (mut ind_roots, mut dep_roots) =
        split_dependent_roots(graph, root_ids, node_selection_mode)?;

    ind_roots.sort_by_key(|id| {
        graph
            .get_node(id)
            .map(|n| node_kind_order.get(&n.get_meta().kind))
    });
    dep_roots.sort_by_key(|id| {
        graph
            .get_node(id)
            .map(|n| node_kind_order.get(&n.get_meta().kind))
    });

    // Get all leaf IDs for the independent roots.
    let ind_leaf_vec: Vec<Uuid> =
        independent_leafs(graph, &ind_roots, node_filter, node_depth).collect();

    // Early return if there are only independent roots.
    if node_selection_mode == &NodeSelectionMode::Independent {
        return Ok(ind_leaf_vec);
    }
    let mut result = ind_leaf_vec.clone();

    // Aggregate them in a set for filtering and sorting functions.
    let ind_leaf_set: BTreeSet<Uuid> = ind_leaf_vec.iter().copied().collect();

    // Get dependent leafs by further filtering after the independent leafs logic.
    let dep_leaf_iter =
        independent_leafs(graph, &dep_roots, node_filter, node_depth).filter(|&leaf_id| {
            let this = BTreeSet::from([leaf_id]);
            graph
                .edges_between_all(&this, &ind_leaf_set)
                .any(|e| edge_filter.satisfies(e))
                || graph
                    .edges_between_all(&ind_leaf_set, &this)
                    .any(|e| edge_filter.satisfies(e))
        });

    result.extend(dep_leaf_iter);

    Ok(result)
}

/// Expand a node in a MDM axis.
pub fn mdm_axis_expand(
    axis: &mut Vec<Uuid>,
    node_id: &Uuid,
    graph: &Graph,
    node_filter: &MetadataFilter,
    edge_filter: &MetadataFilter,
    node_selection_mode: &NodeSelectionMode,
) -> Result<(), MdmError> {
    let position = axis
        .iter()
        .position(|id| id == node_id)
        .with_context(|| NodeNotOnAxisSnafu { id: *node_id })?;

    let children = mdm_axis_children(
        axis,
        node_id,
        graph,
        node_filter,
        edge_filter,
        node_selection_mode,
    )?;

    axis.splice(position..position + 1, children);

    Ok(())
}

pub fn mdm_axis_children<'a>(
    axis: &[Uuid],
    node_id: &Uuid,
    graph: &'a Graph,
    node_filter: &'a MetadataFilter,
    edge_filter: &'a MetadataFilter,
    node_selection_mode: &NodeSelectionMode,
) -> Result<impl Iterator<Item = Uuid> + 'a, MdmError> {
    let children = graph
        .get_node_err(node_id)
        .with_context(|_| NodeStoreSnafu)?
        .children
        .iter()
        .filter(|&child_id| {
            graph
                .get_node(child_id)
                .map(|c| node_filter.satisfies(c))
                .unwrap_or_default()
        });
    let children: Box<dyn Iterator<Item = &Uuid>> = match node_selection_mode {
        NodeSelectionMode::Independent => Box::new(children),
        NodeSelectionMode::Dependent(kinds) => {
            let ind_leaf_set = axis
                .iter()
                .filter(|&id| {
                    graph
                        .get_node(id)
                        .map(|n| kinds.contains(&n.get_meta().kind))
                        .unwrap_or_default()
                })
                .copied()
                .collect::<BTreeSet<_>>();
            Box::new(children.filter(move |&child_id| {
                let this = BTreeSet::from([*child_id]);
                graph
                    .edges_between_all(&this, &ind_leaf_set)
                    .any(|e| edge_filter.satisfies(e))
                    || graph
                        .edges_between_all(&ind_leaf_set, &this)
                        .any(|e| edge_filter.satisfies(e))
            }))
        }
    };
    Ok(children.copied())
}

/// Collapse a node's children in an MDM axis.
pub fn mdm_axis_collapse(
    axis: &mut Vec<Uuid>,
    node_id: &Uuid,
    graph: &Graph,
) -> Result<(), MdmError> {
    let leaf_set = axis.iter().copied().collect::<BTreeSet<_>>();

    let mut to_replace = graph
        .descendant_ids(node_id, true, true, Some(&leaf_set), None)
        .filter_map(|id| id.ok())
        .filter(|&id| leaf_set.contains(id))
        .filter_map(|id| axis.iter().position(|e| e == id));

    if let Some(first) = to_replace.next() {
        let (start, end) =
            to_replace.fold((first, first), |(start, end), c| (start.min(c), end.max(c)));
        axis.splice(start..end + 1, [*node_id]);
    }

    Ok(())
}

/// Split dependent roots and independent roots into two separate vectors of IDs.
fn split_dependent_roots(
    graph: &Graph,
    root_ids: Vec<Uuid>,
    mode: &NodeSelectionMode,
) -> Result<(Vec<Uuid>, Vec<Uuid>), MdmError> {
    Ok(match mode {
        NodeSelectionMode::Independent => (root_ids, vec![]),
        NodeSelectionMode::Dependent(lead_kinds) => {
            let mut ind_roots = vec![];
            let mut dep_roots = vec![];
            for root_id in root_ids.into_iter() {
                if lead_kinds.contains(
                    graph
                        .get_node_err(&root_id)
                        .with_context(|_| NodeStoreSnafu)?
                        .kind(),
                ) {
                    ind_roots.push(root_id);
                } else {
                    dep_roots.push(root_id);
                }
            }
            (ind_roots, dep_roots)
        }
    })
}

/// Get relevant leaf node IDs in an independent fashion.
fn independent_leafs<'a>(
    graph: &'a Graph,
    root_ids: &'a [Uuid],
    node_filter: &'a MetadataFilter,
    node_depth: Option<usize>,
) -> impl Iterator<Item = Uuid> + 'a {
    root_ids.iter().flat_map(move |root_id| {
        let descendants: Box<dyn Iterator<Item = &Uuid>> = if node_depth == Some(0)
            || graph
                .get_node(root_id)
                .map(|r| r.is_leaf())
                .unwrap_or_default()
        {
            Box::new(Some(root_id).into_iter())
        } else {
            Box::new(
                graph
                    .descendant_ids(root_id, true, true, None, node_depth)
                    .filter_map(|id| id.ok()),
            )
        };
        descendants.filter_map(|id| {
            graph.get_node(id).and_then(|node| {
                if node_filter.satisfies(node) {
                    Some(*id)
                } else {
                    None
                }
            })
        })
    })
}

/// Do a typical display sorting of the given input node IDs.
pub fn display_sort(
    graph: &Graph,
    node_ids: &[Uuid],
    node_kind_order: Option<&BTreeMap<String, usize>>,
    leaf_ids: Option<&BTreeSet<Uuid>>,
) -> Vec<usize> {
    let mut nodes: Vec<(usize, &Node)> = node_ids
        .iter()
        .filter_map(|x| graph.get_node(x))
        .enumerate()
        .collect();
    nodes.sort_unstable_by_key(|&(_, node)| {
        (
            node_kind_order.map(|x| x.get(node.kind())),
            graph.node_width(node.id(), false, leaf_ids, None).unwrap(),
            node.name(),
            node.id(),
        )
    });
    nodes.into_iter().map(|x| x.0).collect()
}