0
$\begingroup$

I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:

for all u in G1
  for all v in G2
    if u.label == v.label then
       do something here
    end if
  end for
end for

Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?

I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic.

Is there a better/more efficient approach for doing this?

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by David Richerby, jmite, Evil, Luke Mathieson, vonbrand Oct 6 '15 at 9:36

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Well, you are just comparing two sets. The fact that the elements of those sets are also vertices in some graphs doesn't play a role. As for this operation, you'd be better off if you first sorted both sets and then compared them, it would give you $O(n \log n)$ since sorting would dominate the comparison. Provided you don't care about repetitions. $\endgroup$ – wvxvw Oct 5 '15 at 15:45
  • 3
    $\begingroup$ What do you know about the distribution of labels? What is the do something? The answer will depend on these two. For instance, if each label is a single bit and do something is print u,v, then there's no asymptotically faster solution, as you need to print $\Theta(n^2)$ lines of output no matter what. Have you considered using a hash table to hash vertices by label, or sorting vertices by label? $\endgroup$ – D.W.♦ Oct 5 '15 at 15:45
  • $\begingroup$ @wvxvw - thanks for giving me a perspective on this $\endgroup$ – Jake Clawson Oct 25 '15 at 0:34
  • $\begingroup$ @D.W. - thanks for elaborating on this. It helped me to think clearly on this question. $\endgroup$ – Jake Clawson Oct 25 '15 at 0:34
2
$\begingroup$

A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.

This also assumes that the "do something"-bit doesn't change the label (and that the order of the "do something"s doesn't matter).

|cite|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.