CODEWITHSUNDEEP
c++computer-sciencegraph-algorithmsymmetric
A. W.
A. W.

Reputation: 35

Axis of symmetry in cyclic graph

I have to write a program in c++ which returns the number of axis of symmetry in a cyclic graph. A cyclic graph has an axis of symmetry when values between opposite vertices or edges on the left are a mirror image for values on the right. The axis of symmetry may intersect both vertices and edges.

for example:

enter image description here

Is there any way to do this faster than O(n^2)?

Upvotes: 1

Views: 397

Answers (1)

SoVictor
SoVictor

Reputation: 36

n.m.’s answer is actually nearly correct, but not in any case.

Lets call one of the nodes the start node, and the axis, passing start node, the main axis. Flipping a graph over some axis is equals to flipping it over main axis and rotation:

pic 1

After rotation, main node can be placed on any other node place (and we also always can find current axis for doing this).

If we store our graph as a string, then flipped graph described by a reversed string cyclically shifted by 0 to N-1 positions. Equality of those strings means the equality of the graphs. Obviously, number of such matches is equals to the number of occurs of reversed string in the twice repeated graph’s string:

pic 2

So yes, KMP does the trick with O(N) complexity.

But you should avoid the case when str equals to reverse(str), because match will be counted with both 0 and N shifts, despite the fact they describe the same axis. So, you should use not concatenation of str and itself, but only first (2*N – 1) chars of this concatenation to achieve the proper behavior in any case.

Upvotes: 2

Related Questions