NAME

Graph - graphs and graph algorithms

SYNOPSIS

use Graph;

DESCRIPTION

The Graph class provides graph data structures and some commonly used graph algorithms.

METHODS

CONSTRUCTOR

$graph = Graph->new;

The Constructor. Creates a new directed graph. If you want undirected graphs, use the new() constructor of the class Graph::Undirected. Read more about directedness later in this document.

print "g = ", $g->as_string, "\n";

The stringifier -- a string representation of the graph. Normally there is no need to use this directly as operator overloading (see overload) works:

print "g = $g\n";

Edges are listed first, unconnected vertices last, all separated by commas. Vertices are printed by their names, edges from vertex u to vertex v either

u-v

u=v

depending on whether the graph is directed or undirected, respectively.

ADDING VERTICES

$vertex   = $graph->add_vertex($vertex_name);

Add one vertex to the graph. Return the vertex, regardless of whether it already was in the graph.

@vertices = $graph->add_vertices($v1, $v2, ..., $vn);

Add one or more vertices to the graph. In list context return the list of the n added vertices, regardless of whether they already were in there graph. In array context return the number of really added vertices.

$in_same_element = $graph->find( $vertex, $another_vertex );

Return true if the two vertices are in the same connected $graph element. This is the other half of the union-find fame. Union-find is the name of a method which enables extremely fast graph connectedness checks. The other half, union, is not available because explicitly using it would be a bad idea: add_edge and add_edges will call it implicitly.

$is_connected    = $graph->is_connected;

Return true if the $graph is connected: that is, one can reach every vertex from any other vertex. Makes sense only for undirected graphs, for directed graphs a similar concept does exist but it is called strong connectivity.

NOTE: the union-find structure is not currently updated when vertices or edges of the graph are deleted. Yes, this is a bug.

ADDING EDGES

$edge  = $add->add_edge($v1, $v2[, $edge_name]);

Add one edge to the graph by the names of the vertices. The vertices are implicitly added to the graph if not already there. Return the edge, regardless of whether it already was in the graph. An optional symbolic name can be attached to the edge. This is normally unnecessary because an edge is fully specified by its vertices.

@edges = $add->add_edges($e1_v1, $e1_v2,
                         $e2_v1, $e2_v2,
                         ...,
                         $en_v1, $e2_v2);

Add one or more edges to the graph by the names of the vertices. The vertices are implicitly added to the graph if not already there. In list context return the list of the n edges, regardless of whether they already were in the graph. In scalar context return the number of really added edges.

See Graph::Vertex for how to find out which edges start from and leave a vertex, and to find out which vertices are behind those edges. See Graph::Edge for how to retrieve the vertices of edges.

RETRIEVING VERTICES

$vertex   = $graph->vertex($vertex_name);

Return one vertex of the graph by its name names. If the vertex does not exist, undef is returned.

@vertices = $graph->vertices($v1, $v2, ..., $vn);

Return the list of the n vertices of the graph by their names. If a vertex by a name does not exists, undef is returned for that vertex.

@vertices = $graph->vertices;

If no names are specified all the vertices are returned, in pseudorandom order.

$has_vertex   = $graph->has_vertex($vertex_name);

Return true if the the graph has the vertex.

@has_vertices = $graph->has_vertices($v1, $v2, ...);

In list context return a list of truth values, one for each vertex: true if the graph has the vertex, false if not. In scalar context, return the logical and of the list, that is, all the vertices must exist.

RETRIEVING EGDES

$edge  = $graph->edge($v1, $v2);

Return an edge of the graph by its vertex names, or vertices. If vertices are used they must be vertices of the graph. 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.

@edges = $graph->edges;

If no names are specified all the edges are returned, in pseudorandom order.

$has_edge  = $graph->has_edge($v1, $v2);

Return true if the graph has the edge defined by the vertices, false if not.

@edges = $graph->edges($e1_v1, $e1_v2,
                       $e2_v1, $e2_v2,
                       ...,
                       $en_v1, $en_v2);

Return a list of n truth values, one for each edge, true if the edge exists, false if not. In scalar context, return the logical and of the list, that is, all the edges must exist.

RETRIEVING EGDES BY NAMES

$edge  = $graph->edge_by_name($edge_name);

@edges = $graph->edges_by_names($e1, $e2, ...);

Return one or more edges by their symbolic names, or if no names are given, all the edges. The symbolic name can be given using either in edge creation time

$graph->add_edge($v1, $v2, $edge_name);

or later

$edge->name($edge_name);

DELETING EDGES

$deleted = $graph->delete_edge( $v1, $v2 );

Delete one edge by its vertices. Return true if the edge really was deleted and false if the edge wasn't there.

$deleted = $graph->delete_edge( $e );

