Does optimize_edit_paths work for digraphs? Also, how accurate is it?

[ilanashapiro]

Hi! I need to find the GED and edit paths for pairs of DiGraphs. It's unclear if optimize_edit_paths will work for digraphs. There is a comment on the source code (https://networkx.org/documentation/stable/_modules/networkx/algorithms/similarity.html#optimize_edit_paths:~:text=%23%20TODO%3A%20support%20DiGraph) indicating it doesn't yet work for digraphs, but there is code deeper in the method (https://networkx.org/documentation/stable/_modules/networkx/algorithms/similarity.html#optimize_edit_paths:~:text=if%20nx.is_directed(G1)%20or%20nx.is_directed(G2)%3A) that appears to handle DiGraphs, so I am unsure.

Also, could someone comment on how accurate this method is? When I try running it on small graphs, the edit paths have a lot of strange operations like replace node A with itself. Furthermore, I'm using this method as a cost function for a Markov Chain Monte Carlo simulation. When I build up the target graph, I can verify that the graph changes, but the approximate cost from optimize_edit_paths doesn't change at all even after 20 iterations. Is this just because this method isn't granular enough/the approximation is too broad? Someone apparently also asked this question a few years ago (#6229), stating that the paper associated with method never actually evaluated it. Thanks!

[dschult]

The function graph_edit_distance is tested for DiGraphs (as well as simrank_similarity). But there are no tests on DiGraphs for optimize_edit_paths and optimal_edit_paths. The Todo comment about DiGraphs is unfortunately not a good indicator of which parts do or do not work with digraphs. The code you refer to in the sub-function match_edges does handle digraphs. But its not clear whether that functionality extends beyond that function.

The doc_string for the module states that the problem is NP-hard and invites improvements to the algorithm. Features of inefficiency like you are pointing out may lead to improvements in the algorithm.

I'm sure that improvements would be appreciated. For sure by NetworkX, but in the larger algorithm world as well.