-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtree_kernel.py
100 lines (73 loc) · 2.61 KB
/
tree_kernel.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import networkx as nx
from lxml import html
import matplotlib.pyplot as plt
from bs4 import BeautifulSoup
from bs4.element import NavigableString
from networkx.algorithms.traversal.depth_first_search import dfs_tree
from sklearn.metrics.pairwise import cosine_similarity
import numpy as np
raw = "<html><head><title></title></head><body><p><p><br><p></body></html>"
raw2 = "<html><head><title></title></head><body><script></script><p></body></html>"
def traverse(parent, graph, labels):
labels[hash(parent)] = parent.name
for node in parent.children:
if isinstance(node, NavigableString):
continue
graph.add_edge(hash(parent), hash(node))
traverse(node, graph, labels)
soup = BeautifulSoup(raw)
html_tag = next(soup.children)
soup = BeautifulSoup(raw2)
html_tag2 = next(soup.children)
#H=G.subgraph(G.nodes()[0:2])
G = nx.DiGraph()
H = nx.DiGraph()
labels = {} # needed to map from node to tag
labels2={}
#html_tag = html.document_fromstring(raw)
traverse(html_tag, G, labels)
traverse(html_tag2, H, labels2)
pos = nx.graphviz_layout(G, prog='dot',args="-Gsize=10")
#nx.draw(G,with_labels=False)
label_props = {'size': 16,
'color': 'black',
'weight': 'bold',
'horizontalalignment': 'center',
'verticalalignment': 'center',
'clip_on': True}
bbox_props = {'boxstyle': "round, pad=0.1",
'fc': "grey",
'ec': "b",
'lw': 1.5}
nx.draw_networkx_edges(G, pos, arrows=False)
ax = plt.gca()
for node, label in labels.items():
x, y = pos[node]
ax.text(x, y, label,
bbox=bbox_props,
**label_props)
ax.xaxis.set_visible(False)
ax.yaxis.set_visible(False)
plt.show()
subtrees_G=[]
subtrees_H=[]
for i,node in enumerate(G.nodes()):
subtrees_G.append(dfs_tree(G,node))
for i,node in enumerate(H.nodes()):
subtrees_H.append(dfs_tree(H,node))
def label_check(d1,d2):
return d1['labels']==d2['labels']
for subtree in subtrees_H:
for node in subtree.nodes():
subtree.node[node]['labels']=labels2[node]
for subtree in subtrees_G:
for node in subtree.nodes():
subtree.node[node]['labels']=labels[node]
all_subtrees=subtrees_G+subtrees_H
v=[]
w=[]
for i,subtree in enumerate(all_subtrees):
if subtree.nodes()!=[]:
v.append(np.sum(np.array(map(lambda x: nx.is_isomorphic(subtree,x,node_match=label_check),subtrees_G),dtype=float)))
w.append(np.sum(np.array(map(lambda x: nx.is_isomorphic(subtree,x,node_match=label_check),subtrees_H),dtype=float)))
print cosine_similarity(v,w)