graph.pod

nasm早期的源代码,比较简单是学习汇编和编译原理的好例子

    $g->get_vertex_attribute_by_id($v, $id, $name)
    $g->has_vertex_attribute_by_id($v, $id, $name)
    $g->delete_vertex_attribute_by_id($v, $id, $name)
    $g->set_vertex_attributes_by_id($v, $id, $attr)
    $g->get_vertex_attributes_by_id($v, $id)
    $g->get_vertex_attribute_values_by_id($v, $id)
    $g->get_vertex_attribute_names_by_id($v, $id)
    $g->has_vertex_attributes_by_id($v, $id)
    $g->delete_vertex_attributes_by_id($v, $id)

=back

For edge attributes:

=over 4

=item set_edge_attribute

    $g->set_edge_attribute($u, $v, $name, $value)

Set the named edge attribute.

If the edge does not exist, the set_...() will create it, and the other
edge attribute methods will return false or empty.

B<NOTE>: any attributes beginning with an underscore (C<_>) are
reserved for the internal use of the Graph module.

=item get_edge_attribute

    $value = $g->get_edge_attribute($u, $v, $name)

Return the named edge attribute.

=item has_edge_attribute

    $g->has_edge_attribute($u, $v, $name)

Return true if the edge has an attribute, false if not.

=item delete_edge_attribute

    $g->delete_edge_attribute($u, $v, $name)

Delete the named edge attribute.

=item set_edge_attributes

    $g->set_edge_attributes($u, $v, $attr)

Set all the attributes of the edge from the anonymous hash $attr.

B<NOTE>: any attributes beginning with an underscore (C<_>) are
reserved for the internal use of the Graph module.

=item get_edge_attributes

    $attr = $g->get_edge_attributes($u, $v)

Return all the attributes of the edge as an anonymous hash.

=item get_edge_attribute_names

    @name = $g->get_edge_attribute_names($u, $v)

Return the names of edge attributes.

=item get_edge_attribute_values

    @value = $g->get_edge_attribute_values($u, $v)

Return the values of edge attributes.

=item has_edge_attributes

    $g->has_edge_attributes($u, $v)

Return true if the edge has any attributes, false if not.

=item delete_edge_attributes

    $g->delete_edge_attributes($u, $v)

Delete all the attributes of the named edge.

=back

If you are using multiedges, use the I<by_id> variants:

=over 4

=item set_edge_attribute_by_id

=item get_edge_attribute_by_id

=item has_edge_attribute_by_id

=item delete_edge_attribute_by_id

=item set_edge_attributes_by_id

=item get_edge_attributes_by_id

=item get_edge_attribute_names_by_id

=item get_edge_attribute_values_by_id

=item has_edge_attributes_by_id

=item delete_edge_attributes_by_id

    $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
    $g->get_edge_attribute_by_id($u, $v, $id, $name)
    $g->has_edge_attribute_by_id($u, $v, $id, $name)
    $g->delete_edge_attribute_by_id($u, $v, $id, $name)
    $g->set_edge_attributes_by_id($u, $v, $id, $attr)
    $g->get_edge_attributes_by_id($u, $v, $id)
    $g->get_edge_attribute_values_by_id($u, $v, $id)
    $g->get_edge_attribute_names_by_id($u, $v, $id)
    $g->has_edge_attributes_by_id($u, $v, $id)
    $g->delete_edge_attributes_by_id($u, $v, $id)

=back

For graph attributes:

=over 4

=item set_graph_attribute

    $g->set_graph_attribute($name, $value)

Set the named graph attribute.

B<NOTE>: any attributes beginning with an underscore (C<_>) are
reserved for the internal use of the Graph module.

=item get_graph_attribute

    $value = $g->get_graph_attribute($name)

Return the named graph attribute.

=item has_graph_attribute

    $g->has_graph_attribute($name)

Return true if the graph has an attribute, false if not.

=item delete_graph_attribute

    $g->delete_graph_attribute($name)

