[13132] in Perl-Users-Digest
Perl-Users Digest, Issue: 542 Volume: 9
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Sun Aug 15 11:07:26 1999
Date: Sun, 15 Aug 1999 08:05:07 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Sun, 15 Aug 1999 Volume: 9 Number: 542
Today's topics:
Re: Can anyone help me please? <rick.delaney@home.com>
Re: containing results???confused <mcmike123@worldnet.att.net>
Re: HARASSMENT -- Monthly Autoemail (Jim Seymour)
Re: How to format string? <rick.delaney@home.com>
Re: How to format string? <Perl@astronomy.org.hk>
intel machines: what freebie compilers available? <paseymo@ix.netcom.com>
Re: intel machines: what freebie compilers available? (Greg Martin)
Re: Nastiness contrary to the spirit of perl? (Id Est)
Re: Nastiness contrary to the spirit of perl? <cmcurtin@interhack.net>
Re: Perl Programmers' Web Design "Difficulties" (Abigail)
Re: Perl Programmers' Web Design "Difficulties" (Abigail)
Perl/NT Problem (John Frank)
Re: Search algorithm in Perl (Benjamin Franz)
Re: search script in need of help <mcmike123@worldnet.att.net>
Re: Things my math teacher forgot to tell me (Benjamin Franz)
Re: tree structure (Abigail)
Re: while loop teminates too early <cmcurtin@interhack.net>
Re: Why use Perl when we've got Python?! <tchrist@mox.perl.com>
Digest Administrivia (Last modified: 1 Jul 99) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Sun, 15 Aug 1999 14:33:59 GMT
From: Rick Delaney <rick.delaney@home.com>
Subject: Re: Can anyone help me please?
Message-Id: <37B6CFBA.85C2CAA@home.com>
[posted & mailed]
andy wrote:
>
> I have a problem that reqires CGI to solve, I have tried to resolve this
> myself but I just can't seem to figure this whole CGI thing it out.
This is off-topic for this newsgroup since requiring CGI does not entail
requiring Perl. You might want to look for a group with 'cgi' in its
name.
> If anybody is prepared to help me sort this out for free, I can repay
> the favour by placing your Banner or a good link on all of the pages
> generated by the system.
This group is also not a place to come to for a handout or to offer
jobs. You might want to post to a group with 'jobs' in its name (or
'handout' if one exists).
--
Rick Delaney
rick.delaney@home.com
------------------------------
Date: Sun, 15 Aug 1999 10:28:54 -0400
From: "mike" <mcmike123@worldnet.att.net>
Subject: Re: containing results???confused
Message-Id: <7p6ipn$1m0$1@bgtnsc02.worldnet.att.net>
this is the error im getting
Can't locate LWP/Simple.pm in @INC (@INC contains:
/usr/local/lib/perl5/i386-freebsd/5.00404 /usr/local/lib/perl5
/usr/local/lib/perl5/site_perl/i386-freebsd /usr/local/lib/perl5/site_perl
.) at search.cgi line 12.
BEGIN failed--compilation aborted at search.cgi line 12.
does this help?
------------------------------
Date: 15 Aug 1999 14:05:30 GMT
From: jseymour@jimsun.LinxNet.com (Jim Seymour)
Subject: Re: HARASSMENT -- Monthly Autoemail
Message-Id: <7p6hfa$i3c$2@ink.msen.com>
In article <MPG.121fef56fe1efc159896b9@nntp1.ba.best.com>,
moseley@best.com (Bill Moseley) writes:
> Jim Seymour (jseymour@jimsun.LinxNet.com) seems to say...
[Over-quoting is a pain: snip]
>
> Even at my slow 56k modem speed it doesn't bug me THAT much to see an
> entire article quoted.
[snip]
>
> I don't feel like it's a huge waste of my time reading articles that
> aren't quoted properly....
[snip]
Ever try following a thread with lots of such badly-quoted
articles on DN lately? It's down-right *painful*. Even at
work, where I have a T1 connection and am running a Sparc
workstation.
Admittedly this is as much Deja's fault as that of the errant
posters--what with their pages having way more screen real
estate devoted to adverts and graphical garbage than the actual
articles, but still...
> ... But, I do find it a waste of my time trying
> weed out the interesting perl related articles from all the threads like
> this one.
Point taken. But IMO these are a bit easier to handle. You can
just ignore the entire thread based on the subject. Particularly
easy if you're using a newsreader with kill- file capability.
>
> I feel sorry for people that come here for real perl help only to have
> their questions lost in the noise.
Again: point taken. But the thing is: if the offending users
would first take the time to read the introductory articles to
UseNet, or even follow "corrective" posts or emails when they
make posting mistakes, there'd likely be a lot less of them. It
would also be nice if all news client apps would enforce at
least *minimal* guidelines regarding the ratio of quoted/new
lines. Mine does. And tho it's sometimes a pain, and I could
easily re-build the app to eliminate this, I think it's a Good
Idea. It keeps me honest :-).
Just my HO.
>
> Bring me another beer, bartender.
Now in this we're in total agreement :-).
This'll be my last post in this thread. It's wildly OT for the
newsgroup. You may have the last word, if you're so-inclined.
Regards,
Jim
--
Jim Seymour | PGP Public Key available at:
jseymour@jimsun.LinxNet.com | http://www.uk.pgp.net/pgpnet/pks-commands.html
http://home.msen.com/~jimsun | http://www.trustcenter.de/cgi-bin/SearchCert.cgi
------------------------------
Date: Sun, 15 Aug 1999 14:07:45 GMT
From: Rick Delaney <rick.delaney@home.com>
Subject: Re: How to format string?
Message-Id: <37B6C993.AFFD3D00@home.com>
[posted & mailed]
Thomas Tsoi wrote:
>
> > Chi Yu <chi@cybie.com> says...
> > >
> > > e.g. "212.67.198.54" would become "212067198054"
[snip 3 working solutions from Larry Rosler]
> why don't simply write
> $ip =~ s/\.//g;
WHWYTI (What happened when you tried it?)
Take the IP in Chi Yu's example and run it through each of Larry's
methods, observing each time how it results in the desired output.
Now do the same with yours.
Now you have an answer to your question.
P.S.
When posting untested code, it's customary to do so as a follow-up to
the querant. Then Larry will come along and correct you. It seems kind
of silly to wait for Larry to provide a correct solution first and
*then* post a wrong answer. :-)
The Jeopardy plague is mutating and spreading.
--
Rick Delaney
rick.delaney@home.com
------------------------------
Date: Sun, 15 Aug 1999 22:25:17 +0800
From: "Thomas Tsoi" <Perl@astronomy.org.hk>
Subject: Re: How to format string?
Message-Id: <7p6iib$fji$1@imsp009a.netvigator.com>
just a misunderstanding of the question, i guess it is not necessary for you
to be that arrogant.
Rick Delaney <rick.delaney@home.com> wrote in message
news:37B6C993.AFFD3D00@home.com...
> [posted & mailed]
>
> Thomas Tsoi wrote:
> >
> > > Chi Yu <chi@cybie.com> says...
> > > >
> > > > e.g. "212.67.198.54" would become "212067198054"
>
> [snip 3 working solutions from Larry Rosler]
>
> > why don't simply write
> > $ip =~ s/\.//g;
>
> WHWYTI (What happened when you tried it?)
>
> Take the IP in Chi Yu's example and run it through each of Larry's
> methods, observing each time how it results in the desired output.
>
> Now do the same with yours.
>
> Now you have an answer to your question.
>
> P.S.
>
> When posting untested code, it's customary to do so as a follow-up to
> the querant. Then Larry will come along and correct you. It seems kind
> of silly to wait for Larry to provide a correct solution first and
> *then* post a wrong answer. :-)
>
> The Jeopardy plague is mutating and spreading.
>
> --
> Rick Delaney
> rick.delaney@home.com
------------------------------
Date: Sun, 15 Aug 1999 10:19:38 +0100
From: Pauline Seymour <paseymo@ix.netcom.com>
Subject: intel machines: what freebie compilers available?
Message-Id: <ant150938b49#mt$@paseymo.ix.netcom.com>
I have bought myself a win98 laptop, would like to play with
some ideas using c, c++ (if I have to!), java and learn something
about perl. I've bought a book on perl but there is nothing like
trying it out. I (obviously) have downloaded Java from the Sun
site BUT are there any other freebie compilers around. I use
ANSI c (for its portability) at work and have used lots of other
languages on various other systems so am not looking for
"how to write programs" info BUT neither do I need great big
sooper-dooper IDEs because few programs are going to be
greater than a few hundred lines.
-------
Pauline
------------------------------
Date: Sun, 15 Aug 1999 14:34:30 GMT
From: gregm@netidea.com (Greg Martin)
Subject: Re: intel machines: what freebie compilers available?
Message-Id: <37b6ce69.3717688@news.netidea.com>
On Sun, 15 Aug 1999 10:19:38 +0100, Pauline Seymour
<paseymo@ix.netcom.com> wrote:
>I have bought myself a win98 laptop, would like to play with
>some ideas using c, c++ (if I have to!), java and learn something
>about perl. I've bought a book on perl but there is nothing like
>trying it out. I (obviously) have downloaded Java from the Sun
>site BUT are there any other freebie compilers around. I use
>ANSI c (for its portability) at work and have used lots of other
>languages on various other systems so am not looking for
>"how to write programs" info BUT neither do I need great big
>sooper-dooper IDEs because few programs are going to be
>greater than a few hundred lines.
>-------
>Pauline
>
There's quite a few of them around. I program on a UNIX machine and an
MSWindows machine and consequently like the cygwin package which gives
you a couple of compilers with a lot of the POSIX stuff as well as
ANSI. The compiler is gcc or egcs. They also have a smaller package.
You can check www.cygnus.com. You might check www.gnu.org and
www.delorie.com. Incidently this is a question often asked so you
might peruse the list for other answers. You can read the faq at
http://www.eskimo.com/~scs/C-faq/top.html
Regards,
Greg Martin.
------------------------------
Date: Sun, 15 Aug 1999 14:26:32 GMT
From: id-est@home.com (Id Est)
Subject: Re: Nastiness contrary to the spirit of perl?
Message-Id: <slrn7rdje1.b7n.id-est@erato.bigredrockeater.com>
In article <o7st3.4416$wC.107947@stones>, Jeffrey Roe wrote:
>I cannot believe that you plonked someone who appears to me to be one of the
>best perlers (?) that posts to this group. Having lurked in this group for
>last three weeks to try to learn about Perl and what it's used for and any
>Gotcha's for newbie's I can see that although Abigail may be a bit short
>with people who post silly questions she knows her Perl.
a BIT short? i've been on USENET for nearly 20 years and Abigail is one
of the worst offenders i've seen, short of complete yahoos like Plutonium
or Sternlight. i wouldn't work with with her or hire her. lots of people
are as good or better at perl.
------------------------------
Date: 15 Aug 1999 10:39:43 -0400
From: Matt Curtin <cmcurtin@interhack.net>
Subject: Re: Nastiness contrary to the spirit of perl?
Message-Id: <xlxwvux2jm8.fsf@gold.cis.ohio-state.edu>
>>>>> On Fri, 13 Aug 1999 16:07:29 GMT, geoff@access1.net (Geoff Joy) said:
Geoff> If you have the time to lurk and read this group, and if you
Geoff> have the time to post a response, then let it convey good
Geoff> information about Perl, not about your sense of humor
I'm afraid that Perl and a good, healthy sense of humor are
inseparable. If you believe otherwise, you might find a reread of the
Camel Book, documentation, and the Perl source code itself instructive.
Geoff> not about how smart you are,
I don't seem to recall many posts here where people proclaim their own
intelligence.
Geoff> not about how dumb the questioner is.
Nor do I see much in the way of "wow, you're dumb."
Perhaps my scoring mechanism is preventing me from seeing something.
What I have seen is a drastic increase in the number of people posting
without any intention of doing their own homework in the last year or
two. I strongly believe that we, by telling people where to go in
order to solve their own problems, reminding them to do their homework
before posting, etc., are doing them a favor.
What's really interesting is that when I was first starting to look at
Perl (in 1991), there wasn't anywhere near the amount of documentation
or example code that there is now. Discussion of Perl on the net,
though, was a lot more interesting; no one expected anyone to hand
them answers to things. The rule then is now the exception. The more
documentation that has been created, the more examples that are
available, the more that newbies expect to have handed to them.
Should we answer every newbie question directly, we would do nothing
more than spoonfeed the newbie, preventing him from gaining an
understanding of how to feed himself. Should we ignore such
questions, he would never learn to feed himself, either, but that
wouldn't matter, because he'd also starve in the short term.
A great deal of documentation has been written. A great deal of code
has been published. Allowing the newbie to operate as if these did
not exist would be cheating him out of the Perl Experience.
--
Matt Curtin cmcurtin@interhack.net http://www.interhack.net/people/cmcurtin/
------------------------------
Date: 15 Aug 1999 09:40:12 -0500
From: abigail@delanet.com (Abigail)
Subject: Re: Perl Programmers' Web Design "Difficulties"
Message-Id: <slrn7rdkcb.a5.abigail@alexandra.delanet.com>
Shawn Grant (tristar@direct.ca) wrote on MMCLXXIII September MCMXCIII in
<URL:news:682t3.48528$U42.82597@news1.rdc1.bc.home.com>:
&& I don't mean to make a sweeping generalization, but it
&& appears that the more advanced programmers can't seem
&& to create attractive web sites. Not that this is an insult...we
&& all have our strengths and weaknesses. Maybe it's a left/right
&& brain thing. Lets look at some examples:
&&
&& http://www.stonehenge.com
&& http://www.perl.org
&& http://www.tpj.com Perl Journal's was simple too, but now it forwards
&& to itknowledge.com (who probably staff web/graphic designers).
&& http://www.perl.com/CPAN
&&
&& To be fair, http://www.perl.com looks good, as does
&& http://www.activestate.com
The new www.perl.com is just plain ugly; and I seldomly go there. Only
if someone points me to a specific page. It looked a lot better when
www.perl.com was still done by Tom.
Abigail
--
perl -we 'print split /(?=(.*))/s => "Just another Perl Hacker\n";'
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----
------------------------------
Date: 15 Aug 1999 09:44:03 -0500
From: abigail@delanet.com (Abigail)
Subject: Re: Perl Programmers' Web Design "Difficulties"
Message-Id: <slrn7rdkjh.a5.abigail@alexandra.delanet.com>
Benjamin Franz (snowhare@long-lake.nihongo.org) wrote on MMCLXXIV
September MCMXCIII in <URL:news:aL5t3.494$bZ1.46109@typhoon01.swbell.net>:
``
`` Mmmmm...Living on *both* sides of the fence as I have for the last
`` five years, I have to disagree. Graphics and design are *part* of
`` effective communication. It is a fundamental error to believe
`` that presentation *can* be 100% seperated from content. In some
`` degree, presentation is *part* of content. Which is not to say
`` that I don't think it is a good thing to seperate content from
`` information *internally* for processing as much as possible. But
`` for human consumption - the two are inseperable. If you don't think
`` so - how about we start delivering your morning paper on microdots?
I have several blind friends. I don't think they agree with you.
Abigail
--
echo "==== ======= ==== ======"|perl -pes/=/J/|perl -pes/==/us/|perl -pes/=/t/\
|perl -pes/=/A/|perl -pes/=/n/|perl -pes/=/o/|perl -pes/==/th/|perl -pes/=/e/\
|perl -pes/=/r/|perl -pes/=/P/|perl -pes/=/e/|perl -pes/==/rl/|perl -pes/=/H/\
|perl -pes/=/a/|perl -pes/=/c/|perl -pes/=/k/|perl -pes/==/er/|perl -pes/=/./;
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----
------------------------------
Date: Sun, 15 Aug 1999 15:02:16 GMT
From: jwfrank@toad.net (John Frank)
Subject: Perl/NT Problem
Message-Id: <YDAt3.1364$%02.2260@newsfeed.slurp.net>
I am using Perl on a NT machine. What I want to do is
read in directories and subdirectories, to to each one, read in
a list of files and then modify some things in the file. The
problem lies, I think, in that after I get the directory/subdirectory
list Perl views the \ character as the Perl character vice the
NT directory separator. Any ideas on how I can modify the code below
to make this work?
John jwfrank@toad.net
print "Type in the full path of the directory you wish to use: ";
$SEARCHDIR = <>;
chomp $SEARCHDIR;
$SEARCHCMD = "dir/ad/s/b |";
$NEWSEARCH = "dir/b *.htm |";
chdir($SEARCHDIR);
open(DIRLIST, $SEARCHCMD);
while ($dir =<DIRLIST>){
open (INDIR, "<$dir") or warn "I could not open $dir\n";
** This is where the problem first occurs.
chdir "$dir" or die "I could not change directory\n";
open (LIST, $NEWSEARCH);
** I may have a similar problem here but it hasn't got this far yet.
while ($file = <LIST>) {
open (INFILE, "<$file") or warn "I could not open $file!\n";
open (TEMPOUT, ">tmpfile") or warn "I could not open tempout
file\n";
------------------------------
Date: Sun, 15 Aug 1999 14:17:13 GMT
From: snowhare@long-lake.nihongo.org (Benjamin Franz)
Subject: Re: Search algorithm in Perl
Message-Id: <JZzt3.1$Jv5.2796@typhoon01.swbell.net>
In article <7p4ras$ako$1@nnrp1.deja.com>, Dheera <dheera@usa.net> wrote:
>Thanks for your help guys. May I please make one more request - on the
>modules themselves? I tried to download the Search::InvertedIndex, or
>the DBFile modules, but they simply created Makefiles.
>
>I do not run Linux - I am running the Win32 version of Perl on Windows
>98. Could you please direct me on how to dissect the makefile to get
>the module working with Windows?
I'm not a Win32 expert, but it depends if you are running ActiveState
Perl or not. If you are, then you need to install DB_File and Digest::MD5
using 'ppm' (which came with your ActiveState install) first. Then
you will have to use 'nmake' to install using the Makefile for
Search::InvertedIndex.
Take a look at <URL:http://www.activestate.com/ActivePerl/docs/perl-win32/>
for questions on installing modules under their port of Perl.
--
Benjamin Franz
------------------------------
Date: Sun, 15 Aug 1999 10:31:19 -0400
From: "mike" <mcmike123@worldnet.att.net>
Subject: Re: search script in need of help
Message-Id: <7p6itp$25g$1@bgtnsc02.worldnet.att.net>
thank you for the help now i have the error
Can't locate LWP/Simple.pm in @INC (@INC contains:
/usr/local/lib/perl5/i386-freebsd/5.00404 /usr/local/lib/perl5
/usr/local/lib/perl5/site_perl/i386-freebsd /usr/local/lib/perl5/site_perl
.) at search.cgi line 12.
BEGIN failed--compilation aborted at search.cgi line 12.
does this mean all is lost and im doomed because i cant use the the
LWP/Simple.pm.
or is there another way?
Bart Lateur wrote in message <37b9c136.3211299@news.skynet.be>...
>mike wrote:
>
>>Thank you for the help, I don't have shell access at least for another
month
>>or so.
>>the server im running this on only allows ftp access.
>
>For debugging purposes, try putting this at the front of your CGI
>script:
>
> BEGIN {
> print "Content-type: text/plain\n\n";
> open STDERR, '>&STDOUT';
> $| = 1;
> }
>
>You'll see the results, and error messages, in the browser window as if
>the script was run from the shell.
>
> HTH,
> Bart.
------------------------------
Date: Sun, 15 Aug 1999 14:37:36 GMT
From: snowhare@long-lake.nihongo.org (Benjamin Franz)
Subject: Re: Things my math teacher forgot to tell me
Message-Id: <QgAt3.5$Jv5.9255@typhoon01.swbell.net>
In article <7p5h1s$v91$1@lublin.zrz.tu-berlin.de>,
Anno Siegel <anno4000@lublin.zrz.tu-berlin.de> wrote:
>John Callender <jbc@shell2.la.best.com> wrote in comp.lang.perl.misc:
>>Disclaimer: Nothing to do with Perl. Followups to that effect endured
>>silently, with head hung low.
>
>[snip reasonable questions]
>
>>This is silly, I know. But new immigrants often look silly as they try
>>to contend with the unfamiliar ways of their new environment. Like I
>>said, any pointers on how to address my remedial educational needs will
>>be appreciated.
>
>For an in-depth treatment of these things I still think Don Knuth,
>_The Art of Computer Programming_ contains all you want to know,
>probably all in the first volume.
[...]
A good side-document is 'The Jargon File',
<URL:http://www.tuxedo.org/~esr/jargon/>
--
Benjamin Franz
------------------------------
Date: 15 Aug 1999 09:35:01 -0500
From: abigail@delanet.com (Abigail)
Subject: Re: tree structure
Message-Id: <slrn7rdk2i.a5.abigail@alexandra.delanet.com>
Michael Masouras (m.masouras@on-board-info.com) wrote on MMCLXXIII
September MCMXCIII in <URL:news:934535498.6244.0.nnrp-13.c29fdfa7@news.demon.co.uk>:
$$ I have a table that represents a tree structure. The table is dynamic and
$$ there is no limit on the levels it can have.
$$
$$ It looks like this:
$$
$$ 1 2
$$ 2 9
$$ 9 4
$$
$$ If I have this in an array, how can I get all the relevant parents of a
$$ child?
$$ (e.g. I have $x = 4, how can I get 1, 2,9, 4)?
package Algorithm::Graphs::TransitiveClosure;
################################################################################
#
# $Author: abigail $
#
# $Date: 1999/03/01 21:10:02 $
#
# $Id: TransitiveClosure.pm,v 1.4 1999/03/01 21:10:02 abigail Exp abigail $
#
# $Log: TransitiveClosure.pm,v $
# Revision 1.4 1999/03/01 21:10:02 abigail
# Changed license.
#
# Revision 1.3 1999/03/01 19:51:11 abigail
# Renamed primary namespace to Algorithm::
#
# Revision 1.2 1998/03/23 04:00:37 abigail
# Fixed order of loop variables in the ARRAYREF case.
# It's k, i, j, not i, j, k.
#
# Revision 1.1 1998/03/22 06:54:42 abigail
# Initial revision
#
#
#
################################################################################
use strict;
use vars qw /$VERSION @ISA @EXPORT @EXPORT_OK/;
use Exporter;
@ISA = qw /Exporter/;
@EXPORT = qw //;
@EXPORT_OK = qw /floyd_warshall/;
($VERSION) = '$Revision: 1.4 $' =~ /(\d+\.\d+)/;
sub floyd_warshall ($) {
my $graph = shift;
if (ref $graph eq 'HASH') {
my @vertices = keys %{$graph};
foreach my $k (@vertices) {
foreach my $i (@vertices) {
foreach my $j (@vertices) {
# Don't use ||= here, to avoid autovivication.
$graph -> {$i} -> {$j} = 1 if $graph -> {$k} -> {$j} &&
$graph -> {$i} -> {$k};
}
}
}
}
elsif (ref $graph eq 'ARRAY') {
my $count = @{$graph};
for (my $k = 0; $k < $count; $k ++) {
for (my $i = 0; $i < $count; $i ++) {
for (my $j = 0; $j < $count; $j ++) {
$graph -> [$i] -> [$j] ||= $graph -> [$k] -> [$j] &&
$graph -> [$i] -> [$k];
}
}
}
}
$graph;
}
1;
__END__
=head1 NAME
Algorithms::Graphs::TransitiveClosure - Calculate the transitive closure.
=head1 SYNOPSIS
use Algorithms::Graphs::TransitiveClosure qw /floyd_warshall/;
my $graph = [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 0], [1, 0, 1, 1]];
floyd_warshall $graph;
print "There is a path from 2 to 0.\n" if $graph -> [2] -> [0];
my $graph2 = {one => {one => 1},
two => {two => 1, three => 1, four => 1},
three => {two => 1, three => 1},
four => {one => 1, four => 1}};
floyd_warshall $graph2;
print "There is a path from three to one.\n" if
$graph2 -> {three} -> {one};
=head1 DESCRIPTION
This is an implementation of the well known I<Floyd-Warshall> algorithm. [1,2]
The subroutine C<floyd_warshall> takes a directed graph, and calculates
its transitive closure, which will be returned. The given graph is
actually modified, so be sure to pass a copy of the graph to the routine
if you need to keep the original graph.
The subroutine takes graphs in one of the two following formats:
=over
=item floyd_warshall ARRAYREF
The graph I<G = (V, E)> is described with a list of lists, C<$graph>,
representing I<V x V>. If there is an edge between vertices C<$i> and
C<$j> (or if C<$i == $j>), then C<$graph -E<gt> [$i] -E<gt> [$j] == 1>. For all
other pairs C<($k, $l)> from I<V x V>, C<$graph -E<gt> [$k] -E<gt> [$l] == 0>.
The resulting C<$graph> will have C<$graph -E<gt> [$i] -E<gt> [$j] == 1> iff
C<$i == $j> or there is a path in I<G> from C<$i> to C<$j>, and
C<$graph -E<gt> [$i] -E<gt> [$j] == 0> otherwise.
=item floyd_warshall HASHREF
The graph I<G = (V, E)>, with labeled vertices, is described with
a hash of hashes, C<$graph>, representing I<V x V>. If there is an
edge between vertices C<$label1> and C<$label2> (or if C<$label1 eq $label2>),
then C<$graph -E<gt> {$label1} -E<gt> {$label2} == 1>. For all other pairs
C<($label3, $label4)> from I<V x V>, C<$graph -E<gt> {$label3} -E<gt> {$label4}>
does not exist.
The resulting C<$graph> will have
C<$graph -E<gt> {$label1} -E<gt> {$label2} == 1>
iff C<$label1 eq $label2> or there is a path in I<G> from
C<$label1> to C<$label2>, and C<$graph -E<gt> {$label1} -E<gt> {$label2}>
does not exist otherwise.
=back
=head1 EXAMPLES
my $graph = [[1, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 0],
[1, 0, 1, 1]];
floyd_warshall $graph;
foreach my $row (@$graph) {print "@$row\n"}
1 0 0 0
1 1 1 1
1 1 1 1
1 1 1 1
my $graph = {one => {one => 1},
two => {two => 1, three => 1, four => 1},
three => {two => 1, three => 1},
four => {one => 1, three => 1, four => 1}};
floyd_warshall $graph;
foreach my $l1 (qw /one two three four/) {
print "$l1: ";
foreach my $l2 (qw /one two three four/) {
next if $l1 eq $l2;
print "$l2 " if $graph -> {$l1} -> {$l2};
}
print "\n";
}
one:
two: one three four
three: one two four
four: one two three
=head1 COMPLEXITY
The running time of the algorithm is cubed in the number of vertices of the
graph. The author of this package is not aware of any faster algorithms,
nor of a proof if this is optimal. Note than in specific cases, when
the graph can be embedded on surfaces of bounded genus, or in the case
of sparse connection matrices, faster algorithms than cubed in the number
of vertices exist.
The space used by this algorithm is at most quadratic in the number of
vertices, which is optimal as the resulting transitive closure can have
a quadratic number of edges. In case when the graph is represented as a
list of lists, the quadratic bound will always be achieved, as the list
of lists already has that size. The hash of hashes however will use space
linear to the size of the resulting transitive closure.
=head1 LITERATURE
The Floyd-Warshall algorithm is due to Floyd [2], and based on a
theorem of Warshall [3]. The implemation of this package is based on an
implementation of Floyd-Warshall found in Cormen, Leiserson and Rivest [1].
=head1 REFERENCES
=over
=item [1]
Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
I<Introduction to Algorithms>. Cambridge: MIT Press, B<1990>.
ISBN 0-262-03141-8.
=item [2]
Robert W. Floyd: "Algorithm 97 (SHORTEST PATH)".
I<Communications of the ACM>, 5(6):345, B<1962>.
=item [3]
Stephan Warshall: "A theorem on boolean matrices."
I<Journal of the ACM>, 9(1):11-12, B<1962>.
=back
=head1 HISTORY
$Date: 1999/03/01 21:10:02 $
$Log: TransitiveClosure.pm,v $
Revision 1.4 1999/03/01 21:10:02 abigail
Changed license.
Revision 1.3 1999/03/01 19:51:11 abigail
Renamed primary namespace to Algorithm::
Revision 1.2 1998/03/23 04:00:37 abigail
Fixed order of loop variables in the ARRAYREF case.
It's k, i, j, not i, j, k.
Revision 1.1 1998/03/22 06:54:42 abigail
Initial revision
=head1 AUTHOR
This package was written by Abigail.
=head1 COPYRIGHT
Copyright 1998 by Abigail.
=head1 LICENSE
This package is free and open software.
You may use, copy, modify, distribute and sell this package or any
modifications there of in any form you wish, provided you do not do any
of the following:
- claim that any of the original code was written by someone
else than the original author(s).
- restrict someone in using, copying, modifying, distributing or
selling this program or module or any modifications of it.
THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
=cut
--
perl -we 'print q{print q{print q{print q{print q{print q{print q{print q{print
qq{Just Another Perl Hacker\n}}}}}}}}}' |\
perl -w | perl -w | perl -w | perl -w | perl -w | perl -w | perl -w | perl -w
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----
------------------------------
Date: 15 Aug 1999 10:53:08 -0400
From: Matt Curtin <cmcurtin@interhack.net>
Subject: Re: while loop teminates too early
Message-Id: <xlxu2q12izv.fsf@gold.cis.ohio-state.edu>
>>>>> On Thu, 12 Aug 1999 15:57:08 GMT,
bart.lateur@skynet.be (Bart Lateur) said:
Bart> All the problems were caused because Perl considers the string
Bart> "0" to be False. Nobody in his right mind would have thought any
Bart> string but the empty string could be considered False, but Perl
Bart> had a mind of it's own.
Do you think it is reasonable to consider the number 0 to be false?
If not, why?
If so, how do you propose telling the difference between "0" and 0?
Perl, after all, is a late-typing language, and whether you've got a
string or an integer cannot be determined until you apply some
operation to it (like eq or ==). In fact, the very same thing can be
an integer in one case and a string in another.
--
Matt Curtin cmcurtin@interhack.net http://www.interhack.net/people/cmcurtin/
------------------------------
Date: 15 Aug 1999 08:12:11 -0700
From: Tom Christiansen <tchrist@mox.perl.com>
Subject: Re: Why use Perl when we've got Python?!
Message-Id: <37b6cabb@cs.colorado.edu>
[courtesy cc of this posting mailed to cited author]
In comp.lang.perl.misc, abigail@delanet.com writes:
:That's all the significant C experience I have.
So much for the notion that you have to be a hot-shot C programmer
to learn Perl. :-)
--tom
--
if (instr(buf,sys_errlist[errno])) /* you don't see this */
--Larry Wall in eval.c from the 4.0 perl source code
------------------------------
Date: 1 Jul 99 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 1 Jul 99)
Message-Id: <null>
Administrivia:
The Perl-Users Digest is a retransmission of the USENET newsgroup
comp.lang.perl.misc. For subscription or unsubscription requests, send
the single line:
subscribe perl-users
or:
unsubscribe perl-users
to almanac@ruby.oce.orst.edu.
To submit articles to comp.lang.perl.misc (and this Digest), send your
article to perl-users@ruby.oce.orst.edu.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
To request back copies (available for a week or so), send your request
to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
where x is the volume number and y is the issue number.
The Meta-FAQ, an article containing information about the FAQ, is
available by requesting "send perl-users meta-faq" from
almanac@ruby.oce.orst.edu. The real FAQ, as it appeared last in the
newsgroup, can be retrieved with the request "send perl-users FAQ" from
almanac@ruby.oce.orst.edu. Due to their sizes, neither the Meta-FAQ nor
the FAQ are included in the digest.
The "mini-FAQ", which is an updated version of the Meta-FAQ, is
available by requesting "send perl-users mini-faq" from
almanac@ruby.oce.orst.edu.
For other requests pertaining to the digest, send mail to
perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
sending perl questions to the -request address, I don't have time to
answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V9 Issue 542
*************************************
