gryf 0.2.1

//! Determine whether a graph is [connected].
//!
//! See available parameters [here](ConnectedBuilder#implementations).
//!
//! For directed graphs, the default behavior is weak connectivity, that is, the
//! connectivity is checked as if the graph was undirected. To determine
//! **strong connectivity**, see [ConnectedBuilder::strong] or
//! [is_strongly_connected].
//!
//! [connected]: https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
//!
//! # Examples
//!
//! ```
//! use gryf::{algo::is_connected, Graph};
//!
//! let mut graph = Graph::new_undirected();
//!
//! let a = graph.add_vertex("a");
//! let b = graph.add_vertex("b");
//! let c = graph.add_vertex("c");
//! let d = graph.add_vertex("d");
//!
//! graph.add_edge(a, b, ());
//! graph.add_edge(c, d, ());
//!
//! assert!(!is_connected(&graph));
//!
//! graph.add_edge(b, c, ());
//!
//! assert!(is_connected(&graph));
//! ```

use crate::core::{GraphBase, Neighbors, VertexSet, marker::Directed};

mod builder;
mod dfs;

pub use builder::ConnectedBuilder;

/// Information whether a graph or two vertices are connected.
///
/// See [module](self) documentation for more details and example.
pub struct Connected<G>
where
    G: GraphBase,
{
    disconnected_any: Option<(G::VertexId, G::VertexId)>,
    strong: bool,
}

impl<G> Connected<G>
where
    G: GraphBase,
{
    /// Returns `true` if the graph is connected.
    pub fn is(&self) -> bool {
        self.disconnected_any.is_none()
    }

    /// If the graph is not connected, returns a pair of vertices from
    /// disconnected components.
    pub fn disconnected_any(&self) -> Option<(&G::VertexId, &G::VertexId)> {
        self.disconnected_any.as_ref().map(|(u, v)| (u, v))
    }
}

impl<G> Connected<G>
where
    G: GraphBase<EdgeType = Directed>,
{
    /// Returns `true` if the connectivity corresponds to strong connectivity.
    pub fn strong(&self) -> bool {
        self.strong
    }

    /// Returns `true` if the connectivity was determined with directionality of
    /// the edges ignored.
    pub fn weak(&self) -> bool {
        !self.strong
    }
}

/// Returns `true` if the graph is connected.
///
/// Note that for directed graph, this function performs weak connectivity
/// check. For strong connectivity, use [is_strongly_connected].
pub fn is_connected<G>(graph: &G) -> bool
where
    G: Neighbors + VertexSet,
{
    Connected::on(graph).run().is()
}

/// Returns `true` if the graph is **strongly** connected.
pub fn is_strongly_connected<G>(graph: &G) -> bool
where
    G: GraphBase<EdgeType = Directed> + Neighbors + VertexSet,
{
    Connected::on(graph).strong().run().is()
}

/// Returns `true` if there is a path between given vertices.
pub fn is_path_between<G>(graph: &G, from: &G::VertexId, to: &G::VertexId) -> bool
where
    G: Neighbors + VertexSet,
{
    Connected::on(graph).between(from, to).run().is()
}

#[cfg(test)]
mod tests {
    use std::collections::HashSet;

    use proptest::prelude::*;

    use crate::{
        core::{
            GraphAdd,
            base::NeighborReference,
            id::{IdType, VertexId},
            marker::{Directed, Direction, Undirected},
        },
        infra::proptest::{graph_directed, graph_undirected},
        storage::AdjList,
        visit::VisitSet,
    };

    use super::*;

    fn assert_valid<G>(
        connected: Connected<G>,
        graph: &G,
        between: Option<(G::VertexId, G::VertexId)>,
    ) where
        G: Neighbors + VertexSet,
    {
        match connected.disconnected_any() {
            Some((u, v)) => {
                // Check that the vertices are indeed disconnected. Also check
                // if the given vertices are disconnected.
                for (u, v) in std::iter::once((u.clone(), v.clone())).chain(between.clone()) {
                    let mut visited = HashSet::with_capacity(graph.vertex_count());
                    let mut stack = vec![u.clone()];

                    while let Some(w) = stack.pop() {
                        assert!(
                            w != v,
                            "algorithm reported connected vertices as disconnected ({u:?}, {v:?})"
                        );

                        if visited.visit(w.clone()) {
                            for n in graph.neighbors_directed(&w, Direction::Outgoing) {
                                stack.push(n.id().into_owned());
                            }
                        }
                    }
                }
            }
            None => {
                // Check that the graph is indeed connected. We use undirected
                // algorithm which is simpler and therefore correct. This is
                // fine because connected graph in directed sense is also
                // connected in undirected sense. We are missing case in which
                // the algorithm determined that a directed graph is connected,
                // while it is not in directed sense, but is in undirected
                // sense.
                let mut visited = HashSet::with_capacity(graph.vertex_count());
                let start = match between {
                    Some((ref start, _)) => start.clone(),
                    None => match graph.vertices_by_id().next() {
                        Some(start) => start,
                        None => return,
                    },
                };
                let mut stack = vec![start];

                while let Some(u) = stack.pop() {
                    if visited.visit(u.clone()) {
                        for n in graph.neighbors_undirected(&u) {
                            stack.push(n.id().into_owned());
                        }
                    }
                }

                if let Some((_, to)) = between {
                    assert!(
                        visited.is_visited(&to),
                        "algorithm reported connected vertices while they are not"
                    )
                } else {
                    assert_eq!(
                        visited.visited_count(),
                        graph.vertex_count(),
                        "algorithm reported connected graph while it is not"
                    )
                }
            }
        }
    }

