python类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 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