Delete one edge. Return true if the edge really was deleted and false if the edge wasn't there.

@deleted = $graph->delete_edges( $e1_v1, $e1_v2,
                                 $e2_v1, $e2_v2,
                                 ...,
                                 $en_v1, $en_v2);

Delete one or more edges by their vertices. In list context return the list of n truth values, one for each edge: true for the edges really deleted and false for the edges that weren't there. In scalar context return the number of really deleted edges.

DELETING VERTICES

$deleted = $graph->delete_vertex($vertex_name);

Delete one vertex and the edges depending on it from the graph. Return true if the vertex did exist, false if not.

@deleted = $graph->delete_vertices($v1, $v2, ...);

Delete one or more vertices and the edges depending on them from the graph. In list context return a list of truth values, one for each vertex: true if the vertex did exist, false if not. In scalar context return the number of really deleted vertices.

RETRIEVING NEIGHBOURING VERTICES

@neighbours   = $graph->vertex_neighbours( $vertex );

Return all the neighbouring vertices of the vertex. Also the American neigbors are available.

@successors   = $graph->vertex_successors( $vertex );

Return all the successor vertices of the vertex.

@predecessors = $graph->vertex_predecessors( $vertex );

Return all the predecessor vertices of the vertex.

RETRIEVING NEIGHBOURING EDGES

@all = $graph->vertex_edges( $vertex );

Return all the neighboring edges of the vertex.

@out = $graph->vertex_out_edges( $vertex );

Return all the edges leaving the vertex.

@in  = $graph->vertex_in_edges( $vertex );

Return all the edges arriving at the vertex.

VERTEX CLASSES

The vertices returned by the following methods are in pseudorandom order.

@connected_vertices   = $graph->connected_vertices;

The list of connected vertices of the graph.

@unconnected_vertices = $graph->unconnected_vertices;

The list of unconnected vertices of the graph.

@sink_vertices        = $graph->sink_vertices;

The list of sink vertices of the graph.

@source_vertices      = $graph->source_vertices;

The list of source vertices of the graph.

@exterior_vertices    = $graph->exterior_vertices;

The list of exterior vertices (sinks and sources) of the graph.

@interior_vertices    = $graph->interior_vertices;

The list of interior vertices (non-sinks and non-sources) of the graph.

@selfloop_vertices    = $graph->selfloop_vertices;

The list of self-loop vertices of the graph.

PATHS

A path is a connected set of the n-1 edges v1 v2, v2 v3, ..., leading from the vertex v1 to the vertex vn.

ADDING PATHS

@edges = $graph->add_path($v1, $v2, $v3, ..., $vn);

Add one or more edges, a path, to the graph. The vertices are added to the graph explicitly if they already aren't there. Return the list of the n-1 edges.

RETRIEVING PATHS

@edges  = $graph->path($v1, $v2, ..., $vn);

Return the n-1 edges of the path. If an edge does not exist (that is, the path does not exist), undef is returned for that edge.

$has_path = $graph->has_path($v1, $v2, ..., $vn);

Return true if the graph has the path, that is, it has all the n-1 edges.

DELETING PATHS

@deleted = $graph->delete_path($v1, $v2, ..., $vn);

Delete one or more edges, a path, from the graph. Return a list of n-1 truth values, one for each edge in the path: true if the edge did exist, false if not.

CYCLES

A cycle is a cyclical path, defined by the n edges v1 v2, v2 v3, ..., vn v1, starting from and returning back to the vertex v1.

ADDING CYCLES

@edges = $graph->add_cycle($v1, $v2, $v3, ..., $vn);

Add one or more edges, a cycle, to the graph. The vertices are added to the graph explicitly if they already aren't there. Return the list of the n edges.

RETRIEVING CYCLES

@edges  = $graph->cycle($v1, $v2, ..., $vn);

Return the n edges of the cycle. If an edge does not exist (that is, the cycle does not exist), undef is returned for that edge.

$has_cycle = $graph->has_cycle($v1, $v2, ..., $vn);

Return true if the graph has the cycle, that is, it has all the n edges.

DELETING CYCLES

@edges = $graph->delete_cycle($v1, $v2, $v3, ..., $vn);

Delete one or more edges, a cycle, from the graph. In list context return a list of n truth values, one for each edge in the cycle: true if the edge did exist, false if not.

DETECTING CYCLES

@cycle = $graph->is_cyclic;

Return true if the graph is cyclic, false if the graph is not cyclic (acyclic).

ADDING ATTRIBUTED EDGES AND PATHS

$graph->add_attributed_edge( $attribute_name,
                             $vertex_from,
                             $attribute_value,
                             $vertex_to );

Add the attribute to the edge (and create the edge if it does not exist).

