TransWikia.com

Comparing two graphs when starting from a single edge

Theoretical Computer Science Asked by Freiburger0 on November 23, 2021

Let’s assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
enter image description here

$G_1$ and $G_2$ are isomorphic (including matching of the edge weights). However, I would like to check whether they look the same when ‘building’ them from one edge. i.e. we pick one (not necessarily the same) edge in both graphs and would like to know if they look the same starting from that edge. For the example above, we could choose the edge (1,2) in both graphs and see that they are not the same. If we would choose (1,2) and (5,6), they would be the same.

Are you aware of any algorithm to check this kind of similarity? Or is there even a NetworkX function? For tree graphs I could just use NetworkX’s is_isomorphic function. However, my intuition is that this similarity measure should be easier (i.e. faster) to check than isomorphism.

Thanks a lot

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP