---
name: "Graph::Traversal"
section: "3pm"
platform: "linux"
package: "libgraph-perl"
version: "1:0.9735-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Graph::Traversal"
---

# Graph::Traversal(3pm)

traverse graphs

## NAME

Graph::Traversal - traverse graphs

## SYNOPSIS

Don't use Graph::Traversal directly, use Graph::Traversal::DFS or Graph::Traversal::BFS instead.

```
    use Graph;
    my $g = Graph->new;
    $g->add_edge(...);
    use Graph::Traversal::...;
    my $t = Graph::Traversal::...->new($g, %opt);
    $t->...
```

## DESCRIPTION

You can control how the graph is traversed by the various callback parameters in the `%opt`.  In the parameters descriptions below the `$u` and `$v` are vertices, and the `$self` is the traversal object itself.

### Callback parameters

The following callback parameters are available:

- tree\_edge

  Called when traversing an edge that belongs to the traversal tree. Called with arguments ($u, `$v`, `$self`).

- non\_tree\_edge

  Called when an edge is met which either leads back to the traversal tree (either a `"back_edge"`, a `"down_edge"`, or a `"cross_edge"`). Called with arguments ($u, `$v`, `$self`).

- pre\_edge

  Called for edges in preorder. Called with arguments ($u, `$v`, `$self`).

- post\_edge

  Called for edges in postorder. Called with arguments ($u, `$v`, `$self`).

- back\_edge

  Called for back edges. Called with arguments ($u, `$v`, `$self`).

- down\_edge

  Called for down edges. Called with arguments ($u, `$v`, `$self`).

- cross\_edge

  Called for cross edges. Called with arguments ($u, `$v`, `$self`).

- pre

  - pre\_vertex

  Called for vertices in preorder. Called with arguments ($v, `$self`).

- post

  - post\_vertex

  Called for vertices in postorder. Called with arguments ($v, `$self`).

- first\_root

  Called when choosing the first root (start) vertex for traversal. Called with arguments ($self, `$unseen`) where `$unseen` is a hash reference with the unseen vertices as keys. If not supplied, defaults to the same as `"next_root"`.

- next\_root

  Called when choosing the next root (after the first one) vertex for traversal (useful when the graph is not connected).  Called with arguments ($self, `$unseen`) where `$unseen` is a hash reference with the unseen vertices as keys.  If you want only the first reachable subgraph to be processed, set the next\_root to `"undef"`.

- start

  Identical to defining `"first_root"` and undefining `"next_root"`.

- next\_alphabetic

  Set this to true if you want the vertices to be processed in alphabetic order (and leave first\_root/next\_root undefined).

- next\_numeric

  Set this to true if you want the vertices to be processed in numeric order (and leave first\_root/next\_root undefined).

- next\_successor

  Called when choosing the next vertex to visit.  Called with arguments ($self, `$next`) where `$next` is a hash reference with the possible next vertices as keys.  Use this to provide a custom ordering for choosing vertices, as opposed to `"next_numeric"` or `"next_alphabetic"`.

The parameters `"first_root"` and `"next_successor"` have a 'hierarchy' of how they are determined: if they have been explicitly defined, use that value.  If not, use the value of `"next_alphabetic"`, if that has been defined.  If not, use the value of `"next_numeric"`, if that has been defined.  If not, the next vertex to be visited is chosen randomly.

### Methods

The following methods are available:

- unseen

  Return the unseen vertices in random order.

- seen

  Return the seen vertices in random order.

- seeing

  Return the active fringe vertices in random order.

- preorder

  Return the vertices in preorder traversal order.

- postorder

  Return the vertices in postorder traversal order.

- vertex\_by\_preorder

  ```
      $v = $t->vertex_by_preorder($i)
  ```

  Return the ith (0..$V-1) vertex by preorder.

- preorder\_by\_vertex

  ```
      $i = $t->preorder_by_vertex($v)
  ```

  Return the preorder index (0..$V-1) by vertex.

- vertex\_by\_postorder

  ```
      $v = $t->vertex_by_postorder($i)
  ```

  Return the ith (0..$V-1) vertex by postorder.

- postorder\_by\_vertex

  ```
      $i = $t->postorder_by_vertex($v)
  ```

  Return the postorder index (0..$V-1) by vertex.

- preorder\_vertices

  Return a hash with the vertices as the keys and their preorder indices as the values.

- postorder\_vertices

  Return a hash with the vertices as the keys and their postorder indices as the values.

- tree

  Return the traversal tree as a graph.

- has\_state

  ```
      $t->has_state('s')
  ```

  Test whether the traversal has state 's' attached to it.

- get\_state

  ```
      $t->get_state('s')
  ```

  Get the state 's' attached to the traversal (`"undef"` if none).

- set\_state

  ```
      $t->set_state('s', $s)
  ```

  Set the state 's' attached to the traversal.

- delete\_state

  ```
      $t->delete_state('s')
  ```

  Delete the state 's' from the traversal.

### Special callbacks

If in a callback you call the special `"terminate"` method, the traversal is terminated, no more vertices are traversed.

## SEE ALSO

Graph::Traversal::DFS, Graph::Traversal::BFS

## AUTHOR AND COPYRIGHT

Jarkko Hietaniemi *jhi@iki.fi*

## LICENSE

This module is licensed under the same terms as Perl itself.