GraphViz2::Marpa::TreeUtils

Table of contents

NAME
Synopsis
Description
Scripts shipped with this distro
Distributions
Installation
Constructor and Initialization
Calling new()
Methods
allow_cycles([$integer])
command()
dot_input()
dot_output()
driver([$pathToDot])
find_fixed_length_paths()
format([$string])
image_size([$size_specification])
new()
output_fixed_length_paths($title)
path_length([$integer])
path_set()
report_fixed_length_paths()
report_paths([$Boolean])
root()
start_node([$string])
tree_dot_file([$name])
tree_image_file([$name])
FAQ
The number of options is confusing!
Isn't your code at risk from the 'combinatorial explosion' problem?
How are cycles in the graph handled?
Are all paths found unique?
Reference
Version Numbers
Machine-Readable Change Log
Support
Author
Copyright

NAME

GraphViz2::Marpa::TreeUtils - Provide various analyses of Graphviz dot files

Synopsis

Perl usage:

Either pass parameters in to new():

        GraphViz2::Marpa::TreeUtils -> new
        (
            allow_cycles    => 1,
            input_file      => 'data/90.KW91.gv',
            path_length     => 4,
            report_paths    => 1,
            start_node      => 'Act_1',
            tree_dot_file   => 'data/fixed.length.paths.gv',
            tree_image_file => 'html/fixed.length.paths.svg',
        ) -> find_fixed_length_paths;

Or call methods to set parameters;

        my($parser) = GraphViz2::Marpa::TreeUtils -> new;

        $parser -> allow_cycles(1);
        $parser -> input_file('data/90.KW91.gv');
        $parser -> path_length(4);
        $parser -> report_paths(1);
        $parser -> start_node('Act_1');
        $parser -> tree_dot_file('data/fixed.length.paths.gv');
        $parser -> tree_image_file('html/fixed.length.paths.sgv');

        $parser -> find_fixed_length_paths;

Command line usage:

        shell> perl scripts/fixed.length.paths.pl -h

Or see scripts/fixed.length.paths.sh, which hard-codes my test data.

All scripts and input and output files listed here are shipped with the distro.

Description

GraphViz2::Marpa::TreeUtils parses Graphviz dot files and processes the output in various ways.

This class is a descendent of GraphViz2::Marpa, and hence inherits all its keys to new(), and all its methods.

Currently, the only feature available is to find all paths of a given length starting from a given node.

Sample output: http://savage.net.au/Perl-modules/html/graphviz2.marpa/fixed.length.paths.html.

Note: Currently the code ignores the directions of the edges, meaning all input graphs are assumed to be undirected.

Scripts shipped with this distro

All scripts are in the scripts/ directory. This means they do not get installed along with the package.

Data files are in data/, and html and svg files are in html/.

o fixed.length.paths.pl

This runs the find_fixed_length_paths() method in GraphViz2::Marpa::TreeUtils.

Try shell> perl fixed.length.paths.pl -h

o fixed.length.paths.sh

This runs fixed.length.paths.pl with hard-coded parameters, and is what I use for testing new code.

Then it runs generate.demo.pl.

Lastly it copies the output to my web server's directory (under the doc root called $DR).

o generate.demo.pl

This uses the Text::Xslate template file html/fixed.length.paths.tx to generate fixed.length.paths.html.

See also t/fixed.length.paths.t.

Distributions

This module is available as a Unix-style distro (*.tgz).

See http://savage.net.au/Perl-modules/html/installing-a-module.html for help on unpacking and installing distros.

Installation

Install GraphViz2::Marpa::TreeUtils as you would for any Perl module:

Run:

        cpanm GraphViz2::Marpa::TreeUtils

or run:

        sudo cpan GraphViz2::Marpa::TreeUtils

or unpack the distro, and then either:

        perl Build.PL
        ./Build
        ./Build test
        sudo ./Build install

or:

        perl Makefile.PL
        make (or dmake or nmake)
        make test
        make install

Constructor and Initialization

Calling new()

new() is called as my($obj) = GraphViz2::Marpa::TreeUtils -> new(k1 => v1, k2 => v2, ...).

It returns a new object of type GraphViz2::Marpa::TreeUtils.

This class is a descendent of GraphViz2::Marpa, and hence inherits all its keys to new(), and all its methods.

Further, these key-value pairs are accepted in the parameter list (see corresponding methods for details [e.g. "path_length($integer)"]):

o allow_cycles => $integer

Specify whether or not cycles are allowed in the paths found.

Values for $integer:

o 0 - Do not allow any cycles

This is the default.

o 1 - Allow any node to be included once or twice.

Default: 0.

o driver => thePathToDot

Specify the OS's path to the dot program, to override the default.

Default: Use which('dot'), via the module File::Which, to find the dot executable.

o format => $aDOTOutputImageFormat

Specify the image type to pass to dot, as the value of dot's -T option.

Default: 'svg'.

o image_size => xInches,yInches

Specify the size of the output image, in inches.

Default: ''.

o path_length => $integer

Specify the length of all paths to be included in the output.

Here, length means the number of edges between nodes.

Default: 0.

This parameter is mandatory, and must be > 0.

o report_paths => $Boolean

Specify whether or not to print a report of the paths found.

Default: 0 (do not print).

o start_node => $theNameOfANode

Specify the name of the node where all paths must start from.

Default: ''.

This parameter is mandatory.

The name can be the empty string, but must not be undef.

o tree_dot_file => aDOTInputFileName

Specify the name of a file to write which will contain the DOT description of the image of all solutions.

