“is_chordal(graph)” 总是返回 False。

huangapple
go评论145阅读模式
英文:

is_chordal(graph) always returns False

问题

我正在尝试编写一个函数来检查图是否是弦图，但它总是返回False。 有什么想法吗？

英文:

I am trying to write a function to check if a graph is chordal but it always returns False.

  1. def lexbfs(graph):
  2.     queue = deque()  
  3.     result = []  
  4.     
  5.     if len(graph) == 0:
  6.         return result
  7.     
  8.     visited = set() 
  9.         
  10.     start_node = next(iter(graph))  
  11.     
  12.     queue.append(start_node)
  13.     visited.add(start_node)
  15.     while queue:
  16.         node = queue.popleft()
  17.         result.append(node)
  18.         
  19.         for neighbor in graph[node]:
  20.             if neighbor not in visited:
  21.                 visited.add(neighbor)
  22.                 queue.append(neighbor)
  24.     return result
  26. def is_chordal(graph):
  27.     reversed_bfs_order = lexbfs(graph)[::-1]
  28.     
  29.     for u in reversed_bfs_order:
  30.         neighbors_u = set(graph[u]) 
  31.         
  32.         for v in reversed_bfs_order:  
  33.             if v in neighbors_u:      
  34.                 neighbors_v = set(graph[v])  
  35.                
  36.                 A = neighbors_u - {v}
  37.                 if not A.issubset(neighbors_v):   
  38.                     return False
  39.     
  40.     return True

Any idea?

答案1

得分: 1

I had a look at the algorithm on wikipedia, and it seems your code for is_chordal is off on a few points: you should look for the earlier neighbors of u and v, not all neighbors; furthermore, you shouldn't restart from the initial neighbors_u for every v, but from the last one. Here's my fixed version of the function (note that I only tested it on a basic diamond shape and on a triangle, so I may have overlooked something):

我查看了维基百科上的算法，发现您的is_chordal代码存在一些问题：您应该查找u和v的较早邻居，而不是所有邻居；此外，您不应该为每个v从初始的neighbors_u重新开始，而应该从上一个邻居继续。以下是我修复的函数版本（请注意，我只在基本的菱形和三角形上进行了测试，所以可能有遗漏的地方）：

  1. def is_chordal(graph):
  2.     reversed_bfs_order = lexbfs(graph)[::-1]
  3.     
  4.     for i, u in enumerate(reversed_bfs_order):
  5.         neighbors_u = set(graph[u]).intersection(reversed_bfs_order[i+1:]) 
  6.         
  7.         for j, v in enumerate(reversed_bfs_order[i+1:]):  
  8.             if v in neighbors_u:      
  9.                 neighbors_v = set(graph[v]).intersection(reversed_bfs_order[i+j+1:])
  10.                
  11.                 neighbors_u.remove(v)
  12.                 if not neighbors_u.issubset(neighbors_v):   
  13.                     return False
  14.     
  15.     return True

Examples

示例：

  1. diamond = {'A':('B', 'C', 'D'), 'B':('A','C'), 'C':('A','B', 'D'), 'D':('A','C')}
  2. is_chordal(diamond)
  3. Out[80]: True
  4. triangle = {'A':('B', 'C'), 'B':('A','C'), 'C':('A','B')}
  5. is_chordal(triangle)
  6. Out[80]: True
英文:

I had a look at the algorithm on wikipedia, and it seems your code for is_chordal is off on a few points: you should look for the earlier neighbors of u and v, not all neighbors; furthermore, you shouldn't restart from the initial neighbors_u for every v, but from the last one. Here's my fixed version of the function (note that I only tested it on a basic diamond shape and on a triangle, so I may have overlooked something):

  1. def is_chordal(graph):
  2.     reversed_bfs_order = lexbfs(graph)[::-1]
  3.     
  4.     for i, u in enumerate(reversed_bfs_order):
  5.         neighbors_u = set(graph[u]).intersection(reversed_bfs_order[i+1:]) 
  6.         
  7.         for j, v in enumerate(reversed_bfs_order[i+1:]):  
  8.             if v in neighbors_u:      
  9.                 neighbors_v = set(graph[v]).intersection(reversed_bfs_order[i+j+1:])
  10.                
  11.                 neighbors_u.remove(v)
  12.                 if not neighbors_u.issubset(neighbors_v):   
  13.                     return False
  14.     
  15.     return True

Examples

  1. diamond = {'A':('B', 'C', 'D'), 'B':('A','C'), 'C':('A','B', 'D'), 'D':('A','C')}
  2. is_chordal(diamond)
  3. Out[80]: True
  4. triangle = {'A':('B', 'C'), 'B':('A','C'), 'C':('A','B')}
  5. is_chordal(triangle)
  6. Out[80]: True

答案2

得分: 0

以下是翻译好的部分：

  1. def is_chordal(graph):
  2.     reversed_bfs_order = lexbfs(graph)[::-1]
  3.     
  4.     for u in reversed_bfs_order:
  5.         neighbors_u = set(graph[u]) 
  6.         
  7.         for v in reversed_bfs_order:  
  8.             if v in neighbors_u:      
  9.                 neighbors_v = set(graph[v])  
  10.                
  11.                 A = neighbors_u - {v}
  12.                 if not A <= neighbors_v:   # corrected condition
  13.                     return False
  14.     
  15.     return True

在你的代码中，条件是 if not A.issubset(neighbors_v): return False，这个条件检查的是除了 v 外，u 的所有邻居是否也是 v 的邻居，但它并没有考虑到那些既不是 u 的邻居也不是 v 的邻居之间的关系。这可能导致误报，就像在你的情况中发生的那样。

相比之下，在修正后的条件中，它会检查除了 v 外，u 的所有邻居是否也是 v 的邻居，包括那些既不是 u 的邻居也不是 v 的邻居的情况。

英文:

There is an issue with your is_chordal function. Perhaps this could be the correct implementation:

  1. def is_chordal(graph):
  2.     reversed_bfs_order = lexbfs(graph)[::-1]
  3.     
  4.     for u in reversed_bfs_order:
  5.         neighbors_u = set(graph[u]) 
  6.         
  7.         for v in reversed_bfs_order:  
  8.             if v in neighbors_u:      
  9.                 neighbors_v = set(graph[v])  
  10.                
  11.                 A = neighbors_u - {v}
  12.                 if not A &lt;= neighbors_v:   # corrected condition
  13.                     return False
  14.     
  15.     return True

In your code, where the condition is 'if not A.issubset(neighbors_v): return False', this condition checks if all the neighbours of u except v are also neighbors of v, but it doesn't consider the relationship between the neighbors of u that are not neighbors of v. This can lead to a false negative, as is happening in your case.

Whereas in the corrected condition, the condition checks if all the neighbors of u except v are also neighbors of v, including the neighbors of u that are not neighbors of v.

huangapple
  • 本文由 发表于 2023年5月14日 01:48:20
  • 转载请务必保留本文链接：https://go.coder-hub.com/76244152.html
  • graph
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定