我们从Python开源项目中，提取了以下50个代码示例，用于说明如何使用graph.Graph()。
def graph_function_low_level_il (function) : ''' Returns a graph where each LLIL Basic Block is a vertex in the graph ''' graph = Graph(0) # get the low_level_il basic blocks basic_blocks = function.low_level_il.basic_blocks # We are going to add each basic block to our graph for basic_block in basic_blocks : graph.add_vertex(basic_block.start, basic_block) # Now we are going to add all the edges for basic_block in basic_blocks : for outgoing_edge in basic_block.outgoing_edges : target = outgoing_edge.target graph.add_edge_by_indices(basic_block.start, target.start, None) # Now return the graph return graph
def graph_function (function) : ''' Returns a graph where each basic block is a vertex in the graph ''' graph = Graph(function.start) basic_blocks = function.basic_blocks for basic_block in basic_blocks : graph.add_vertex(basic_block.start, basic_block) for basic_block in basic_blocks : for outgoing_edge in basic_block.outgoing_edges : target = outgoing_edge.target graph.add_edge_by_indices(basic_block.start, target.start, None) return graph
def main(): ''' Create render and a graph, get some edge calling some graph function and draw them, finally save the results in FILENAME Bergamo = [.337125 ,.245148] Roma = [.4936765,.4637286] Napoli = [.5936468,.5253573] ''' render = Render() #coords = load_italy_coords() g = Graph( points=None, oriented=False, rand=True, n=300, max_neighbours=9) edges = g.tsp(0) render.draw_points(g.nodes) render.draw_lines(g.coords_edges(g.edges)) render.sur.write_to_png(FILENAME) import pdb pdb.set_trace() render.draw_lines(g.coords_edges(edges), color=True, filename='tsp/tsp') #render.draw_lines(g.coords_edges(edges), color=True, filename='kruskal/kru') render.sur.write_to_png(FILENAME)
def buildGraphDictionary(words): g = Graph() for w in words: g.addVertex(w) for i in range(len(words)): source = words[i] for w in words: if source == w: pass else: if find_edit_distance(source, w) == 1: g.addEdge(source, w, 1) #for vertex in g: # for w in vertex.getConnections(): # print("( %s , %s )" % (vertex.getId(), w.getId())) return g
def btn_solve_on_click(self): if self.grp is None or self.img is None: tkMessageBox.showerror("Error", "Please load a maze first!") return self.perform_process(lambda: self.traverse_graph(), "Traversing graph...") self.perform_process(lambda: self.write_to_file(), "Writing to file...") tkMessageBox.showinfo("Info", "Solved the maze in " + str(self.steps) + " steps!\n" + "Path length:\t\t%d\n" % self.graph_traverser.path_length + "Graph loading time:\t\t%.5lfs\n" % self.exec_time + "Graph traverse time:\t\t%.5lfs\n" % (self.traverse_time_end - self.traverse_time_start) + "File writing time:\t\t%.5lfs\n" % (self.imgwrite_time_end - self.imgwrite_time_start) + "Total execution time:\t\t%.5lfs" % (self.exec_time + (self.imgwrite_time_end - self.traverse_time_start)) ) if self.show_solution.get() == True: # Showing solution in new window if sys.platform.startswith('linux'): subprocess.call(["xdg-open", self.output_path]) else: os.startfile(self.output_path)
def traverse_graph(self): # Creating new graph traverser if self.rbSelectedValue.get() == "DFS": if self.dfs_query == "yes": self.graph_traverser = dfs_iterative.DFSIterative(self.grp) else: self.graph_traverser = dfs_recursive.DFSRecursive(self.grp) elif self.rbSelectedValue.get() == "BFS": self.graph_traverser = bfs.BFS(self.grp) elif self.rbSelectedValue.get() == "Dijkstra": self.graph_traverser = dijkstra.Dijkstra(self.grp, None) elif self.rbSelectedValue.get() == "Astar": self.graph_traverser = astar.AStar(self.grp, self.rb_heuristic_value.get()) # Traversing the graph and getting traverse node path self.traverse_time_start = time.time() self.path, self.steps = self.graph_traverser.traverse() if self.path == []: tkMessageBox.showerror("Error", "Graph traversing failed") self.traverse_time_end = time.time()
def generate_graph(): i = 0; faces = []; for edge in edges : faces.append(edges[i][0].tolist()) g[i] = [] i = i+1 graph = Graph(g) i=0; for face in faces: for vertice in range(len(face)-1): viz = check_adjacent_face_has_vertices(faces,i,face[vertice],face[vertice+1]) graph.add_edge({i,viz}) viz = check_adjacent_face_has_vertices(faces,i,face[0],face[vertice+1]) graph.add_edge({i,viz}) i=i+1 print(g) return
def setUp(self): self.graphs = [] v1 = Vertex(1) v2 = Vertex(2) v3 = Vertex(3) v4 = Vertex(4) v5 = Vertex(5) v6 = Vertex(6) self.v1 = v1 self.v2 = v2 self.v3 = v3 self.v4 = v4 self.v5 = v5 self.v6 = v6 vertices = [v1,v2,v3,v4,v5,v6] edges = [(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v2, v5), (v3, v4), (v3, v6), (v4, v5), (v5, v6)] self.graphs.append(Graph(vertices, edges)) edges = [(v1, v2), (v2, v3), (v3, v4), (v4, v2), (v3, v5), (v2, v4), (v4, v3)] self.graphs.append(Graph([v1, v2, v3, v4, v5], edges))
def testSCC(self): a = Vertex('a') b = Vertex('b') c = Vertex('c') d = Vertex('d') e = Vertex('e') f = Vertex('f') g = Vertex('g') h = Vertex('h') vertices = [a, b, c, d, e, f, g, h] edges = [(e, a), (a, b), (b, c), (d, c), (c, d), (b, e), (e, f), (b, f), (g, f), (f, g), (c, g), (g, h), (h, h)] G = Graph(vertices, edges) G.strongly_connected_components() self.assertEquals(a.cc, 1) self.assertEquals(b.cc, 1) self.assertEquals(c.cc, 2) self.assertEquals(d.cc, 2) self.assertEquals(e.cc, 1) self.assertEquals(f.cc, 3) self.assertEquals(g.cc, 3) self.assertEquals(h.cc, 4)
def testKruskal(self): a = Vertex('a') b = Vertex('b') c = Vertex('c') d = Vertex('d') e = Vertex('e') f = Vertex('f') g = Vertex('g') h = Vertex('h') i = Vertex('i') vertices = [a, b, c, d, e, f, g, h, i] edges = [(a, b), (a, h), (b, a), (b, c), (b, h), (c, b), (c, i), (c, f), (c, d), (d, c), (d, e), (d, f), (e, d), (e, f), (f, d), (f, e), (f, c), (f, g), (g, f), (g, h), (g, i), (h, a), (h, b), (h, i), (h, g), (i, c), (i, h), (i, g)] G = Graph(vertices, edges) weight = [4, 8, 4, 8, 11, 8, 2, 4, 7, 7, 9, 14, 9, 10, 14, 10, 4, 2, 2, 1, 6, 8, 11, 7, 1, 2, 7, 6] z = dict() for x,y in zip(edges, weight): z[x] = y print "{}: {}".format(x, y) def w(x, y): return z[(x, y)] ls = G.Kruskal(w) print ls
def testBellmanFord(self): s = Vertex('s') t = Vertex('t') y = Vertex('y') x = Vertex('x') z = Vertex('z') vertices = [s, t, y, x, z] edges = [(s, t), (s, y), (t, y), (t, x), (t, z), (y, x), (y, z), (x, t), (z, s), (z, x)] weight = [6, 7, 8, 5, -4, -3, 9, -2, 2, 7] G = Graph(vertices, edges) we = dict() for x,y in zip(edges, weight): we[x] = y def w(x, y): return we[(x, y)] G.Bellman_Ford(w, z)
def testTopologicalSort(self): r = Vertex('r') s = Vertex('s') t = Vertex('t') x = Vertex('x') y = Vertex('y') z = Vertex('z') vertices = [r, s, t, x, y, z] edges = [(r, s), (r, t), (s, t), (s, x), (t, x), (t, y), (t, z), (x, y), (x, z), (y, z)] G = Graph(vertices, edges) l = G.topological_sort() self.assertEquals(l, [r, s, t, x, y, z]) result = [] l = [self.v1, self.v2, self.v3, self.v4, self.v5, self.v6] result.append(l) for i in range(len(self.graphs)): self.assertEquals(self.graphs[i].topological_sort(), result[i])
def testSingleEdge(self): a = Vertex(1) b = Vertex(2) c = Vertex(3) d = Vertex(4) vertices = [a, b, c, d] edges = [(a, b), (b, a), (a, c), (d, d)] G = Graph(vertices, edges) G2 = G.single_edge() edges = set([(a, b), (b, a), (a, c), (c, a)]) vertices = set(vertices) self.assertEquals(G2.vertices, vertices) self.assertEquals(G2.edges, edges) self.assertEquals(G2.adj[a], {b, c}) self.assertEquals(G2.adj[b], {a}) self.assertEquals(G2.adj[c], {a}) self.assertEquals(G2.adj[d], set())
def testSquareGraph(self): a = Vertex(1) b = Vertex(2) c = Vertex(3) d = Vertex(4) G = Graph([a, b, c, d], [(a, b), (a, c), (c, d)]) sqrt = G.square() self.assertEquals(sqrt.vertices, {a, b, c, d}) self.assertEquals(sqrt.edges, {(a, b), (a, c), (a, d), (c, d)}) self.assertEquals(sqrt.adj[a], {b, c, d}) self.assertEquals(sqrt.adj[b], set()) self.assertEquals(sqrt.adj[c], {d}) self.assertEquals(sqrt.adj[d], set()) a = Vertex(1) b = Vertex(2) c = Vertex(3) G = Graph([a, b, c], [(a, b), (b, c), (a, c)]) sqrt = G.square() self.assertEquals(G, sqrt)
def difference_constraints_without_aux_vertex(A, b): row = len(A) col = len(A[0]) vertices_num = col vertices = [] edges = [] weights = dict() for i in range(vertices_num): vertices.append(Vertex(i + 1)) for i in range(0, row): u = A[i].index(-1) v = A[i].index(1) edges.append((vertices[u], vertices[v])) weights[(vertices[u], vertices[v])] = b[i] G = Graph(vertices, edges) if Bellman_Ford_without_aux_vertex(G, lambda x, y: weights[(x, y)]): return [v.d for v in vertices] else: return None
def single_variable_constraints(A, b): row = len(A) col = len(A[0]) vertices_num = col vertices = [] edges = [] weights = dict() for i in range(0, vertices_num + 1): vertices.append(Vertex(i)) for i in range(0, row): for j in range(0, len(A[i])): if A[i][j] == 1: edges.append((vertices[0], vertices[j + 1])) weights[(vertices[0], vertices[j + 1])] = b[i] break elif A[i][j] == -1: edges.append((vertices[j + 1], vertices[0])) weights[(vertices[j + 1], vertices[0])] = b[i] break G = Graph(vertices, edges) if G.Bellman_Ford(lambda x, y: weights[(x, y)], vertices[0]): return [v.d for v in vertices[1:]] else: return None
def test_most_reliable_path(self): s = Vertex('s') u = Vertex('u') v = Vertex('v') w = Vertex('w') vertices = [s, u, v, w] edges = [(s, u), (s, v), (s, w), (u, v), (u, w), (w, u)] G = Graph(vertices, edges) probabilities = [0.2, 0.1, 0.15, 0.7, 0.6, 0.9] re = dict() for i,j in zip(edges, probabilities): re[i] = j def r(x, y): return re[(x, y)] most_reliable_path(G, r, s) self.assertEquals([i.p for i in vertices], [None, s, u, s]) self.assertEquals([round(i.r, 2) for i in vertices], [1, 0.2, 0.14, 0.15]) most_reliable_path(G, r, u) self.assertEquals([i.p for i in vertices], [None, None, u, u]) self.assertEquals([round(i.r, 2) for i in vertices], [0, 1, 0.7, 0.6])
def old_main() : pass #graph = Graph(db) #graph.undirected_graph #graph.save("dump/graph-zhwiki.dump") #for k in range(10, 501, 10) : # cores = graph.k_core(k = k) # print "k = %d, len(cores) = %d" % (k, len(cores)) #w2v = Word2Vec(db) #w2v.train(workers = 64) #w2v.save("dump/w2v-zhwiki.dump") #lda = LDA(db) #lda.train() #lda.save("dump/lda2-zhwiki.dump")
def buttonClicked(self): s = 'graph.txt' tt = graph.Graph(self.day.currentText(), self.time.currentText()) tt.list_node = tt.read_nodes_graph(s) tt.schedule = tt.read_schedule() a = tt.analysis_graph() for i in range(len(self.label)): try: self.update(a[i], i) except IndexError: self.update('', i) if len(a) == 0: self.update("?????? ? ?????? ????? ???", 2)
def button_optimazeClicked(self): s = 'graph.txt' tt = graph.Graph(self.day.currentText(), self.time.currentText()) tt.list_node = tt.read_nodes_graph(s) tt.schedule = tt.read_schedule() a = tt.optimization_graph() for i in range(len(self.label)): try: self.update(a[i], i) except IndexError: self.update('', i) if len(a) == 0: self.update("?????? ? ?????? ????? ???", 2)
def __init__(self): super(WallEEGApp, self).__init__() self.user = User() self.graph = Graph(xlabel='X', ylabel='Y', x_ticks_minor=5, x_ticks_major=25, y_ticks_major=0.001, y_grid_label=True, x_grid_label=True, padding=5, x_grid=True, y_grid=True, xmin=-0, xmax=100, ymin=-0.1, ymax=0.1) self.plot = MeshLinePlot(color=[1, 0, 0, 1]) self.counter = 0 # def build(self): # return InSenseView() # def build(self): # g = Gui() # point_collection = PointsCollection(1000, 1000, 0, 100, 0, 100) # # for i in range(100): # x_coord = random.randint( # point_collection.x_min, point_collection.x_max) # y_coord = random.randint( # point_collection.y_min, point_collection.y_max) # # point_collection.add_point_vals(x_coord, y_coord) # # for point in point_collection.points_list: # g.grid.add_widget(point) # # for i in range(24): # # g.grid.add_widget(Button(text='test')) # # return g
def graph_function_llil_instructions (function) : ''' Returns a graph where each LLIL instruction is a vertex in the graph ''' graph = Graph(0) # Get the low_level_il basic blocks basic_blocks = function.low_level_il.basic_blocks # Add all the low_level_il instructions as their own vertices for basic_block in basic_blocks : for ins in basic_block : graph.add_vertex(ins.instr_index, ins) # Go back through and add edges for basic_block in basic_blocks : # Add edges between instructions in block previous_ins = None for ins in basic_block : if previous_ins == None : previous_ins = ins.instr_index continue graph.add_edge_by_indices(previous_ins, ins.instr_index) previous_ins = ins.instr_index # Add edges between basic blocks for outgoing_edge in basic_block.outgoing_edges : target = outgoing_edge.target.start graph.add_edge_by_indices(previous_ins, target) return graph
def __init__(self): self.graph = Graph() self.priors = semantic_priors() # these are really inefficient (ignore it) self.lemma_hash = defaultdict(lambda: []) self.name_hash = defaultdict(lambda: []) self.pos_hash = defaultdict(lambda: [])
def test_has_method(method): """Test that graph has all the correct methods.""" from graph import Graph assert hasattr(ClassDef(), method)
def btn_import_on_click(self): # Loading image from file... loading_time_start = time.time() self.perform_process(lambda: self.load_from_file(self.ent_filename.get()), "Loading image...") if self.img is None: return # Creating graph graph_time_start = time.time() try: self.perform_process(lambda: self.create_graph(), "Creating graph...") if self.grp.nodes_num is None: raise Exception except: tkMessageBox.showerror("Error", "Invalid image!\n" + "Image must have a black border and only one entry and exit point\n" + "Also, the exit point must not have a black square above it." ) return graph_time_end = time.time() self.exec_time = graph_time_end - loading_time_start tkMessageBox.showinfo("Info", "Maze successfully imported!\n\n" + "File loading time:\t\t%.5lfs\n" % (graph_time_start - loading_time_start) + "Graph creation time:\t\t%.5lfs\n" % (graph_time_end - graph_time_start) + "Nodes created:\t\t%u\n" % self.grp.nodes_num + "Elapsed time:\t\t%.5lfs" % self.exec_time )
def create_graph(self): self.grp = graph.Graph(self.img.pixel_map, self.img.h, self.img.w)
def get_connected_conditions(conditions): agraph = graph.Graph(conditions) var_to_conditions = dict([(var, []) for var in get_variables(conditions)]) for cond in conditions: for var in cond.args: if var[0] == "?": var_to_conditions[var].append(cond) # Connect conditions with a common variable for var, conds in var_to_conditions.items(): for cond in conds[1:]: agraph.connect(conds[0], cond) return sorted(map(sorted, agraph.connected_components()))
def compute_and_save_lifted_nh(ds, segId, liftedNeighborhood, with_defects = False): uvs_local = modified_adjacency(ds, segId) if (with_defects and ds.defect_slices) else ds._adjacent_segments(segId) n_nodes = uvs_local.max() + 1 # TODO maybe we should remove the uvs connected to a ignore segment if we have a seg mask # should be done if this takes too much time if we have a seg mask if ds.has_seg_mask: where_uv = (uvs_local != ds.ignore_seg_value).all(axis=1) uvs_local = uvs_local[where_uv] originalGraph = agraph.Graph(n_nodes) originalGraph.insertEdges(uvs_local) print ds.ds_name print "Computing lifted neighbors for range:", liftedNeighborhood lm = agraph.liftedMcModel(originalGraph) agraph.addLongRangeNH(lm , liftedNeighborhood) uvIds = lm.liftedGraph().uvIds() return uvIds[uvs_local.shape[0]:,:] # TODO adapt to defects # we assume that uv is consecutive #@cacher_hdf5() # sample size 0 means we do not sample!
def compute_and_save_long_range_nh(uvIds, min_range, max_sample_size=0): import random import itertools originalGraph = agraph.Graph(uvIds.max()+1) originalGraph.insertEdges(uvIds) uv_long_range = numpy.array(list(itertools.combinations(numpy.arange(originalGraph.numberOfVertices), 2)), dtype=numpy.uint64) lm_short = agraph.liftedMcModel(originalGraph) agraph.addLongRangeNH(lm_short, min_range) uvs_short = lm_short.liftedGraph().uvIds() # Remove uvs_short from uv_long_range # ----------------------------------- # Concatenate both lists concatenated = numpy.concatenate((uvs_short, uv_long_range), axis=0) # Find unique rows according to # http://stackoverflow.com/questions/16970982/find-unique-rows-in-numpy-array b = numpy.ascontiguousarray(concatenated).view(numpy.dtype((numpy.void, concatenated.dtype.itemsize * concatenated.shape[1]))) uniques, idx, counts = numpy.unique(b, return_index=True, return_counts=True) # Extract those that have count == 1 # TODO this is not tested long_range_idx = idx[counts == 1] uv_long_range = concatenated[long_range_idx] # Extract random sample if max_sample_size: sample_size = min(max_sample_size, uv_long_range.shape[0]) uv_long_range = numpy.array(random.sample(uv_long_range, sample_size)) return uv_long_range
def test_size(): g = Graph([Vertex(Vertex._make_test_vertex())]) assert g.size() == len(g.vertices)
def test_graph_empty(): a = Graph([]) assert a.size() == 0
def test_graph_single_vertex(): a = Vertex(Vertex._make_test_vertex()) b = Graph([a]) assert b.size() == 1
def test_graph_normal_set(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) g = Graph([a, b]) assert g.size() == 2
def test_graph_duplicate_vertex(): a = Vertex(Vertex._make_test_vertex()) g = Graph([a, a]) assert g.size() == 1
def test_graph_add_new_vertex_new(): a = Vertex(Vertex._make_test_vertex()) g = Graph([a]) g.add_vertex(Vertex(Vertex._make_test_vertex())) assert g.size() == 2
def test_graph_add_invalid_vertex(): g = Graph([Vertex(Vertex._make_test_vertex())]) assert_raises(TypeError, g.add_vertex, "String name")
def test_is_connected_empty(): g = Graph([]) assert g.is_connected()
def test_is_connected_single(): g = Graph([Vertex(Vertex._make_test_vertex())]) assert g.is_connected()
def test_is_connected_two_single(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) g = Graph([a, b]) assert not g.is_connected()
def test_is_connected_two_doubly_connected(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) a.add_edge(Edge(b)) b.add_edge(Edge(a)) g = Graph([a, b]) assert g.is_connected()
def test_is_connected_three_vert_two_connections(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) c = Vertex(Vertex._make_test_vertex()) a.add_edge(Edge(b)) b.add_edge(Edge(c)) c.add_edge(Edge(a)) g = Graph([a, b, c]) assert g.is_connected()
def test_has_cycle_self_loop(): a = Vertex(Vertex._make_test_vertex()) a.add_edge(Edge(a)) g = Graph([a]) assert g.has_cycle()
def test_has_cycle_single_no_loop(): a = Vertex(Vertex._make_test_vertex()) g = Graph([a]) assert not g.has_cycle()
def test_has_cycle_two_vertices_linked(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) a.add_edge(Edge(b)) b.add_edge(Edge(a)) g = Graph([a, b]) assert g.has_cycle()
def test_has_cycle_implicit(): """A Vertex is accessible to the Graph but not explicitly part of it.""" a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) c = Vertex(Vertex._make_test_vertex()) a.add_edge(Edge(b)) b.add_edge(Edge(c)) c.add_edge(Edge(a)) g = Graph([a, b]) assert g.has_cycle()
def test_top_sort_empty(): g = Graph([]) assert g.top_sort() == []
def test_top_sort_single(): a = Vertex(Vertex._make_test_vertex()) g = Graph([a]) assert g.top_sort() == [a]
def test_top_sort_two_single_vertices(): a = Vertex(Vertex._make_test_vertex()) b = Vertex(Vertex._make_test_vertex()) g = Graph([a, b]) assert g.top_sort() in [[a, b], [b, a]]
