/*
* $Revision: 2555 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-06 12:12:10 +0200 (Fr, 06. Jul 2012) $
***************************************************************/
/** \file
* \brief Implementation of class CombinatorialEmbedding
*
* \author Carsten Gutwenger
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#include "CombinatorialEmbedding.h"
#include "FaceArray.h"
#define MIN_FACE_TABLE_SIZE (1 << 4)
namespace ogdf {
ConstCombinatorialEmbedding::ConstCombinatorialEmbedding()
{
m_cpGraph = 0;
m_externalFace = 0;
m_nFaces = m_faceIdCount = 0;
m_faceArrayTableSize = MIN_FACE_TABLE_SIZE;
}
ConstCombinatorialEmbedding::ConstCombinatorialEmbedding(const Graph &G) :
m_cpGraph(&G), m_rightFace(G,0)
{
computeFaces();
}
ConstCombinatorialEmbedding::ConstCombinatorialEmbedding(
const ConstCombinatorialEmbedding &C)
: m_cpGraph(C.m_cpGraph), m_rightFace(*C.m_cpGraph,0)
{
computeFaces();
if(C.m_externalFace == 0)
m_externalFace = 0;
else
m_externalFace = m_rightFace[C.m_externalFace->firstAdj()];
}
ConstCombinatorialEmbedding &ConstCombinatorialEmbedding::operator=(
const ConstCombinatorialEmbedding &C)
{
init(*C.m_cpGraph);
if(C.m_externalFace == 0)
m_externalFace = 0;
else
m_externalFace = m_rightFace[C.m_externalFace->firstAdj()];
return *this;
}
void ConstCombinatorialEmbedding::init(const Graph &G)
{
m_cpGraph = &G;
m_rightFace.init(G,0);
computeFaces();
}
void ConstCombinatorialEmbedding::init()
{
m_cpGraph = 0;
m_externalFace = 0;
m_nFaces = m_faceIdCount = 0;
m_faceArrayTableSize = MIN_FACE_TABLE_SIZE;
m_rightFace.init();
m_faces.clear();
reinitArrays();
}
void ConstCombinatorialEmbedding::computeFaces()
{
m_externalFace = 0; // no longer valid!
m_faceIdCount = 0;
m_faces.clear();
m_rightFace.fill(0);
node v;
forall_nodes(v,*m_cpGraph) {
adjEntry adj;
forall_adj(adj,v) {
if (m_rightFace[adj]) continue;
#ifdef OGDF_DEBUG
face f = OGDF_NEW FaceElement(this,adj,m_faceIdCount++);
#else
face f = OGDF_NEW FaceElement(adj,m_faceIdCount++);
#endif
m_faces.pushBack(f);
adjEntry adj2 = adj;
do {
m_rightFace[adj2] = f;
f->m_size++;
adj2 = adj2->faceCycleSucc();
} while (adj2 != adj);
}
}
m_nFaces = m_faceIdCount;
m_faceArrayTableSize = Graph::nextPower2(MIN_FACE_TABLE_SIZE,m_faceIdCount);
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
face ConstCombinatorialEmbedding::createFaceElement(adjEntry adjFirst)
{
if (m_faceIdCount == m_faceArrayTableSize) {
m_faceArrayTableSize <<= 1;
for(ListIterator it = m_regFaceArrays.begin();
it.valid(); ++it)
{
(*it)->enlargeTable(m_faceArrayTableSize);
}
}
#ifdef OGDF_DEBUG
face f = OGDF_NEW FaceElement(this,adjFirst,m_faceIdCount++);
#else
face f = OGDF_NEW FaceElement(adjFirst,m_faceIdCount++);
#endif
m_faces.pushBack(f);
m_nFaces++;
return f;
}
edge CombinatorialEmbedding::split(edge e)
{
face f1 = m_rightFace[e->adjSource()];
face f2 = m_rightFace[e->adjTarget()];
edge e2 = m_pGraph->split(e);
m_rightFace[e->adjSource()] = m_rightFace[e2->adjSource()] = f1;
f1->m_size++;
m_rightFace[e->adjTarget()] = m_rightFace[e2->adjTarget()] = f2;
f2->m_size++;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return e2;
}
void CombinatorialEmbedding::unsplit(edge eIn, edge eOut)
{
face f1 = m_rightFace[eIn->adjSource()];
face f2 = m_rightFace[eIn->adjTarget()];
--f1->m_size;
--f2->m_size;
if (f1->m_adjFirst == eOut->adjSource())
f1->m_adjFirst = eIn->adjSource();
if (f2->m_adjFirst == eIn->adjTarget())
f2->m_adjFirst = eOut->adjTarget();
m_pGraph->unsplit(eIn,eOut);
}
node CombinatorialEmbedding::splitNode(adjEntry adjStartLeft, adjEntry adjStartRight)
{
face fL = leftFace(adjStartLeft);
face fR = leftFace(adjStartRight);
node u = m_pGraph->splitNode(adjStartLeft,adjStartRight);
adjEntry adj = adjStartLeft->cyclicPred();
m_rightFace[adj] = fL;
++fL->m_size;
m_rightFace[adj->twin()] = fR;
++fR->m_size;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return u;
}
node CombinatorialEmbedding::contract(edge e)
{
// Since we remove face e, we also remove adjSrc and adjTgt.
// We make sure that node of them is stored as first adjacency
// entry of a face.
adjEntry adjSrc = e->adjSource();
adjEntry adjTgt = e->adjTarget();
face fSrc = m_rightFace[adjSrc];
face fTgt = m_rightFace[adjTgt];
if(fSrc->m_adjFirst == adjSrc) {
adjEntry adj = adjSrc->faceCycleSucc();
fSrc->m_adjFirst = (adj != adjTgt) ? adj : adj->faceCycleSucc();
}
if(fTgt->m_adjFirst == adjTgt) {
adjEntry adj = adjTgt->faceCycleSucc();
fTgt->m_adjFirst = (adj != adjSrc) ? adj : adj->faceCycleSucc();
}
node v = m_pGraph->contract(e);
--fSrc->m_size;
--fTgt->m_size;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return v;
}
edge CombinatorialEmbedding::splitFace(adjEntry adjSrc, adjEntry adjTgt)
{
OGDF_ASSERT(m_rightFace[adjSrc] == m_rightFace[adjTgt])
OGDF_ASSERT(adjSrc != adjTgt)
edge e = m_pGraph->newEdge(adjSrc,adjTgt);
face f1 = m_rightFace[adjTgt];
face f2 = createFaceElement(adjSrc);
adjEntry adj = adjSrc;
do {
m_rightFace[adj] = f2;
f2->m_size++;
adj = adj->faceCycleSucc();
} while (adj != adjSrc);
f1->m_adjFirst = adjTgt;
f1->m_size += (2 - f2->m_size);
m_rightFace[e->adjSource()] = f1;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return e;
}
//special version of the above function doing a pushback of the new edge
//on the adjacency list of v making it possible to insert new degree 0
//nodes into a face
edge CombinatorialEmbedding::splitFace(node v, adjEntry adjTgt)
{
adjEntry adjSrc = v->lastAdj();
edge e = 0;
bool degZ = v->degree() == 0;
if (degZ) {
e = m_pGraph->newEdge(v, adjTgt);
}
else
{
OGDF_ASSERT(m_rightFace[adjSrc] == m_rightFace[adjTgt])
OGDF_ASSERT(adjSrc != adjTgt)
e = m_pGraph->newEdge(adjSrc,adjTgt); //could use ne(v,ad) here, too
}
face f1 = m_rightFace[adjTgt];
//if v already had an adjacent edge, we split the face in two faces
int subSize = 0;
if (!degZ)
{
face f2 = createFaceElement(adjSrc);
adjEntry adj = adjSrc;
do
{
m_rightFace[adj] = f2;
f2->m_size++;
adj = adj->faceCycleSucc();
} while (adj != adjSrc);
subSize = f2->m_size;
}//if not zero degree
else
{
m_rightFace[e->adjTarget()] = f1;
}
f1->m_adjFirst = adjTgt;
f1->m_size += (2 - subSize);
m_rightFace[e->adjSource()] = f1;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return e;
}//splitface
//--
//-----------------
//incremental stuff
//special version of the above function doing a pushback of the new edge
//on the adjacency list of v making it possible to insert new degree 0
//nodes into a face, end node v
edge CombinatorialEmbedding::splitFace(adjEntry adjSrc, node v)
{
adjEntry adjTgt = v->lastAdj();
edge e = 0;
bool degZ = v->degree() == 0;
if (degZ)
{
e = m_pGraph->newEdge(adjSrc, v);
}
else
{
OGDF_ASSERT(m_rightFace[adjSrc] == m_rightFace[adjTgt])
OGDF_ASSERT(adjSrc != adjTgt)
e = m_pGraph->newEdge(adjSrc, adjTgt); //could use ne(v,ad) here, too
}
face f1 = m_rightFace[adjSrc];
//if v already had an adjacent edge, we split the face in two faces
int subSize = 0;
if (!degZ)
{
face f2 = createFaceElement(adjTgt);
adjEntry adj = adjTgt;
do
{
m_rightFace[adj] = f2;
f2->m_size++;
adj = adj->faceCycleSucc();
} while (adj != adjTgt);
subSize = f2->m_size;
}//if not zero degree
else
{
m_rightFace[e->adjSource()] = f1;
}
f1->m_adjFirst = adjSrc;
f1->m_size += (2 - subSize);
m_rightFace[e->adjTarget()] = f1;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return e;
}//splitface
//update face information after inserting a merger ith edge e in a copy graph
void CombinatorialEmbedding::updateMerger(edge e, face fRight, face fLeft)
{
//two cases: a single face/two faces
fRight->m_size++;
fLeft->m_size++;
m_rightFace[e->adjSource()] = fRight;
m_rightFace[e->adjTarget()] = fLeft;
//check for first adjacency entry
if (fRight != fLeft)
{
fRight->m_adjFirst = e->adjSource();
fLeft->m_adjFirst = e->adjTarget();
}//if
}//updateMerger
//--
face CombinatorialEmbedding::joinFaces(edge e)
{
OGDF_ASSERT(e->graphOf() == m_pGraph);
// get the two faces adjacent to e
face f1 = m_rightFace[e->adjSource()];
face f2 = m_rightFace[e->adjTarget()];
OGDF_ASSERT(f1 != f2);
// we will reuse the largest face and delete the other one
if (f2->m_size > f1->m_size)
swap(f1,f2);
// the size of the joined face is the sum of the sizes of the two faces
// f1 and f2 minus the two adjacency entries of e
f1->m_size += f2->m_size - 2;
// If the stored (first) adjacency entry of f1 belongs to e, we must set
// it to the next entry in the face, because we will remove it by deleting
// edge e
if (f1->m_adjFirst->theEdge() == e)
f1->m_adjFirst = f1->m_adjFirst->faceCycleSucc();
// each adjacency entry in f2 belongs now to f1
adjEntry adj1 = f2->firstAdj(), adj = adj1;
do {
m_rightFace[adj] = f1;
} while((adj = adj->faceCycleSucc()) != adj1);
m_pGraph->delEdge(e);
m_faces.del(f2);
--m_nFaces;
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return f1;
}
void CombinatorialEmbedding::reverseEdge(edge e)
{
// reverse edge in graph
m_pGraph->reverseEdge(e);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void CombinatorialEmbedding::moveBridge(adjEntry adjBridge, adjEntry adjBefore)
{
OGDF_ASSERT(m_rightFace[adjBridge] == m_rightFace[adjBridge->twin()]);
OGDF_ASSERT(m_rightFace[adjBridge] != m_rightFace[adjBefore]);
face fOld = m_rightFace[adjBridge];
face fNew = m_rightFace[adjBefore];
adjEntry adjCand = adjBridge->faceCycleSucc();
int sz = 0;
adjEntry adj;
for(adj = adjBridge->twin(); adj != adjCand; adj = adj->faceCycleSucc()) {
if(fOld->m_adjFirst == adj)
fOld->m_adjFirst = adjCand;
m_rightFace[adj] = fNew;
++sz;
}
fOld->m_size -= sz;
fNew->m_size += sz;
edge e = adjBridge->theEdge();
if(e->source() == adjBridge->twinNode())
m_pGraph->moveSource(e, adjBefore, after);
else
m_pGraph->moveTarget(e, adjBefore, after);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void CombinatorialEmbedding::removeDeg1(node v)
{
OGDF_ASSERT(v->degree() == 1);
adjEntry adj = v->firstAdj();
face f = m_rightFace[adj];
if(f->m_adjFirst == adj || f->m_adjFirst == adj->twin())
f->m_adjFirst = adj->faceCycleSucc();
f->m_size -= 2;
m_pGraph->delNode(v);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void CombinatorialEmbedding::clear()
{
m_pGraph->clear();
m_faces.clear();
m_nFaces = m_faceIdCount = 0;
m_faceArrayTableSize = MIN_FACE_TABLE_SIZE;
m_externalFace = 0;
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
face ConstCombinatorialEmbedding::chooseFace() const
{
if (m_nFaces == 0) return 0;
int k = ogdf::randomNumber(0,m_nFaces-1);
face f = firstFace();
while(k--) f = f->succ();
return f;
}
face ConstCombinatorialEmbedding::maximalFace() const
{
if (m_nFaces == 0) return 0;
face fMax = firstFace();
int max = fMax->size();
for(face f = fMax->succ(); f != 0; f = f->succ())
{
if (f->size() > max) {
max = f->size();
fMax = f;
}
}
return fMax;
}
ListIterator ConstCombinatorialEmbedding::
registerArray(FaceArrayBase *pFaceArray) const
{
return m_regFaceArrays.pushBack(pFaceArray);
}
void ConstCombinatorialEmbedding::unregisterArray(
ListIterator it) const
{
m_regFaceArrays.del(it);
}
void ConstCombinatorialEmbedding::reinitArrays()
{
ListIterator it = m_regFaceArrays.begin();
for(; it.valid(); ++it)
(*it)->reinit(m_faceArrayTableSize);
}
bool ConstCombinatorialEmbedding::consistencyCheck()
{
if (m_cpGraph->consistencyCheck() == false)
return false;
if(m_cpGraph->representsCombEmbedding() == false)
return false;
AdjEntryArray visited(*m_cpGraph,false);
int nF = 0;
face f;
forall_faces(f,*this) {
#ifdef OGDF_DEBUG
if (f->embeddingOf() != this)
return false;
#endif
nF++;
adjEntry adj = f->firstAdj(), adj2 = adj;
int sz = 0;
do {
sz++;
if (visited[adj2] == true)
return false;
visited[adj2] = true;
if (m_rightFace[adj2] != f)
return false;
adj2 = adj2->faceCycleSucc();
} while(adj2 != adj);
if (f->size() != sz)
return false;
}
if (nF != m_nFaces)
return false;
node v;
forall_nodes(v,*m_cpGraph) {
adjEntry adj;
forall_adj(adj,v) {
if (visited[adj] == false)
return false;
}
}
return true;
}
} // end namespace ogdf