use super::graph_dto::{CoreGraphDTO, GraphParts};
use crate::core::core_types::{
Edge, Node, NodeId, NodeName, Nodes, Orientation, Path, PathName, Sequence,
};
use crate::error::{PanGraphXError, PanResult};
use std::cmp::Ordering;
use std::collections::HashMap;
use std::sync::OnceLock;
#[derive(Debug, Clone)]
pub struct CoreGraph {
nodes: Nodes,
edges: Vec<Edge>,
paths: Vec<Path>,
path_index: HashMap<PathName, usize>,
node_name_map: Option<HashMap<NodeId, NodeName>>,
incident_edges: OnceLock<Vec<Vec<usize>>>,
}
impl CoreGraph {
#[must_use]
pub fn new(graph: CoreGraphDTO) -> Self {
let GraphParts {
nodes,
edges,
paths,
node_name_map,
} = GraphParts::from(graph);
Self {
incident_edges: OnceLock::new(),
path_index: index_paths(&paths),
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 incident_edge_indices(&self, node_id: NodeId) -> &[usize] {
self.incident_edges()
.get(node_id)
.map_or(&[], Vec::as_slice)
}
fn incident_edges(&self) -> &[Vec<usize>] {
self.incident_edges
.get_or_init(|| build_incident_edges(self.nodes.len(), &self.edges))
}
pub fn add_node(&mut self, sequence: Sequence, name: Option<NodeName>) -> NodeId {
self.nodes.push(sequence);
let node_id = self.nodes.len() - 1;
if let Some(incident) = self.incident_edges.get_mut() {
incident.push(Vec::new());
}
if let Some(node_name) = name {
self.node_name_map
.get_or_insert_with(HashMap::new)
.insert(node_id, node_name);
}
node_id
}
pub fn add_edge(&mut self, edge: Edge) -> PanResult<usize> {
self.check_node(edge.from_node)?;
self.check_node(edge.to_node)?;
let edge_idx = self.edges.len();
if let Some(incident) = self.incident_edges.get_mut() {
add_incident(incident, &edge, edge_idx);
}
self.edges.push(edge);
Ok(edge_idx)
}
pub fn add_path(&mut self, path: Path) -> PanResult<()> {
if self.path_index.contains_key(&path.name) {
return Err(PanGraphXError::InvalidGraph(format!(
"path {} already exists",
String::from_utf8_lossy(&path.name)
)));
}
self.check_steps(&path)?;
self.path_index.insert(path.name.clone(), self.paths.len());
self.paths.push(path);
Ok(())
}
pub fn remove_node(&mut self, node_id: NodeId) -> PanResult<()> {
self.check_node(node_id)?;
self.nodes.remove(node_id);
self.edges
.retain(|edge| edge.from_node != node_id && edge.to_node != node_id);
for edge in &mut self.edges {
if edge.from_node > node_id {
edge.from_node -= 1;
}
if edge.to_node > node_id {
edge.to_node -= 1;
}
}
self.incident_edges = OnceLock::new();
for path in &mut self.paths {
remove_steps_of(path, node_id)?;
}
self.paths.retain(|path| !path.steps.is_empty());
self.path_index = index_paths(&self.paths);
if let Some(names) = self.node_name_map.take() {
self.node_name_map = Some(
names
.into_iter()
.filter_map(|(id, name)| match id.cmp(&node_id) {
Ordering::Less => Some((id, name)),
Ordering::Equal => None,
Ordering::Greater => Some((id - 1, name)),
})
.collect(),
);
}
Ok(())
}
pub fn remove_edge(&mut self, edge_idx: usize) -> PanResult<()> {
if edge_idx >= self.edges.len() {
return Err(PanGraphXError::InvalidGraph(format!(
"edge index {edge_idx} is out of bounds"
)));
}
self.edges.remove(edge_idx);
self.incident_edges = OnceLock::new();
Ok(())
}
pub fn remove_path(&mut self, path_name: &[u8]) -> PanResult<()> {
let index = self
.path_index
.remove(path_name)
.ok_or_else(|| missing_path(path_name))?;
self.paths.remove(index);
for later in self.path_index.values_mut() {
if *later > index {
*later -= 1;
}
}
Ok(())
}
#[must_use]
pub const fn node_count(&self) -> usize {
self.nodes.len()
}
#[must_use]
pub const fn edge_count(&self) -> usize {
self.edges.len()
}
#[must_use]
pub const fn path_count(&self) -> usize {
self.paths.len()
}
pub fn get_node(&self, node_id: NodeId) -> PanResult<&Node> {
self.nodes.get(node_id).ok_or_else(|| missing_node(node_id))
}
pub fn set_sequence(&mut self, node_id: NodeId, sequence: Sequence) -> PanResult<()> {
*self
.nodes
.sequence_mut(node_id)
.ok_or_else(|| missing_node(node_id))? = sequence;
Ok(())
}
pub fn get_edge(&self, edge_idx: usize) -> PanResult<&Edge> {
self.edges.get(edge_idx).ok_or_else(|| {
PanGraphXError::InvalidGraph(format!("edge index {edge_idx} is out of bounds"))
})
}
pub fn get_path(&self, path_name: &[u8]) -> PanResult<&Path> {
self.path_index
.get(path_name)
.map(|&index| &self.paths[index])
.ok_or_else(|| missing_path(path_name))
}
pub fn replace_path(&mut self, path: Path) -> PanResult<Path> {
let index = *self
.path_index
.get(&path.name)
.ok_or_else(|| missing_path(&path.name))?;
self.check_steps(&path)?;
Ok(std::mem::replace(&mut self.paths[index], path))
}
pub fn get_outgoing_edges(&self, node_id: NodeId) -> PanResult<Vec<&Edge>> {
self.check_node(node_id)?;
Ok(self
.incident_edge_indices(node_id)
.iter()
.map(|&idx| &self.edges[idx])
.filter(|edge| edge.from_node == node_id)
.collect())
}
#[must_use]
pub fn has_edge(
&self,
from_node: NodeId,
from_orient: Orientation,
to_node: NodeId,
to_orient: Orientation,
) -> bool {
self.incident_edge_indices(from_node)
.iter()
.any(|&idx| self.edges[idx].is_link(from_node, from_orient, to_node, to_orient))
}
pub(crate) fn keep_only_paths(&mut self) {
self.edges = Vec::new();
self.incident_edges = OnceLock::new();
self.node_name_map = None;
}
fn check_node(&self, node_id: NodeId) -> PanResult<()> {
if node_id < self.nodes.len() {
Ok(())
} else {
Err(missing_node(node_id))
}
}
fn check_steps(&self, path: &Path) -> PanResult<()> {
path.steps
.iter()
.try_for_each(|step| self.check_node(step.node_id()))
}
}
fn build_incident_edges(node_count: usize, edges: &[Edge]) -> Vec<Vec<usize>> {
let mut incident = vec![Vec::new(); node_count];
for (i, edge) in edges.iter().enumerate() {
add_incident(&mut incident, edge, i);
}
incident
}
fn add_incident(incident: &mut [Vec<usize>], edge: &Edge, index: usize) {
incident[edge.from_node].push(index);
if edge.to_node != edge.from_node {
incident[edge.to_node].push(index);
}
}
fn index_paths(paths: &[Path]) -> HashMap<PathName, usize> {
paths
.iter()
.enumerate()
.map(|(index, path)| (path.name.clone(), index))
.collect()
}
fn remove_steps_of(path: &mut Path, node_id: NodeId) -> PanResult<()> {
if !path.steps.iter().any(|step| step.node_id() >= node_id) {
return Ok(());
}
let with_overlaps = !path.overlaps.is_empty();
let mut steps = Vec::with_capacity(path.steps.len());
let mut overlaps = Vec::new();
let mut previous: Option<usize> = None;
for (i, &step) in path.steps.iter().enumerate() {
let id = step.node_id();
if id == node_id {
continue;
}
if with_overlaps && let Some(p) = previous {
let adjacent = p + 1 == i;
overlaps.push(if adjacent {
path.overlaps.get(p).copied().unwrap_or(0)
} else {
0
});
}
steps.push(if id > node_id {
step.with_node_id(id - 1)?
} else {
step
});
previous = Some(i);
}
path.steps = steps;
path.overlaps = overlaps;
Ok(())
}
fn missing_node(node_id: NodeId) -> PanGraphXError {
PanGraphXError::InvalidGraph(format!("node {node_id} does not exist"))
}
fn missing_path(name: &[u8]) -> PanGraphXError {
PanGraphXError::InvalidGraph(format!(
"path {} does not exist",
String::from_utf8_lossy(name)
))
}
impl From<CoreGraph> for CoreGraphDTO {
fn from(graph: CoreGraph) -> Self {
Self::from_valid_parts(GraphParts {
nodes: graph.nodes,
edges: graph.edges,
paths: graph.paths,
node_name_map: graph.node_name_map,
})
}
}