判断一个简单图是否为平面图(c++ )

居v回溯就可以找到一个环
buildTheCircle:
circle *c = new circle;
if (depth[v] > depth[u])
{
c->push_front(v);
v = parent[v];
}
while (u != v)
{
c->push_front(u);
c->push_back(v);
u = parent[u];
v = parent[v];
}
c->push_front(u);
return c;
}

vector< fragment* >* getFragments(const graph *g)
{
int pointCount = g->size();
for (int i=0; i<pointCount; i++)
{
colour[i] = WHITE;
if (pointEmbed[i] || g->at(i)->empty())
{
pointKind[i] = EMBEDED;
}
else
{
pointKind[i] = AVAILABLE;
}
}

vector< fragment* >* fragmentsVector = new vector< fragment* >;
int fragmentsCount = 0;
queue<int> q;
list<int>::iterator ltra;
list<int>::iterator lend;
///广度优先遍历找fragment,
///将fragment分成两类: 1包含末嵌入到平面的结点的, 2不包含...的
for (i=0; i<pointCount; i++)
{
if (colour[i] == WHITE)
{ ///fragment有可能不只一个
if (pointKind[i] == AVAILABLE)
{ ///从末嵌入平面的结点出发遍历
fragment *f = createGraph(pointCount);
fragmentsCount++;
colour[i] = GRAY;
parent[i] = -1;
pointKind[i] = fragmentsCount;
q.push(i);
while (!q.empty())
{
int u = q.front(); q.pop();
ltra = g->at(u)->begin();
lend = g->at(u)->end();
for (; ltra != lend; ltra++)
{
int v = *ltra;
if (colour[v] == WHITE)
{
if (pointKind[v] == AVAILABLE)
{
pointKind[v] = fragmentsCount;
parent[v] = u;
colour[v] = GRAY;
q.push(v);
f->at(u)->push_back(v);
f->at(v)->push_back(u);
}
///如果邻居结点已经嵌入平面,
///则只将边加入到fragment而不入队(中止从此类结点出发的遍历);
else if (pointKind[v] == EMBEDED)
{
f->at(u)->push_back(v);
f->at(v)->push_back(u);
}
}
///如果邻居结点在队列中或者结点已经嵌入平面,
///则只将边加入到fragment而不入队(中止从此类结点出发的遍历);
else if (colour[v] == GRAY || pointKind[v] == EMBEDED)
{
f->at(u)->push_back(v);
f->at(v)->push_back(u);
}
}
colour[u] = BLACK;
}
fragmentsVector->push_back(f);
}
///如果出发结点已经嵌入平面, 则只找那些仅包含已经嵌入平面的结点的fragment
///这些fragment只有一条边, edgeEmbed[]是用来提供已经嵌入平面的边的信息的
else if (pointKind[i] == EMBEDED)
{
ltra = g->at(i)->begin();
lend = g->at(i)->end();
for (; ltra!=lend; ltra++)
{
assert(i != *ltra);
if (pointKind[*ltra] == EMBEDED && !edgeEmbed[i][*ltra])
{
frag