标签: directed-graph

这是一棵树:

1. 会有一个根.

2. 每个树节点都有零个或多个子节点.

3. 允许两个节点指向同一个子节点.比如,节点A和节点B都有子C.

但是,禁止

节点A是节点B的后代,节点B是节点A的后代.

一个被禁止的案例是

节点A有一个子节点C和节点D,

Node C和D都有一个子节点E,

节点E有一个孩子A.

问题是,如何以最快的方式确定这个圈子？

更新:我意识到这是在有向图中找到任何循环.刚才我设法想出了类似于Tarjan算法的解决方案.

感谢您的评论.

我正在努力解决这个算法问题:

我如何编写一个theta(m+n)算法来打印m边,n-顶点有向图中每个顶点的入度和出度,其中有向图用相邻列表表示.

julia LightGraphs中的weakly_connected_components是否应该提供连接组件,如果将DiGraph转换为无向图,那么每个组件应该连接？我试过这个,我没有收到这样的组件？作为一个例子,我在政治博客数据上尝试了这个作为无向网络

data=readdlm(path,',',Int64) #contains edges in each row
N_ = length(unique(vcat(data[:,1],data[:,2]))) ##to get number of vertices
network  = LightGraphs.DiGraph(N_)
#construct the network
for i in 1:size(data,1)
    add_edge!(network, Edge(data[i,1], data[i,2]))
end
#largest weakly connected component
net = weakly_connected_components(network)[1]
temp_net,vmap = induced_subgraph(network, net)

在获得最大的弱连接组件后,我看到以下内容:

isempty([i for i in vertices(temp_net) if isempty(edges(temp_net).adj[i])])

julia>false

签名一些节点没有传入或传出边缘.可能是什么问题？我使用的是最新版本6,但LightGraphs软件包测试似乎正在运行.

以下是我正在研究的问题：

考虑一个有向加权图 G ，其中所有边的权重都是正的。这个问题的目标是找到G 中 两个预先指定的顶点s 和 t之间 的最短路径 ，但有一个额外的扭曲：您可以将（您选择的）恰好一条边的权重更改为零。

换句话说，您必须在G 中选择一条边 以设置为零，以最小化s 和 t之间的最短路径 。给出一个有效的算法来在O ( E lg V )时间内实现这个目标， 并分析你的算法的运行时间。次优解决方案将获得较少的信用。

提示：您可能需要反转边缘，多次运行熟悉的算法，并做一些额外的工作

所以我尝试将 Dijkstra 从s运行到所有其他节点，然后我尝试反转边缘并再次从s运行它到所有其他节点。但是，我发现我们必须从s到所有其他节点运行 Dijskstra ，然后反转边，然后从所有其他节点运行 Dijkstra到t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们只需将最大权重边缘设置为零。反转边缘有什么意义？

在有向网络中的聚类和社区检测：调查中， Malliaros & Vazirgiannis (2013) 描述了许多用于有向图中聚类和社区检测的算法。我有一个相对较大的图，400.000 个节点，180.000.000 个边，正在寻找可以检测其中社区的软件，但是我研究过的网络分析程序（ R 的igraph包）似乎没有任何功能能够检测大型有向网络中的簇的算法（igraph具有cluster_fast_greedy()，cluster_louvain()但它们仅适用于无向图）。R 或 python 中是否有任何包可以做到这一点？

在一个非常大的图上的社区检测中提出了类似的问题，区别在于我需要 python 或 R 的包。

简单问题：G 是带边的有向图

a->b
a->c
c->d

它存储在 Python 字典中

G={'a':['b','c'], c:['d']}

我想要a和d之间的路径，d和a之间的路径，b和d之间的路径等等。

我试图了解如何正确生成基于Erdős-Rényi模型的有向随机图.我看过网络x上的erdos_renyi_graph功能.我已经将我的真实网络(5317)的节点数设置为n参数,然后为pi计算:

p = (< k_in > + < k_out >)/(n-1) = (78,302 )/(5317-1) = 0, 014729496

我已经计算出平均度数为in_degree和out_degree的总和.

应用此概率,它生成了一个包含5317个节点和415.727个边的随机图.比我的真实网络(207.167边缘)更多的边缘.

我做错什么了吗？

为什么在 n 个顶点和 m 条边上的完整有向图 G 有 m = n(n-1) 条边。但是我尝试了很多例子来证明这个陈述是错误的，这将是 n(n-1)/2 但是我们的教授对这个陈述给出了正确的答案。有人可以向我解释这种说法的正确性吗？