时间戳

首页 > 解决方案 > 基于一些数据使用节点和顶点构造图

python - 基于一些数据使用节点和顶点构造图

问题描述

我正在使用由邻接表示给出的有向图。换句话说，图 G 将由一个字典表示，其键是顶点，其值是字典，其键是顶点的邻居，其值可以分配为 1。给定两个顶点 u，v 在有向图 G 可能存在从 u 到 v 的边，但反之则不然。然而，在两个方向上都可能存在边缘。

我创建了一个名为reachable_vertices 的函数，它将一个图G 和顶点v 作为输入，并返回一个可以从v 到达的G 中所有顶点的列表。如果顶点w 可以通过v 到达，这意味着存在一条链 v → v1 → v2... → w，其中从链中的每个顶点到紧随其后的顶点都有一条边。顶点 v 不必具有特定类型，例如 int 或 string，它可以是其中任何一种，它只需要是表示图 G 的字典中的键。

我已经定义了一个名为 cfb_graph 的函数，它不接受任何参数。我从文件 cfb2010.csv（链接如下）中形成了一个有向图，将团队视为顶点，并且仅当团队 1 击败团队 2 时才在团队 1 和团队 2 之间创建一条边。数据集链接 = 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 的值将是 while 循环中的第一个顶点 u，其中 w 是 u 的邻居。

另外，我想定义一个名为 path 的函数，它将一个图 G 和两个顶点 v 和 w 作为输入。如果 w 可以从 v 到达，它将返回一个顶点列表，其第一个元素是 v，最后一个元素是 w，其他顶点是从 v 到 w 的路径上的顶点，按照它们被遍历的顺序。如果没有路径，我应该返回 None。我可能想使用上面定义的函数。

标签： pythonpython-3.xalgorithmdictionarygraph

解决方案

我想快速而强大的图形处理库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 还有一个与您的函数相等的函数，称为路径函数：

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

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

PS 可达节点构建使用BFS 算法。

推荐阅读