python类Graph()的实例源码

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 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]]