use super::core_types::{Edge, NodeId, NodeLabel, NodeName, Nodes, Path};
use crate::error::{PanGraphXError, PanResult};
use rayon::prelude::*;
use std::collections::{HashMap, HashSet};
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct GraphParts {
pub nodes: Nodes,
pub edges: Vec<Edge>,
pub paths: Vec<Path>,
pub node_name_map: Option<HashMap<NodeId, NodeName>>,
}
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct CoreGraphDTO {
nodes: Nodes,
edges: Vec<Edge>,
paths: Vec<Path>,
node_name_map: Option<HashMap<NodeId, NodeName>>,
}
impl TryFrom<GraphParts> for CoreGraphDTO {
type Error = PanGraphXError;
fn try_from(parts: GraphParts) -> PanResult<Self> {
if let Some(message) = invalid_reference(&parts) {
return Err(PanGraphXError::InvalidGraph(message));
}
Ok(Self::from_valid_parts(parts))
}
}
impl From<CoreGraphDTO> for GraphParts {
fn from(graph: CoreGraphDTO) -> Self {
Self {
nodes: graph.nodes,
edges: graph.edges,
paths: graph.paths,
node_name_map: graph.node_name_map,
}
}
}
impl CoreGraphDTO {
pub(crate) fn from_valid_parts(parts: GraphParts) -> Self {
let GraphParts {
nodes,
edges,
paths,
node_name_map,
} = parts;
Self {
nodes,
edges,
paths,
node_name_map,
}
}
#[must_use]
pub const fn nodes(&self) -> &Nodes {
&self.nodes
}
#[must_use]
pub const fn edges(&self) -> &[Edge] {
self.edges.as_slice()
}
#[must_use]
pub const fn paths(&self) -> &[Path] {
self.paths.as_slice()
}
#[must_use]
pub const fn node_name_map(&self) -> Option<&HashMap<NodeId, NodeName>> {
self.node_name_map.as_ref()
}
#[must_use]
pub fn node_label(&self, node_id: NodeId) -> NodeLabel<'_> {
self.node_name_map
.as_ref()
.and_then(|map| map.get(&node_id))
.map_or(NodeLabel::Id(node_id), |name| NodeLabel::Name(name))
}
}
fn invalid_reference(parts: &GraphParts) -> Option<String> {
let n = parts.nodes.len();
if let Some(edge) = parts
.edges
.par_iter()
.find_first(|e| e.from_node >= n || e.to_node >= n)
{
return Some(format!(
"edge {} -> {} refers to a missing node",
edge.from_node, edge.to_node
));
}
if let Some(message) = parts.paths.par_iter().find_map_first(|path| {
path.steps.iter().find(|s| s.node_id() >= n).map(|step| {
format!(
"path {} refers to missing node {}",
String::from_utf8_lossy(&path.name),
step.node_id()
)
})
}) {
return Some(message);
}
if let Some(id) = parts
.node_name_map
.as_ref()
.and_then(|map| map.keys().filter(|&&id| id >= n).min())
{
return Some(format!("node name given for missing node {id}"));
}
let mut names = HashSet::with_capacity(parts.paths.len());
parts
.paths
.iter()
.find(|path| !names.insert(path.name.as_slice()))
.map(|path| {
format!(
"duplicate path name {}",
String::from_utf8_lossy(&path.name)
)
})
}
#[cfg(test)]
impl CoreGraphDTO {
pub(crate) fn eq_by_node_names(&self, other: &Self) -> bool {
if self.nodes.len() != other.nodes.len()
|| self.edges.len() != other.edges.len()
|| self.paths.len() != other.paths.len()
{
return false;
}
let self_name_to_id: HashMap<NodeLabel<'_>, NodeId> = (0..self.nodes.len())
.map(|id| (self.node_label(id), id))
.collect();
let other_name_to_id: HashMap<NodeLabel<'_>, NodeId> = (0..other.nodes.len())
.map(|id| (other.node_label(id), id))
.collect();
if self_name_to_id.len() != self.nodes.len() || other_name_to_id.len() != other.nodes.len()
{
return false;
}
if self_name_to_id.len() != other_name_to_id.len() {
return false;
}
let mut id_mapping: HashMap<NodeId, NodeId> = HashMap::with_capacity(self.nodes.len());
for (name, &self_id) in &self_name_to_id {
let Some(&other_id) = other_name_to_id.get(name) else {
return false; };
if self.nodes[self_id].sequence != other.nodes[other_id].sequence {
return false; }
id_mapping.insert(self_id, other_id);
}
let other_edge_set: HashSet<&Edge> = other.edges.iter().collect();
let all_edges_match = self.edges.par_iter().all(|edge| {
let Some(&mapped_from) = id_mapping.get(&edge.from_node) else {
return false;
};
let Some(&mapped_to) = id_mapping.get(&edge.to_node) else {
return false;
};
let remapped = Edge {
from_node: mapped_from,
from_orient: edge.from_orient,
to_node: mapped_to,
to_orient: edge.to_orient,
overlap: edge.overlap,
};
other_edge_set.contains(&remapped)
});
if !all_edges_match {
return false;
}
let other_paths_by_name: HashMap<&[u8], &Path> =
other.paths.iter().map(|p| (p.name.as_slice(), p)).collect();
self.paths.par_iter().all(|self_path| {
let Some(other_path) = other_paths_by_name.get(self_path.name.as_slice()) else {
return false; };
if self_path.steps.len() != other_path.steps.len() {
return false;
}
self_path
.steps
.iter()
.zip(other_path.steps.iter())
.all(|(s, o)| {
let Some(&mapped_id) = id_mapping.get(&s.node_id()) else {
return false;
};
mapped_id == o.node_id() && s.orientation() == o.orientation()
})
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::core::core_types::{Orientation, Step};
fn parts(edge_to: NodeId, step_node: NodeId) -> GraphParts {
GraphParts {
nodes: Nodes::from_seq(vec![b"A".to_vec(), b"C".to_vec()]),
edges: vec![Edge {
from_node: 0,
from_orient: Orientation::Forward,
to_node: edge_to,
to_orient: Orientation::Forward,
overlap: 0,
}],
paths: vec![Path {
name: b"p".to_vec(),
steps: vec![Step::new(step_node, Orientation::Forward).unwrap()],
overlaps: Vec::new(),
}],
node_name_map: None,
}
}
fn rejection(parts: GraphParts) -> String {
match CoreGraphDTO::try_from(parts) {
Err(PanGraphXError::InvalidGraph(message)) => message,
other => panic!("expected InvalidGraph, got {other:?}"),
}
}
#[test]
fn valid_parts_round_trip() {
let graph = CoreGraphDTO::try_from(parts(1, 1)).unwrap();
assert_eq!(GraphParts::from(graph), parts(1, 1));
assert!(CoreGraphDTO::try_from(GraphParts::default()).is_ok());
}
#[test]
fn dangling_references_are_rejected() {
assert!(rejection(parts(2, 1)).contains("edge 0 -> 2"));
assert!(rejection(parts(1, 5)).contains("node 5"));
}
#[test]
fn names_of_missing_nodes_are_rejected() {
let mut bad = parts(1, 1);
bad.node_name_map = Some(HashMap::from([(0, b"a".to_vec()), (7, b"b".to_vec())]));
assert!(rejection(bad).contains("missing node 7"));
}
#[test]
fn duplicate_path_names_are_rejected() {
let mut bad = parts(1, 1);
bad.paths.push(bad.paths[0].clone());
assert!(rejection(bad).contains("duplicate path name p"));
}
}