network_graph 0.1.2

//! This module provides generic interfaces for network graphs. These interfaces are implemented
//! for the members of [crate::widget].

use std::any::type_name;
use std::collections::HashSet;
use std::error::Error;
use std::fmt::{Debug, Display};
use std::hash::Hash;

/// Marker trait for types that can be use as either a node or edge identifier.
pub trait Identifier: Eq + Ord + Hash + Clone + Debug {}

impl<T> Identifier for T where T: Eq + Ord + Hash + Clone + Debug {}

/// Error thrown when an attempt to remove a node fails due to the node having existing dependent
/// edges.
#[derive(Debug)]
pub struct RemainingConnectedEdgesError<EdgeIdentifier>(pub HashSet<EdgeIdentifier>)
where
    EdgeIdentifier: Identifier;

impl<EdgeIdentifier> Display for RemainingConnectedEdgesError<EdgeIdentifier>
where
    EdgeIdentifier: Identifier,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        return write!(
            f,
            "the node still has {} remaining edges connected",
            self.0.len()
        );
    }
}

impl<EdgeIdentifier> Error for RemainingConnectedEdgesError<EdgeIdentifier> where
    EdgeIdentifier: Identifier
{
}

/// Error thrown when an attempt to add an edge fails due to one of the edge's dependent ends not
/// existing.
#[derive(Debug)]
pub struct InvalidEdgeEndError<NodeIdentifier>(pub [Option<NodeIdentifier>; 2])
where
    NodeIdentifier: Identifier;

impl<NodeIdentifier> Display for InvalidEdgeEndError<NodeIdentifier>
where
    NodeIdentifier: Identifier,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        return write!(
            f,
            "the edge has {} ends tied to non-existent nodes",
            &self.0.iter().filter_map(|n| n.as_ref()).count()
        );
    }
}

impl<NodeIdentifier> Error for InvalidEdgeEndError<NodeIdentifier> where NodeIdentifier: Identifier {}

/// Trait that defines a node element within a graph structure.
pub trait Node {
    type Identifier: Identifier;

    fn identifier(&self) -> &Self::Identifier;
}

/// Trait that defines an edge element within a graph structure.
pub trait Edge<N>
where
    N: Node,
{
    type Identifier: Identifier;

    fn identifier(&self) -> &Self::Identifier;

    fn ends(&self) -> [N::Identifier; 2];
}

/// Trait that defines a graph structure.
pub trait Graph<N, E>
where
    N: Node,
    E: Edge<N>,
{
    /// Attempts to insert an edge into the graph.
    ///
    /// If there edge end ids are not represented as nodes in the graph, this will return in error.
    /// Otherwise, this will return an option possibly containing a replaced edge.
    fn insert_edge(&mut self, edge: E) -> Result<Option<E>, InvalidEdgeEndError<N::Identifier>>;

    /// Removes an edge from the graph.
    ///
    /// Returns an option containing the removed edge entry if the identified edge was present.
    fn remove_edge(&mut self, identifier: &E::Identifier) -> Option<E>;

    /// Inserts a node into the graph.
    ///
    /// Returns an option possibly containing a replaced node.
    fn insert_node(&mut self, node: N) -> Option<N>;

    /// Attempts to remove a node from the graph.
    fn remove_node(
        &mut self,
        identifier: &N::Identifier,
    ) -> Result<Option<N>, RemainingConnectedEdgesError<E::Identifier>>;

    /// Removes a node and all dependent edges from the graph.
    ///
    /// This implicitly depends on remove_node and remove_edge to work as excpted, otherwise it may
    /// panic.
    fn remove_node_with_edges(&mut self, identifier: &N::Identifier) -> Option<(N, Vec<E>)> {
        let removed_edges = match self.remove_node(identifier) {
            Ok(ret) => return ret.map(|ret| (ret, Vec::new())),
            Err(RemainingConnectedEdgesError(edges)) => {
                edges.iter().filter_map(|e| self.remove_edge(e)).collect()
            }
        };
        return self.remove_node(identifier)
                .expect(&format!(
                    "The implementation of either Graph::remove_node or Graph::remove_edge for {} does not behave as expected",
                    type_name::<Self>()
                )).map(|ret| (ret, removed_edges));
    }
}