标签: graph-theory

我正在尝试找到一个简单的Java API来创建图形关系.它应该有一些功能,例如addEdge(),addNode(),isConnected(node1, node2),findPaths(node1, node2),等我不需要UI,只是逻辑.

我发现了一堆学术项目,但似乎都没有" The Definitive Graph API ".

有谁知道这样的API？

我希望能够计算家谱中两个人之间的家庭关系,给定以下数据模式(从我的实际数据模式简化,仅显示直接适用于此问题的列):

individual
----------
id
gender

child
----------
child_id
father_id
mother_id

通过这种结构,如何计算两个个体id(即堂兄,大叔叔等)之间的关系.

另外,由于实际上有两种关系(即AB可能是侄子而BA是叔叔),如何生成另一种的补充(给定叔叔,并假设我们知道性别,我们如何生成侄子？).这是一个微不足道的问题,前者是我真正感兴趣的.

谢谢大家!

带有MST的图形(正权重边)如果某个边缘,e被修改为新值,更新MST而不完全重建它的最佳方法是什么.我认为这可以在线性时间内完成.此外,似乎我需要一个不同的算法,基于1)e是否已经是MST的一部分,2)新边缘e是大于还是小于原始边缘

我试图理解顶点覆盖和支配集之间的区别.

根据理解,在支配集中,集合D包含与不在D中的其他顶点相邻的顶点(对于V中的每个v,v在D中或者在D中与1相邻).

在顶点覆盖中,D中的所有顶点都覆盖了所有边缘,但是通过这样做,它们与其他顶点相邻,它们不在D中 - 那么为什么它不是一个支配集？

我担心这可能会影响NP-Complete问题.我希望有人可以给我一个答案,不管它是否存在.而且我正在寻找更多的答案,而不仅仅是是或否.我想知道为什么.如果你可以说,"这基本上是这个问题'x',它不是NP-Complete.(维基百科链接)"

(不,这不是作业)

有没有办法确定两个点是否连接在任意非有向图上.例如,以下

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

点A到M(没有'I')是控制点(如天然气管道中的阀门),可以是打开的或关闭的.'+'是节点(比如管道T),我猜Well和House也是节点.

我想知道我是否关闭了一个任意控制点(例如C)井和房子是否仍然连接(其他控制点也可以关闭).例如,如果B,K和D关闭,我们仍然有一条通过AEJFCGLM的路径,关闭C将断开Well和House.当然; 如果只是D被关闭,只关闭C不会断开众议院.

另一种说法是C桥/切边/地峡？

我可以将每个控制点视为图形上的权重(0表示打开,1表示关闭); 然后找到Well和House之间的最短路径(结果> = 1表示它们已断开连接.我可以通过各种方法将算法短路以找到最短路径(例如,一旦达到1就丢弃路径,停止搜索一旦我们有任何连接井和房子的路径等等.当然,我也可以在放弃之前对要检查的跳数进行一些人为的限制.

有人必须先把这类问题归类,我才错过这个名字.

我正在研究图切割算法的数据结构.问题是在最短路径上进行不同的切割.我制作了数据结构,我不确定属性.

输入是最短路径的有向图,它是有界点阵,有最小和最大元素的部分有序集.

将节点n的下一个节点N(n)定义为一组节点b,其中a <b且没有c,其中<c <b.类似地定义前一节点P(n).扩展集合的定义,N(n)对于S中的n的N(S)并集,类似于P(S).

在节点集合L,N(L),N(N(L)),...的列表上容易进行不同的切割,其中对于每个相邻的集合对A,N(A)= B认为存在没有分区:

A = A_1 union A_2
B = B_1 union B_2
with B_i = N(A_i), A_i = P(B_i) for i=1,2.

使用此属性创建具有映射的新晶格:

• 子格到一个节点
• 如果找到上部分区而不是创建边缘(分区基数编号).

简单来说,格子 - >点阵映射的算法是:

A = {minimum node}
new_node = [A]
1:
while A, N(A) don't have partitions
  append N(A) to new_node
  A = N(A)
for each partition $B_i$
  last_new_node = new_node
  create new_node = [B_i]
  create edge last_new_node to new_node
  go to 1
At the end fix …

给定一个无向图,我想生成所有子图,这些子图是大小为N的树,其中size指的是树中边的数量.

我知道它们中有很多(至少对于具有恒定连通性的图形呈指数多) - 但这很好,因为我相信节点和边缘的数量使得这对于至少小的N值(例如10或更小)来说易于处理).

该算法应该具有内存效率 - 也就是说,它不需要同时在内存中包含所有图形或其中的一些大部分子集,因为即使对于相对较小的图形,这也可能超过可用内存.所以像DFS这样的东西是可取的.

给出起始图graph和所需长度,这是我在伪代码中的想法N:

选择任意节点,root作为起点并调用alltrees(graph, N, root)

alltrees(graph, N, root)
 given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
 for each tuple (X1, X2, ... XM) above
   create a subgraph "current" initially empty
   for each integer Xi in X1...XM (the …

我在我的一本AI书中读过,用于模拟或游戏中寻路的流行算法(A-Star,Dijkstra)也用于解决众所周知的"15-puzzle".

任何人都可以给我一些关于如何将15-puzzle减少到节点和边缘图的指针,以便我可以应用其中一种算法？

如果我将图中的每个节点视为游戏状态,那么该树不会变得非常大吗？或者只是这样做的方式？

根据书(算法简介),在dfs中,边被分为4种:

1. 树边缘,如果在边缘(u,v)中,首先发现v,则(u,v)是树边缘.
2. Back Edge,如果......,v已经被发现而v是一个祖先,那么它就是一个后缘.
3. 前向边缘,如果......,v已经被发现而v是u的后代,它是前沿.
4. Cross Edge,除上述三个以外的所有边缘.

我的问题是,当我试图找出(u,v)是后边缘还是前边缘时,如何确定v是你的祖先还是后代？

I am calculating triad census as follows for my undirected network.

import networkx as nx
G = nx.Graph()
G.add_edges_from(
    [('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E', 'F'),
     ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G')])

from itertools import combinations
#print(len(list(combinations(G.nodes, 3))))

triad_class = {}
for nodes in combinations(G.nodes, 3):
    n_edges = G.subgraph(nodes).number_of_edges()
    triad_class.setdefault(n_edges, []).append(nodes)
print(triad_class)

It works fine with small networks. However, now I have a bigger network with approximately 4000-8000 nodes. When I try to run …