| Revision: | 1.2 |
| Committed: | Fri Dec 10 13:41:40 2004 UTC (20 years, 4 months ago) by sashby |
| Content type: | text/plain |
| Branch: | MAIN |
| CVS Tags: | V1_1_7, V1_1_6, V1_1_5, V1_2_0-cand1, V1_1_4, V1_1_3, V1_1_2, V1_1_0_reltag8, V1_1_0_reltag7, V1_1_0_reltag6, V1_1_1, V1_1_0_reltag5, V1_1_0_reltag4, V1_1_0_reltag3, V1_1_0_reltag2, V1_1_0_reltag1, V1_1_0_reltag, V1_0_3-p4, V1_1_0_cand3, V1_1_0_cand2, V1_1_0_cand1, HEAD_SM_071214, forV1_1_0, v103_xml_071106, V1_0_3-p3, V1_0_3-p2, V1_1_0, v110p1, V110p6, V110p5, V110p4, V110p3, before110xmlBRmerge, V110p2, V110p1, V1_0_4p1, V1_0_3-p1, V1_0_3, V1_0_2, V1_0_2_p1, v102p1, V1_0_1, V1_0_0 |
| Branch point for: | forBinLess_SCRAM, HEAD_BRANCH_SM_071214, v200branch, v103_with_xml, v103_branch |
| Changes since 1.1: | +112 -0 lines |
| Log Message: | Merged V1_0 branch to HEAD |
| # | User | Rev | Content |
|---|---|---|---|
| 1 | sashby | 1.2 | 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; |