[Perl-flat-commit-notify] SF.net SVN: perl-flat: [108] trunk/perl-flat

[notifies s. of c. c. <per...@li...>]

Revision: 108
          http://svn.sourceforge.net/perl-flat/?rev=108&view=rev
Author:   estrabd
Date:     2007-02-26 19:01:37 -0800 (Mon, 26 Feb 2007)

Log Message:
-----------
prototype function emits all valid strings for all acyclic paths in the digraph ... on to handling cycles

Modified Paths:
--------------
    trunk/perl-flat/dev-scripts/bdetest.pl
    trunk/perl-flat/lib/FLAT/DFA.pm

Modified: trunk/perl-flat/dev-scripts/bdetest.pl
===================================================================
--- trunk/perl-flat/dev-scripts/bdetest.pl	2007-02-26 22:52:23 UTC (rev 107)
+++ trunk/perl-flat/dev-scripts/bdetest.pl	2007-02-27 03:01:37 UTC (rev 108)
@@ -3,9 +3,51 @@
 
 use lib qw(../lib);
 use FLAT::DFA;
-use FLAT::NFA;
-use FLAT::PFA;
 use FLAT::Regex::WithExtraOps;
 
 my $dfa = FLAT::Regex::WithExtraOps->new($ARGV[0])->as_pfa->as_nfa->as_dfa->as_min_dfa->trim_sinks;
-$dfa->acyclic();
+
+my %nodes = $dfa->as_node_list();
+
+my %dflabel       = ();    # "global" lookup table for dflable
+my %backtracked   = (); # "global" lookup table for backtracked edges
+my %low           = (); # "global" lookup table for low
+my $lastDFLabel   = 0;
+my $recurse_level = 0; # tracks recurse level
+my @string        = ();
+# anonymous, recursive function
+
+&acyclic($dfa->get_starting());
+
+# this function finds all acyclic paths in the dfa for each symbol!!
+sub acyclic {                            
+  my $startNode = shift;
+  $recurse_level++; # <- tracker
+# tree edge detection
+  if (!exists($dflabel{$startNode})) {
+    $dflabel{$startNode} = ++$lastDFLabel;  # the order inwhich this link was explored
+    $low{$startNode} = $lastDFLabel;
+    $backtracked{$startNode} = 0;           # marks this node as visited before - for cross edge detection
+    foreach my $adjacent (keys(%{$nodes{$startNode}})) {
+      if (!exists($dflabel{$adjacent})) {      # initial tree edge
+        foreach my $symbol (@{$nodes{$startNode}{$adjacent}}) {
+	  push(@string,$symbol);
+          acyclic($adjacent);
+          $backtracked{$adjacent}++;  # <- track backtracked nodes
+	  if ($low{$startNode} > $low{$adjacent}) {
+	    $low{$startNode} = $low{$adjacent};
+	  }	
+	  if ($dfa->is_accepting($adjacent)) {
+            printf("%s\n",join('',@string));
+	  }
+	  pop(@string);
+        }
+      }
+    } 
+  }
+  # remove startNode entry to facilitate acyclic path determination
+  delete($dflabel{$startNode});
+  $lastDFLabel--;
+  $recurse_level--; # <- tracker
+  return;     
+};

Modified: trunk/perl-flat/lib/FLAT/DFA.pm
===================================================================
--- trunk/perl-flat/lib/FLAT/DFA.pm	2007-02-26 22:52:23 UTC (rev 107)
+++ trunk/perl-flat/lib/FLAT/DFA.pm	2007-02-27 03:01:37 UTC (rev 108)
@@ -203,113 +203,6 @@
   return %node;
 }
 