$graph->add_attributed_path( $attribute_name,
                             $vertex_1,
                             $attribute_value_1,
                             $vertex_2,
                             $attribute_value_2,
                             ...
                             $vertex_n );

Add the n-1 attribute values to the n-1 edges along the path (and creating the edges if needed).

RETRIEVING EDGES' AND PATHS' ATTRIBUTES

$attribute_value = $graph->attributed_edge( $attribute_name,
                                            $vertex_from,
                                            $vertex_to );

Return the attribute of the edge. If the edge does not exist undef is returned.

@attribute_values = $graph->attributed_path( $attribute_name,
                                             $vertex_1,
                                             $vertex_2,
                                             ...
                                             $vertex_n );

Return the list of the n-1 attribute values. If an edge does not exist, undef is returned for that edge.

GRAPH PROPERTIES

GRAPH DENSITY

$density = $graph->density;

Return the density of the $graph as a number between 0 and 1. Graph density is defined as the relative number of edges. A zero signifies an empty graph: no edges; a one signifies a complete graph: |V|(|V|-1)/2 edges (for undirected graphs) or |V|(|V|-1) (for directed graphs), |V| being the number of vertices.

$is_sparse = $graph->is_sparse;

Return true if the $graph is sparse; that is, its density is less than |V|(|V|-1)/6 (for undirected graphs) or |V|(|V|-1)/3 (for directed graphs).

$is_dense = $graph->is_dense;

Return true if the $graph is dense; that is, its density is greater than |V|(|V|-1)/3 (for undirected graphs) or 2|V|(|V|-1)/3 (for directed graphs).

($sparse, $dense) = $graph->density_limits;

Return the limits for being sparse and being dense. The $graph is sparse if it has as many or less edges than $sparse and dense if it has as many or more fewer edges than $dense.

DERIVATIVE GRAPHS

The four following methods are graph constructors. They copy always the vertices, the edges if applicable, and all the graph, vertex, and edge attributes.

$copy       = $graph->copy;

Return a copy of the $graph.

$transpose  = $graph->transpose_graph;

Return a transpose graph of the $graph, a graph where every edge is reversed. Makes sense only for directed graphs.

$complete   = $graph->complete_graph;

Return a complete graph of the $graph, a graph that has every possible edge (without resorting to multiedges).

$complement = $graph->complement_graph;

Return a complement graph of the $graph, a graph that has every edge that the $graph does not.

DIRECTEDNESS

A graph can be directed or undirected. Or more precisely, the edges of the graph can be directed or undirected. The difference between a directed edge and an undirected edge is that if there is an undirected edge from vertex v1 to vertex v2, there is also an implicit edge in the opposite direction, from vertex v2 to vertex v1.

For this module, however, the directedness property is attached to the graph. If a graph is undirected, either by instantiating an object of the Graph::Undirected class, or marking a graph undirected (see below), whenever an edge is added to graph, also the edge going to the other direction is added, and likewise for deleting edges. If you do not want this dual behaviour, mark the graph directed.

The directedness of a graph can be examined and set using the following methods:

$is_directed   = $graph->directed;
$is_undirected = $graph->undirected;

Test the directedness of the graph.

$graph->directed( 1 );
$graph->undirected( 0 );

Mark the graph directed.

$graph->undirected( 1 );
$graph->directed( 0 );

Mark the graph undirected.

TOPOLOGICAL SORT

@topo = $graph->topological_sort;

Return the vertices of the $graph sorted topologically, that is, in an order that respects the partial ordering of the graph. There may be many possible topological orderings of the graph.

MINIMUM SPANNING TREES

A minimum spanning tree (MST) is a derivative graph of an undirected `weighted' graph, a graph that has an attribute called Weight attached to each edge, see the add_attributed_path method. Each edge weighs something or in other words has a cost associated with it. A MST spans all the vertices with the least possible total weight.

$mst = $graph->MST_kruskal;

Return a Kruskal's minimum spanning tree of the $graph. Notice the 'a tree', if there are many edges with similar costs, multiple equally minimal trees can exist.

As a matter of fact the `weight' does not need to be called Weight:

$mst = $graph->MST_kruskal('Distance');

as long as you adjust your call to add_attributed_path accordingly.

ALL-PAIRS SHORTEST PATHS

All-pairs shortest paths algorithms find out the shortest possible paths between any pair of vertices.

FLOYD-WARSHALL ALL-PAIRS SHORTEST PATHS

$fw_apsp = $graph->APSP_floyd_warshall;

Return the Floyd-Warshall all-pairs shortest paths as a graph. More specifically: in the returned graph every possible (path-connected) pair is an edge.

