graph_types/graphs/

mod.rs

use crate::{Edge, EdgeID, EdgeInsertID, EdgeQuery, GraphKind, NodeID};

pub mod weighted;
use crate::{edges::typed_edges::IndeterminateEdge, errors::GraphError, vertexes::NodeDegree};
use std::{
    mem::size_of,
    ops::{Deref, DerefMut},
};

pub mod named;

/// Represent a graph storage, with a set of nodes and edges.
///
/// # Examples
///
/// ```
/// use graph_theory::GraphEngine;
/// ```
#[allow(unused_variables)]
pub trait GraphEngine
where
    Self: Sized,
{
    /// According to a given vertex, find all neighbor nodes.
    /// See more in [Self::all_neighbors], [Self::all_incoming], [Self::all_outgoing].
    type NeighborIterator<'a>: DoubleEndedIterator<Item = NodeID>
    where
        Self: 'a;
    /// An iterator over the edges.
    type BridgeIterator<'a>: DoubleEndedIterator<Item = IndeterminateEdge>
    where
        Self: 'a;
    /// Traverse all nodes in the graph,
    /// note that this traversal is neither BFS nor DFS, but the most friendly traversal to the data structure.
    /// See more in [Self::all_nodes].
    type NodeTraverser<'a>: DoubleEndedIterator<Item = NodeID>
    where
        Self: 'a;
    /// An iterator over the edges.
    type EdgeTraverser<'a>: DoubleEndedIterator<Item = EdgeID>
    where
        Self: 'a;
    /// An iterator over the edges.
    type BridgeTraverser<'a>: DoubleEndedIterator<Item = IndeterminateEdge>
    where
        Self: 'a;

    /// Check the graph kind, it can be directed or undirected.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
    /// assert_eq!(CompleteGraph::one_way(5).get_node(6), false);
    /// ```
    fn graph_kind(&self) -> GraphKind;
    /// Check if the node exists, return the node id if exists.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
    /// assert_eq!(CompleteGraph::one_way(5).get_node(6), false);
    /// ```
    fn get_node(&self, node: NodeID) -> Result<NodeID, GraphError>;
    /// Traverse all nodes in the entire graph in the most friendly way to the data structure, and the order of this traversal is arbitrary.
    ///
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// let mut graph = CompleteGraph::one_way(5);
    /// assert_eq!(graph.all_nodes().count(), 20)
    /// ```
    fn all_nodes<'a>(&'a self) -> Self::NodeTraverser<'a>;
    /// Count the number of nodes in the graph.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).count_nodes(), 5);
    /// ```
    fn count_nodes<'a>(&'a self) -> usize {
        self.all_nodes().count()
    }
    /// Given a vertex, return all adjacent nodes.
    ///
    ///
    /// Return [None] if the node does not exist.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
    /// let graph = UnGraphAND::default();
    /// assert_eq!(graph.all_neighbors(5).count(), 5);
    /// ```
    fn all_neighbors<'a>(&'a self, node: NodeID) -> Self::NeighborIterator<'a>;
    /// Given a vertex as the starting point, return the ids corresponding to all ending points.
    ///
    /// In an undirected graph, it is equivalent to calling [Self::all_neighbors].
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
    /// let graph = UnGraphAND::default();
    /// assert_eq!(graph.all_outgoing(5).count(), 5);
    /// ```
    fn all_outgoing<'a>(&'a self, node: NodeID) -> Self::NeighborIterator<'a> {
        debug_assert!(self.graph_kind() == GraphKind::Undirected);
        self.all_neighbors(node)
    }
    /// Given a vertex as the ending point, return the ids corresponding to all starting points.
    ///
    /// In an undirected graph, it is equivalent to calling [Self::all_neighbors].
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
    /// let graph = UnGraphAND::default();
    /// assert_eq!(graph.all_incoming(5).count(), 5);
    /// ```
    fn all_incoming<'a>(&'a self, node: NodeID) -> Self::NeighborIterator<'a> {
        debug_assert!(self.graph_kind() == GraphKind::Undirected);
        self.all_neighbors(node)
    }
    /// Check if the node exists, return the node id if exists.
    ///
    /// Return [None] if the node does not exist.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).count_nodes(), 5);
    /// ```
    fn count_degree<'a>(&'a self, node: NodeID) -> NodeDegree {
        match self.graph_kind() {
            GraphKind::Directed => {
                NodeDegree::Directed { in_coming: self.all_incoming(node).count(), out_going: self.all_outgoing(node).count() }
            }
            GraphKind::Undirected => NodeDegree::Undirected { total: self.all_neighbors(node).count() },
        }
    }

    /// Check if the edge exists, return the node id if exists.
    ///
    /// At most one element will be returned, even if there are multiple edges with the same starting point and ending point.
    ///
    /// If you need to return all eligible edges, use [Self::get_bridges].
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
    /// assert_eq!(CompleteGraph::one_way(5).get_node(6), false);
    /// ```
    fn get_edge(&self, edge: EdgeID) -> Result<EdgeID, GraphError>;
    /// Traverse all edges in the entire graph in the most friendly way to the data structure, the order of traversal is arbitrary.
    ///
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// let mut graph = CompleteGraph::one_way(5);
    /// assert_eq!(graph.all_nodes().count(), 20)
    /// ```
    fn all_edges<'a>(&'a self) -> Self::EdgeTraverser<'a>;
    /// Count the number of edges in the graph.
    ///
    /// # Examples
    ///
    /// ```
    /// # use graph_theory::{GraphEngine};
    /// # use graph_theory::graph_engines::{CycleGraph, StarGraph, CompleteGraph};
    /// assert_eq!(CycleGraph::one_way(5).count_edges(), 5);
    /// assert_eq!(CycleGraph::two_way(5).count_edges(), 10);
    /// assert_eq!(StarGraph::one_way(5).count_edges(), 5);
    /// assert_eq!(StarGraph::two_way(5).count_edges(), 10);
    /// assert_eq!(CompleteGraph::one_way(5).count_edges(), 5);
    /// assert_eq!(CompleteGraph::one_way(5).count_edges(), 10);
    /// ```
    fn count_edges<'a>(&'a self) -> usize {
        self.all_edges().count()
    }
    fn get_bridge(&self, edge: EdgeID) -> Result<IndeterminateEdge, GraphError>;
    /// Give all edges matching the start and end points
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
    /// assert_eq!(CompleteGraph::one_way(5).get_node(6), false);
    /// ```
    fn get_bridges<'a>(&'a self, from: NodeID, goto: NodeID) -> Self::BridgeIterator<'a>;
    /// Get the edges of the graph.
    ///
    ///
    /// ```
    /// use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
    /// let mut graph = CompleteGraph::one_way(5);
    /// assert_eq!(graph.all_nodes().count(), 20)
    /// ```
    fn all_bridges<'a>(&'a self) -> Self::BridgeTraverser<'a>;
    /// Query the total space occupied by the structure, return 0 if failed to query
    ///
    /// Note that this volume contains garbage data, call [GraphEngine::shrink] at the right time to perform garbage collection.
    fn size_hint(&self) -> usize {
        size_of::<Self>()
    }
}

