README

此包允许您创建、持久化和删除有向无环图。

基本用法
安装
使用
警告
测试
附加说明
变更日志
贡献
安全
致谢
许可证

基本用法

创建直接边

$newEdges = dag()->createEdge($startVertex, $endVertex, $source);
// $newEdges contains all new edges, including the specified direct edge, that were created as a result of the request.

删除直接边

$deleted = dag()->deleteEdge($startVertex, $endVertex, $source);
// $deleted is true if any edges were deleted as a result of the request, false otherwise.

安装

此包需要PHP 7.2或更高版本以及Laravel 6.0或更高版本。

您可以通过composer安装此包

composer require telkins/laravel-dag-manager

该包将自动注册自身。

您可以使用以下命令发布迁移

php artisan vendor:publish --provider="Telkins\Dag\Providers\DagServiceProvider" --tag="migrations"

注意：默认迁移假定您正在使用整数作为您的DAG边ID。

您还可以选择使用以下命令发布配置文件

php artisan vendor:publish --provider="Telkins\Dag\Providers\DagServiceProvider" --tag="config"

这是发布配置文件的内容

return [
    /**
     *-------------------------------------------------------------------------
     * Max Hops
     *-------------------------------------------------------------------------
     *
     * This value represents the maximum number of hops that are allowed where
     * hops "[i]ndicates how many vertex hops are necessary for the path; it is
     * zero for direct edges".
     *
     * The more hops that are allowed (and used), then the more DAG edges will
     * be created.  This will have an increasing impact on performance, space,
     * and memory.  Whether or not it's negligible, noticeable, or impactful
     * depends on a variety of factors.
     */
    'max_hops' => 5,

    /**
     *-------------------------------------------------------------------------
     * Default Database Connection Name
     *-------------------------------------------------------------------------
     *
     * This is the name of the database connection where the dag table
     * can be found.
     *
     * Set to `null` to use the default connection.
     */
    'default_database_connection_name' => null,

    /**
     *-------------------------------------------------------------------------
     * Table Name
     *-------------------------------------------------------------------------
     *
     * This is the name of the table where the dag structure
     * will be stored.
     */
    'table_name' => 'dag_edges',
];

警告

来自Kemal Erdogan的文章，"在SQL数据库上表示有向无环图（DAG）的模型"

理论上，使用此模型，公平的有向无环图的传递闭包集的大小可以非常大，远远超过数百万。给定DAG本身的边数是图论中的研究课题，但我的实际测试表明，存在具有100个顶点和300条边的DAG，其传递闭包将创建超过2,000,000行的数据。

在创建“过大”和/或复杂的图时，请注意这一点。

使用

对于“DAG管理”的Eloquent模型，您可以添加Telkins\Models\Traits\IsDagManaged特质

use Illuminate\Database\Eloquent\Model;
use Telkins\Models\Traits\IsDagManaged;

class MyModel extends Model
{
    use IsDagManaged;

    // ...
}

这将允许您轻松访问模型类中的某些功能。

要应用仅包括指定模型ID后代模型的范围

$descendants = MyModel::dagDescendantsOf($myModel->id, 'my-source')->get();

必须提供ID和来源。

同样，要应用仅包括指定模型ID祖先模型的范围

$ancestors = MyModel::dagAncestorsOf($myModel->id, 'my-source')->get();

再次，必须提供ID和来源。

最后，可以应用一个范围，将获取祖先和后代

$ancestors = MyModel::dagRelationsOf($myModel->id, 'my-source')->get();

上述每种方法也允许调用者根据跳数限制结果。因此，如果您想获取指定模型ID的直接子代，则可以进行以下操作

$descendants = MyModel::dagDescendantsOf($myModel->id, 'my-source', 0)->get();

当然，为了获取指定模型ID的父母和祖父母，您可以执行以下操作

$ancestors = MyModel::dagAncestorsOf($myModel->id, 'my-source', 1)->get();

不提供$maxHops参数表示将返回所有后代、祖先或关系。

自定义DAG边模型

如果您需要自定义DAG边模型的行为，则可以使用自己的模型类。

您的自定义模型类必须扩展Telkins\Models\DagEdge类

namespace App\Models;

use Telkins\Models\DagEdge as BaseModel;

class MyDagEdge extends BaseModel
{
...

然后您可以在包配置文件中指定您自定义模型的完全限定类名。

// config/laravel-dag-manager.php
...
'edge_model' => \App\Models\MyDagEdge::class,
...

测试

composer test

附加说明

贡献者可能想考虑利用以下任何一个

relaxedws/lca：一个用于从有向无环图中找到最低公共祖先的PHP库。
clue/graph：一个用PHP编写的数学图/网络库。
graphp/algorithms：PHP中的图算法，包括常见（和不那么常见）的算法。

变更日志

有关最近更改的更多信息，请参阅变更日志。

贡献

请参阅CONTRIBUTING以获取详细信息。

安全

待定

致谢

此外

Kemal Erdogan及其文章《"在SQL数据库中表示有向无环图（DAG）的模型"。
xib及其MySQL存储过程移植（目前未使用，但可能在未来的版本中使用）：xib/DAG_MySQL.sql

许可证

MIT许可证（MIT）。请参阅许可文件以获取更多信息。

telkins / laravel-dag-manager

维护者

详细信息

README

基本用法

安装

警告

使用

自定义DAG边模型

测试

附加说明

变更日志

贡献

安全

致谢

许可证