Source code for graph_tool.search

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# graph_tool -- a general graph manipulation python module
#
# Copyright (C) 2006-2017 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

"""
``graph_tool.search`` - Search algorithms
-----------------------------------------

This module includes several search algorithms, which are customizable to
arbitrary purposes. It is mostly a wrapper around the Visitor interface of the
`Boost Graph Library <http://www.boost.org/doc/libs/release/libs/graph/doc/visitor_concepts.html>`_,
and the respective search functions.


Summary
+++++++

.. autosummary::
   :nosignatures:

   bfs_search
   bfs_iterator
   dfs_search
   dfs_iterator
   dijkstra_search
   dijkstra_iterator
   astar_search
   astar_iterator
   bellman_ford_search
   BFSVisitor
   DFSVisitor
   DijkstraVisitor
   BellmanFordVisitor
   AStarVisitor
   StopSearch

Examples
++++++++

In this module, most documentation examples will make use of the network
:download:`search_example.xml <search_example.xml>`, shown below.

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> pos = g.vp["pos"]
>>> gt.graph_draw(g, pos, vertex_text=name, vertex_font_size=12, vertex_shape="double_circle",
...               vertex_fill_color="#729fcf", vertex_pen_width=3,
...               edge_pen_width=weight, output="search_example.pdf")
<...>

.. testcode::
   :hide:

   gt.graph_draw(g, pos=pos, vertex_text=name, vertex_font_size=12, vertex_shape="double_circle",
                 vertex_fill_color="#729fcf", vertex_pen_width=3,
                 edge_pen_width=weight, output="search_example.png")

.. figure:: search_example.*
   :alt: search example
   :align: center

   This is the network used in the examples below. The width of the edges
   correspond to the values of the "weight" property map.


Contents
++++++++
"""

from __future__ import division, absolute_import, print_function
import sys
if sys.version_info < (3,):
    range = xrange

from .. dl_import import dl_import
dl_import("from . import libgraph_tool_search")

from .. import _prop, _python_type, _get_null_vertex
import weakref
import numpy

__all__ = ["bfs_search", "bfs_iterator", "BFSVisitor", "dfs_search",
           "dfs_iterator", "DFSVisitor", "dijkstra_search", "dijkstra_iterator",
           "DijkstraVisitor", "bellman_ford_search", "BellmanFordVisitor",
           "astar_search", "astar_iterator", "AStarVisitor", "StopSearch"]


