Repository: Qiskit/rustworkx (language: python)

Issue:
Add `is_semiconnected` function.
<!-- ⚠️ If you do not respect this template, your issue will be closed -->
<!-- ⚠️ Make sure to browse the opened and closed issues to confirm this idea does not exist. -->

### What is the expected enhancement?
A graph is semiconnected if, and only if, for any pair of nodes, either one is reachable from the other, or they are mutually reachable. 

For reference, see https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.is_semiconnected.html#networkx.algorithms.components.is_semiconnected

For the implementation, we can consider adapting `petgraph::condesation` function https://docs.rs/petgraph/0.6.0/petgraph/algo/fn.condensation.html. We can't use it directly since it only works with `petgraph::Graph` but we have a `petgraph::StableGraph` as our underlying graph data structure.





Discussion / hints:
Hey @georgios-ts !

Can you please tell where do we need to add this function, where are we going to use it ?

Hi, I was wondering if I could be assigned to this issue!
Of course, I've assigned the issue to you.

Fix patch:
diff --git a/releasenotes/notes/is-semi-connected-d4176b228aa62baf.yaml b/releasenotes/notes/is-semi-connected-d4176b228aa62baf.yaml
new file mode 100644
index 000000000..81e4baea1
--- /dev/null
+++ b/releasenotes/notes/is-semi-connected-d4176b228aa62baf.yaml
@@ -0,0 +1,5 @@
+---
+features:
+  - |
+    Added a new function, :func: `~rustworkx.is_semi_connected()` which will 
+    check if a :class: `~rustworkx.PyDiGraph` object is semi connected
\ No newline at end of file
diff --git a/rustworkx/__init__.pyi b/rustworkx/__init__.pyi
index 11edc5922..2732018bd 100644
--- a/rustworkx/__init__.pyi
+++ b/rustworkx/__init__.pyi
@@ -59,6 +59,7 @@ from .rustworkx import graph_bipartite_edge_color as graph_bipartite_edge_color
 from .rustworkx import connected_components as connected_components
 from .rustworkx import is_connected as is_connected
 from .rustworkx import is_weakly_connected as is_weakly_connected
+from .rustworkx import is_semi_connected as is_semi_connected
 from .rustworkx import number_connected_components as number_connected_components
 from .rustworkx import number_weakly_connected_components as number_weakly_connected_components
 from .rustworkx import node_connected_component as node_connected_component
diff --git a/rustworkx/rustworkx.pyi b/rustworkx/rustworkx.pyi
index 47c8e3673..c1964c35f 100644
--- a/rustworkx/rustworkx.pyi
+++ b/rustworkx/rustworkx.pyi
@@ -168,6 +168,7 @@ def graph_bipartite_edge_color(graph: PyGraph, /) -> dict[int, int]: ...
 def connected_components(graph: PyGraph, /) -> list[set[int]]: ...
 def is_connected(graph: PyGraph, /) -> bool: ...
 def is_weakly_connected(graph: PyDiGraph, /) -> bool: ...
+def is_semi_connected(graph: PyDiGraph, /) -> bool: ...
 def number_connected_components(graph: PyGraph, /) -> int: ...
 def number_weakly_connected_components(graph: PyDiGraph, /) -> bool: ...
 def node_connected_component(graph: PyGraph, node: int, /) -> set[int]: ...
diff --git a/src/connectivity/mod.rs b/src/connectivity/mod.rs
index eeddd109b..c3023d6d8 100644
--- a/src/connectivity/mod.rs
+++ b/src/connectivity/mod.rs
@@ -21,8 +21,9 @@ use super::{
 };
 
 use hashbrown::{HashMap, HashSet};
-
 use petgraph::algo;
+use petgraph::algo::condensation;
+use petgraph::graph::DiGraph;
 use petgraph::stable_graph::NodeIndex;
 use petgraph::unionfind::UnionFind;
 use petgraph::visit::{EdgeRef, IntoEdgeReferences, NodeCount, NodeIndexable, Visitable};
@@ -43,6 +44,7 @@ use crate::{EdgeType, StablePyGraph};
 use crate::graph::PyGraph;
 use rustworkx_core::coloring::two_color;
 use rustworkx_core::connectivity;
+use rustworkx_core::dag_algo::longest_path;
 
 /// Return a list of cycles which form a basis for cycles of a given PyGraph
 ///
@@ -266,6 +268,50 @@ pub fn is_weakly_connected(graph: &digraph::PyDiGraph) -> PyResult<bool> {
     Ok(weakly_connected_components(graph)[0].len() == graph.graph.node_count())
 }
 
