This is Info file pm.info, produced by Makeinfo version 1.68 from the input file bigpm.texi.  File: pm.info, Node: GnuPG/Key, Next: GnuPG/Options, Prev: GnuPG/Interface, Up: Module List GnuPG Key Object **************** NAME ==== GnuPG::Key - GnuPG Key Object SYNOPSIS ======== # assumes a GnuPG::Interface object in $gnupg my @keys = $gnupg->get_public_keys( 'ftobin' ); # now GnuPG::PublicKey objects are in @keys DESCRIPTION =========== GnuPG::Key objects are generally not instantiated on their own, but rather used as a superclass of GnuPG::PublicKey, GnuPG::SecretKey, or GnuPG::SubKey objects. OBJECT METHODS ============== Initialization Methods ---------------------- new( *%initialization_args* ) This methods creates a new object. The optional arguments are initialization of data members; the initialization is done in a manner according to the method created as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. hash_init( *%args* ). This method works as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. short_hex_id This returns the commonly-used short, 8 character short hex id of the key. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, or `"object"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. length Number of bits in the key. algo_num They algorithm number that the Key is used for. hex_data The data of the key. hex_id The long hex id of the key. This is not the fingerprint nor the short hex id, which is 8 hex characters. creation_date_string =item expiration_date_string Formatted date of the key's creation and expiration. fingerprint A GnuPG::Fingerprint object. SEE ALSO ======== *Note GnuPG/Fingerprint: GnuPG/Fingerprint,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: GnuPG/Options, Next: GnuPG/PublicKey, Prev: GnuPG/Key, Up: Module List GnuPG options embodiment ************************ NAME ==== GnuPG::Options - GnuPG options embodiment SYNOPSIS ======== # assuming $gnupg is a GnuPG::Interface object $gnupg->options->armor( 1 ); $gnupg->options->push_recipients( 'ftobin', '0xABCD1234' ); DESCRIPTION =========== GnuPG::Options objects are generally not instantiated on their own, but rather as part of a GnuPG::Interface object. OBJECT METHODS ============== new( *%initialization_args* ) This methods creates a new object. The optional arguments are initialization of data members; the initialization is done in a manner according to the method created as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. hash_init( *%args* ). This method works as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. copy Returns a copy of this object. Useful for 'saving' options. get_args Returns a list of arguments to be passed to GnuPG based on data members which are 'meta_' options, regular options, and then extra_args, in that order. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"boolean"', *Note Class/MethodMaker: Class/MethodMaker,, `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, and `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. homedir armor textmode default_key no_greeting verbose no_verbose quiet batch always_trust comment status_fd logger_fd passphrase_fd compress_algo force_v3_sigs rfc1991 openpgp options no_options encrypt_to recipients These options correlate directly to many GnuPG options. For those that are boolean to GnuPG, simply that argument is passed. For those that are associated with a scalar, that scalar is passed passed as an argument appropriate. For those that can be specified more than once, such as recipients, those are considered lists and passed accordingly. Each are undefined or false to begin. Meta Options ------------ Meta options are those which do not correlate directly to any option in GnuPG, but rather are generally a bundle of options used to accomplish a specific goal, such as obtaining compatibility with PGP 5. The actual arguments each of these reflects may change with time. Each defaults to false unless otherwise specified. These options are being designed and to provide a non-GnuPG-specific abstraction, to help create compatibility with a possible PGP::Interface module. To help avoid confusion, methods with take a form of a key as an object shall be prepended with *_id(s)* if they only take an id; otherwise assume an object of type GnuPG::Key is required. meta_pgp_5_compatible If true, arguments are generated to try to be compatible with PGP 5.x. meta_pgp_2_compatible If true, arguments are generated to try to be compatible with PGP 2.x. meta_interactive If false, arguments are generated to try to help the using program use GnuPG in a non-interactive environment, such as CGI scripts. Default is true. meta_signing_key_id This scalar reflects the key used to sign messages. Currently this is synonymous with *default-key*. meta_signing_key This GnuPG::Key object reflects the key used to sign messages. meta_recipients_key_ids This list of scalar key ids are used to generate the appropriate arguments having these keys as recipients. meta_recipients_keys This list of keys of the type GnuPG::Key are used to generate the appropriate arguments having these keys as recipients. Other Data Members ------------------ extra_args This is a list of any other arguments used to pass to GnuPG. Useful to pass an argument not yet covered in this package. SEE ALSO ======== *Note GnuPG/Interface: GnuPG/Interface,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: GnuPG/PublicKey, Next: GnuPG/SecretKey, Prev: GnuPG/Options, Up: Module List GnuPG Public Key Objects ************************ NAME ==== GnuPG::PublicKey - GnuPG Public Key Objects SYNOPSIS ======== # assumes a GnuPG::Interface object in $gnupg my @keys = $gnupg->get_public_keys( 'ftobin' ); # now GnuPG::PublicKey objects are in @keys DESCRIPTION =========== GnuPG::PublicKey objects are generally instantiated through various methods of GnuPG::Interface. They embody various aspects of a GnuPG primary key. This package inherits data members and object methods from GnuPG::Key, which are not described here, but rather in *Note GnuPG/Key: GnuPG/Key,. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, or `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. user_ids A list of GnuPG::UserId objects associated with this key. subkeys A list of GnuPG::SubKey objects associated with this key. local_id GnuPG's local id for the key. owner_trust The scalar value GnuPG reports as the ownertrust for this key. See GnuPG's DETAILS file for details. SEE ALSO ======== *Note GnuPG/Key: GnuPG/Key,, *Note GnuPG/UserId: GnuPG/UserId,, *Note GnuPG/SubKey: GnuPG/SubKey,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: GnuPG/SecretKey, Next: GnuPG/Signature, Prev: GnuPG/PublicKey, Up: Module List GnuPG Secret Key Objects ************************ NAME ==== GnuPG::SecretKey - GnuPG Secret Key Objects SYNOPSIS ======== # assumes a GnuPG::Interface object in $gnupg my @keys = $gnupg->get_public_keys( 'ftobin' ); # now GnuPG::PublicKey objects are in @keys DESCRIPTION =========== GnuPG::SecretKey objects are generally instantiated through various methods of GnuPG::Interface. They embody various aspects of a GnuPG secret key. This package inherits data members and object methods from GnuPG::Key, which are not described here, but rather in *Note GnuPG/Key: GnuPG/Key,. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, or `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. user_ids A list of GnuPG::UserId objects associated with this key. subkeys A list of GnuPG::SubKey objects associated with this key. local_id GnuPG's local id for the key. owner_trust The scalar value GnuPG reports as the ownertrust for this key. See GnuPG's DETAILS file for details. SEE ALSO ======== *Note GnuPG/Key: GnuPG/Key,, *Note GnuPG/UserId: GnuPG/UserId,, *Note GnuPG/SubKey: GnuPG/SubKey,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: GnuPG/Signature, Next: GnuPG/SubKey, Prev: GnuPG/SecretKey, Up: Module List GnuPG Key Signature Objects *************************** NAME ==== GnuPG::Signature - GnuPG Key Signature Objects SYNOPSIS ======== # assumes a GnuPG::SubKey object in $key my $signing_id = $key->signature->hex_id(); DESCRIPTION =========== GnuPG::Signature objects are generally not instantiated on their own, but rather as part of GnuPG::Key objects. They embody various aspects of a GnuPG signature on a key. OBJECT METHODS ============== new( *%initialization_args* ) This methods creates a new object. The optional arguments are initialization of data members; the initialization is done in a manner according to the method created as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, or `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. algo_num The number of the algorithm used for the signature. hex_id The hex id of the signing key. user_id_string The first user id string on the key that made the signature. This may not be defined if the signing key is not on the local keyring. date_string The formatted date the signature was performed on. SEE ALSO ======== See also *Note Class/MethodMaker: Class/MethodMaker,.  File: pm.info, Node: GnuPG/SubKey, Next: GnuPG/Tie, Prev: GnuPG/Signature, Up: Module List GnuPG Sub Key objects ********************* NAME ==== GnuPG::SubKey - GnuPG Sub Key objects SYNOPSIS ======== # assumes a GnuPG::PublicKey object in $key my @subkeys = $key->subkeys(); # now GnuPG::SubKey objects are in @subkeys DESCRIPTION =========== GnuPG::SubKey objects are generally instantiated through various methods of GnuPG::Interface. They embody various aspects of a GnuPG sub key. This package inherits data members and object methods from GnuPG::Key, which are not described here, but rather in *Note GnuPG/Key: GnuPG/Key,. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, or `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. validity A scalar holding the value GnuPG reports for the trust of authenticity (a.k.a.) validity of a key. See GnuPG's DETAILS file for details. local_id GnuPG's local id for the key. owner_trust The scalar value GnuPG reports as the ownertrust for this key. See GnuPG's DETAILS file for details. signature A GnuPG::Signature object holding the representation of the signature on this key. SEE ALSO ======== *Note GnuPG/Key: GnuPG/Key,, *Note GnuPG/Signature: GnuPG/Signature,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: GnuPG/Tie, Next: GnuPG/UserId, Prev: GnuPG/SubKey, Up: Module List Tied filehandle interface to encryption with the GNU Privacy Guard. ******************************************************************* NAME ==== GnuPG::Tie::Encrypt - Tied filehandle interface to encryption with the GNU Privacy Guard. GnuPG::Tie::Decrypt - Tied filehandle interface to decryption with the GNU Privacy Guard. SYNOPSIS ======== use GnuPG::Tie::Encrypt; use GnuPG::Tie::Decrypt; tie *CIPHER, 'GnuPG::Tie::Encrypt', armor => 1, recipient => 'User'; print CIPHER <; close CIPHER; untie CIPHER; tie *PLAINTEXT, 'GnuPG::Tie::Decrypt', passphrase => 'secret'; print PLAINTEXT $ciphertext; my $plaintext = ; # $plaintext should now contains 'This is a secret' close PLAINTEXT; untie PLAINTEXT DESCRIPTION =========== GnuPG::Tie::Encrypt and GnuPG::Tie::Decrypt provides a tied file handle interface to encryption/decryption facilities of the GNU Privacy guard. With GnuPG::Tie::Encrypt everyting you write to the file handle will be encrypted. You can read the ciphertext from the same file handle. With GnuPG::Tie::Decrypt you may read the plaintext equivalent of a ciphertext. This is one can have been written to file handle. All options given to the tie constructor will be passed on to the underlying GnuPG object. You can use a mix of options to ouput directly to a file or to read directly from a file, only remember than once you start reading from the file handle you can't write to it anymore. IMPLEMENTATIONS DETAILS ======================= This interface will fork twice, once for the gnupg process and one the controls the gpg process. AUTHOR ====== Francis J. Lacoste <francis.lacoste@iNsu.COM> COPYRIGHT ========= Copyright (c) 1999, 2000 iNsu Innovations Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. SEE ALSO ======== gpg(1) GnuPG(3)  File: pm.info, Node: GnuPG/UserId, Next: Gnus/Newsrc, Prev: GnuPG/Tie, Up: Module List GnuPG User ID Objects ********************* NAME ==== GnuPG::UserId - GnuPG User ID Objects SYNOPSIS ======== # assumes a GnuPG::PublicKey object in $publickey my $first_userid_string = $publickey->user_ids_ref->[0]->user_id_string; DESCRIPTION =========== GnuPG::UserId objects are generally not instantiated on their own, but rather as part of GnuPG::PublicKey or GnuPG::SecretKey objects. OBJECT METHODS ============== new( *%initialization_args* ) This methods creates a new object. The optional arguments are initialization of data members; the initialization is done in a manner according to the method created as described in `"new_hash_init"', *Note Class/MethodMaker: Class/MethodMaker,. OBJECT DATA MEMBERS =================== Note that these data members are interacted with via object methods created using the methods described in `"get_set"', *Note Class/MethodMaker: Class/MethodMaker,, `"object"', *Note Class/MethodMaker: Class/MethodMaker,, or `"list"', *Note Class/MethodMaker: Class/MethodMaker,. Please read there for more information. user_id_string A string of the user id. validity A scalar holding the value GnuPG reports for the trust of authenticity (a.k.a.) validity of a key. See GnuPG's DETAILS file for details. signatures A list of GnuPG::Signature objects embodying the signatures on this user id. SEE ALSO ======== *Note GnuPG/Signature: GnuPG/Signature,, *Note Class/MethodMaker: Class/MethodMaker,  File: pm.info, Node: Gnus/Newsrc, Next: GoXML/XQI, Prev: GnuPG/UserId, Up: Module List parse ~/.newsrc.eld files ************************* NAME ==== Gnus::Newsrc - parse ~/.newsrc.eld files SYNOPSIS ======== $newsrc = Gnus::Newsrc->new; ($level, $read, $marks, $server, $group_para) = @{$newsrc->alish_hash->{"comp.lang.perl.misc"}}; DESCRIPTION =========== The `Gnus::Newsrc' objects represents the content of the ~/newsrc.eld files that the Gnus newsreader use to store away its state. The following methods are provided: $newsrc = Gnus::Newsrc->new( [$filename] ) The object constructor takes an optional filename as argument. The file defaults to `~/.newsrc.eld'. It will read and parse the file and return a reference to a `Gnus::Newsrc' object. The constructor will croak if the file can't be found or can't be parsed. $newsrc->file_version Return the version number found in the file *(gnus-newsrc-file-version)*. The version number is a string like `"Gnus v5.5"'. $newsrc->last_checked_date Returns a string like `"Sat Oct 18 14:05:53 1997"' *(gnus-newsrc-last-checked-date)*. $newsrc->alist Returns a reference to an array that will have one element for each active newsgroup *(gnus-newsrc-alist)*. Each element is a array with the following values: $group_name $group_level $read_articles \%marks \@server \%group_parameters The `$read_articles' and `%marks' values is a string of integer ranges, and it is suitable for initializing a `Set::IntSpan' objects. $newsrc->alist_hash Returns a reference to a hash indexed by group names. The hash values are the same as the `alist' elements, but the `$group_name' is missing. $newsrc->server_alist *(gnus-server-alist)*. $newsrc->killed_list A reference to an array that contains all the killed newsgroups *(gnus-killed-list)*. $newsrc->zombie_list A reference to an array that contains all zombie newsgroups *(gnus-zombie-list)*. $newsrc->format_specs SEE ALSO ======== `Lisp::Reader' in this node, *Note Set/IntSpan: Set/IntSpan,, http://www.gnus.org COPYRIGHT ========= Copyright 1997 Gisle Aas. This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  File: pm.info, Node: GoXML/XQI, Next: Graph, Prev: Gnus/Newsrc, Up: Module List Perl extension for the XML Query Interface at xqi.goxml.com. ************************************************************ NAME ==== GoXML::XQI - Perl extension for the XML Query Interface at xqi.goxml.com. SYNOPSIS ======== use GoXML::XQI; $q = new GoXML::XQI( HOST => 'www.goxml.com', PORT => '5910', ); $fh = $q->Query( KEYWORD => $keywd, TAG => $tag, CATEGORY => $categ); while (<$fh>) { # Do something with the search results.. } $resp = $q->Submit( HREF => $url, DESCRIPTION => $description, CATEGORY => $category); print "Succeeded.\n" if $resp; DESCRIPTION =========== This module was designed to allow authorized third parties to connect to the XML index at www.goxml.com:5910. While generally a trivial task, this module will stay up to date and backwards compatible with newer and older versions of XQI. Everyone is _authorized_ to use this service, but people who are paying us get first priority :). CATEGORIES ========== Below is a list of categories currently accepted by Submit(): 1 = Arts & Humanities 2 = Health 3 = Business & Economy 4 = News & Media 5 = Computers & Internet 6 = Recreation & Sports 7 = Education 8 = Reference [DEFAULT] 9 = Entertainment 10 = Science 11 = Family 12 = Shopping 13 = Government 14 = Society & Culture 15 = News Groups (XSL-List, ebXML-*, your-list??) AUTHOR ====== C. Matthew MacKenzie <matt@xmlglobal.com> SEE ALSO ======== http://www.goxml.com  File: pm.info, Node: Graph, Next: Graph/BFS, Prev: GoXML/XQI, Up: Module List graph operations **************** NAME ==== Graph - graph operations SYNOPSIS ======== use Graph; $g = new Graph; DESCRIPTION =========== This is just a front-end class for Graph::Directed and Graph::Base. Instantiated Graph objects (like $g in the the above description) are in fact Graph::Base objects in disguise, look there for the methods available. If you want undirected graphs, create Graph::Undirected objects. COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/BFS, Next: Graph/Base, Prev: Graph, Up: Module List graph breadth-first search ************************** NAME ==== Graph::BFS - graph breadth-first search SYNOPSIS ======== use Graph::BFS; DESCRIPTION =========== $bfs = Graph::BFS->new($G, %param) Returns a new breadth-first search object for the graph $G and the (optional) parameters %param. See also `Graph::Traversal'. COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/Base, Next: Graph/DFS, Prev: Graph/BFS, Up: Module List graph base class **************** NAME ==== Graph::Base - graph base class SYNOPSIS ======== use Graph::Directed; use Graph::Undirected; $d1 = new Graph; $d2 = new Graph::Directed; $u = new Graph::Undirected; DESCRIPTION =========== You create new graphs by calling the new constructors of classes Graph, `Graph::Directed', and `Graph::Undirected'. The classes Graph and `Graph::Directed' are identical. After creating the graph you can modify and explore the graph with following methods. $G = Graph->new(@V) Returns a new graph $G with the optional vertices @V. $G = $G->add_vertices(@v) Adds the vertices to the graph $G, returns the graph. $G = $G->add_vertex($v) Adds the vertex $v to the graph $G, returns the graph. @V = $G->vertices In list context returns the vertices @V of the graph $G. In scalar context returns the number of the vertices. $G->has_vertices(@v) In list context returns a list which contains the vertex of the vertices @v if the vertex exists in the graph $G and undef if it doesn't. In scalar context returns the number of the existing vertices. $b = $G->has_vertex($v) Returns true if the vertex $v exists in the graph $G and false if it doesn't. $v = $G->has_vertex($v) Returns the vertex $v if the vertex exists in the graph $G or undef if it doesn't. $b = $G->directed($d) Set the directedness of the graph $G to $d or return the current directedness. Directedness defaults to true. $b = $G->undirected($d) Set the undirectedness of the graph $G to $u or return the current undirectedness. Undirectedness defaults to false. $b = $G->has_edge($u, $v) Return true if the graph $G has the edge between the vertices $u, $v. $G->has_edges($u1, $v1, $u2, $v2, ...) In list context returns a list which contains true for each edge in the graph $G defined by the vertices $u1, $v1, ..., and false for each non-existing edge. In scalar context returns the number of the existing edges. $G->has_path($u, $v, ...) Return true if the graph $G has the cycle defined by the vertices $u, $v, ..., false otherwise. $G->has_cycle($u, $v, ...) Return true if the graph $G has the cycle defined by the vertices $u, $v, ...,false otherwise. $s = $G->vertex_set($v) Returns the vertex set of the vertex $v in the graph $G. A "vertex set" is represented by its parent vertex. $G = $G->add_edge($u, $v) Adds the edge defined by the vertices $u, $v, to the graph $G. Also implicitly adds the vertices. Returns the graph. $G = $G->add_edges($u1, $v1, $u2, $v2, ...) Adds the edge defined by the vertices $u1, $v1, ..., to the graph $G. Also implicitly adds the vertices. Returns the graph. $G->add_path($u, $v, ...) Adds the path defined by the vertices $u, $v, ..., to the graph $G. Also implicitly adds the vertices. Returns the graph. $G = $G->add_cycle($u, $v, ...) Adds the cycle defined by the vertices $u, $v, ..., to the graph $G. Also implicitly adds the vertices. Returns the graph. @n = $G->neighbors($v) Returns the neighbor vertices of the vertex in the graph. (Also 'neighbours' works.) @s = $G->successors($v) Returns the successor vertices of the vertex in the graph. @p = $G->predecessors($v) Returns the predecessor vertices of the vertex in the graph. @e = $G->out_edges($v) Returns the edges leading out of the vertex $v in the graph $G. In list context returns the edges as ($start_vertex, $end_vertex) pairs. In scalar context returns the number of the edges. @e = $G->in_edges($v) Returns the edges leading into the vertex $v in the graph $G. In list context returns the edges as ($start_vertex, $end_vertex) pairs; in scalar context returns the number of the edges. @e = $G->edges($u, $v) Returns the edges between the vertices $u and $v, or if $v is undefined, the edges leading into or out of the vertex $u, or if $u is undefined, returns all the edges, of the graph $G. In list context returns the edges as a list of $start_vertex, $end_vertex pairs; in scalar context returns the number of the edges. $G = $G->delete_edge($u, $v) Deletes an edge defined by the vertices $u, $v from the graph $G. Note that the edge need not actually exist. Returns the graph. $G = $G->delete_edges($u1, $v1, $u2, $v2, ..) Deletes edges defined by the vertices $u1, $v1, ..., from the graph $G. Note that the edges need not actually exist. Returns the graph. $G = $G->delete_path($u, $v, ...) Deletes a path defined by the vertices $u, $v, ..., from the graph $G. Note that the path need not actually exist. Returns the graph. $G = $G->delete_cycle($u, $v, ...) Deletes a cycle defined by the vertices $u, $v, ..., from the graph $G. Note that the cycle need not actually exist. Returns the graph. $G = $G->delete_vertex($v) Deletes the vertex $v and all its edges from the graph $G. Note that the vertex need not actually exist. Returns the graph. $G = $G->delete_vertices(@v) Deletes the vertices @v and all their edges from the graph $G. Note that the vertices need not actually exist. Returns the graph. $d = $G->in_degree($v) Returns the in-degree of the vertex $v in the graph $G, or, if $v is undefined, the total in-degree of all the vertices of the graph, or undef if the vertex doesn't exist in the graph. $d = $G->out_degree($v) Returns the out-degree of the vertex $v in the graph $G, or, if $v is undefined, the total out-degree of all the vertices of the graph, of undef if the vertex doesn't exist in the graph. $d = $G->degree($v) Returns the degree of the vertex $v in the graph $G or, if $v is undefined, the total degree of all the vertices of the graph, or undef if the vertex $v doesn't exist in the graph. $d = $G->average_degree Returns the average degree of the vertices of the graph $G. $b = $G->is_source_vertex($v) Returns true if the vertex $v is a source vertex of the graph $G. $b = $G->is_sink_vertex($v) Returns true if the vertex $v is a sink vertex of the graph $G. $b = $G->is_isolated_vertex($v) Returns true if the vertex $v is a isolated vertex of the graph $G. $b = $G->is_exterior_vertex($v) Returns true if the vertex $v is a exterior vertex of the graph $G. $b = $G->is_interior_vertex($v) Returns true if the vertex $v is a interior vertex of the graph $G. $b = $G->is_self_loop_vertex($v) Returns true if the vertex $v is a self-loop vertex of the graph $G. @s = $G->source_vertices Returns the source vertices @s of the graph $G. @s = $G->sink_vertices Returns the sink vertices @s of the graph $G. @i = $G->isolated_vertices Returns the isolated vertices @i of the graph $G. @e = $G->exterior_vertices Returns the exterior vertices @e of the graph $G. @i = $G->interior_vertices Returns the interior vertices @i of the graph $G. @s = $G->self_loop_vertices Returns the self-loop vertices @s of the graph $G. ($sparse, $dense, $complete) = $G->density_limits Returns the density limits for the number of edges in the graph $G. Note that reaching $complete edges does not really guarantee completeness because we can have multigraphs. The limit of sparse is less than 1/4 of the edges of the complete graph, the limit of dense is more than 3/4 of the edges of the complete graph. $d = $G->density Returns the density $d of the graph $G. $d = $G->is_sparse Returns true if the graph $G is sparse. $d = $G->is_dense Returns true if the graph $G is dense. $C = $G->complete; Returns a new complete graph $C corresponding to the graph $G. $C = $G->complement; Returns a new complement graph $C corresponding to the graph $G. $C = $G->copy; Returns a new graph $C corresponding to the graph $G. $T = $G->transpose; Returns a new transpose graph $T corresponding to the graph $G. $G->set_attribute($attribute, $value) $G->set_attribute($attribute, $v, $value) $G->set_attribute($attribute, $u, $v, $value) Sets the $attribute of graph/vertex/edge to $value but only if the vertex/edge already exists. Returns true if the attribute is set successfully, false if not. $value = $G->get_attribute($attribute) $value = $G->get_attribute($attribute, $v) $value = $G->get_attribute($attribute, $u, $v) Returns the $value of $attribute of graph/vertex/edge. $value = $G->has_attribute($attribute) $value = $G->has_attribute($attribute, $v) $value = $G->has_attribute($attribute, $u, $v) Returns the $value of $attribute of graph/vertex/edge. %attributes = $G->get_attributes() %attributes = $G->get_attributes($v) %attributes = $G->get_attributes($u, $v) Returns as a hash all the attribute names and values of graph/vertex/edge. $G->delete_attribute($attribute) $G->delete_attribute($attribute, $v) $G->delete_attribute($attribute, $u, $v) Deletes the $attribute of graph/vertex/edge. $G->delete_attributes() $G->delete_attributes($v) $G->delete_attributes($u, $v) Deletes all the attributes of graph/vertex/edge. $G->add_weighted_edge($u, $w, $v, $a) Adds in the graph $G an edge from vertex $u to vertex $v and the edge attribute 'weight' set to $w. $G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) Adds in the graph $G the weighted edges. $G->add_weighted_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) Adds in the graph $G the n edges defined by the path $v1 ... $vn with the n-1 'weight' attributes $w1 ... $wnm1 $MST = $G->MST_Kruskal; Returns Kruskal's Minimum Spanning Tree (as a graph) of the graph $G based on the 'weight' attributes of the edges. (Needs the ->vertex_set() method.) @C = $G->edge_classify(%param) Returns the edge classification as a list where each element is a triplet [$u, $v, $class] the $u, $v being the vertices of an edge and $class being the class. The %param can be used to control the search. @toposort = $G->toposort Returns the vertices of the graph $G sorted topologically. @S = $G->strongly_connected_components Returns the strongly connected components @S of the graph $G as a list of anonymous lists of vertices, each anonymous list containing the vertices belonging to one strongly connected component. $T = $G->strongly_connected_graph Returns the strongly connected graph $T of the graph $G. The names of the strongly connected components are formed from their constituent vertices by concatenating their names by '+'-characters: "a" and "b" -> "a+b". $APSP = $G->APSP_Floyd_Warshall Returns the All-pairs Shortest Paths graph of the graph $G computed using the Floyd-Warshall algorithm and the attribute 'weight' on the edges. The returned graph has an edge for each shortest path. An edge has attributes "weight" and "path"; for the length of the shortest path and for the path (an anonymous list) itself. $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall Returns the Transitive Closure graph of the graph $G computed using the Floyd-Warshall algorithm. The resulting graph has an edge between each *ordered* pair of vertices in which the second vertex is reachable from the first. @A = $G->articulation_points(%param) Returns the articulation points (vertices) @A of the graph $G. The %param can be used to control the search. $b = $G->is_biconnected Returns true is the graph $G is biconnected (has no articulation points), false otherwise. $v = $G->largest_out_degree( @V ) Selects the vertex $v from the vertices @V having the largest out degree in the graph $G. $MST = $G->MST_Prim($u) Returns Prim's Minimum Spanning Tree (as a graph) of the graph $G based on the 'weight' attributes of the edges. The optional start vertex is $u, if none is given, a hopefully good one (a vertex with a large out degree) is chosen. $SSSP = $G->SSSP_Dijkstra($s) Returns the Single-source Shortest Paths (as a graph) of the graph $G starting from the vertex $s using Dijktra's SSSP algorithm. $SSSP = $G->SSSP_Bellman_Ford($s) Returns the Single-source Shortest Paths (as a graph) of the graph $G starting from the vertex $s using Bellman-Ford SSSP algorithm. If there are one or more negatively weighted cycles, returns undef. $SSSP = $G->SSSP_DAG($s) Returns the Single-source Shortest Paths (as a graph) of the DAG $G starting from vertex $s. $G->add_capacity_edge($u, $w, $v, $a) Adds in the graph $G an edge from vertex $u to vertex $v and the edge attribute 'capacity' set to $w. $G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) Adds in the graph $G the capacity edges. $G->add_capacity_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) Adds in the graph $G the n edges defined by the path $v1 ... $vn with the n-1 'capacity' attributes $w1 ... $wnm1 $F = $G->Flow_Ford_Fulkerson($S) Returns the (maximal) flow network of the flow network $G, parametrized by the state $S. The $G must have 'capacity' attributes on its edges. $S->{ source } must contain the source vertex and $S->{ sink } the sink vertex, and most importantly $S->{ next_augmenting_path } must contain an anonymous subroutine which takes $F and $S as arguments and returns the next potential augmenting path. Flow_Ford_Fulkerson will do the augmenting. The result graph $F will have 'flow' and (residual) 'capacity' attributes on its edges. $F = $G->Flow_Edmonds_Karp($source, $sink) Return the maximal flow network of the graph $G built using the Edmonds-Karp version of Ford-Fulkerson. The input graph $G must have 'capacity' attributes on its edges; resulting flow graph will have 'capacity' and 'flow' attributes on its edges. $G->eq($H) Return true if the graphs (actually, their string representations) are identical. This means really identical: they must have identical vertex names and identical edges between the vertices, and they must be similarly directed. (Just isomorphism isn't enough.) COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/DFS, Next: Graph/Directed, Prev: Graph/Base, Up: Module List graph depth-first search ************************ NAME ==== Graph::DFS - graph depth-first search SYNOPSIS ======== *see description* DESCRIPTION =========== $dfs = Graph::DFS->new($G, %param) Returns a new depth-first search object for the graph $G and the (optional) parameters %param. See also `Graph::Traversal'. COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/Directed, Next: Graph/Edge, Prev: Graph/DFS, Up: Module List directed graphs *************** NAME ==== Graph::Directed - directed graphs SYNOPSIS ======== use Graph::Directed; $g = new Graph::Directed; DESCRIPTION =========== See Graph::Base for the available methods. COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/Edge, Next: Graph/Element, Prev: Graph/Directed, Up: Module List a base class for graph edges **************************** NAME ==== Graph::Edge - a base class for graph edges SYNOPSIS ======== *Not to be used directly*. DESCRIPTION =========== This class is not to be used directly because an edge always must belong to a graph. The graph classes will do this right. Some useful public methods exist, though. RETRIEVING EDGES ---------------- $edge = $graph->edge($v1, $v2); Return an edge of the graph by its vertex names, or vertices. If the edge does not exist, undef is returned. @edges = $graph->edges($e1_v1, $e1_v2, $e2_v1, $e2_v2, ..., $en_v1, $en_v2); Return the list of n edges of the graph by their vertex names, or vertices. If an edge by its vertices does not exist, undef is returned for that edge. If no names are specified all the edges are returned, in pseudorandom order. RETRIEVING EDGE VERTICES ------------------------ $start_vertex = $edge->start; $stop_vertex = $edge->stop; The start and stop vertices of the edge. ( $start_vertex, $stop_vertex ) = $edge->vertices; Even in an undirected graph these will be in the order defined originally by add_edge method. ADDING AND DELETING EDGES ------------------------- See *Note Graph: Graph,. SEE ALSO ======== *Note Graph: Graph,, *Note Graph/Element: Graph/Element,. VERSION ======= See *Note Graph: Graph,. AUTHOR ====== Jarkko Hietaniemi <`jhi@iki.fi'> COPYRIGHT ========= Copyright 1998, O'Reilly and Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/Element, Next: Graph/HeapElem, Prev: Graph/Edge, Up: Module List a base class for all things graph ********************************* NAME ==== Graph::Element - a base class for all things graph SYNOPSIS ======== *Not to be used directly*. DESCRIPTION =========== This class is a base class for all the graph elements: vertices, edges, and the graphs themselves. Though largely this class is for internal use only and will bite viciously if approached by strangers it does provide some public methods. METHODS ======= $name = $element->name; Get the current name of the element. Vertices always have names (they are defined by their names), edges and graphs not necessarily. $element->name($new_name); Set the name of the element. VIRTUAL METHODS =============== This class also implements a `virtual method' in this node for all the graph elements: if an unknown method is invoked on an element, it is assumed to be an attribute get/set method from then onwards. For example: $graph->yabadabadoo('fred'); $flintstone = $graph->yabadabadoo; C<$flintstone> will be now C<'fred'>. This feature is both very comfortable and very uncomfortable: no need to separately define methods -- and a pain in nether parts if you are prone to typos. ATTRIBUTE METHODS ================= If you want to play safe with the attributes (as opposed to the virtual attribute methods), you must use explicit language: $attribute_value = $element->attribute($attribute_name); Get the attribute of the element. $element->attribute($attribute_name, $attribute_value); Set the attribute of the element. $element->delete_attribute($attribute_name); Delete the attribute of the element. You can also $element->attribute($attribute_name, undef) but that doesn't really get rid of the attribute, the `has_attribute' method will still find the attribute, but after `delete_attribute' even that will fail. Tests whether the element has the attribute, regardless of the value of the attribute. SEE ALSO ======== *Note Graph: Graph,, *Note Graph/Directed: Graph/Directed,, *Note Graph/Undirected: Graph/Undirected,. VERSION ======= See *Note Graph: Graph,. AUTHOR ====== Jarkko Hietaniemi, <`jhi@iki.fi'> COPYRIGHT ========= Copyright 1998, O'Reilly & Associates. This code is distributed under the same copyright terms as perl itself.  File: pm.info, Node: Graph/HeapElem, Next: Graph/Kruskal, Prev: Graph/Element, Up: Module List internal use only ***************** NAME ==== Graph::HeapElem - internal use only SYNOPSIS ======== DESCRIPTION =========== *INTERNAL USE ONLY* for the Graph module COPYRIGHT ========= Copyright 1999, O'Reilly & Associates. This code is distributed under the same copyright terms as Perl itself.  File: pm.info, Node: Graph/Kruskal, Next: Graph/Reader, Prev: Graph/HeapElem, Up: Module List Kruskal's Algorithm for Minimal Spanning Trees in Graphs ******************************************************** NAME ==== Graph::Kruskal - Kruskal's Algorithm for Minimal Spanning Trees in Graphs Computes the Minimal Spanning Tree of a given graph according to some cost function defined on the edges of the graph. SYNOPSIS ======== * `use Graph::Kruskal qw(define_vortices define_edges' `heapify makeheap heapsort find union kruskal example);' * `use Graph::Kruskal qw(:all);' * `&define_vortices(2,3,5,7,11,13,17,19,23,29,31);' Define a list of vortices (integers > 0) * `&define_edges( 2,13,3, 3,13,2, 5,13,1, 3,5,2, 3,29,21 );' Define (non-directed) edges on the vortices previously defined (always in triplets: "from" vortice, "to" vortice and cost of that edge) * `&heapify($i,$n);' Main subroutine for sorting the edges according to their costs * `&makeheap($n);' Routine to initialize sorting of the edges * `&heapsort($n);' The famous heapsort algorithm (not needed for Kruskal's algorithm as a whole but included here for the sake of completeness) for sorting the edges according to their costs * `&find($i);' * `&union($i,$j);' Disjoint (!) sets are stored as trees in an array in this algorithm. Each element of some set (a cell in the array) contains a pointer to (the number of) another element, up to the root element that does not point anywhere, but contains the (negative) number of elements the set contains. The number of the root element is also used as an identifier for the set. Example: i : | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | -------------+-----+-----+-----+-----+-----+-----+-----+-----+ parent[i] : | -4 | -3 | 1 | 2 | 1 | -1 | 3 | 4 | This array contains the three sets S1, S2 and S6: 1 2 6 / \ | 3 5 4 / | 7 8 "find" returns the number of the root element (= the identifier of the set) of the tree in which the given element is contained: find(a) := i so that a in Si It also reduces the height of that tree by changing all the pointers from the given element up to the root element to point DIRECTLY to the root element. Example: find(7) returns "1" and modifies the array as follows: i : | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | -------------+-----+-----+-----+-----+-----+-----+-----+-----+ parent[i] : | -4 | -3 | 1 | 2 | 1 | -1 | 1 | 4 | 1 2 6 /|\ | 3 5 7 4 | 8 "union" takes the identifiers of two sets (= the numbers of their respective root elements) and merges the two sets by appending one of the two trees to the other. It always appends the SMALLER set to the LARGER one (to keep the height of the resulting tree as small as possible) and updates the number of elements contained in the resulting set which is stored in the root element's cell of the array. Example: union(2,6) does the following: i : | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | -------------+-----+-----+-----+-----+-----+-----+-----+-----+ parent[i] : | -4 | -4 | 1 | 2 | 1 | 2 | 1 | 4 | 1 2 /|\ / \ 3 5 7 4 6 | 8 complexity for O(n) "find" operations: O( G(n) n ) complexity for one "union" operation: O(1) complexity for O(n) ( "find" + "union" ) operations: O( G(n) n ) where G(n) := min{ j | F(j) >= n } and F(j) := 1 for j = 0 F(j) := 2 ^ F(j-1) for j > 0 also, G(n) <= ld n for all n * `&kruskal();' This routine carries out the computations associated with Kruskal's algorithm. Returns an array of hashes (each hash containing the keys "from", "to" and "cost" and the corresponding values) representing the minimal spanning tree of the graph previously defined by calls to "define_vortices" and "define_edges". The result can also be found in @Graph::Kruskal::T. See the implementation of the subroutine "example" to see how to access this array directly (remember to fully qualify the name of this array in your program, i.e., use "@Graph::Kruskal::T" instead of just "@T", since this array is not exported - or your program will not work!) * `&example();' Demonstrates how to use the various subroutines in this module. Computes the minimal spanning tree of a sample graph. Just say "use Graph::Kruskal qw(example);" and "&example();" in a little Perl script to see it "in action". DESCRIPTION =========== This algorithm computes the Minimal Spanning Tree of a given graph according to some cost function defined on the edges of that graph. Input: A set of vortices which constitute a graph (some cities on a map, for example), a set of edges (i.e., roads) between the vortices of the (non-directed and connected) graph (i.e., the edges can be traveled in either direction, and a path must exist between any two vortices), and the cost of each edge (for instance, the geographical distance). Output: A set of edges forming a spanning tree (i.e., a set of edges linking all vortices, so that a path exists between any two vortices) which is free of circles (because it's a tree) and which is minimal in terms of the cost function defined on the set of edges. See Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms" for more details on the algorithm. SEE ALSO ======== Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3). VERSION ======= This man page documents "Graph::Kruskal" version 2.0. AUTHOR ====== Steffen Beyer <sb@sdm.de>. COPYRIGHT ========= Copyright (c) 1995, 1996, 1997 by Steffen Beyer. All rights reserved. LICENSE ======= This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  File: pm.info, Node: Graph/Reader, Next: Graph/Reader/XML, Prev: Graph/Kruskal, Up: Module List base class for Graph file format readers **************************************** NAME ==== Graph::Reader - base class for Graph file format readers SYNOPSIS ======== package Graph::Reader::MyFormat; use Graph::Reader; use vars qw(@ISA); @ISA = qw(Graph::Reader); sub _read_graph { my ($self, $graph, $FILE) = @_; # read $FILE and populate $graph } DESCRIPTION =========== Graph::Reader is a base class for Graph file format readers. A particular subclass of Graph::Reader will handle a specific file format, and generate a Graph, represented using Jarkko Hietaniemi's Graph class. You should never create an instance of this class yourself, it is only meant for subclassing. If you try to create an instance of Graph::Reader, the constructor will throw an exception. METHODS ======= new() ----- Constructor - generate a new reader instance. This is a virtual method, or whatever the correct lingo is. You're not meant to call this on the base class, it is inherited by the subclasses. Ie if you do something like: $reader = Graph::Reader->new(); It will throw an exception. read_graph() ------------ Read a graph from the specified file: $graph = $reader->read_graph($file); The $file argument can either be a filename, or a filehandle for a previously opened file. SUBCLASSING =========== To create your own graph format reader, create a module which subclasses Graph::Reader. For example, suppose DGF is a directed graph format - create a *Graph::Reader::DGF* module, with the following structure: package Graph::Reader::DGF; use Graph::Reader; use vars qw(@ISA); @ISA = qw(Graph::Reader); sub _read_graph { my $self = shift; my $graph = shift; my $FILE = shift; while (<$FILE>) { } return 1; } 1; Note the leading underscore on the *_read_graph()* method. The base class provides the public method, and invokes the private method which you're expected to provide, as above. If you want to perform additional initialisation at construction time, you can provide an *_init()* method, which will be invoked by the base class's constructor. You should invoke the superclass's initialiser as well, as follows: sub _init { my $self = shift; $self->SUPER::_init(); # your initialisation here } Someone can then use your class as follows: use Graph::Reader::DGF; $reader = Graph::Reader::DGF->new(); $graph = $reader->read_graph('foo.dgf'); SEE ALSO ======== Graph Jarkko Hietaniemi's modules for representing directed graphs, available from CPAN under modules/by-module/Graph/ Algorithms in Perl This O'Reilly book has a chapter on directed graphs, which is based around Jarkko's modules. Graph::Reader::XML A simple subclass of this class for reading a simple XML format for directed graphs. Graph::Writer A baseclass for Graph file format writers. AUTHOR ====== Neil Bowers <neilb@cre.canon.co.uk> COPYRIGHT ========= Copyright (c) 2001, Canon Research Centre Europe. All rights reserved. This script is free software; you can redistribute it and/or modify it under the same terms as Perl itself.