#!/usr/bin/env python3
from graph_library import out_neighbor_lists, random_digraph, random_graph
def depth_first_search(V, E, previsit=None, postvisit=None):
neighbors = out_neighbor_lists(V, E)
visited = set()
def DFS1(u, parent=None):
visited.add(u)
if previsit:
previsit(u, parent)
for w in neighbors[u]:
if w not in visited:
DFS1(w, u)
if postvisit:
postvisit(u, parent)
for v in V:
if v not in visited:
DFS1(v)
def topological_sort(V, E):
finished = []
def postvisit(u, parent):
finished.append(u)
depth_first_search(V, E, postvisit=postvisit)
return list(reversed(finished))
def test_topological_sort(n=10, m=None):
from random import shuffle
V, E = random_digraph(n, m, acyclic=True)
shuffle(V)
V = topological_sort(V, E)
rank = dict((v, i) for i, v in enumerate(V))
assert all(rank[u] < rank[w] for u, w in E)
def count_forward_edges(V, E):
neighbors = out_neighbor_lists(V, E)
visited = set()
being_visited = set()
n_forward_edges = 0
def DFS1(u):
nonlocal n_forward_edges
visited.add(u)
being_visited.add(u)
for w in neighbors[u]:
if w not in visited:
DFS1(w)
elif w not in being_visited:
n_forward_edges += 1
being_visited.remove(u)
for v in V:
if v not in visited:
DFS1(v)
return n_forward_edges
def count_connected_components(V, E):
# (V, E) is undirected graph
n_components = 0
def previsit(u, parent):
nonlocal n_components
if parent is None:
n_components += 1
depth_first_search(V, E, previsit=previsit)
return n_components
def test_count_forward_edges(n=10, m=None):
V, E = random_graph(n, m)
assert n == len(V)
n_components = count_connected_components(V, E)
n_tree_edges = n - n_components
n_forward_edges = count_forward_edges(V, E)
assert n_tree_edges + n_forward_edges == len(E) / 2
# def strong_components(G):
# assert isinstance(G, DiGraph)
# finished = []
# depth_first_search(G, postvisit=lambda u, _: finished.append(u))
# G_reversed = DiGraph(vertices=list(reversed(finished)),
# edges=set((w, u) for (u, w) in G.edges))
# components = []
# def previsit(u, tree_edge):
# if tree_edge is None:
# components.append([])
# components[-1].append(u)
# depth_first_search(G_reversed, previsit)
# return components
# class DFS_edge_classifier:
# def __init__(self, G):
# self.G = G
# self.start_times = {}
# self.finish_times = {}
# counter = 0
# def time():
# nonlocal counter
# counter += 1
# return counter
# self.tree_edges = set()
# def previsit(u, tree_edge):
# if tree_edge is not None:
# self.tree_edges.add(tree_edge)
# self.start_times[u] = time()
# def postvisit(u, _):
# self.finish_times[u] = time()
# depth_first_search(G, previsit, postvisit)
# self.forward_edges = set()
# self.back_edges = set()
# self.cross_edges = set()
# for e in G.edges:
# if e not in self.tree_edges:
# u, w = e
# s_u, f_u = self.start_times[u], self.finish_times[u]
# s_w, f_w = self.start_times[w], self.finish_times[w]
# if e == {u, w}: # undirected edge
# assert s_w < s_u < f_u < f_w or s_u < s_w < f_w < f_u
# self.forward_edges.add(e)
# elif s_u < s_w < f_w < f_u:
# self.forward_edges.add(e)
# elif s_w < s_u < f_u < f_w:
# self.back_edges.add(e)
# elif s_w < f_w < s_u < f_u:
# self.cross_edges.add(e)
# else:
# assert False
if __name__ == "__main__":
for _ in range(5):
test_topological_sort(10)
for _ in range(5):
test_count_forward_edges(10)
print("test passed")
IyEvdXNyL2Jpbi9lbnYgcHl0aG9uMwoKZnJvbSBncmFwaF9saWJyYXJ5IGltcG9ydCBvdXRfbmVpZ2hib3JfbGlzdHMsIHJhbmRvbV9kaWdyYXBoLCByYW5kb21fZ3JhcGgKCgpkZWYgZGVwdGhfZmlyc3Rfc2VhcmNoKFYsIEUsIHByZXZpc2l0PU5vbmUsIHBvc3R2aXNpdD1Ob25lKToKCiAgICBuZWlnaGJvcnMgPSBvdXRfbmVpZ2hib3JfbGlzdHMoViwgRSkKICAgIHZpc2l0ZWQgPSBzZXQoKQoKICAgIGRlZiBERlMxKHUsIHBhcmVudD1Ob25lKToKICAgICAgICB2aXNpdGVkLmFkZCh1KQogICAgICAgIGlmIHByZXZpc2l0OgogICAgICAgICAgICBwcmV2aXNpdCh1LCBwYXJlbnQpCiAgICAgICAgZm9yIHcgaW4gbmVpZ2hib3JzW3VdOgogICAgICAgICAgICBpZiB3IG5vdCBpbiB2aXNpdGVkOgogICAgICAgICAgICAgICAgREZTMSh3LCB1KQogICAgICAgIGlmIHBvc3R2aXNpdDoKICAgICAgICAgICAgcG9zdHZpc2l0KHUsIHBhcmVudCkKCiAgICBmb3IgdiBpbiBWOgogICAgICAgIGlmIHYgbm90IGluIHZpc2l0ZWQ6CiAgICAgICAgICAgIERGUzEodikKCgpkZWYgdG9wb2xvZ2ljYWxfc29ydChWLCBFKToKCiAgICBmaW5pc2hlZCA9IFtdCgogICAgZGVmIHBvc3R2aXNpdCh1LCBwYXJlbnQpOgogICAgICAgIGZpbmlzaGVkLmFwcGVuZCh1KQoKICAgIGRlcHRoX2ZpcnN0X3NlYXJjaChWLCBFLCBwb3N0dmlzaXQ9cG9zdHZpc2l0KQoKICAgIHJldHVybiBsaXN0KHJldmVyc2VkKGZpbmlzaGVkKSkKCgpkZWYgdGVzdF90b3BvbG9naWNhbF9zb3J0KG49MTAsIG09Tm9uZSk6CiAgICBmcm9tIHJhbmRvbSBpbXBvcnQgc2h1ZmZsZQoKICAgIFYsIEUgPSByYW5kb21fZGlncmFwaChuLCBtLCBhY3ljbGljPVRydWUpCgogICAgc2h1ZmZsZShWKQogICAgViA9IHRvcG9sb2dpY2FsX3NvcnQoViwgRSkKCiAgICByYW5rID0gZGljdCgodiwgaSkgZm9yIGksIHYgaW4gZW51bWVyYXRlKFYpKQoKICAgIGFzc2VydCBhbGwocmFua1t1XSA8IHJhbmtbd10gZm9yIHUsIHcgaW4gRSkKCgpkZWYgY291bnRfZm9yd2FyZF9lZGdlcyhWLCBFKToKCiAgICBuZWlnaGJvcnMgPSBvdXRfbmVpZ2hib3JfbGlzdHMoViwgRSkKICAgIHZpc2l0ZWQgPSBzZXQoKQogICAgYmVpbmdfdmlzaXRlZCA9IHNldCgpCiAgICBuX2ZvcndhcmRfZWRnZXMgPSAwCgogICAgZGVmIERGUzEodSk6CiAgICAgICAgbm9ubG9jYWwgbl9mb3J3YXJkX2VkZ2VzCgogICAgICAgIHZpc2l0ZWQuYWRkKHUpCiAgICAgICAgYmVpbmdfdmlzaXRlZC5hZGQodSkKCiAgICAgICAgZm9yIHcgaW4gbmVpZ2hib3JzW3VdOgogICAgICAgICAgICBpZiB3IG5vdCBpbiB2aXNpdGVkOgogICAgICAgICAgICAgICAgREZTMSh3KQogICAgICAgICAgICBlbGlmIHcgbm90IGluIGJlaW5nX3Zpc2l0ZWQ6CiAgICAgICAgICAgICAgICBuX2ZvcndhcmRfZWRnZXMgKz0gMQoKICAgICAgICBiZWluZ192aXNpdGVkLnJlbW92ZSh1KQoKICAgIGZvciB2IGluIFY6CiAgICAgICAgaWYgdiBub3QgaW4gdmlzaXRlZDoKICAgICAgICAgICAgREZTMSh2KQoKICAgIHJldHVybiBuX2ZvcndhcmRfZWRnZXMKCgpkZWYgY291bnRfY29ubmVjdGVkX2NvbXBvbmVudHMoViwgRSk6CgogICAgIyAoViwgRSkgaXMgdW5kaXJlY3RlZCBncmFwaAoKICAgIG5fY29tcG9uZW50cyA9IDAKCiAgICBkZWYgcHJldmlzaXQodSwgcGFyZW50KToKICAgICAgICBub25sb2NhbCBuX2NvbXBvbmVudHMKICAgICAgICBpZiBwYXJlbnQgaXMgTm9uZToKICAgICAgICAgICAgbl9jb21wb25lbnRzICs9IDEKCiAgICBkZXB0aF9maXJzdF9zZWFyY2goViwgRSwgcHJldmlzaXQ9cHJldmlzaXQpCgogICAgcmV0dXJuIG5fY29tcG9uZW50cwoKCmRlZiB0ZXN0X2NvdW50X2ZvcndhcmRfZWRnZXMobj0xMCwgbT1Ob25lKToKCiAgICBWLCBFID0gcmFuZG9tX2dyYXBoKG4sIG0pCiAgICBhc3NlcnQgbiA9PSBsZW4oVikKCiAgICBuX2NvbXBvbmVudHMgPSBjb3VudF9jb25uZWN0ZWRfY29tcG9uZW50cyhWLCBFKQogICAgbl90cmVlX2VkZ2VzID0gbiAtIG5fY29tcG9uZW50cwogICAgbl9mb3J3YXJkX2VkZ2VzID0gY291bnRfZm9yd2FyZF9lZGdlcyhWLCBFKQoKICAgIGFzc2VydCBuX3RyZWVfZWRnZXMgKyBuX2ZvcndhcmRfZWRnZXMgPT0gbGVuKEUpIC8gMgoKCiMgZGVmIHN0cm9uZ19jb21wb25lbnRzKEcpOgojICAgICBhc3NlcnQgaXNpbnN0YW5jZShHLCBEaUdyYXBoKQoKIyAgICAgZmluaXNoZWQgPSBbXQojICAgICBkZXB0aF9maXJzdF9zZWFyY2goRywgcG9zdHZpc2l0PWxhbWJkYSB1LCBfOiBmaW5pc2hlZC5hcHBlbmQodSkpCgojICAgICBHX3JldmVyc2VkID0gRGlHcmFwaCh2ZXJ0aWNlcz1saXN0KHJldmVyc2VkKGZpbmlzaGVkKSksCiMgICAgICAgICAgICAgICAgICAgICAgICAgIGVkZ2VzPXNldCgodywgdSkgZm9yICh1LCB3KSBpbiBHLmVkZ2VzKSkKCiMgICAgIGNvbXBvbmVudHMgPSBbXQoKIyAgICAgZGVmIHByZXZpc2l0KHUsIHRyZWVfZWRnZSk6CiMgICAgICAgICBpZiB0cmVlX2VkZ2UgaXMgTm9uZToKIyAgICAgICAgICAgICBjb21wb25lbnRzLmFwcGVuZChbXSkKIyAgICAgICAgIGNvbXBvbmVudHNbLTFdLmFwcGVuZCh1KQoKIyAgICAgZGVwdGhfZmlyc3Rfc2VhcmNoKEdfcmV2ZXJzZWQsIHByZXZpc2l0KQoKIyAgICAgcmV0dXJuIGNvbXBvbmVudHMKCgojIGNsYXNzIERGU19lZGdlX2NsYXNzaWZpZXI6CiMgICAgIGRlZiBfX2luaXRfXyhzZWxmLCBHKToKIyAgICAgICAgIHNlbGYuRyA9IEcKIyAgICAgICAgIHNlbGYuc3RhcnRfdGltZXMgPSB7fQojICAgICAgICAgc2VsZi5maW5pc2hfdGltZXMgPSB7fQoKIyAgICAgICAgIGNvdW50ZXIgPSAwCgojICAgICAgICAgZGVmIHRpbWUoKToKIyAgICAgICAgICAgICBub25sb2NhbCBjb3VudGVyCiMgICAgICAgICAgICAgY291bnRlciArPSAxCiMgICAgICAgICAgICAgcmV0dXJuIGNvdW50ZXIKCiMgICAgICAgICBzZWxmLnRyZWVfZWRnZXMgPSBzZXQoKQoKIyAgICAgICAgIGRlZiBwcmV2aXNpdCh1LCB0cmVlX2VkZ2UpOgojICAgICAgICAgICAgIGlmIHRyZWVfZWRnZSBpcyBub3QgTm9uZToKIyAgICAgICAgICAgICAgICAgc2VsZi50cmVlX2VkZ2VzLmFkZCh0cmVlX2VkZ2UpCiMgICAgICAgICAgICAgc2VsZi5zdGFydF90aW1lc1t1XSA9IHRpbWUoKQoKIyAgICAgICAgIGRlZiBwb3N0dmlzaXQodSwgXyk6CiMgICAgICAgICAgICAgc2VsZi5maW5pc2hfdGltZXNbdV0gPSB0aW1lKCkKCiMgICAgICAgICBkZXB0aF9maXJzdF9zZWFyY2goRywgcHJldmlzaXQsIHBvc3R2aXNpdCkKCiMgICAgICAgICBzZWxmLmZvcndhcmRfZWRnZXMgPSBzZXQoKQojICAgICAgICAgc2VsZi5iYWNrX2VkZ2VzID0gc2V0KCkKIyAgICAgICAgIHNlbGYuY3Jvc3NfZWRnZXMgPSBzZXQoKQoKIyAgICAgICAgIGZvciBlIGluIEcuZWRnZXM6CiMgICAgICAgICAgICAgaWYgZSBub3QgaW4gc2VsZi50cmVlX2VkZ2VzOgojICAgICAgICAgICAgICAgICB1LCB3ID0gZQojICAgICAgICAgICAgICAgICBzX3UsIGZfdSA9IHNlbGYuc3RhcnRfdGltZXNbdV0sIHNlbGYuZmluaXNoX3RpbWVzW3VdCiMgICAgICAgICAgICAgICAgIHNfdywgZl93ID0gc2VsZi5zdGFydF90aW1lc1t3XSwgc2VsZi5maW5pc2hfdGltZXNbd10KIyAgICAgICAgICAgICAgICAgaWYgZSA9PSB7dSwgd306ICAgICAjIHVuZGlyZWN0ZWQgZWRnZQojICAgICAgICAgICAgICAgICAgICAgYXNzZXJ0IHNfdyA8IHNfdSA8IGZfdSA8IGZfdyBvciBzX3UgPCBzX3cgPCBmX3cgPCBmX3UKIyAgICAgICAgICAgICAgICAgICAgIHNlbGYuZm9yd2FyZF9lZGdlcy5hZGQoZSkKIyAgICAgICAgICAgICAgICAgZWxpZiBzX3UgPCBzX3cgPCBmX3cgPCBmX3U6CiMgICAgICAgICAgICAgICAgICAgICBzZWxmLmZvcndhcmRfZWRnZXMuYWRkKGUpCiMgICAgICAgICAgICAgICAgIGVsaWYgc193IDwgc191IDwgZl91IDwgZl93OgojICAgICAgICAgICAgICAgICAgICAgc2VsZi5iYWNrX2VkZ2VzLmFkZChlKQojICAgICAgICAgICAgICAgICBlbGlmIHNfdyA8IGZfdyA8IHNfdSA8IGZfdToKIyAgICAgICAgICAgICAgICAgICAgIHNlbGYuY3Jvc3NfZWRnZXMuYWRkKGUpCiMgICAgICAgICAgICAgICAgIGVsc2U6CiMgICAgICAgICAgICAgICAgICAgICBhc3NlcnQgRmFsc2UKCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgoKICAgIGZvciBfIGluIHJhbmdlKDUpOgogICAgICAgIHRlc3RfdG9wb2xvZ2ljYWxfc29ydCgxMCkKCiAgICBmb3IgXyBpbiByYW5nZSg1KToKICAgICAgICB0ZXN0X2NvdW50X2ZvcndhcmRfZWRnZXMoMTApCgogICAgcHJpbnQoInRlc3QgcGFzc2VkIik=