input networkx graph into zss algorithm (tree edit distance)

Question

I want to compute the Zhang-Shasha tree-edit distance between 2 trees (zss library). However, my trees are in the form of networkx graphs (they actually represent DOM html trees). The example in the zss documentation shows how to create a tree by hand:

from zss import *
A = (
    Node("f")
        .addkid(Node("a")
            .addkid(Node("h"))
            .addkid(Node("c")
                .addkid(Node("l"))))
        .addkid(Node("e"))
    )
zss.simple_distance(A, A) # [0.0]

Which would be the same tree as:

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([('f', 'a'), ('a', 'h'), ('a', 'c'), ('c', 'l'), ('f', 'e')])

so I would like to convert tree objects of networkx class into a zss Node object, then compute the edit distance between 2 trees.

Thanks

(and do not hesitate to tell me if you think this is a XY problem)

Seems to me like depth first traversal.

Paul Brodersen
– Paul Brodersen

2019-01-18 13:36:40 +00:00
Commented Jan 18, 2019 at 13:36 — Paul Brodersen
– Paul Brodersen, Commented Jan 18, 2019 at 13:36

zohar.kom · Accepted Answer · 2019-01-21 07:50:21Z

2

Using dfs_tree can definitely help:

import zss
import networkx as nx

G=nx.DiGraph()
G.add_edges_from([('f', 'a'), ('a', 'h'), ('a', 'c'), ('c', 'l'), ('f', 'e')])
T = nx.dfs_tree(G, source='f')
nodes_dict = {}
for edge in T.edges():
    if edge[0] not in nodes_dict:
        nodes_dict[edge[0]] = zss.Node(edge[0])
    if edge[1] not in nodes_dict:
        nodes_dict[edge[1]] = zss.Node(edge[1])
    nodes_dict[edge[0]].addkid(nodes_dict[edge[1]])

print(zss.simple_distance(nodes_dict['f'], nodes_dict['f'])) # 0.0

In case we don't know which node is G's root node, but know we have a valid tree, we can get the source node by calling:

source = [n for (n, d) in G.in_degree() if d == 0][0]
T = nx.dfs_tree(G, source=source)

Since the root is the only node with no incoming nodes, that should work.

edited Jan 21, 2019 at 7:50

answered Jan 20, 2019 at 14:02

zohar.kom

1,8453 gold badges13 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

agenis - code en bois Over a year ago

thanks, you supply the source argument as the top node, i guess? How would I automatize this in a function, i mean could I initialize it as T = nx.dfs_tree(G, source=list(G.nodes)[0]), right?

zohar.kom Over a year ago

That would work, as well as simply omitting the source argument and calling nx.dfs_tree(G). However, it assumes G has a specific node ordering, which is true in the above example, but depends on the way we build it. Added an edit to handle this step in the answer.

Collectives™ on Stack Overflow

input networkx graph into zss algorithm (tree edit distance)

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related