home *** CD-ROM | disk | FTP | other *** search
/ PC Professionell 2004 December / PCpro_2004_12.ISO / files / webserver / tsw / TSW_3.4.0.exe / Apache2 / perl / Undirected.pm < prev    next >
Encoding:
Perl POD Document  |  1999-08-18  |  2.0 KB  |  113 lines
  1. package Graph::Undirected;
  2.  
  3. use strict;
  4. local $^W = 1;
  5.  
  6. use Graph::Base;
  7.  
  8. use vars qw(@ISA);
  9. @ISA = qw(Graph::Base);
  10.  
  11. use overload '""' => \&stringify;
  12.  
  13. =head1 NAME
  14.  
  15. Graph::Directed - directed graphs
  16.  
  17. =head1 SYNOPSIS
  18.  
  19.     use Graph::Directed;
  20.  
  21.     $g = new Graph::Directed;
  22.  
  23. =head1 DESCRIPTION
  24.  
  25. See Graph::Base for the available methods.
  26.  
  27. =head1 COPYRIGHT
  28.  
  29. Copyright 1999, O'Reilly & Associates.
  30.  
  31. This code is distributed under the same copyright terms as Perl itself.
  32.  
  33. =cut
  34.  
  35. # new
  36. #
  37. #    $U = Graph::Undirected->new(@V)
  38. #
  39. #    The Constructor.  Returns a new undirected graph $U, possibly
  40. #    populated with the optional initial vertices @V.
  41. #
  42. sub new {
  43.     my $class = shift;
  44.  
  45.     my $G = Graph::Base->new(@_);
  46.  
  47.     bless $G, $class;
  48.  
  49.     $G->directed(0);
  50.  
  51.     return $G;
  52. }
  53.  
  54. sub stringify {
  55.     my $G = shift;
  56.  
  57.     return $G->_stringify("=", ",");
  58. }
  59.  
  60. sub eq {
  61.     my ($G, $H) = @_;
  62.     
  63.     return ref $H ? $G->stringify eq $H->stringify : $G->stringify eq $H;
  64. }
  65.  
  66. # _edges
  67. #
  68. #    @e = $G->_edges($u, $v, $E)
  69. #
  70. #    (INTERNAL USE ONLY)
  71. #    Both vertices undefined:
  72. #        returns all the edges of the graph.
  73. #    Both vertices defined:
  74. #        returns all the edges between the vertices.
  75. #    Only 1st vertex defined:
  76. #        returns all the edges at the vertex.
  77. #    Only 2nd vertex defined:
  78. #        returns all the edges at the vertex.
  79. #    The already seen vertices are recorded in $E.
  80. #    Edges @e are returned as ($start_vertex, $end_vertex) pairs.
  81. #
  82. sub _edges {
  83.     my ($G, $u, $v, $E) = @_;
  84.     my @e;
  85.  
  86.     $E = { } unless defined $E;
  87.  
  88.     if (defined $u and defined $v) {
  89.     if (exists $G->{ Succ }->{ $u }->{ $v }) {
  90.         @e = ($u, $v)
  91.         if not $E->{ $u }->{ $v } and
  92.            not $E->{ $v }->{ $u };
  93.         $E->{ $u }->{ $v } = $E->{ $v }->{ $u } = 1;
  94.     }
  95.     } elsif (defined $u) {
  96.     foreach $v ($G->successors($u)) {
  97.         push @e, $G->_edges($u, $v);
  98.     }
  99.     } elsif (defined $v) {
  100.     foreach $u ($G->predecessors($v)) {
  101.         push @e, $G->_edges($u, $v);
  102.     }
  103.     } else {
  104.     foreach $u ($G->vertices) {
  105.         push @e, $G->_edges($u);
  106.     }
  107.     }
  108.  
  109.     return @e;
  110. }
  111.  
  112. 1;
  113.