Delete the named graph attribute.

=item set_graph_attributes

    $g->get_graph_attributes($attr)

Set all the attributes of the graph from the anonymous hash $attr.

B<NOTE>: any attributes beginning with an underscore (C<_>) are
reserved for the internal use of the Graph module.

=item get_graph_attributes

    $attr = $g->get_graph_attributes()

Return all the attributes of the graph as an anonymous hash.

=item get_graph_attribute_names

    @name = $g->get_graph_attribute_names()

Return the names of graph attributes.

=item get_graph_attribute_values

    @value = $g->get_graph_attribute_values()

Return the values of graph attributes.

=item has_graph_attributes

    $g->has_graph_attributes()

Return true if the graph has any attributes, false if not.

=item delete_graph_attributes

    $g->delete_graph_attributes()

Delete all the attributes of the named graph.

=back

=head2 Weighted

As convenient shortcuts the following methods add, query, and
manipulate the attribute C<weight> with the specified value to the
respective Graph elements.

=over 4

=item add_weighted_edge

    $g->add_weighted_edge($u, $v, $weight)

=item add_weighted_edges

    $g->add_weighted_edges($u1, $v1, $weight1, ...)

=item add_weighted_path

    $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)

=item add_weighted_vertex

    $g->add_weighted_vertex($v, $weight)

=item add_weighted_vertices

    $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)

=item delete_edge_weight

    $g->delete_edge_weight($u, $v)

=item delete_vertex_weight

    $g->delete_vertex_weight($v)

=item get_edge_weight

    $g->get_edge_weight($u, $v)

=item get_vertex_weight

    $g->get_vertex_weight($v)

=item has_edge_weight

    $g->has_edge_weight($u, $v)

=item has_vertex_weight

    $g->has_vertex_weight($v)

=item set_edge_weight

    $g->set_edge_weight($u, $v, $weight)

=item set_vertex_weight

    $g->set_vertex_weight($v, $weight)

=back

=head2 Isomorphism

Two graphs being I<isomorphic> means that they are structurally the
same graph, the difference being that the vertices might have been
I<renamed> or I<substituted>.  For example in the below example $g0
and $g1 are isomorphic: the vertices C<b c d> have been renamed as
C<z x y>.

	$g0 = Graph->new;
	$g0->add_edges(qw(a b a c c d));
	$g1 = Graph->new;
	$g1->add_edges(qw(a x x y a z));

In the general case determining isomorphism is I<NP-hard>, in other
words, really hard (time-consuming), no other ways of solving the problem
are known than brute force check of of all the possibilities (with possible
optimization tricks, of course, but brute force still rules at the end of
the day).

A B<very rough guess> at whether two graphs B<could> be isomorphic
is possible via the method

=over 4

=item could_be_isomorphic

    $g0->could_be_isomorphic($g1)    

=back

If the graphs do not have the same number of vertices and edges, false
is returned.  If the distribution of I<in-degrees> and I<out-degrees>
at the vertices of the graphs does not match, false is returned.
Otherwise, true is returned.

What is actually returned is the maximum number of possible isomorphic
graphs between the two graphs, after the above sanity checks have been
conducted.  It is basically the product of the factorials of the
absolute values of in-degrees and out-degree pairs at each vertex,
with the isolated vertices ignored (since they could be reshuffled and
renamed arbitrarily).  Note that for large graphs the product of these
factorials can overflow the maximum presentable number (the floating
point number) in your computer (in Perl) and you might get for example
I<Infinity> as the result.

=head2 Miscellaneous

The "expect" methods can be used to test a graph and croak if the
graph is not as expected.

=over 4

=item expect_acyclic

=item expect_dag

=item expect_directed

=item expect_multiedged

=item expect_multivertexed

=item expect_non_multiedged

=item expect_non_multivertexed

=item expect_undirected

=back

In many algorithms it is useful to have a value representing the
infinity.  The Graph provides (and itself uses):

=over 4

=item Infinity

