0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This question is related: cstheory.stackexchange.com/questions/21962/… $\endgroup$
    – Denis
    Jul 22, 2020 at 12:53
  • $\begingroup$ Can you define precisely what it means to "look the same starting from an edge"? Are you asking whether there is a graph isomorphism that maps that edge in $G_1$ to a particular edge in $G_2$? $\endgroup$
    – D.W.
    Jul 23, 2020 at 8:27
  • $\begingroup$ Thanks for your comments! @D.W. That was a bit sloppy - sorry. I think you can think of it as following. Let's assume both graphs have an edge $e=(x,y)$. I would like to check if $G_1$ and $G_2$ are isomorphic with the constraint that the mapping (the isomorphism) maps the edge $e = (x,y)$ of $G_1$ to the same edge $e=(x,y)$ of $G_2$. In the more general case, we could assume - as above - that we have an edge $e_1=(x_1,y_1)$ of $G_1$ and $e_2 = (x_2,y_2)$ of $G_2$ and the constraint that the isomorphism has to map $e_1$ on $e_2$. $\endgroup$
    – Freiburger0
    Jul 27, 2020 at 13:09
  • $\begingroup$ OK, please edit the question to make that clear, so people don't have to read the comments to understand your question. You can revise it to read well for someone who encounters it for the first time. $\endgroup$
    – D.W.
    Jul 27, 2020 at 15:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.