implemented rewrite AG for alternative graph representation

The implementation is much faster than the one for the simple
representation. Instead of the 75x overhead, we have an overhead of less
than 2x.