(Not exported, use Graph::Infinity explicitly)

=back

=head2 Size Requirements

A graph takes up at least 1172 bytes of memory.

A vertex takes up at least 100 bytes of memory.

An edge takes up at least 400 bytes of memory.

(A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)

These size approximations are B<very> approximate and optimistic
(they are based on total_size() of Devel::Size).  In real life many
factors affect these numbers, for example how Perl is configured.
The numbers are for a 32-bit platform and for Perl 5.8.8.

Roughly, the above numbers mean that in a megabyte of memory you can
fit for example a graph of about 1000 vertices and about 2500 edges.

=head2 Hyperedges, hypervertices, hypergraphs

B<BEWARE>: this is a rather thinly tested feature, and the theory
is even less so.  Do not expect this to stay as it is (or at all)
in future releases.

B<NOTE>: most usual graph algorithms (and basic concepts) break
horribly (or at least will look funny) with these hyperthingies.
Caveat emptor.

Hyperedges are edges that connect a number of vertices different
from the usual two.

Hypervertices are vertices that consist of a number of vertices
different from the usual one.

Note that for hypervertices there is an asymmetry: when adding
hypervertices, the single vertices are also implicitly added.

Hypergraphs are graphs with hyperedges.

To enable hyperness when constructing Graphs use the C<hyperedged>
and C<hypervertexed> attributes:

   my $h = Graph->new(hyperedged => 1, hypervertexed => 1);

To add hypervertexes, either explicitly use more than one vertex (or,
indeed, I<no> vertices) when using add_vertex()

   $h->add_vertex("a", "b")
   $h->add_vertex()

or implicitly with array references when using add_edge()

   $h->add_edge(["a", "b"], "c")
   $h->add_edge()

Testing for existence and deletion of hypervertices and hyperedges
works similarly.

To test for hyperness of a graph use the

=over 4

=item is_hypervertexed

=item hypervertexed

    $g->is_hypervertexed
    $g->hypervertexed

=item is_hyperedged

=item hyperedged

    $g->is_hyperedged
    $g->hyperedged

=back

Since hypervertices consist of more than one vertex:

=over 4

=item vertices_at

    $g->vertices_at($v)

=back

Return the vertices at the vertex.  This may return just the vertex
or also other vertices.

To go with the concept of undirected in normal (non-hyper) graphs,
there is a similar concept of omnidirected I<(this is my own coinage,
"all-directions")> for hypergraphs, and you can naturally test for it by

=over 4

=item is_omnidirected

=item omnidirected

=item is_omniedged

=item omniedged

   $g->is_omniedged

   $g->omniedged

   $g->is_omnidirected

   $g->omnidirected

Return true if the graph is omnidirected (edges have no direction),
false if not.

=back

You may be wondering why on earth did I make up this new concept, why
didn't the "undirected" work for me?  Well, because of this:

   $g = Graph->new(hypervertexed => 1, omnivertexed => 1);

That's right, vertices can be omni, too - and that is indeed the
default.  You can turn it off and then $g->add_vertex(qw(a b)) no
more means adding also the (hyper)vertex qw(b a).  In other words,
the "directivity" is orthogonal to (or independent of) the number of
vertices in the vertex/edge.

=over 4

=item is_omnivertexed

=item omnivertexed

=back

Another oddity that fell out of the implementation is the uniqueness
attribute, that comes naturally in C<uniqedged> and C<uniqvertexed>
flavours.  It does what it sounds like, to unique or not the vertices
participating in edges and vertices (is the hypervertex qw(a b a) the
same as the hypervertex qw(a b), for example).  Without too much
explanation:

=over 4

=item is_uniqedged

=item uniqedged

=item is_uniqvertexed

=item uniqvertexed

=back

=head2 Backward compatibility with Graph 0.2

The Graph 0.2 (and 0.2xxxx) had the following features

=over 4

=item *

vertices() always sorted the vertex list, which most of the time is
unnecessary and wastes CPU.

=item *

edges() returned