is_chordal(graph) always returns False

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

def lexbfs(graph):
    queue = deque()  
    result = []  
    
    if len(graph) == 0:
        return result
    
    visited = set() 
        
    start_node = next(iter(graph))  
    
    queue.append(start_node)
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

def is_chordal(graph):
    reversed_bfs_order = lexbfs(graph)[::-1]
    
    for u in reversed_bfs_order:
        neighbors_u = set(graph[u]) 
        
        for v in reversed_bfs_order:  
            if v in neighbors_u:      
                neighbors_v = set(graph[v])  
               
                A = neighbors_u - {v}
                if not A.issubset(neighbors_v):   
                    return False
    
    return True

Any idea?

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):

def is_chordal(graph):
    reversed_bfs_order = lexbfs(graph)[::-1]
    
    for i, u in enumerate(reversed_bfs_order):
        neighbors_u = set(graph[u]).intersection(reversed_bfs_order[i+1:]) 
        
        for j, v in enumerate(reversed_bfs_order[i+1:]):  
            if v in neighbors_u:      
                neighbors_v = set(graph[v]).intersection(reversed_bfs_order[i+j+1:])
               
                neighbors_u.remove(v)
                if not neighbors_u.issubset(neighbors_v):   
                    return False
    
    return True

Examples

diamond = {'A':('B', 'C', 'D'), 'B':('A','C'), 'C':('A','B', 'D'), 'D':('A','C')}
is_chordal(diamond)
Out[80]: True
triangle = {'A':('B', 'C'), 'B':('A','C'), 'C':('A','B')}
is_chordal(triangle)
Out[80]: True

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

def is_chordal(graph):
    reversed_bfs_order = lexbfs(graph)[::-1]
    
    for u in reversed_bfs_order:
        neighbors_u = set(graph[u]) 
        
        for v in reversed_bfs_order:  
            if v in neighbors_u:      
                neighbors_v = set(graph[v])  
               
                A = neighbors_u - {v}
                if not A <= neighbors_v:   # corrected condition
                    return False
    
    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.