Menu
▾
▴
[Perl-flat-commit-notify] SF.net SVN: perl-flat: [97] trunk/perl-flat/lib
|
From: notifies s. of c. c. <per...@li...> - 2007-02-17 19:28:55
|
Revision: 97
http://svn.sourceforge.net/perl-flat/?rev=97&view=rev
Author: estrabd
Date: 2007-02-17 11:28:55 -0800 (Sat, 17 Feb 2007)
Log Message:
-----------
got as_undirected to work by avoiding the unset_start thing and it now looks like it works fine
Modified Paths:
--------------
trunk/perl-flat/lib/FLAT/DFA.pm
trunk/perl-flat/lib/FLAT/NFA.pm
trunk/perl-flat/lib/FLAT.pm
Modified: trunk/perl-flat/lib/FLAT/DFA.pm
===================================================================
--- trunk/perl-flat/lib/FLAT/DFA.pm 2007-02-17 00:20:43 UTC (rev 96)
+++ trunk/perl-flat/lib/FLAT/DFA.pm 2007-02-17 19:28:55 UTC (rev 97)
@@ -72,13 +72,13 @@
# this is meant to enforce 1 starting state for a DFA, but it is getting us into trouble
# when a DFA object calls unset_starting
-#sub unset_starting {
-# my $self = shift;
-# $self->SUPER::unset_starting(@_);
-# my $num = () = $self->unset_starting;
-# croak "DFA must have exactly one starting state"
-# if $num != 1;
-#}
+sub unset_starting {
+ my $self = shift;
+ $self->SUPER::unset_starting(@_);
+ my $num = () = $self->unset_starting;
+ croak "DFA must have exactly one starting state"
+ if $num != 1;
+}
sub trim_sinks {
my $self = shift;
Modified: trunk/perl-flat/lib/FLAT/NFA.pm
===================================================================
--- trunk/perl-flat/lib/FLAT/NFA.pm 2007-02-17 00:20:43 UTC (rev 96)
+++ trunk/perl-flat/lib/FLAT/NFA.pm 2007-02-17 19:28:55 UTC (rev 97)
@@ -211,46 +211,49 @@
# This format is just a undirected graph - so transition and state info is lost
sub as_undirected {
-# return "This function is not implemented yet because of weird problem...";
my $self = shift;
my @symbols = $self->alphabet();
my @states = $self->get_states();
- my @lines = ();
+ my %edges = ();
foreach (@states) {
my $s = $_;
- my @conns = ();
foreach (@symbols) {
my $a = $_;
# foreach state, get all nodes connected to it; ignore symbols and
# treat transitions simply as directed
- push(@conns,$self->successors($s,$a));
- push(@conns,$self->predecessors($s,$a)); #<-- something terribly wrong is going on here
+ push(@{$edges{$s}},$self->successors($s,$a));
+ foreach ($self->successors($s,$a)) {
+ push(@{$edges{$_}},$s);
+ }
}
- @conns = $self->array_unique(@conns);
- push(@lines,sprintf("%s (%s) %s",$s,($#conns+1),join(' ',@conns)));
}
- return sprintf("%s\n%s",($#states+1),join("\n",@lines));
-}
+ my @lines = (($#states+1));
+ foreach (sort{$a <=> $b;}(keys(%edges))) { #<-- iterate over numerically sorted list of keys
+ @{$edges{$_}} = sort {$a <=> $b;} $self->array_unique(@{$edges{$_}}); #<- make items unique and sort numerically
+ push(@lines,sprintf("%s (%s) %s",$_,($#{$edges{$_}}+1),join(' ',@{$edges{$_}})));
+ }
+ return join("\n",@lines);
+ }
# Format that Dr. Sukhamay KUNDU likes to use in his assignments :)
# This format is just a directed graph - so transition and state info is lost
-sub as_directed {
+sub as_digraph {
my $self = shift;
my @symbols = $self->alphabet();
my @states = $self->get_states();
my @lines = ();
foreach (@states) {
my $s = $_;
- my @conns = ();
+ my @edges = ();
foreach (@symbols) {
my $a = $_;
# foreach state, get all nodes connected to it; ignore symbols and
# treat transitions simply as directed
- push(@conns,$self->successors($s,$a));
+ push(@edges,$self->successors($s,$a));
}
- @conns = $self->array_unique(@conns);
- push(@lines,sprintf("%s (%s) %s",$s,($#conns+1),join(' ',@conns)));
+ @edges = sort {$a <=> $b;} $self->array_unique(@edges); #<- make items unique and sort numerically
+ push(@lines,sprintf("%s (%s) %s",$s,($#edges+1),join(' ',@edges)));
}
return sprintf("%s\n%s",($#states+1),join("\n",@lines));
}
Modified: trunk/perl-flat/lib/FLAT.pm
===================================================================
--- trunk/perl-flat/lib/FLAT.pm 2007-02-17 00:20:43 UTC (rev 96)
+++ trunk/perl-flat/lib/FLAT.pm 2007-02-17 19:28:55 UTC (rev 97)
@@ -67,9 +67,9 @@
dfa2gv
nfa2gv
pfa2gv
- dfa2directed
- nfa2directed
- pfa2directed
+ dfa2digraph
+ nfa2digraph
+ pfa2digraph
dfa2undirected
nfa2undirected
pfa2undirected
@@ -115,12 +115,12 @@
"dfa2gv 're1'" # dumps graphviz graph desc | see note[1]
"nfa2gv 're1'" # dumps graphviz graph desc | see note[1]
"pfa2gv 're1'" # dumps graphviz graph desc | see note[1]
- dfa2directed # dumps directed graph without transitions
- nfa2directed # dumps directed graph without transitions
- pfa2directed # dumps directed graph without transitions
- dfa2undirected #broken # dumps undirected graph without transitions
- nfa2undirected #broken # dumps undirected graph without transitions
- pfa2undirected #broken # dumps undirected graph without transitions
+ dfa2digraph # dumps directed graph without transitions
+ nfa2digraph # dumps directed graph without transitions
+ pfa2digraph # dumps directed graph without transitions
+ dfa2undirected # dumps undirected graph without transitions
+ nfa2undirected # dumps undirected graph without transitions
+ pfa2undirected # dumps undirected graph without transitions
random_pre
random_re
help
@@ -250,7 +250,7 @@
# dumps directed graph using Kundu notation
# Usage:
# perl -MFLAT -e "dfa2directed('a&b&c&d*e*')"
-sub dfa2directed {
+sub dfa2digraph {
shift;
use FLAT::Regex::WithExtraOps;
use FLAT::DFA;
@@ -260,12 +260,12 @@
if (@_)
{ foreach (@_)
{ my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa()->as_nfa()->as_dfa->as_min_dfa->trim_sinks();
- print $FA->as_directed;} }
+ print $FA->as_digraph;} }
else
{ while (<STDIN>)
{ chomp;
my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa()->as_nfa()->as_dfa->as_min_dfa->trim_sinks();
- print $FA->as_directed;}
+ print $FA->as_digraph;}
}
print "\n";
}
@@ -273,7 +273,7 @@
# dumps directed graph using Kundu notation
# Usage:
# perl -MFLAT -e "nfa2directed('a&b&c&d*e*')"
-sub nfa2directed {
+sub nfa2digraph {
shift;
use FLAT::Regex::WithExtraOps;
use FLAT::DFA;
@@ -282,12 +282,12 @@
if (@_)
{ foreach (@_)
{ my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa()->as_nfa();
- print $FA->as_directed;} }
+ print $FA->as_digraph;} }
else
{ while (<STDIN>)
{ chomp;
my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa()->as_nfa();
- print $FA->as_directed;}
+ print $FA->as_digraph;}
}
print "\n";
}
@@ -295,19 +295,19 @@
# dumps directed graph using Kundu notation
# Usage:
# perl -MFLAT -e "pfa2directed('a&b&c&d*e*')"
-sub pfa2directed {
+sub pfa2digraph {
shift;
use FLAT::Regex::WithExtraOps;
use FLAT::PFA;
if (@_)
{ foreach (@_)
{ my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa();
- print $FA->as_directed;} }
+ print $FA->as_digraph;} }
else
{ while (<STDIN>)
{ chomp;
my $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa();
- print $FA->as_directed;}
+ print $FA->as_digraph;}
}
print "\n";
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
