Spaces:
Sleeping
Sleeping
| import ast | |
| import gradio as gr | |
| def myfunc(file_path): | |
| with open(file_path, "r") as file: | |
| file_contents = file.read() | |
| string = file_contents | |
| matrix = ast.literal_eval(string) | |
| def sort_vertices_by_degree(matrix): | |
| num_vertices = len(matrix) | |
| degrees = [(i, sum(matrix[i])) for i in range(num_vertices)] | |
| sorted_vertices = sorted(degrees, key=lambda x: x[1], reverse=True) | |
| return [vertex[0] for vertex in sorted_vertices] | |
| sorted_vertices = sort_vertices_by_degree(matrix) | |
| def dfs(u, visited, disc, low, parent, is_cut_vertex): | |
| nonlocal time | |
| children = 0 | |
| visited[u] = True | |
| disc[u] = time | |
| low[u] = time | |
| time += 1 | |
| for v in range(len(matrix)): | |
| if matrix[u][v]: | |
| if not visited[v]: | |
| children += 1 | |
| dfs(v, visited, disc, low, u, is_cut_vertex) | |
| low[u] = min(low[u], low[v]) | |
| if parent == -1 and children > 1: | |
| is_cut_vertex[u] = True | |
| if parent != -1 and low[v] >= disc[u]: | |
| is_cut_vertex[u] = True | |
| elif v != parent: | |
| low[u] = min(low[u], disc[v]) | |
| num_vertices = len(matrix) | |
| visited = [False] * num_vertices | |
| disc = [float("inf")] * num_vertices | |
| low = [float("inf")] * num_vertices | |
| is_cut_vertex = [False] * num_vertices | |
| time = 0 | |
| for i in range(num_vertices): | |
| if not visited[i]: | |
| dfs(i, visited, disc, low, -1, is_cut_vertex) | |
| cut_vertices = [i for i, is_cut in enumerate(is_cut_vertex) if is_cut] | |
| result=[] | |
| for x in sorted_vertices: | |
| for y in cut_vertices: | |
| if x==y: | |
| result.append(y) | |
| return result | |
| iface = gr.Interface( | |
| fn=myfunc, | |
| inputs=gr.File(label="Upload Text File Containing the adjacency matrix of the graph"), | |
| outputs=gr.Text(label="The Important stations are in the order:") | |
| ) | |
| iface.launch(share=True) |