src/Graph/Undirected.pm

package Graph::Undirected;

use strict;
local $^W = 1;

use Graph::Base;

use vars qw(@ISA);
@ISA = qw(Graph::Base);

use overload '""' => \&stringify;

=head1 NAME

Graph::Directed - directed graphs

=head1 SYNOPSIS

    use Graph::Directed;

    $g = new Graph::Directed;

=head1 DESCRIPTION

See Graph::Base for the available methods.

=head1 COPYRIGHT

Copyright 1999, O'Reilly & Associates.

This code is distributed under the same copyright terms as Perl itself.

=cut

# new
#
#       $U = Graph::Undirected->new(@V)
#
#       The Constructor.  Returns a new undirected graph $U, possibly
#       populated with the optional initial vertices @V.
#
sub new {
    my $class = shift;

    my $G = Graph::Base->new(@_);

    bless $G, $class;

    $G->directed(0);

    return $G;
}

sub stringify {
    my $G = shift;

    return $G->_stringify("=", ",");
}

sub eq {
    my ($G, $H) = @_;
    
    return ref $H ? $G->stringify eq $H->stringify : $G->stringify eq $H;
}

# _edges
#
#       @e = $G->_edges($u, $v, $E)
#
#       (INTERNAL USE ONLY)
#       Both vertices undefined:
#               returns all the edges of the graph.
#       Both vertices defined:
#               returns all the edges between the vertices.
#       Only 1st vertex defined:
#               returns all the edges at the vertex.
#       Only 2nd vertex defined:
#               returns all the edges at the vertex.
#       The already seen vertices are recorded in $E.
#       Edges @e are returned as ($start_vertex, $end_vertex) pairs.
#
sub _edges {
    my ($G, $u, $v, $E) = @_;
    my @e;

    $E = { } unless defined $E;

    if (defined $u and defined $v) {
        if (exists $G->{ Succ }->{ $u }->{ $v }) {
            @e = ($u, $v)
                if not $E->{ $u }->{ $v } and
                   not $E->{ $v }->{ $u };
            $E->{ $u }->{ $v } = $E->{ $v }->{ $u } = 1;
        }
    } elsif (defined $u) {
        foreach $v ($G->successors($u)) {
            push @e, $G->_edges($u, $v);
        }
    } elsif (defined $v) {
        foreach $u ($G->predecessors($v)) {
            push @e, $G->_edges($u, $v);
        }
    } else {
        foreach $u ($G->vertices) {
            push @e, $G->_edges($u);
        }
    }

    return @e;
}

1;
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
#	Content
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;