+/// Check if the graph is semi connected
+///
+/// :param PyDiGraph graph: The graph to check if it is semi connected
+///
+/// :returns: Whether the graph is semi connected or not
+/// :rtype: bool
+///
+/// :raises NullGraph: If an empty graph is passed in
+#[pyfunction]
+#[pyo3(text_signature = "(graph, /)")]
+pub fn is_semi_connected(graph: &digraph::PyDiGraph) -> PyResult<bool> {
+    if graph.graph.node_count() == 0 {
+        return Err(NullGraph::new_err("Invalid operation on a NullGraph"));
+    }
+
+    let mut temp_graph = DiGraph::new();
+    let mut node_map = Vec::new();
+
+    for _node in graph.graph.node_indices() {
+        node_map.push(temp_graph.add_node(()));
+    }
+
+    for edge in graph.graph.edge_indices() {
+        let (source, target) = graph.graph.edge_endpoints(edge).unwrap();
+        temp_graph.add_edge(node_map[source.index()], node_map[target.index()], ());
+    }
+
+    let condensed = condensation(temp_graph, true);
+    let n = condensed.node_count();
+    let weight_fn =
+        |_: petgraph::graph::EdgeReference<()>| Ok::<usize, std::convert::Infallible>(1usize);
+
+    match longest_path(&condensed, weight_fn) {
+        Ok(path_len) => {
+            if let Some(path_len) = path_len {
+                Ok(path_len.1 == n - 1)
+            } else {
+                Ok(false)
+            }
+        }
+        Err(_) => Err(PyValueError::new_err("Graph could not be condensed")),
+    }
+}
+
 /// Return the adjacency matrix for a PyDiGraph object
 ///
 /// In the case where there are multiple edges between nodes the value in the
diff --git a/src/lib.rs b/src/lib.rs
index cce7c9175..91cc1c33c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -426,6 +426,7 @@ fn rustworkx(py: Python<'_>, m: &Bound<PyModule>) -> PyResult<()> {
     m.add_wrapped(wrap_pyfunction!(number_weakly_connected_components))?;
     m.add_wrapped(wrap_pyfunction!(weakly_connected_components))?;
     m.add_wrapped(wrap_pyfunction!(is_weakly_connected))?;
+    m.add_wrapped(wrap_pyfunction!(is_semi_connected))?;
     m.add_wrapped(wrap_pyfunction!(is_directed_acyclic_graph))?;
     m.add_wrapped(wrap_pyfunction!(digraph_is_isomorphic))?;
     m.add_wrapped(wrap_pyfunction!(graph_is_isomorphic))?;


Test patch:
diff --git a/tests/digraph/test_is_semi_connected.py b/tests/digraph/test_is_semi_connected.py
new file mode 100644
index 000000000..2cb909d28
--- /dev/null
+++ b/tests/digraph/test_is_semi_connected.py
@@ -0,0 +1,76 @@
+# Licensed under the Apache License, Version 2.0 (the "License"); you may
+# not use this file except in compliance with the License. You may obtain
+# a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations
+# under the License.
+
+import itertools
+import unittest
+
+import rustworkx
+import rustworkx.generators
+
+
+def naive_semi_connected(graph):
+    dists = rustworkx.floyd_warshall(graph)
+    for u, v in itertools.combinations(graph.node_indices(), 2):
+        if (u not in dists[v]) and (v not in dists[u]):
+            return False
+    return True
+
+
+class TestSemiConnected(unittest.TestCase):
+    def test_is_semi_connected_simple(self):
+        graph = rustworkx.PyDiGraph()
+        graph.add_nodes_from(list(range(3)))
+        graph.add_edge(0, 1, None)
+        graph.add_edge(1, 2, None)
+
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_false(self):
+        graph = rustworkx.PyDiGraph()
+        graph.add_nodes_from(list(range(3)))
+        graph.add_edge(0, 1, None)
+        graph.add_edge(2, 1, None)
+
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_single_node(self):
+        graph = rustworkx.PyDiGraph()
+        graph.add_node(0)
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_empty_graph(self):
+        graph = rustworkx.PyDiGraph()
+        with self.assertRaises(rustworkx.NullGraph):
+            rustworkx.is_semi_connected(graph)
+
+    def test_is_semi_connected_disconnected_graph(self):
+        graph = rustworkx.PyDiGraph()
+        graph.add_node(0)
+        graph.add_node(1)
+
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_directed_cycle_graph(self):
+        graph = rustworkx.generators.directed_cycle_graph(100)
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_directed_path_graph(self):
+        graph = rustworkx.generators.directed_path_graph(100)
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_directed_star_graph(self):
+        graph = rustworkx.generators.directed_star_graph(100)
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))
+
+    def test_is_semi_connected_directed_grid_graph(self):
+        graph = rustworkx.generators.directed_grid_graph(50, 50)
+        self.assertEqual(rustworkx.is_semi_connected(graph), naive_semi_connected(graph))