Find the smallest polygon with a certain edge on a 2d dijkstra graph

Sorry for bad English. It's somehow called Minimal Cycle Basis of graph algorithm. I'm currently working on some algorithm to seperate a graph into rooms. Like the example. I have a graph link like the one in left, I want to tell there are 2 rooms in the graph, like the red area and the orange area in the right.

So far, I've tried to walk the shortest path from an edge, which failed. Like, in the left image, I started from the edge marked red, the shortest path would be like the right image.

I've also tried to always take the turn with largest angle in clockwise. If it work in one graph, it would failed when starting with opposite direction.

Is there any cheap solution on this one? I'm currently quick trapped.

Finally, I've got the principles. For an edge inside the graph, which should be shared by 2 circle basises, priorizing the largest signed angle (counter-clockwise) would find one of them, whose edges going counter-clockwisely. And priorizing the smallest (clockwise) would find the other (edges go clockwisely). So both would be correct.

But for an edge on the 'edge' of the graph, who was only contained by 1 circle basis, one of the basises should not exist. So one of the priorizing ways would give the wrong result.

On this scenario, you could find the polygon, in the result, clockwisely doesn't match pathfinding priorizing. So you could change the priorizing and got the right result.

The way to determine if a polygon is clockwise could be found below. How to determine if a list of polygon points are in clockwise order?