读取文件并将其分配给变量

2024-03-29 00:27:03 发布

您现在位置:Python中文网/ 问答频道 /正文

我最近开始编码,并尝试了自定义的“最大流算法”代码,并开始更改函数,以了解它们是如何工作的,以及何时尝试更改

graph = [[0, 16, 13, 0, 0, 0], 
    [0, 0, 10, 12, 0, 0], 
    [0, 4, 0, 0, 14, 0], 
    [0, 0, 9, 0, 0, 20], 
    [0, 0, 0, 7, 0, 4], 
    [0, 0, 0, 0, 0, 0]]

进入

fileobject = open("Testdata.txt","r")
graph = fileobject.readlines();

我发现以下错误:

Traceback (most recent call last):
  File "C:/Users/DELL/Desktop/maxflow.py", line 92, in <module>
    print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))
  File "C:/Users/DELL/Desktop/maxflow.py", line 57, in FordFulkerson
    while self.BFS(source, sink, parent) :
  File "C:/Users/DELL/Desktop/maxflow.py", line 38, in BFS
    if visited[ind] == False and val > 0 :
TypeError: '>' not supported between instances of 'str' and 'int'

这是完整的代码:

from collections import defaultdict 

#This class represents a directed graph using adjacency matrix representation 
class Graph: 

    def __init__(self,graph): 
        self.graph = graph # residual graph 
        self. ROW = len(graph) 
        #self.COL = len(gr[0]) 


    '''Returns true if there is a path from source 's' to sink 't' in 
    residual graph. Also fills parent[] to store the path '''
    def BFS(self,s, t, parent): 

        # Mark all the vertices as not visited 
        visited =[False]*(self.ROW) 

        # Create a queue for BFS 
        queue=[] 

        # Mark the source node as visited and enqueue it 
        queue.append(s) 
        visited[s] = True

        # Standard BFS Loop 
        while queue: 

            #Dequeue a vertex from queue and print it 
            u = queue.pop(0) 

            # Get all adjacent vertices of the dequeued vertex u 
            # If a adjacent has not been visited, then mark it 
            # visited and enqueue it 
            for ind, val in enumerate(self.graph[u]): 
                if visited[ind] == False and val > 0 : 
                    queue.append(ind) 
                    visited[ind] = True
                    parent[ind] = u 

        # If we reached sink in BFS starting from source, then return 
        # true, else false 
        return True if visited[t] else False


    # Returns tne maximum flow from s to t in the given graph 
    def FordFulkerson(self, source, sink): 

        # This array is filled by BFS and to store path 
        parent = [-1]*(self.ROW) 

        max_flow = 0 # There is no flow initially 

        # Augment the flow while there is path from source to sink 
        while self.BFS(source, sink, parent) : 

            # Find minimum residual capacity of the edges along the 
            # path filled by BFS. Or we can say find the maximum flow 
            # through the path found. 
            path_flow = float("Inf") 
            s = sink 
            while(s != source): 
                path_flow = min (path_flow, self.graph[parent[s]][s]) 
                s = parent[s] 

            # Add path flow to overall flow 
            max_flow += path_flow 

            # update residual capacities of the edges and reverse edges 
            # along the path 
            v = sink 
            while(v != source): 
                u = parent[v] 
                self.graph[u][v] -= path_flow 
                self.graph[v][u] += path_flow 
                v = parent[v] 

        return max_flow 


# Create a graph given in the above diagram 

fileobject = open("Testdata.txt","r")
graph = fileobject.readlines();

g = Graph(graph) 

source = 0; sink = 5

print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))

我需要通过读取文件将给定值更改为变量“graph”,而不会出现任何这些错误。有什么建议可以改进这个代码吗


Tags: andthepathinselfsourcequeueis
1条回答
网友
1楼 · 发布于 2024-03-29 00:27:03

我认为您需要将val转换为int。我认为当您从文件中读取图形时,所有数字都被视为字符串

from collections import defaultdict 

#This class represents a directed graph using adjacency matrix representation 
class Graph: 

    def __init__(self,graph): 
        self.graph = graph # residual graph 
        self. ROW = len(graph) 
        #self.COL = len(gr[0]) 


    '''Returns true if there is a path from source 's' to sink 't' in 
    residual graph. Also fills parent[] to store the path '''
    def BFS(self,s, t, parent): 

        # Mark all the vertices as not visited 
        visited =[False]*(self.ROW) 

        # Create a queue for BFS 
        queue=[] 

        # Mark the source node as visited and enqueue it 
        queue.append(s) 
        visited[s] = True

        # Standard BFS Loop 
        while queue: 

            #Dequeue a vertex from queue and print it 
            u = queue.pop(0) 

            # Get all adjacent vertices of the dequeued vertex u 
            # If a adjacent has not been visited, then mark it 
            # visited and enqueue it 
            for ind, val in enumerate(self.graph[u]): 
                if visited[ind] == False and int(val) > 0 : 
                    queue.append(ind) 
                    visited[ind] = True
                    parent[ind] = u 

        # If we reached sink in BFS starting from source, then return 
        # true, else false 
        return True if visited[t] else False


    # Returns tne maximum flow from s to t in the given graph 
    def FordFulkerson(self, source, sink): 

        # This array is filled by BFS and to store path 
        parent = [-1]*(self.ROW) 

        max_flow = 0 # There is no flow initially 

        # Augment the flow while there is path from source to sink 
        while self.BFS(source, sink, parent) : 

            # Find minimum residual capacity of the edges along the 
            # path filled by BFS. Or we can say find the maximum flow 
            # through the path found. 
            path_flow = float("Inf") 
            s = sink 
            while(s != source): 
                path_flow = min (path_flow, self.graph[parent[s]][s]) 
                s = parent[s] 

            # Add path flow to overall flow 
            max_flow += path_flow 

            # update residual capacities of the edges and reverse edges 
            # along the path 
            v = sink 
            while(v != source): 
                u = parent[v] 
                self.graph[u][v] -= path_flow 
                self.graph[v][u] += path_flow 
                v = parent[v] 

        return max_flow 


# Create a graph given in the above diagram 

fileobject = open("Testdata.txt","r")
graph = fileobject.readlines();

g = Graph(graph) 

source = 0; sink = 5

print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))

相关问题 更多 >