Default: ''.

This file is not written if the value is ''.

o tree_image_file => aDOTOutputFileName

Specify the name of a file to write which will contain the output of running dot.

The value of the format option determines what sort of image is created.

Default: ''.

This file is not written if the value is ''.

Methods

This class is a descendent of GraphViz2::Marpa, and hence inherits all its methods.

Further, these methods are implemented.

allow_cycles([$integer])

Here the [] indicate an optional parameter.

Get or set the value determining whether or not cycles are allowed in the paths found.

'allow_cycles' is a parameter to "new()". See "Constructor and Initialization" for details.

command()

Returns an object of type Set::Array where each element is a line of text to be output to a DOT file. The string obtained by combining these elements is returned by "dot_input()".

You would normally never call this method.

dot_input()

Returns the string which will be input to the dot program.

dot_output()

Returns the string which will has been output by the dot program.

driver([$pathToDot])

Here the [] indicate an optional parameter.

Get or set the OS's path to the dot program.

find_fixed_length_paths()

This is the method which does all the work, and hence must be called.

See the "Synopsis" and scripts/fixed.length.paths.pl.

Returns 0 for success and 1 for failure.

format([$string])

Here the [] indicate an optional parameter.

Get or set the type of image to be output when running dot.

'format' is a parameter to "new()". See "Constructor and Initialization" for details.

image_size([$size_specification])

Here the [] indicate an optional parameter.

Get or set the image size embedded in the output DOT file.

The format is '7,10' or '11,20!'. See the DOT definitions of size and point for details.

'image_size' is a parameter to "new()". See "Constructor and Initialization" for details.

new()

See "Constructor and Initialization" for details on the parameters accepted by "new()".

output_fixed_length_paths($title)

This writes the paths found, as a DOT file, as long as new(output_file => $name) was specified, or if output_file($name) was called before "find_fixed_length_paths()" was called.

path_length([$integer])

Here the [] indicate an optional parameter.

Get or set the length of the paths to be searched for.

'path_length' is a parameter to "new()". See "Constructor and Initialization" for details.

path_set()

Returns the arrayref of paths found. Each element is 1 path, and paths are stored as an arrayref of objects of type Tree::DAG_Node.

See the source code of sub "report_fixed_length_paths()" for sample usage.

report_fixed_length_paths()

This prints the paths found, as long as new(report_paths => 1) was specified, or if report_paths(1) was called before "find_fixed_length_paths()" was called.

report_paths([$Boolean])

Here the [] indicate an optional parameter.

Get or set the option which determines whether or not the paths found are printed.

'report_paths' is a parameter to "new()". See "Constructor and Initialization" for details.

root()

Returns the root of the tree of nodes parsed from the original DOT file. Each element in this tree is an object of type Tree::DAG_Node.

You would normally never call this method.

start_node([$string])

Here the [] indicate an optional parameter.

Get or set the name of the node from where all paths must start.

'start_node' is a parameter to "new()". See "Constructor and Initialization" for details.

tree_dot_file([$name])

Here the [] indicate an optional parameter.

Specify the name of the dot input file to write.

'tree_dot_file' is a parameter to "new()". See "Constructor and Initialization" for details.

tree_image_file([$name])

Here the [] indicate an optional parameter.

Specify the name of the dot output file to write.

The type of image comes from the format parameter to new(), or from calling "format($string)" before "find_fixed_length_paths()" is called.

'tree_image_file' is a parameter to "new()". See "Constructor and Initialization" for details.

FAQ

The number of options is confusing!

Agreed. Remember that this code calls GraphViz2::Marpa's run() method, which expects a large number of options because it calls both the lexer and the parser.

The options used only by this code are listed under "Calling new()".

The methods used only by this code, which are not options, are:

o "command()"
o "dot_input()"
o "dot_output()"
o "path_set()"
o "root()"

Isn't your code at risk from the 'combinatorial explosion' problem?

Yes. The code does limit the number of possibilies as quickly as possible, but of course there will always be graphs which can't be processed by this module.

Such graphs are deemed to be pathological.

How are cycles in the graph handled?

This is controlled by the allow_cycles option to new(), or the corresponding method "allow_cycles($integer)".

Sample code: Using the input file data/90.KW91.lex (see scripts/fixed.length.paths.sh) we can specify various combinations of parameters like this:

        allow_cycles  path_length  start node  solutions
        0             3            Act_1       9
        1             3            Act_1       22

        0             4            Act_1       12
        1             4            Act_1       53

Are all paths found unique?

Yes.

Reference

Combinatorial Algorithms for Computers and Calculators, A Nijenhuis and H Wilf, p 240.

This books very clearly explains the backtracking parser I used to process the combinations of nodes found at each point along each path. Source code in the book is in Fortran.

The book is now downloadable as a PDF from http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html.

Version Numbers

Version numbers < 1.00 represent development versions. From 1.00 up, they are production versions.

Machine-Readable Change Log

The file CHANGES was converted into Changelog.ini by Module::Metadata::Changes.

Support

Email the author, or log a bug on RT:

https://rt.cpan.org/Public/Dist/Display.html?Name=GraphViz2::Marpa::TreeUtils.

Author

GraphViz2::Marpa::TreeUtils was written by Ron Savage in 2012.

Home page: http://savage.net.au/index.html.

Copyright

Australian copyright © 2012, Ron Savage.

        All Programs of mine are 'OSI Certified Open Source Software';
        you can redistribute them and/or modify them under the terms of
        The Artistic License, a copy of which is available at:
        http://www.opensource.org/licenses/index.html