From 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 23 Dec 2022 00:36:31 +0800 Subject: 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. --- graph/src/lib.rs | 133 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 131 insertions(+), 2 deletions(-) (limited to 'graph/src/lib.rs') 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; + + /// 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 { + use std::collections::HashSet; + + let mut seen_nodes: HashSet = HashSet::with_capacity(self.nodes_len()); + + for node in self.nodes() { + if seen_nodes.contains(&node) { + continue; + } + + let mut edges_seen_nodes: HashSet = 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 = 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); } /// 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 GraphLabel for T {} +impl 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: Graph { /// /// The efficiency of this method matters in implementations. fn labels_of(&self, node_id: usize) -> Result, 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; } /// A labelled graph that can be extended, but not mutated, in the @@ -201,3 +294,39 @@ pub trait LabelExtGraph: LabelGraph { /// an error. fn extend(&mut self, edges: impl IntoIterator) -> Result; } + +#[cfg(test)] +mod test_cycle_detection { + use super::{builder::Builder, labelled::DLGBuilder, Graph}; + + #[test] + fn test() -> Result<(), Box> { + let mut builder: DLGBuilder = 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(()) + } +} -- cgit v1.2.3-18-g5258