Before the method call each edge should have an attribute, by default Weight, that tells the `cost' of the edge. The name of the attribute can be changed by supplying an argument:

$fw_apsp = $graph->APSP_floyd_warshall( 'Distance' );

After the method call each edge has two attributes: Weight (or what was specified), which is the length of the minimal path up to and including that edge, and prev, which is the second to last vertex on the minimal path.Example: If there is a path from vertex a to vertex f, the edge a-f has the attributes Weight, for example 6, and Prev, for example d, which means that the last edge of the minimal path from a to f is d-f. To trace the path backwards, see the edge a-d. Sounds good but there is a catch: if there is a negative cycle in the path the Prev attributes point along this negative cycle and there is no way to break out of it back to the original minimal path.

TRANSITIVE CLOSURE

$closure_graph = $graph->transitive_closure;

Return as a graph the transitive closure of the $graph. If there is a path between a pair of vertices the the $graph, there is an edge between that pair of vertices in the transitive closure graph. Transitive closure is the Boolean reduction of the all-pairs shortest paths: the length of the path does not matter, just the existence.

COMPATIBILITY

Neil Bowers has written graph-modules-1.001 in Canon Research Center Europe. The whole graph model is very different.

In Bowers' model graph nodes (vertices) and graph edges are instantiated explicitly, in that order. In effect, there is only one graph per one Perl script runtime.

In this module graphs are instantiated and then vertices and edges are added into them, either explicitly or implicitly. There may be multiple graphs active simultaneously, and they may have identically named vertices.

Some simple compatibility mappings are possible:

getAttribute() and setAttribute() are possible either using explicit attribute() or with the implicit virtual attributes, see Graph::Element.
Graph::Node is Graph::Vertex -- but note that you should never explicitly use Graph::Vertex, as opposed to what you have been doing with Graph::Node.

The save() method is available for graphs, see Graph::Archive.

SAVING (AND, SOME DAY, LOADING) GRAPHS

GRAPH FILE FORMATS

The known graph file formats are

graph adjacency list, suffix 'gal'

An example:

gal 001
vertices 6
a b c d e f
edges 5
a b
b c d
c
d
e b e
f
2 _id GLOB(0x15b3e8) directed 1
a 1 _id GLOB(0x15ccdc)
...
b c 1 _id GLOB(0x15cee0)
b d 1 _id GLOB(0x15cee8)
...

The first line identifies the gal format and its version as 001. The next line tells the number of the vertices, V. The next line lists the vertices. The next line tells the number of edges, E. The next E lines are the edges in adjacency list format:

start_vertex end_vertex_1 vertex_2 ...

After the edge lines lines are 1+V+E lines listing the attributes of the graph, the vertices, and the edges. The vertex attribute lines begin with the vertices, the edges attributes lines with the two vertices. The attributes themselves are of the form:

number_of_attributes attribute_key_1 attribute_value_1 ...

The vertices, edges, and attributes can contain whitespace characters but they must be encoded like this: =XX where the XX are two hexadecimal digits, for example =20 is the space character (in ASCII or ISO Latin). Obviously, any possible =s need to be encoded: =3d.

graph adjacency matrix, suffix 'gam'

The gam format is very similar to the gal format. The only difference is in listing the edges an adjacency matrix is used: a boolean matrix in text format that has 1 whenever there is an edge from a vertex to another vertex, 0 elsewhere.

gal 001
vertices 6
a b c d e f
edges 5
0 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 1 0
0 0 0 0 0 0
2 _id GLOB(0x15b3e8) directed 1
a 1 _id GLOB(0x15ccdc)
...
b c 1 _id GLOB(0x15cee0)
b d 1 _id GLOB(0x15cee8)
...

The above gam specififies exactly the same edges as the even-further-above gal.

daVinci, suffix 'daVinci', see http://www.informatik.uni-bremen.de/~davinci/.

SAVING GRAPHS

$graph->save('daV');

The graph will be saved in daVinci format to graph.daVinci.

$graph->save('foo.daV');

The graph will be saved in daVinci format to foo.daVinci.

$graph->save('foo');

The graph will be saved in daVinci format to foo.daVinci.

$graph->save();

The graph will be saved in daVinci format to graph.daVinci.

$graph->save('gal');

The graph will be saved in adjacency list format to graph.gal.

$graph->save('foo.gal');

The graph will be saved in adjacency list format to foo.gal.

$graph->save('gam');

The graph will be saved in adjacency matrix format to graph.gam.

$graph->save('foo.gam');

The graph will be saved in adjacency matrix format to foo.gam.

In all the above the 'suffix' is case-insensitive, the filename part is not.

LOADING GRAPHS

Sorry, at the moment no methods for loading graphs from files are implemented.

VERSION

Version 0.004.

AUTHOR

Jarkko Hietaniemi <jhi@iki.fi>

COPYRIGHT

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

To install Graph, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Graph

CPAN shell

perl -MCPAN -e shell
install Graph

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)