The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Implicit-0.03
River stage zero No dependents
++
/ Graph::Implicit

NAME

Graph::Implicit - graph algorithms for implicitly specified graphs

VERSION

version 0.03

SYNOPSIS

  my $graph = Graph::Implicit->new(sub {
      my $tile = shift;
      map { [$_, $_->intrinsic_cost] }
          $tile->grep_adjacent(sub { $_[0]->is_walkable })
  });
  my @reachable_vertices = $graph->vertices(current_tile());
  my @reachable_edges = $graph->edges(current_tile());
  my ($sssp_predecessors, $dest_vertex) = $graph->dijkstra(
      current_tile(),
      sub { is_target($_[0]) ? 'q' : 0 },
  );
  my @sssp_path = $graph->make_path($sssp_predecessors, $dest_vertex);

DESCRIPTION

This module implements several graph algorithms (for directed, weighted graphs) that can run without having to specify the actual graph. This module models a graph as an arbitrary coderef that maps vertices onto a list of adjacent vertices and weights for the edges to those vertices. Vertices can be represented by any string (or stringifyable piece of data), and don't need to be specified ahead of time; the algorithms will just figure it out. This allows objects to generally just work (they get stringified to "Class=HASH(0xdeadbeef)").

Some caveats: working with complicated data structures which need deep comparisons generally need additional help: [0, 1, 2] ne [0, 1, 2], since those become different references. Also, since the graph isn't specified at all, each method that is called on one needs a vertex to start traversing the graph from, and any vertices not reachable from that vertex won't be found. A few algorithms are also not able to be implemented as efficiently as possible, since the entire graph isn't known ahead of time; for instance, finding all the edges of the graph requires actually doing a graph traversal, rather than just reading them out of the data structure, like you would do in an explicit graph representation.

CONSTRUCTOR

new(CODEREF)

The constructor takes a single argument, a coderef. This coderef should take something representing a vertex, and return a list of arrayrefs, one for each adjacent vertex, which have the vertex as the first element and the weight of the edge to that vertex as the second element. For example, if the graph has three elements A, B, and C, and there is an edge of weight 1 from B to A and an edge of weight 2 from B to C, then the coderef should return ["A", 1], ["C", 2] when called with "B" as its argument.

METHODS

vertices(VERTEX)

Returns a list of all vertices reachable from the given vertex.

edges(VERTEX)

Returns a list of all edges reachable from the given vertex.

neighbors(VERTEX)

Returns a list of neighbors (without weights) of the given vertex.

bfs(VERTEX[, CODEREF])

Does a breadth-first search of the graph, starting at the given vertex. It runs the given coderef (if it exists) on each vertex, as they are encountered. Returns a hashref, whose keys are the encountered vertices, and whose values are the predecessor in the breadth-first search tree.

dfs(VERTEX[, CODEREF])

Does a depth-first search of the graph, starting at the given vertex. It runs the given coderef (if it exists) on each vertex, as they are encountered. Returns a hashref, whose keys are the encountered vertices, and whose values are the predecessor in the depth-first search tree.

dijkstra(VERTEX[, CODEREF])

Runs the Dijkstra single source shortest path algorithm, starting from the given vertex. It also takes a single coderef as an argument, which is called on each vertex as it is encountered - this coderef is expected to return a score for the vertex. If the returned score is 'q', then the search terminates immediately, otherwise it keeps track of the vertex with the highest score. This returns two items: a predicate hashref like the return value of "bfs" and "dfs", and the vertex which was scored highest by the scorer coderef (or the vertex that returned 'q').

astar(VERTEX, CODEREF[, CODEREF])

Runs the A* single source shortest path algorithm. Similar to "dijkstra", but takes an additional coderef parameter (before the scorer coderef), for the heuristic function that the A* algorithm requires.

is_bipartite(VERTEX)

Returns whether or not the reachable part of the graph from the given vertex is bipartite.

make_path(HASHREF, VERTEX)

Takes a predecessor hashref and an ending vertex, and returns the list of vertices traversed to get from the start vertex to the given ending vertex.

BUGS

No known bugs.

Please report any bugs through RT: email bug-graph-implicit at rt.cpan.org, or browse to http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Graph-Implicit.

TODO

dijkstra/astar and bfs/dfs should have more similar interfaces - right now bfs/dfs just call a coderef and do nothing with it, while dijkstra/astar use the coderef to search for a vertex
Several more graph algorithms need implementations
Returning two values from dijkstra and astar is kind of ugly, need to make this better

SEE ALSO

Graph

SUPPORT

You can find this documentation for this module with the perldoc command.

    perldoc Graph::Implicit

You can also look for information at:

AUTHOR

  Jesse Luehrs <doy at tozt dot net>

COPYRIGHT AND LICENSE

This software is copyright (c) 2009 by Jesse Luehrs.

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