networkx-astar-path

提供当前边和前一条边给权重函数的A*实现。

需求

• Python 3.6.1或更高版本

安装

pip install networkx-astar-path

用法

networkx的A*实现将权重函数的参数限制为当前边。有些场景要求当前边的成本取决于前一条边。一个例子是两条边之间的方位角。当然，方位角可以预先计算并存储在节点上，但有时这是不可能的。

此实现的API与之前相同，唯一不同的是权重函数的签名已更改

def weight(graph: nx.Graph, prev_edge: Optional[Tuple[Any, Any]], cur_edge: Tuple[Any, Any]) -> float:
    ...

如果权重函数是第一次被调用，那么prev_edge的值是None，因为我们还没有访问过其他任何边。

示例

注意 此示例不太实用，但它显示了该函数的使用方法。

给定以下图

import networks as nx

graph = nx.DiGraph()

graph.add_edges_from([('S', 'A1')], weight=-2)
graph.add_edges_from([('A1', 'T')], weight=7)
graph.add_edges_from([('S','A2'), ('A2','B2'),('B2','C2'),('C2','T')], weight=1)

我们正在寻找从S到T的最短路径。

已经选择了权重，使得当简单相加时路径['S', 'A2', 'B2', 'C2', 'T']是最短的，但如果当前边的权重除以前一条边的权重，则路径更长。后者的最短路径是['S', 'A1', 'T']。

让我们只通过查看当前边的权重来找到最短路径。

from networkx_astar_path import astar_path

path = astar_path(graph, source='S', target='T', weight="weight")
# ['S', 'A2', 'B2', 'C2', 'T']

我们定义了一个“简单”的权重函数，它考虑了前一个边的权重。

如果我们已经访问过一条边，则权重是当前边的权重除以前一个边的权重。否则，返回当前边的权重。

from networkx_astar_path import astar_path

def dependent_weight(graph: nx.Graph, prev_edge: Optional[Tuple[Any, Any]], cur_edge: Tuple[Any, Any]) -> float:
    if prev_edge is None:
        return graph.get_edge_data(*cur_edge)['weight']

    prev_weight = graph.get_edge_data(*prev_edge)['weight']
    cur_weight = graph.get_edge_data(*cur_edge)['weight']
    return cur_weight / prev_weight

path = astar_path(graph, source='S', target='T', weight=dependent_weight)
# ['S', 'A1', 'T']

开发

本项目使用poetry进行打包和管理所有依赖，并使用pre-commit运行flake8、isort、mypy和black。

克隆此存储库并运行

poetry install
poetry run pre-commit install

以创建包含所有依赖项的虚拟环境。之后，您可以使用以下命令运行测试套件：

poetry run pytest

此存储库遵循常规提交风格。

Cookiecutter模板

本项目使用cruft和cookiecutter-pyproject模板创建。要更新此存储库到最新模板版本，请在存储库根目录中运行：

cruft update

。