    #[test]
    fn connected_basic_undirected() {
        let mut graph = AdjList::<_, _, Undirected, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v1, &v2, ());

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
    }

    #[test]
    fn connected_basic_directed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v1, &v2, ());

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
    }

    #[test]
    fn connected_directed_reversed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v1, &v0, ());
        graph.add_edge(&v2, &v1, ());

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
    }

    #[test]
    fn disconnected_basic_undirected() {
        let mut graph = AdjList::<_, _, Undirected, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());

        let connected = Connected::on(&graph).run();
        assert!(!connected.is());
        assert_eq!(
            connected
                .disconnected_any()
                .map(|(u, v)| [u, v].contains(&&v2)),
            Some(true)
        );
    }

    #[test]
    fn disconnected_basic_directed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());

        let connected = Connected::on(&graph).run();
        assert!(!connected.is());
        assert_eq!(
            connected
                .disconnected_any()
                .map(|(u, v)| [u, v].contains(&&v2)),
            Some(true)
        );
    }

    #[test]
    fn strongly_connected_basic_directed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v1, &v2, ());
        graph.add_edge(&v2, &v0, ());

        let connected = Connected::on(&graph).strong().run();
        assert!(connected.is());
    }

    #[test]
    fn strongly_disconnected_basic_directed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v1, &v2, ());

        let connected = Connected::on(&graph).strong().run();
        assert!(!connected.is());
    }

    #[test]
    fn disconnected_directed_circles() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        let v3 = graph.add_vertex(());
        let v4 = graph.add_vertex(());
        let v5 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v1, &v2, ());
        graph.add_edge(&v2, &v0, ());

        graph.add_edge(&v3, &v4, ());
        graph.add_edge(&v4, &v5, ());
        graph.add_edge(&v5, &v3, ());

        let connected = Connected::on(&graph).run();
        assert!(!connected.is());
    }

    #[test]
    fn connected_directed() {
        let mut graph = AdjList::<_, _, Directed, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());
        graph.add_edge(&v2, &v1, ());

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
        assert!(connected.weak());
    }

    #[test]
    fn connected_between_disconnected_otherwise_undirected() {
        let mut graph = AdjList::<_, _, Undirected, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());

        let connected = Connected::on(&graph).between(&v0, &v1).run();
        assert!(connected.is());
    }

    #[test]
    fn disconnected_between_undirected() {
        let mut graph = AdjList::<_, _, Undirected, _>::default();

        let v0 = graph.add_vertex(());
        let v1 = graph.add_vertex(());
        let v2 = graph.add_vertex(());

        graph.add_edge(&v0, &v1, ());

        let connected = Connected::on(&graph).between(&v0, &v2).run();
        assert!(!connected.is());
        assert_eq!(connected.disconnected_any(), Some((&v0, &v2)));
    }

    #[test]
    fn connected_empty() {
        let graph = AdjList::<(), (), Undirected, _>::default();

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
    }

    #[test]
    fn connected_single() {
        let mut graph = AdjList::<_, (), Undirected, _>::default();

        graph.add_vertex(());

        let connected = Connected::on(&graph).run();
        assert!(connected.is());
    }

    #[test]
    fn connected_with_itself() {
        let mut graph = AdjList::<_, (), Undirected, _>::default();

        graph.add_vertex(());
        let v1 = graph.add_vertex(());
        graph.add_vertex(());

        let connected = Connected::on(&graph).between(&v1, &v1).run();
        assert!(connected.is());
    }

    proptest! {
        #[test]
        #[ignore = "run property-based tests with `cargo test proptest_ -- --ignored`"]
        fn proptest_connected_undirected_any(graph in graph_undirected(any::<()>(), any::<()>())) {
            let connected = Connected::on(&graph).run();
            assert_valid(connected, &graph, None);
        }

        #[test]
        #[ignore = "run property-based tests with `cargo test proptest_ -- --ignored`"]
        fn proptest_connected_directed_any(graph in graph_directed(any::<()>(), any::<()>())) {
            let connected = Connected::on(&graph).run();
            assert_valid(connected, &graph, None);
        }

        #[test]
        #[ignore = "run property-based tests with `cargo test proptest_ -- --ignored`"]
        fn proptest_connected_between_undirected_any(graph in graph_undirected(any::<()>(), any::<()>()), from: u64, to: u64) {
            let n = graph.vertex_count() as u64;
            prop_assume!(n > 0);

            let from = VertexId::from_bits(from % n);
            let to = VertexId::from_bits(to % n);
            let connected = Connected::on(&graph).between(&from, &to).run();
            assert_valid(connected, &graph, Some((from, to)));
        }

        #[test]
        #[ignore = "run property-based tests with `cargo test proptest_ -- --ignored`"]
        fn proptest_connected_between_directed_any(graph in graph_directed(any::<()>(), any::<()>()), from: u64, to: u64) {
            let n = graph.vertex_count() as u64;
            prop_assume!(n > 0);

            let from = VertexId::from_bits(from % n);
            let to = VertexId::from_bits(to % n);
            let connected = Connected::on(&graph).between(&from, &to).run();
            assert_valid(connected, &graph, Some((from, to)));
        }
    }
}