[docs]class BFSVisitor(object): r"""A visitor object that is invoked at the event-points inside the :func:`~graph_tool.search.bfs_search` algorithm. By default, it performs no action, and should be used as a base class in order to be useful."""
[docs] def initialize_vertex(self, u): """This is invoked on every vertex of the graph before the start of the graph search. """ return
[docs] def discover_vertex(self, u): """This is invoked when a vertex is encountered for the first time.""" return
[docs] def examine_vertex(self, u): """This is invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u.""" return
[docs] def examine_edge(self, e): """This is invoked on every out-edge of each vertex after it is discovered.""" return
[docs] def tree_edge(self, e): """This is invoked on each edge as it becomes a member of the edges that form the search tree.""" return
[docs] def non_tree_edge(self, e): """This is invoked on back or cross edges for directed graphs and cross edges for undirected graphs. """ return
[docs] def gray_target(self, e): """This is invoked on the subset of non-tree edges whose target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue.""" return
[docs] def black_target(self, e): """This is invoked on the subset of non-tree edges whose target vertex is colored black at the time of examination. The color black indicates that the vertex has been removed from the queue.""" return
[docs] def finish_vertex(self, u): """This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before the out-edges of the adjacent vertices have been examined). """ return
[docs]def bfs_iterator(g, source=None, array=False): r"""Return an iterator of the edges corresponding to a breath-first traversal of the graph. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. source : :class:`~graph_tool.Vertex` (optional, default: ``None``) Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order. array : ``bool`` (optional, default: ``False``) If ``True``, a :class:`numpy.ndarray` will the edge endpoints be returned instead. Returns ------- bfs_iterator : Iterator or :class:`numpy.ndarray` An iterator over the edges in breath-first order. If ``array == True``, this will be a :class:`numpy.ndarray` instead, of shape ``(E,2)``, containing the edge endpoints. See Also -------- dfs_iterator: Depth-first search dijkstra_iterator: Dijkstra's search algorithm astar_iterator: :math:`A^*` heuristic search algorithm Notes ----- See :func:`~graph_tool.search.bfs_search` for an explanation of the algorithm. The time complexity is :math:`O(1)` to create the generator and :math:`O(V + E)` to traverse it completely. Examples -------- >>> for e in gt.bfs_iterator(g, g.vertex(0)): ... print(name[e.source()], "->", name[e.target()]) Bob -> Eve Bob -> Chuck Bob -> Carlos Bob -> Isaac Eve -> Imothep Eve -> Carol Carlos -> Alice Alice -> Oscar Alice -> Dave References ---------- .. [bfs] Edward Moore, "The shortest path through a maze", International Symposium on the Theory of Switching, 1959 .. [bfs-bgl] http://www.boost.org/doc/libs/release/libs/graph/doc/breadth_first_search.html .. [bfs-wikipedia] http://en.wikipedia.org/wiki/Breadth-first_search """ if source is None: source = _get_null_vertex() else: source = int(source) if not array: return libgraph_tool_search.bfs_search_generator(g._Graph__graph, source) else: return libgraph_tool_search.bfs_search_array(g._Graph__graph, source)
[docs]class DFSVisitor(object): r""" A visitor object that is invoked at the event-points inside the :func:`~graph_tool.search.dfs_search` algorithm. By default, it performs no action, and should be used as a base class in order to be useful. """
[docs] def initialize_vertex(self, u): """ This is invoked on every vertex of the graph before the start of the graph search. """ return
[docs] def start_vertex(self, u): """ This is invoked on the source vertex once before the start of the search. """ return
[docs] def discover_vertex(self, u): """This is invoked when a vertex is encountered for the first time.""" return
[docs] def examine_edge(self, e): """ This is invoked on every out-edge of each vertex after it is discovered. """ return
[docs] def tree_edge(self, e): """ This is invoked on each edge as it becomes a member of the edges that form the search tree. """ return
[docs] def back_edge(self, e): """ This is invoked on the back edges in the graph. For an undirected graph there is some ambiguity between tree edges and back edges since the edge (u,v) and (v,u) are the same edge, but both the :meth:`~graph_tool.search.DFSVisitor.tree_edge` and :meth:`~graph_tool.search..DFSVisitor.back_edge` functions will be invoked. One way to resolve this ambiguity is to record the tree edges, and then disregard the back-edges that are already marked as tree edges. An easy way to record tree edges is to record predecessors at the tree_edge event point. """ return
[docs] def forward_or_cross_edge(self, e): """ This is invoked on forward or cross edges in the graph. In an undirected graph this method is never called. """ return
[docs] def finish_vertex(self, e): """ This is invoked on vertex u after finish_vertex has been called for all the vertices in the DFS-tree rooted at vertex u. If vertex u is a leaf in the DFS-tree, then the :meth:`~graph_tool..search.DFSVisitor.finish_vertex` function is called on u after all the out-edges of u have been examined. """ return
[docs]def dfs_iterator(g, source=None, array=False): r"""Return an iterator of the edges corresponding to a depth-first traversal of the graph. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. source : :class:`~graph_tool.Vertex` (optional, default: ``None``) Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order. array : ``bool`` (optional, default: ``False``) If ``True``, a :class:`numpy.ndarray` will the edge endpoints be returned instead. Returns ------- dfs_iterator : Iterator or :class:`numpy.ndarray` An iterator over the edges in depth-first order. If ``array == True``, this will be a :class:`numpy.ndarray` instead, of shape ``(E,2)``, containing the edge endpoints. See Also -------- bfs_iterator: Breadth-first search dijkstra_iterator: Dijkstra's search algorithm astar_iterator: :math:`A^*` heuristic search algorithm Notes ----- See :func:`~graph_tool.search.dfs_search` for an explanation of the algorithm. The time complexity is :math:`O(1)` to create the generator and :math:`O(V + E)` to traverse it completely. Examples -------- >>> for e in gt.dfs_iterator(g, g.vertex(0)): ... print(name[e.source()], "->", name[e.target()]) Bob -> Eve Eve -> Isaac Isaac -> Chuck Chuck -> Imothep Imothep -> Carol Imothep -> Carlos Carlos -> Alice Alice -> Oscar Oscar -> Dave References ---------- .. [dfs-bgl] http://www.boost.org/doc/libs/release/libs/graph/doc/depth_first_search.html .. [dfs-wikipedia] http://en.wikipedia.org/wiki/Depth-first_search """ if source is None: source = _get_null_vertex() else: source = int(source) if not array: return libgraph_tool_search.dfs_search_generator(g._Graph__graph, source) else: return libgraph_tool_search.dfs_search_array(g._Graph__graph, source)
[docs]class DijkstraVisitor(object): r"""A visitor object that is invoked at the event-points inside the :func:`~graph_tool.search.dijkstra_search` algorithm. By default, it performs no action, and should be used as a base class in order to be useful. """
[docs] def initialize_vertex(self, u): """ This is invoked on every vertex of the graph before the start of the graph search. """ return
[docs] def examine_vertex(self, u): """ This is invoked on a vertex as it is popped from the queue. This happens immediately before :meth:`~graph_tool.DijsktraVisitor.examine_edge` is invoked on each of the out-edges of vertex u. """ return
[docs] def examine_edge(self, e): """ This is invoked on every out-edge of each vertex after it is discovered. """ return
[docs] def discover_vertex(self, u): """This is invoked when a vertex is encountered for the first time.""" return
[docs] def edge_relaxed(self, e): """ Upon examination, if the following condition holds then the edge is relaxed (its distance is reduced), and this method is invoked. :: (u, v) = tuple(e) assert(compare(combine(d[u], weight[e]), d[v])) """ return
[docs] def edge_not_relaxed(self, e): """ Upon examination, if the edge is not relaxed (see :meth:`~graph_tool.search.DijsktraVisitor.edge_relaxed`) then this method is invoked. """ return
[docs] def finish_vertex(self, u): """ This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). """ return
[docs]def dijkstra_iterator(g, weight, source=None, dist_map=None, combine=None, compare=None, zero=0, infinity=numpy.inf, array=False): r"""Return an iterator of the edges corresponding to a Dijkstra traversal of the graph. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. weight : :class:`~graph_tool.PropertyMap` Edge property map with weight values. source : :class:`~graph_tool.Vertex` (optional, default: ``None``) Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order. dist_map : :class:`~graph_tool.PropertyMap` (optional, default: ``None``) A vertex property map where the distances from the source will be stored. combine : binary function (optional, default: ``lambda a, b: a + b``) This function is used to combine distances to compute the distance of a path. compare : binary function (optional, default: ``lambda a, b: a < b``) This function is use to compare distances to determine which vertex is closer to the source vertex. zero : int or float (optional, default: ``0``) Value assumed to correspond to a distance of zero by the combine and compare functions. infinity : int or float (optional, default: ``numpy.inf``) Value assumed to correspond to a distance of infinity by the combine and compare functions. array : ``bool`` (optional, default: ``False``) If ``True``, a :class:`numpy.ndarray` will the edge endpoints be returned instead. Returns ------- dfs_iterator : Iterator or :class:`numpy.ndarray` An iterator over the edges in Dijkstra order. If ``array == True``, this will be a :class:`numpy.ndarray` instead, of shape ``(E,2)``, containing the edge endpoints. See Also -------- bfs_iterator: Breadth-first search dfs_iterator: Depth-first search astar_iterator: :math:`A^*` heuristic search algorithm Notes ----- See :func:`~graph_tool.search.dijkstra_search` for an explanation of the algorithm. The time complexity is :math:`O(1)` to create the generator and :math:`O(E + V\log V)` to traverse it completely. Examples -------- >>> for e in gt.dijkstra_iterator(g, weight, g.vertex(0)): ... print(name[e.source()], "->", name[e.target()]) Bob -> Eve Bob -> Chuck Bob -> Carlos Bob -> Isaac Eve -> Imothep Eve -> Carol Carlos -> Alice Alice -> Oscar Alice -> Dave References ---------- .. [dijkstra] E. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1:269-271, 1959. .. [dijkstra-bgl] http://www.boost.org/doc/libs/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html .. [dijkstra-wikipedia] http://en.wikipedia.org/wiki/Dijkstra's_algorithm """ if dist_map is None: dist_map = g.new_vertex_property(weight.value_type()) try: if dist_map.value_type() != "python::object": zero = _python_type(dist_map.value_type())(zero) except OverflowError: zero = (weight.a.max() + 1) * g.num_vertices() zero = _python_type(dist_map.value_type())(zero) try: if dist_map.value_type() != "python::object": infinity = _python_type(dist_map.value_type())(infinity) except OverflowError: infinity = (weight.a.max() + 1) * g.num_vertices() infinity = _python_type(dist_map.value_type())(infinity) if source is None: source = _get_null_vertex() else: source = int(source) if compare is None and combine is None: if not array: return libgraph_tool_search.dijkstra_generator_fast(g._Graph__graph, source, _prop("v", g, dist_map), _prop("e", g, weight), zero, infinity) else: return libgraph_tool_search.dijkstra_array_fast(g._Graph__graph, source, _prop("v", g, dist_map), _prop("e", g, weight), zero, infinity) else: if compare is None: compare = lambda a, b: a < b if combine is None: combine = lambda a, b: a + b if not array: return libgraph_tool_search.dijkstra_generator(g._Graph__graph, source, _prop("v", g, dist_map), _prop("e", g, weight), compare, combine, zero, infinity) else: return libgraph_tool_search.dijkstra_array(g._Graph__graph, source, _prop("v", g, dist_map), _prop("e", g, weight), compare, combine, zero, infinity)
[docs]class BellmanFordVisitor(object): r"""A visitor object that is invoked at the event-points inside the :func:`~graph_tool.search.bellman_ford_search` algorithm. By default, it performs no action, and should be used as a base class in order to be useful. """
[docs] def examine_edge(self, e): """ This is invoked on every edge in the graph ``|V|`` times. """ return
[docs] def edge_relaxed(self, e): """ This is invoked when the distance label for the target vertex is decreased. The edge (u,v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree. """ return
[docs] def edge_not_relaxed(self, e): """ This is invoked if the distance label for the target vertex is not decreased. """ return
[docs] def edge_minimized(self, e): """ This is invoked during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge is minimized then this function is invoked. """ return
[docs] def edge_not_minimized(self, e): """ This is invoked during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge was not minimized, this function is invoked. This happens when there is a negative cycle in the graph. """ return
[docs]class AStarVisitor(object): r"""A visitor object that is invoked at the event-points inside the :func:`~graph_tool.search.astar_search` algorithm. By default, it performs no action, and should be used as a base class in order to be useful. """
[docs] def initialize_vertex(self, u): """ This is invoked on every vertex of the graph before the start of the graph search. """ return
[docs] def examine_vertex(self, u): """ This is invoked on a vertex as it is popped from the queue (i.e. it has the lowest cost on the ``OPEN`` list). This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u. """ return
[docs] def examine_edge(self, e): """ This is invoked on every out-edge of each vertex after it is examined. """ return
[docs] def discover_vertex(self, u): """ This is invoked when a vertex is first discovered and is added to the ``OPEN`` list. """ return
[docs] def edge_relaxed(self, e): """ Upon examination, if the following condition holds then the edge is relaxed (its distance is reduced), and this method is invoked. :: (u, v) = tuple(e) assert(compare(combine(d[u], weight[e]), d[v])) """ return
[docs] def edge_not_relaxed(self, e): """ Upon examination, if the edge is not relaxed (see :meth:`~graph_tool.search.AStarVisitor.edge_relaxed`) then this method is invoked. """ return
[docs] def black_target(self, e): """ This is invoked when a vertex that is on the ``CLOSED`` list is "rediscovered" via a more efficient path, and is re-added to the ``OPEN`` list. """ return
[docs] def finish_vertex(self, u): """ This is invoked on a vertex when it is added to the CLOSED list, which happens after all of its out edges have been examined. """ return
[docs]def astar_iterator(g, source, weight, heuristic=lambda v: 1, dist_map=None, combine=None, compare=None, zero=0, infinity=numpy.inf, array=False): r"""Return an iterator of the edges corresponding to an :math:`A^*` traversal of the graph. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. source : :class:`~graph_tool.Vertex` Source vertex. weight : :class:`~graph_tool.PropertyMap` Edge property map with weight values. heuristic : unary function (optional, default: ``lambda v: 1``) The heuristic function that guides the search. It should take a single argument which is a :class:`~graph_tool.Vertex`, and output an estimated distance from the supplied vertex to the target vertex. dist_map : :class:`~graph_tool.PropertyMap` (optional, default: ``None``) A vertex property map where the distances from the source will be stored. combine : binary function (optional, default: ``lambda a, b: a + b``) This function is used to combine distances to compute the distance of a path. compare : binary function (optional, default: ``lambda a, b: a < b``) This function is use to compare distances to determine which vertex is closer to the source vertex. zero : int or float (optional, default: ``0``) Value assumed to correspond to a distance of zero by the combine and compare functions. infinity : int or float (optional, default: ``numpy.inf``) Value assumed to correspond to a distance of infinity by the combine and compare functions. array : ``bool`` (optional, default: ``False``) If ``True``, a :class:`numpy.ndarray` will the edge endpoints be returned instead. Returns ------- astar_iterator : Iterator or :class:`numpy.ndarray` An iterator over the edges in :math:`A^*` order. If ``array == True``, this will be a :class:`numpy.ndarray` instead, of shape ``(E,2)``, containing the edge endpoints. See Also -------- bfs_iterator: Breadth-first search dfs_iterator: Depth-first search dijkstra_iterator: Dijkstra search algorithm Notes ----- See :func:`~graph_tool.search.astar_search` for an explanation of the algorithm. The time complexity is :math:`O(1)` to create the generator and :math:`O((E + V)\log V)` to traverse it completely. Examples -------- >>> g = gt.load_graph("search_example.xml") >>> name = g.vp["name"] >>> weight = g.ep["weight"] >>> for e in gt.astar_iterator(g, g.vertex(0), weight): ... print(name[e.source()], "->", name[e.target()]) Bob -> Eve Bob -> Chuck Bob -> Carlos Bob -> Isaac Eve -> Imothep Eve -> Carol Carlos -> Alice Alice -> Oscar Alice -> Dave References ---------- .. [astar] Hart, P. E.; Nilsson, N. J.; Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100-107, 1968. :doi:`10.1109/TSSC.1968.300136` .. [astar-bgl] http://www.boost.org/doc/libs/release/libs/graph/doc/astar_search.html .. [astar-wikipedia] http://en.wikipedia.org/wiki/A*_search_algorithm """ if dist_map is None: dist_map = g.new_vertex_property(weight.value_type()) try: if dist_map.value_type() != "python::object": zero = _python_type(dist_map.value_type())(zero) except OverflowError: zero = (weight.a.max() + 1) * g.num_vertices() zero = _python_type(dist_map.value_type())(zero) try: if dist_map.value_type() != "python::object": infinity = _python_type(dist_map.value_type())(infinity) except OverflowError: infinity = (weight.a.max() + 1) * g.num_vertices() infinity = _python_type(dist_map.value_type())(infinity) if compare is None and combine is None: if not array: return libgraph_tool_search.astar_generator_fast(g._Graph__graph, int(source), _prop("v", g, dist_map), _prop("e", g, weight), zero, infinity, heuristic) else: return libgraph_tool_search.astar_array_fast(g._Graph__graph, int(source), _prop("v", g, dist_map), _prop("e", g, weight), zero, infinity, heuristic) else: if compare is None: compare = lambda a, b: a < b if combine is None: combine = lambda a, b: a + b if not array: return libgraph_tool_search.astar_generator(g._Graph__graph, int(source), _prop("v", g, dist_map), _prop("e", g, weight), compare, combine, zero, infinity, heuristic) else: return libgraph_tool_search.astar_array(g._Graph__graph, int(source), _prop("v", g, dist_map), _prop("e", g, weight), compare, combine, zero, infinity, heuristic)
[docs]class StopSearch(Exception): """If this exception is raised from inside any search visitor object, the search is aborted.""" pass