-# finds all acyclic s->f paths (f \in F)
-sub acyclic {
-  my $self = shift;
-  # data structure to do dft over
-  my %nodes = $self->as_node_list();
-  my %dflabel  = ();    # "global" lookup table for dflable
-  my %backtracked = (); # "global" lookup table for backtracked edges
-  my %low         = (); # "global" lookup table for low
-  my $lastDFLabel = 0;
-  my $recurse_level = 0; # tracks recurse level
-  my @string = ();
-  # anonymous, recursive function
-  use Sub::Recursive;  
-  my $search = recursive {                            
-    my $startNode = shift;
-    $recurse_level++; # <- tracker
-# tree edge detection
-    if (!exists($dflabel{$startNode})) {
-      $dflabel{$startNode} = ++$lastDFLabel;  # the order inwhich this link was explored
-      $low{$startNode} = $lastDFLabel;
-      $backtracked{$startNode} = 0;           # marks this node as visited before - for cross edge detection
-      foreach my $adjacent (keys(%{$nodes{$startNode}})) {
-	if (!exists($dflabel{$adjacent})) {      # initial tree edge
-	  push(@string,$nodes{$startNode}{$adjacent}->[0]);
-          $REC->($adjacent);
-          $backtracked{$adjacent}++;  # <- track backtracked nodes
-	  if ($low{$startNode} > $low{$adjacent}) {
-	    $low{$startNode} = $low{$adjacent};
-	  }	
-	}
-	print join('',@string) if ($self->is_accepting($adjacent));
-        pop(@string);
-      } 
-    }
-    # remove startNode entry to facilitate acyclic path determination
-    delete($dflabel{$startNode});
-    $lastDFLabel--;
-    $recurse_level--; # <- tracker
-    return;     
-  };
-  # start the recursive dft search off
-  $search->($self->get_starting());
-  return;
-}
-
-# does a dft of digraph, but does not return a tree
-# incorporates strong component detection, which I
-# think might yield some interesting methods for 
-# generating valid strings
-sub depth_first {
-  my $self = shift;
-  # data structure to do dft over
-  my %nodes = $self->as_node_list();
-  my %dflabel  = ();    # "global" lookup table for dflable
-  my %backtracked = (); # "global" lookup table for backtracked edges
-  my %low         = (); # "global" lookup table for low
-  my $lastDFLabel = 0;
-  my $recurse_level = 0; # tracks recurse level
-  # anonymous, recursive function
-  use Sub::Recursive;  
-  my $search = recursive {                            
-    my $startNode = shift;
-    $recurse_level++; # <- tracker
-# tree edge detection
-    if (!exists($dflabel{$startNode})) {
-      $dflabel{$startNode} = ++$lastDFLabel;  # the order inwhich this link was explored
-      $low{$startNode} = $lastDFLabel;
-      $backtracked{$startNode} = 0;           # marks this node as visited before - for cross edge detection
-      foreach my $adjacent (keys(%{$nodes{$startNode}})) {
-        #printf("%s",$nodes{$startNode}{$adjacent}->[0]);
-	#print "" if ($self->is_accepting($adjacent));
-	if (!exists($dflabel{$adjacent})) {      # initial tree edge
-          print "tree edge! $startNode -> $adjacent"; # for testing only
-          $REC->($adjacent);
-	  print "Backtracking $adjacent -> $startNode";
-          # on back tracking, do the following
-          $backtracked{$adjacent}++;  # <- track backtracked nodes
-#	  print "$startNode -> $adjacent : $backtracked{$adjacent}";
-          # update LOW of $startNode
-	  if ($low{$startNode} > $low{$adjacent}) {
-	    $low{$startNode} = $low{$adjacent};
-	  }	
-	  # detect strong component 
-	  if ($low{$adjacent} == $dflabel{$adjacent}) { 
-	    print "STRONG COMPONENT";
-	  }
-# back edge detection
-	} elsif ($dflabel{$adjacent} < $dflabel{$startNode} && !exists($backtracked{$adjacent})) { # back edge
-           print "back edge! $startNode -> $adjacent";      
-# cross edge detection
-	} elsif ($backtracked{$adjacent}) {
-	    print "cross edge! $startNode -> $adjacent";
-	    # update low(startNode) with dflabel(adjacent) if low is greater than dflabel
-            if ($dflabel{$adjacent} < $low{$startNode}) {
-	      $low{$startNode} = $dflabel{$adjacent};
-	    }
-	}
-      } 
-    }
-    $recurse_level--; # <- tracker
-    return;     
-  };
-  # start the recursive dft search off
-  $search->($self->get_starting());
-  return;
-}
-
 1;
 
 __END__


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.