NAME

Graph::Directed - Perl class for representing directed graphs.

SYNOPSIS

use Graph::Directed;

my $graph = Graph::Directed->new();

$graph->add(1 => 2, 2 => 3, 3 => 2);

print join(' ', $graph->topsort());

DESCRIPTION

This module implements directed graphs and some common algorithms used on such.

CLASS METHODS

Following is a list of class methods available. Class methods affect the entire class of objects; this in contrast with object methods, which only affect the object they are applied to.

new()

Construct a new graph.

OBJECT METHODS

For graphs, the following object methods are defined. Object methods are applied to the objects (in this case the graph). We denote a graph constructed using new (above) by $graph.

$graph->add((from, <to>), ...)

Add the edges to the graph. Possibly create new nodes if needed. Returns GRAPH to allow chained calls.

$graph->nodes()

Return the nodes of GRAPH as a list.

$graph->edge(from,to)

Test if the edge (from,to) is in GRAPH.

$graph->succ(node, ...)

Returns the set of successors to the supplied nodes. Observe that duplicates may be returned.

$graph->pred(node, ...)

Returns the set of predecessors to the supplied nodes. Observe that duplicates may be returned.

$graph->dump()

Emit a ASCII representation of the graph using the Dot format.

$graph->reachable_from(node, ...)

Compute the forward reachability set of the list of nodes, i.e. the states that can be reached from any of the given nodes.

EXPORTABLE OBJECT METHODS

Following are exportable object methods, i.e., methods that can be called either as e.g. $graph-scc()> or scc($graph) (the latter after importing the method).

scc $graph

Use Tarjan's algorithm to find all strongly connected components in the graph.

Returns a list of references to lists containing the strongly connected components.

Since we are using the built-in sort, the time complexity is currently O(e + v log v), where v is the number of nodes of the graph and e is the number of edges. This can be reduced to O(v + e) by using counting sort instead of the built-in sorter.

topsort $graph

Return a list of nodes topologically sorted with respect to the given graph. It is implemented as a depth first pass through the graph, since a topological sorting only exists if the graph is acyclic.

The result if the graph contains a cycle is the undefined value.

The time complexity of the algorithm is O(v + e), where v is the number of nodes in the graph and e is the number of edges in the graph.

INTERNAL OBJECT METHODS

Following are the internal object methods available in the package. These are used for implementation of the routines above, but also available for other uses, if the need should arise.

$graph->dfs_forest(options)

Compute the depth-first search forest of the graph. Currently there are two options available:

DIRECTION => direction

The direction of the search, either FORWARD or BACKWARD.

NODES => [node1, ... ]

The nodes to be searched, in the order of investigation. Observe that this should be a reference to a list.

The forest will be returned as a list of references to lists. This method is used by, among other, the algorithm to compute strongly connected components below.

dfs(adjecency hash, node)

Perform a depth first search of the tree with root node node, marking progress in the hash %Visited. Return a list of visited nodes, in pre-order. Observe that %Visited is not reset prior to searching, this you have to do yourself.

The hash %Visited will contain references to pairs of integers where the first number is the discovery time of the node, while the second number is the finishing time of the node.

NOTES

This version of the package is only a draft version. The final version will have a better structure and separation between the graph internals, the available output formats, and the different graph algorithms.

There is also a package written by Neil Bowers from the Canon Research Center and a package written by Jarkko Hietaniemi. Although the package by Jarkko has a topological sort, the computation of strongly connected components, as well as forward reachability are missing in the packages (not a big deal, they can be added).

This package is acually the result of me needing exactly these algorithms for other work. The package was written prior to the distribution of packages by Neil and Jarkko, which is why the work was not based on any of those.

COPYRIGHT

Copyright 1998 Mats Kindahl. All rights reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.