Построение графа с использованием узлов и вершин на основе некоторых данных

Question

Я работаю с ориентированными графами, заданными представлением смежности.Другими словами, граф G будет представлен словарем, ключами которого являются вершины, а значениями являются словари, ключами которых являются соседи вершины, значения которых могут быть присвоены 1. При заданных двух вершинах u, v в направленномВ графе G может быть ребро от u до v, но не наоборот.Однако возможно, что в обоих направлениях есть ребро.

Я создал функцию под названием reachable_vertices, которая будет принимать граф G и вершину v в качестве входных данных и возвращает список всех вершин в G, которые могутбыть достигнутым из v. Если вершина w может быть достигнута посредством v, это означает, что существует цепочка v → v1 → v2 ... → w, где есть ребро от каждой вершины в цепочке до той, которая находится сразу после нее.Вершина v не обязательно должна иметь определенный тип, такой как int или string, это может быть любой из них, это должен быть только ключ в словаре, представляющий граф G.

Я определил функцию с именемcfb_graph, который не принимает аргументов.Я сформировал ориентированный граф из файла cfb2010.csv (ссылка ниже), рассматривая команды как вершины и создавая грань между team1 и team2, только если team1 победила team2.Ссылка на набор данных = https://drive.google.com/open?id=1ZgNjH_QE7if1xHMfRU2-ebd9bNpL2E3d

cfb_graph вернет словарь с таким представлением.

Мне удалось найти следующие вопросы, к которым я прилагаю свой код ниже: i.Какие команды не доступны из Оберн.Храните их в списке.II.Какие команды доступны из Нотр-Дама.Храните их в списке.III.Какие команды не достижимы из Алабамы.Сохраните их в списке.

Я работаю над следующим кодом:

def reachable(G, v, setA): # This function checks if it's possible to reach w from v
    setA|={v}
    try:
        for w in set(G[v])-setA:reachable(G,w,setA)
    except KeyError:
        donothing = 0   
    return setA    
##   2a ##
def reachable_vertices(G, v):
    setA=set()
    setA|={v}
    try:
        for n in set(G[v])-setA:reachable(G,n,setA)
    except KeyError:
        donothing = 0    
    return setA    

def cfb_graph():
    svertex = []
    evertex = []
    count= 0
    file = open("cfb2010.csv","r")
    for line in file:  
        fields = line.split(",")
        if fields[5].replace("\n", "") == 'W':
            svertex.append(fields[1])
            evertex.append(fields[2])
        if count == 0:
            count = count +1


    graph = {}
    for i in range(len(svertex)):
        v = svertex[i]
        if v in graph:
            graph[v] |= set([evertex[i]])
        else:
            graph[v] = set([evertex[i]])    

    for key, value in graph.items():
          graph[key] =  dict.fromkeys(value,1) 
    return(graph)


######Part 2 c############
auburn_answer = list(set(cfb_graph().keys()).difference(set(reachable_vertices(cfb_graph(), "Auburn"))))
notre_dame_answer = reachable_vertices(cfb_graph(), "Notre Dame")
alabama_answer = list(set(cfb_graph().keys()).difference(set(reachable_vertices(cfb_graph(), "Alabama"))))

В частности, для каждой вершины я хочу вернуть словарь, в котором ключи являются достижимыми вершинами и значениямикак сейчас будет описано.Если вершина w достижима из вершины v, существует путь от v к w.Значением, соответствующим w в возвращаемом словаре, будет вершина, которая непосредственно предшествует ему в некотором пути от v до w.Если я использую подход очереди, тогда значение w будет первой вершиной u в цикле while, для которого w является соседом u.

Кроме того, я хочу определить функцию с именем path, которая будет принимать в качестве входных данныхграф G и две вершины v и w.Если w достижимо из v, он вернет список вершин, первый элемент которых равен v, а последним элементом является w, а остальные вершины - это те, которые находятся на пути от v к w в том порядке, в котором они были пройдены.Если пути нет, я должен вернуть None.Я, вероятно, захочу использовать функцию, определенную выше.

Answer 1

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

Я создал небольшой рабочий процесс, который копирует все ваши функциональные возможности и решает ваши проблемы:

# Imports
import networkx as nx
import csv

# Load CSV file and construct the directed graph
G = nx.DiGraph()
with open('cfb2010.csv', 'r') as f:
    sreader = csv.reader(f, delimiter=',')
    for line in sreader:
        if line[-1] != 'W':
            continue
        G.add_node(line[1])
        G.add_node(line[2])
        G.add_edge(line[1], line[2])

# Get all nodes
all_nodes = set(G.nodes())

# Get nodes that can be reached from the particular node
notredame_nodes = set(nx.bfs_tree(G, 'Notre Dame').nodes())
alabama_nodes = set(nx.bfs_tree(G, 'Alabama').nodes())
auburn_nodes = set(nx.bfs_tree(G, 'Auburn').nodes())

# Construct lists of nodes you need
print(all_nodes - alabama_nodes)
print(all_nodes - auburn_nodes)
print(notredame_nodes)

В Networkx также есть функция, равная вашей функции, называемой path function:

print(nx.shortest_path(G, 'Florida', 'Illinois'))

['Florida', 'Penn St', 'Michigan', 'Illinois']

PS При построении достижимых узлов используется алгоритм BFS .