renaming core to chain and some other changes

Some changes:

- The core crate is renamed to "chain".

- The crate "viz" is added, which will provide layered graph drawing
  algorithms.

- A function is added to convert from a grammar to the regular
  language of its left-linear closures.

- A function is added to convert from a nondeterministic finite
  automaton to its "null" closure.  A null closure is the same
  automaton with edges added, as if some edges are "null".  Whether an
  edge is null is determined by a function.
  Combined with the previous change, we can convert a grammar to the
  regular language of the null closure of its left-linear closures.

---

Now it remains to test more grammars and add an Atom trait, before
finishing the part about compilations.

1 files changed, 131 insertions, 2 deletions

diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 7b74ee1..2d23af3 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -8,6 +8,8 @@
 
 use std::hash::Hash;
 
+use core::fmt::{Debug, Display};
+
 pub mod error;
 
 pub mod adset;
@@ -22,6 +24,10 @@ pub mod labelled;
 
 pub use labelled::DLGraph;
 
+pub mod builder;
+
+pub use builder::Builder;
+
 use error::Error;
 
 /// The expected behaviour of an immutable graph.
@@ -101,6 +107,83 @@ pub trait Graph: Default {
     /// Return an error if either the source or the target is an
     /// invalid node.
     fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error>;
+
+    /// Output the edges into a graphviz file.
+    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let preamble = "digraph nfa {
+    fontname=\"Helvetica,Arial,sans-serif\"
+    node [fontname=\"Helvetica,Arial,sans-serif\"]
+    edge [fontname=\"Helvetica,Arial,sans-serif\"]
+    rankdir=LR;\n";
+
+        let mut post = String::new();
+
+        use std::fmt::Write as FWrite;
+
+        for (source, target) in self.edges() {
+            let _ = writeln!(post, "{source} -> {target}");
+        }
+
+        post.push_str("}\n");
+
+        let result = format!("{preamble}{post}");
+
+        if std::fs::metadata(filename).is_ok() {
+            std::fs::remove_file(filename)?;
+        }
+
+        let mut file = std::fs::File::options()
+            .write(true)
+            .create(true)
+            .open(filename)?;
+
+        use std::io::Write;
+
+        file.write_all(result.as_bytes())
+    }
+
+    /// Returns whether or not the graph contains cycles.
+    ///
+    /// If, and only if, the graph contains invalid nodes, an error
+    /// will be signalled.
+    fn contains_cycles(&self) -> Result<bool, Error> {
+        use std::collections::HashSet;
+
+        let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());
+
+        for node in self.nodes() {
+            if seen_nodes.contains(&node) {
+                continue;
+            }
+
+            let mut edges_seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());
+
+            let mut stack = Vec::with_capacity(self.nodes_len());
+            stack.push(node);
+
+            while let Some(top) = stack.pop() {
+                if edges_seen_nodes.contains(&top) {
+                    // a cycle is found
+                    return Ok(true);
+                }
+
+                edges_seen_nodes.insert(top);
+
+                let mut local_stack: Vec<usize> = self.children_of(top)?.collect();
+
+                local_stack.reverse();
+
+                stack.extend(local_stack);
+            }
+
+            seen_nodes.extend(edges_seen_nodes);
+        }
+
+        Ok(false)
+    }
+
+    /// Replace the contents of the graph by a builder.
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>);
 }
 
 /// A graph that can be extended, but not mutated, in the sense that
@@ -121,9 +204,15 @@ pub trait ExtGraph: Graph {
 }
 
 /// The type of labels should be comparable and hashable.
-pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {}
+pub trait GraphLabel:
+    Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug
+{
+}
 
-impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd> GraphLabel for T {}
+impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug> GraphLabel
+    for T
+{
+}
 
 /// A labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
@@ -182,6 +271,10 @@ pub trait LabelGraph<T: GraphLabel>: Graph {
     ///
     /// The efficiency of this method matters in implementations.
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>;
+
+    /// Return true if and only if the node has an edge with the given
+    /// label and target.
+    fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error>;
 }
 
 /// A labelled graph that can be extended, but not mutated, in the
@@ -201,3 +294,39 @@ pub trait LabelExtGraph<T: GraphLabel>: LabelGraph<T> {
     /// an error.
     fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error>;
 }
+
+#[cfg(test)]
+mod test_cycle_detection {
+    use super::{builder::Builder, labelled::DLGBuilder, Graph};
+
+    #[test]
+    fn test() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder: DLGBuilder<usize> = DLGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        // Link each node to its successor and link the last node with
+        // the first one to form a cycle.
+        for i in 0..5 {
+            builder.add_edge(i, if i < 4 { i + 1 } else { 0 }, i)?;
+        }
+
+        let graph = builder.build_ref();
+
+        assert_eq!(graph.contains_cycles()?, true);
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        let graph = builder.build();
+
+        assert_eq!(graph.contains_cycles()?, false);
+
+        Ok(())
+    }
+}