|
From: notifies s. of c. c. <per...@li...> - 2007-03-05 22:50:47
|
Revision: 116
http://svn.sourceforge.net/perl-flat/?rev=116&view=rev
Author: estrabd
Date: 2007-03-05 14:50:48 -0800 (Mon, 05 Mar 2007)
Log Message:
-----------
modified acyclic path search to accept @goals nodes in addition to the src node
Modified Paths:
--------------
trunk/perl-flat/dev-scripts/all-strings-no-cycles.pl
trunk/perl-flat/dev-scripts/explode.pl
Modified: trunk/perl-flat/dev-scripts/all-strings-no-cycles.pl
===================================================================
--- trunk/perl-flat/dev-scripts/all-strings-no-cycles.pl 2007-03-05 04:52:51 UTC (rev 115)
+++ trunk/perl-flat/dev-scripts/all-strings-no-cycles.pl 2007-03-05 22:50:48 UTC (rev 116)
@@ -68,10 +68,7 @@
foreach my $symbol (@{$nodes{$startNode}{$adjacent}}) {
push(@string,$symbol);
acyclic($adjacent);
- if ($low{$startNode} > $low{$adjacent}) {
- $low{$startNode} = $low{$adjacent};
- }
- if ($dfa->is_accepting($adjacent)) {
+ if ($dfa->array_is_subset([$adjacent],[$dfa->get_accepting()])) { #< proof of concept
printf("%s\n",join('',@string));
}
pop(@string);
Modified: trunk/perl-flat/dev-scripts/explode.pl
===================================================================
--- trunk/perl-flat/dev-scripts/explode.pl 2007-03-05 04:52:51 UTC (rev 115)
+++ trunk/perl-flat/dev-scripts/explode.pl 2007-03-05 22:50:48 UTC (rev 116)
@@ -16,21 +16,6 @@
use FLAT::DFA;
use FLAT::Regex::WithExtraOps;
-# fucking A!
-# perl bdetest.pl "a&b&c&d" will give you all permutations ... once the transformations are done.
-# because it takes so darn long to do transformations, it it might be useful to have a native
-# interface to dumping a "frozen" DFA object to file...time to investigate
-
-print STDERR <<END;
-
- This example includes the serialization of the DFA object,
- so if the file exists, it will not go through the transformation again;
- In a basic sense, this is an example of compressing data - compare the
- size of the serialized object with a text file containing all strings stored
- in the DFA. The "compression" is even more extreme if you compare the size
- of the output'd text with the size of the actual regular expression.
-END
-
my $dfa;
#example:
use Storable;
@@ -55,11 +40,12 @@
my @string = ();
# anonymous, recursive function
-&acyclic($dfa->get_starting());
+&acyclic($dfa->get_starting(),$dfa->get_accepting()); #<-- accepts start node and set of possible goals
# this function finds all acyclic paths in the dfa for each symbol!!
sub acyclic {
my $startNode = shift;
+ my @goalNodes = @_;
# tree edge detection
if (!exists($dflabel{$startNode})) {
$dflabel{$startNode} = ++$lastDFLabel; # the order inwhich this link was explored
@@ -67,11 +53,8 @@
if (!exists($dflabel{$adjacent})) { # initial tree edge
foreach my $symbol (@{$nodes{$startNode}{$adjacent}}) {
push(@string,$symbol);
- acyclic($adjacent);
- if ($low{$startNode} > $low{$adjacent}) {
- $low{$startNode} = $low{$adjacent};
- }
- if ($dfa->is_accepting($adjacent)) {
+ acyclic($adjacent,@goalNodes);
+ if ($dfa->array_is_subset([$adjacent],[@goalNodes])) { #< proof of concept
printf("%s\n",join('',@string));
}
pop(@string);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|