/// Mark a graph engine that can add and delete edges or points
pub trait MutableGraph: GraphEngine {
    /// Insert a node without any neighbors (edges).
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::AdjacencyNodeDict, GraphEngine};
    /// let mut graph = AdjacencyNodeDict::default();
    /// assert_eq!(graph.count_nodes(), 0);
    /// graph.insert_node(5);
    /// assert_eq!(graph.count_nodes(), 1);
    /// ```
    fn insert_node(&mut self, node_id: usize) -> bool;
    /// Insert a node without any neighbors (edges).
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::AdjacencyNodeDict, GraphEngine};
    /// let mut graph = AdjacencyNodeDict::default();
    /// assert_eq!(graph.count_nodes(), 0);
    /// graph.insert_node(5);
    /// assert_eq!(graph.count_nodes(), 1);
    /// ```
    fn create_node(&mut self) -> usize;

    /// Remove the given node.
    ///
    /// # Undefined Behavior
    ///
    /// - If the node has any edges, the behavior is undefined.
    ///
    /// It is recommended to remove all edges before removing the node, see [`GraphEngine::remove_node_with_edges`].
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::AdjacencyNodeDict, GraphEngine};
    /// let mut graph = AdjacencyNodeDict::default();
    /// assert_eq!(graph.count_nodes(), 0);
    /// graph.insert_node(5);
    /// assert_eq!(graph.count_nodes(), 1);
    /// ```
    fn remove_node(&mut self, node_id: usize) {
        self.remove_node_with_edges(node_id)
    }
    /// Remove the given node and all edges connected to it.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{graph_engines::AdjacencyNodeDict, GraphEngine};
    /// let mut graph = AdjacencyNodeDict::default();
    /// assert_eq!(graph.count_nodes(), 0);
    /// graph.insert_node(5);
    /// assert_eq!(graph.count_nodes(), 1);
    /// ```
    fn remove_node_with_edges(&mut self, node_id: usize);
    /// Insert a edge between two nodes.
    ///
    /// # Undefined Behaviors
    ///
    /// - If the nodes does not exist, the behavior is undefined.
    ///
    /// It is recommended to check the existence of the nodes before inserting the edge, see [`GraphEngine::insert_edge_with_nodes`].
    ///
    /// - Insert undirected edge to directed graph.
    ///
    /// Two edges will be inserted, but only return last edge's id.
    ///
    /// # Panics
    ///
    /// - No such ability
    ///
    /// Not all graph engine supports insert edge.
    ///
    /// - Insert disconnected edge
    ///
    /// Meaningless, don't do that.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::GraphEngine;
    /// ```
    fn insert_edge<E: Edge>(&mut self, edge: E) -> EdgeInsertID {
        self.insert_edge_with_nodes(edge)
    }
    /// Insert edge to graph, if the nodes does not exist, also insert them.
    ///
    /// # Panics
    ///
    /// - No such ability
    ///
    /// Not all graph engine supports insert edge.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::GraphEngine;
    /// ```
    fn insert_edge_with_nodes<E: Edge>(&mut self, edge: E) -> EdgeInsertID;
    /// Remove edge by given edge-id or start and end node-id.
    ///
    /// # Panics
    ///
    /// - No such ability
    ///
    /// Not all graph engine supports insert edge.
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::GraphEngine;
    /// ```
    fn remove_edge<E>(&mut self, edge: E)
    where
        E: Into<EdgeQuery>;

    /// Remove invalid edges and nodes to improve the efficiency of subsequent queries.
    fn shrink(&mut self) {}
}