определить, является ли список вершин путем в графе - PullRequest
Новая
       28

определить, является ли список вершин путем в графе

0 голосов
/ 30 апреля 2018

При условии ввода графа и списка вершин, является ли список вершин путем в графе? 

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 3), ({'d', 'g'}, 7), ({'d', 'h'}, 0) ,
      ({'e', 'i'}, 1), ({'e', 'j'}, 5), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]


L1 = ['a', 'd', 'h', 'g']

Как лучше всего решить эту проблему?

РЕДАКТИРОВАТЬ

Теперь это решено - с помощью Эймери. 

def edges(G):
    edgeset = [tuple(sorted(x[0])) for x in G[1]]
    return edgeset

def is_a_path(G,L,edgeset):
    for i in range(len(L)-1):
        a= tuple(sorted((L[i], L[i+1])))
        print(edgeset, a)
        if a not in edgeset:
            return False
    return True

1 Ответ

0 голосов
/ 30 апреля 2018

Примечание: Я предполагаю, G[0] - это список вершин, G[1] список (неориентированных) ребер, представленный как ({<vertex tag>, <vertex tag>}, <weight>). Поскольку вы используете наборы для представления ребер, я предположил, что ваш график не является ненаправленным.

Прежде всего, вы можете проверить, что все элементы в L1 являются вершинами. 

for candidate in L1:
    if not (candidate in G[0]]):
        # If it's not a vertex, we exit returning False
        return False
# If we're here, it means every candidate was a vertex
return True

Как только это будет сделано, вы должны проверить, что элементы L1 являются путями, то есть для каждого элемента L1 (кроме последнего) существуют ребро этого элемента и следующего. 

for i in range(len(L1)-1):
    # Create a candidate edge
    candidate = { L1[i], L1[i+1] }
    if not (candidate in G[0][:][0]):
        # If it's not in the list of edges, we exit returning False
        return False
# If every candidate edge is indeed an edge, then it's a path
return True
...