Преобразовать структуру сообщества (список) в список смежности - PullRequest
Новая
       92

Преобразовать структуру сообщества (список) в список смежности

1 голос
/ 07 июня 2019

Учитывая структуру сообщества (список списков):

[[A,B,C], [B,D,E,G], [A,C,F,H],[F,K, H]]

и предполагается, что каждое ребро имеет вес 1, не ориентированный в подгруппе.

Я хотел бы найти самого влиятельного человека, который имеет самую короткую связь с G, F (минимальной суммой краев), применяя поиск по ширине / глубине для каждого человека.

Вотуниверсальный код поиска в ширину: 

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

Дело в том, что «граф» должен быть представлен в виде списка смежности.Например: 

graph = {'A': set(['B', 'C', 'F', 'H']),
         'B': set(['D', 'E','G']),
         'C': set(['A', 'F', 'H']),
         'D': set(['B', 'E', 'G' ]),
         'E': set(['B', 'D', 'G' ]),
         'F': set(['K', 'H']),
         'G': set(['B', 'D', 'E'])
         'H': set(['K', 'F']}

Основной вопрос: Как преобразовать структуру (список) сообщества в список смежности?

Дополнительный вопрос: Есть ли другой подходящий алгоритм?

Edit1: я пытался следовать этому stackoverflow post .Но я застрял в улучшении кода для достижения ожидаемого результата

Ответы [ 2 ]

1 голос
/ 07 июня 2019

Предполагая, что все сообщества полностью связаны, вы можете довольно быстро преобразовать их в список смежности, перебирая группы и используя setdefault, чтобы создать новую запись, где это необходимо, и добавив узлы: 

community = [['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K','H']]

adj_list = {}

for group in community:
    for member in group:
        adj_list.setdefault(member, set()).update((set(group) - {member}))

adj_list будет тогда: 

{'A': {'B', 'C', 'F', 'H'},
 'B': {'A', 'C', 'D', 'E', 'G'},
 'C': {'A', 'B', 'F', 'H'},
 'D': {'B', 'E', 'G'},
 'E': {'B', 'D', 'G'},
 'G': {'B', 'D', 'E'},
 'F': {'A', 'C', 'H', 'K'},
 'H': {'A', 'C', 'F', 'K'},
 'K': {'F', 'H'}}

Альтернативой может быть использование defaultdict(set), тогда вы можете просто проиндексировать его и обновить аналогичным образом.

1 голос
/ 07 июня 2019

Это может получить желаемый результат 

A1=[['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K', 'H']]
dict1={}
for l in A1:
    for i in l:
        dict1[i]=[]

for i in dict1:

        index=100
        for j in A1:
            try:

                if j.index(i)<index:
                    index=j.index(i)
                    dict1[i]=[]
                    for k in j:
                        if k!=i:
                            dict1[i].append(k)
            except:
                pass
...