Commit | Line | Data |
---|---|---|
86530b38 AT |
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; |