标签: directed-graph

我正在考虑图形数据结构实现，并正在查看“发生率列表”表示。这里有一个简短的描述：

发生率列表

因此图中的每个顶点都存储它所关联的边的列表。

鉴于我的图是有向图，从这个描述中我不太清楚以下几点：

1. 图本身是否也存储所有边的列表？
2. 顶点只存储出边，还是入出边？
3. 如果两者都有，它们是否在单独的列表中？

我非常熟悉其他图表示形式（邻接列表、邻接矩阵、边列表、关联矩阵），所以这不是一个关于一般图实现的问题，只是这个特定的问题。

任何指示将不胜感激。

我有一个每秒在内存中创建数千个图形的应用程序。我希望找到一种方法来保存这些以供后续查询。它们并不是特别大（可能最多约 1k 个节点）。

我需要能够存储整个图形对象，包括节点属性和边缘属性。然后，我需要能够根据节点中的时间属性在特定时间窗口内搜索图形。

有没有一种简单的方法可以将这些数据强制转换为 neo4j ？我还没有找到任何这方面的例子。虽然我发现了几个 python 库，包括嵌入式 neo4j 和休息客户端。

手动遍历图形并以这种方式存储它的常见方法是？

有没有更好的持久性替代方案？

问题

我需要在 sqlite 数据库中存储有向图，我想知道如何解决这个问题。

我的第一个解决方案是创建两个表，一个用于节点，一个用于边缘，但是与问题的非关系模型相比，我对插入性能不满意。

给定一个包含 10 万个节点的典型图，每个节点都有 50 个传出边，插入到关系模型中大约需要 20 秒，而使用扁平方法则需要 7 秒。

实际问题

• 我可以做些什么来加快使用关系模型将图形插入数据库的过程吗？
• 我是否以次优的方式使用 SQLite API？
• 我是否应该考虑使用关系方法，因为它不是必需的，只是“很好”？

附加信息

我写了两个示例来演示我的问题：

关系法

    public sealed class RelationalGraphDatabase
        : IDatabase
    {
        private readonly SQLiteConnection _connection;

        public RelationalGraphDatabase()
        {
            const string fname = @"E:\relational_graph.db";
            if (File.Exists(fname))
                File.Delete(fname);

            var conn = new SQLiteConnectionStringBuilder
                {
                    DataSource = fname
                };
            _connection = new SQLiteConnection(conn.ToString());
            _connection.Open();
            using (
                var command = new SQLiteCommand("CREATE TABLE Node (Id INTEGER PRIMARY KEY, Name TEXT)", _connection))
            {
                command.ExecuteNonQuery(); …

我实现了一项功能，您可以平移和缩放整个图表，而且还可以拖动一个特定节点。我现在的问题是，我找不到在拖动节点时更新边缘的方法。

在这里您可以找到最小设置：

http://codepen.io/anon/pen/XJZrxm

在：

function dragstarted(d) {
  // find edges which link to the currently moved node
} 
function dragged(d) {
  // update edges
}

当然，这种行为也应该适用于更多的节点和边。

我想计算有向图中可用的有向循环总数（只需要计数）。

您可以假设图形是作为邻接矩阵给出的。

我知道DFS但无法为这个问题制定一个有效的算法。

请提供一些使用DFS.

有向图和无向图上的 bfs 在实现上有何不同。

我在网上找到了以下伪代码。我对无向图没问题。但不知道如何实现有向图。

 frontier = new Queue()
  mark root visited (set root.distance = 0)
  frontier.push(root)
  while frontier not empty {
     Vertex v = frontier.pop()
    for each successor v' of v {
    if v' unvisited {
        frontier.push(v')
        mark v' visited (v'.distance = v.distance + 1)
    }
    }
  }

我正在为我的有向图寻找一种高效的Union-Find（又名Disjoint Set）数据结构，它具有循环和森林。鉴于这样的图表，我想回答以下查询：G

1. 我可以v从到达节点u吗？
2. 从该节点u是不可达？

对于单个“源”节点u，我可以运行DFS搜索并回答我是否可以v从它访问。m + n在最坏的情况下，单个 DFS 搜索的上限成本为，其中m和n分别是图中顶点和边的数量。但是，我有很多这样的“源”节点，我想知道是否有比将 DFS 与所有m“源”节点分开运行更好的方法（m * (m + n)在最坏的情况下，它的上限成本为。）

似乎有向图的 Union-Find 数据结构可以有效地回答这两个问题。令我惊讶的是，经过大量的在线搜索后，我找不到任何解决方案。我是否在错误的方向思考问题？

我找到了这个答案，但无法理解。

我有 pandas 数据框，由 10 列组成。

• 每行包含用户在线执行的一个步骤。总共 10 列，因此所有 10 个步骤过程
• 假设第一个活动是预订机票，那么步骤是登录网站-->给出 src 目的地时间-->选择座位-->付款--查看

所以每一步都可能发生各种排列，我想从所有数据集中绘制一个有向图。

目前networkx仅支持2列

# libraries
import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# Build your graph
G=nx.from_pandas_dataframe(df, 'src', 'dest',create_using=nx.DiGraph())

# Plot it
nx.draw(G, with_labels=True)
plt.show()

有人可以告诉我如何为两列以上的有向图绘制它吗

描述

该问题的目的是实现一个接口，该接口将根据任务的依赖关系信息对任务列表进行排序。例如，如果任务 A 依赖于任务 B 和 C，则这意味着要开始处理任务 A，必须首先完成任务 B 和 C。我认为它应该像有向图结构。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * The task class represents a certain activities that must be done as the part of the project planning
 */
class Task {

    /**
     * Unique name of the activity
     */
    private String name;

    /**
     * A list of names of the activities that must be completed in order to be able to start the current activity
     */
    private List<String> predecessors;

    public …

我需要在php和MySQL中构建一个家谱.我很惊讶缺乏开源可定制的html系列树构建软件,但我离题了.我花了很多时间阅读有关存储MySQL有向图和家谱的知识.一切都对我有意义:拥有一个包含节点(人)的表和一个包含边(关系)的表.

我唯一的问题是我不确定存储不一定相邻的关系的最佳方式,例如兄弟和祖父母的关系.起初我并不认为这会是一件大事,因为我可以无形地强制执行一个解决这些联系的父母(每个人都有父母).

但是,我还需要能够存储可能没有共同父母的关系,例如浪漫的伴侣.我已经读到的一切表明,父子关系,但因为恋爱对象不共享一个共同的父(希望),我不知道如何将它存储在边表.我应该使用不同的表格,还是什么？如果它在同一个表中,我该如何表示？只要我用非熟悉的关系做这件事,我也可以和家人一起做.

总结一下,有三个问题:

• 我如何表示横向关系？
• 如果横向关系有一个共同的父母,我该如何存储它？这应该是family表格中存在其他横向关系的标志吗？
• 如何在孩子离开两个或多个边缘(祖父母)的情况下存储父子关系,但是直接父母不可用？

任何帮助表示赞赏,如果有人对某些javascript/html系列树构建软件有任何建议,那将是非常棒的.