/*
* $Revision: 2523 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
***************************************************************/
/** \file
* \brief Implementation of Graph class
*
* \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 "Array.h"
#include "AdjEntryArray.h"
#include "../fileformats/GmlParser.h"
#include "simple_graph_alg.h"
#include "GraphObserver.h"
#define MIN_NODE_TABLE_SIZE (1 << 4)
#define MIN_EDGE_TABLE_SIZE (1 << 4)
namespace ogdf {
Graph::Graph()
{
m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
m_edgeArrayTableSize = MIN_EDGE_TABLE_SIZE;
}
Graph::Graph(const Graph &G)
{
m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
copy(G);
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
}
Graph::~Graph()
{
ListIterator itVNext;
for(ListIterator itV = m_regNodeArrays.begin();
itV.valid(); itV = itVNext)
{
itVNext = itV.succ();
(*itV)->disconnect();
}
ListIterator itENext;
for(ListIterator itE = m_regEdgeArrays.begin();
itE.valid(); itE = itENext)
{
itENext = itE.succ();
(*itE)->disconnect();
}
ListIterator itAdjNext;
for(ListIterator itAdj = m_regAdjArrays.begin();
itAdj.valid(); itAdj = itAdjNext)
{
itAdjNext = itAdj.succ();
(*itAdj)->disconnect();
}
for (node v = m_nodes.begin(); v; v = v->succ()) {
v->m_adjEdges.~GraphList();
}
}
Graph &Graph::operator=(const Graph &G)
{
clear(); copy(G);
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return *this;
}
void Graph::assign(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge)
{
clear();
copy(G,mapNode,mapEdge);
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
reinitArrays();
}
void Graph::construct(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge)
{
copy(G,mapNode,mapEdge);
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
}
void Graph::copy(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge)
{
if (G.m_nNodes == 0) return;
mapNode.init(G,0);
node vG;
forall_nodes(vG,G) {
node v = mapNode[vG] = pureNewNode();
v->m_indeg = vG->m_indeg;
v->m_outdeg = vG->m_outdeg;
}
if (G.m_nEdges == 0) return;
mapEdge.init(G,0);
edge e, eC;
forall_edges(e,G) {
m_edges.pushBack(eC = mapEdge[e] =
OGDF_NEW EdgeElement(
mapNode[e->source()],mapNode[e->target()],m_edgeIdCount));
eC->m_adjSrc = OGDF_NEW AdjElement(eC,m_edgeIdCount<<1);
(eC->m_adjTgt = OGDF_NEW AdjElement(eC,(m_edgeIdCount<<1)|1))
->m_twin = eC->m_adjSrc;
eC->m_adjSrc->m_twin = eC->m_adjTgt;
m_edgeIdCount++;
}
m_nEdges = G.m_nEdges;
EdgeArray mark(G,false);
forall_nodes(vG,G) {
node v = mapNode[vG];
GraphList &adjEdges = vG->m_adjEdges;
for (AdjElement *adjG = adjEdges.begin(); adjG; adjG = adjG->succ()) {
int id = adjG->m_edge->index();
edge eC = mapEdge[id];
adjEntry adj;
if (eC->isSelfLoop()) {
if (mark[id])
adj = eC->m_adjTgt;
else {
adj = eC->m_adjSrc;
mark[id] = true;
}
} else
adj = (v == eC->m_src) ? eC->m_adjSrc : eC->m_adjTgt;
v->m_adjEdges.pushBack(adj);
adj->m_node = v;
}
}
}
void Graph::copy(const Graph &G)
{
NodeArray mapNode;
EdgeArray mapEdge;
copy(G,mapNode,mapEdge);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void Graph::constructInitByNodes(
const Graph &G,
const List &nodes,
NodeArray &mapNode,
EdgeArray &mapEdge)
{
// clear
for (node v = m_nodes.begin(); v; v = v->succ()) {
v->m_adjEdges.~GraphList();
}
m_nodes.clear();
m_edges.clear();
m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
// list of edges adjacent to nodes in nodes
SListPure edges;
// create nodes and assemble list of edges
ListConstIterator itG;
for(itG = nodes.begin(); itG.valid(); ++itG) {
node vG = *itG;
node v = mapNode[vG] = pureNewNode();
v->m_indeg = vG->m_indeg;
v->m_outdeg = vG->m_outdeg;
adjEntry adjG;
forall_adj(adjG,vG) {
// corresponding adjacency entries differ by index modulo 2
// the following conditions makes sure that each edge is
// added only once to edges
if ((adjG->m_id & 1) == 0)
edges.pushBack(adjG->m_edge);
}
}
// create edges
SListConstIterator it;
for(it = edges.begin(); it.valid(); ++it)
{
edge eG = *it;
node v = mapNode[eG->source()];
node w = mapNode[eG->target()];
edge eC = mapEdge[eG] = OGDF_NEW EdgeElement(v, w, m_edgeIdCount);
m_edges.pushBack(eC);
eC->m_adjSrc = OGDF_NEW AdjElement(eC, m_edgeIdCount<<1);
(eC->m_adjTgt = OGDF_NEW AdjElement(eC, (m_edgeIdCount<<1)|1))
->m_twin = eC->m_adjSrc;
eC->m_adjSrc->m_twin = eC->m_adjTgt;
++m_edgeIdCount;
++m_nEdges;
}
EdgeArray mark(G,false);
for(itG = nodes.begin(); itG.valid(); ++itG) {
node vG = *itG;
node v = mapNode[vG];
GraphList &adjEdges = vG->m_adjEdges;
for (AdjElement *adjG = adjEdges.begin(); adjG; adjG = adjG->succ()) {
int id = adjG->m_edge->index();
edge eC = mapEdge[id];
adjEntry adj;
if (eC->isSelfLoop()) {
if (mark[id])
adj = eC->m_adjTgt;
else {
adj = eC->m_adjSrc;
mark[id] = true;
}
} else
adj = (v == eC->m_src) ? eC->m_adjSrc : eC->m_adjTgt;
v->m_adjEdges.pushBack(adj);
adj->m_node = v;
}
}
/*
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjSrc);
//v->m_outdeg++;
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
w->m_adjEdges.pushBack(adjTgt);
//w->m_indeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
++m_nEdges;
m_edges.pushBack(e);
mapEdge[eG] = adjSrc->m_edge = adjTgt->m_edge = e;
}*/
// set size of associated arrays and reinitialize all (we have now a
// completely new graph)
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
//------------------
//mainly a copy of the above code, remerge this again
void Graph::constructInitByActiveNodes(
const List &nodes,
const NodeArray &activeNodes,
NodeArray &mapNode,
EdgeArray &mapEdge)
{
// clear
for (node v = m_nodes.begin(); v; v = v->succ()) {
v->m_adjEdges.~GraphList();
}
m_nodes.clear();
m_edges.clear();
m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
// list of edges adjacent to nodes in nodes
SListPure edges;
// create nodes and assemble list of edges
//NOTE: nodes is a list of ACTIVE nodes
ListConstIterator itG;
for(itG = nodes.begin(); itG.valid(); ++itG) {
node vG = *itG;
node v = mapNode[vG] = pureNewNode();
//we cannot assign the original degree, as there
//may be edges to non-active nodes
//v->m_indeg = vG->m_indeg;
//v->m_outdeg = vG->m_outdeg;
int inCount = 0;
int outCount = 0;
adjEntry adjG;
forall_adj(adjG,vG)
{
// coresponding adjacency entries differ by index modulo 2
// the following conditions makes sure that each edge is
// added only once to edges
if (activeNodes[adjG->m_edge->opposite(vG)])
{
if ((adjG->m_id & 1) == 0)
{
edges.pushBack(adjG->m_edge);
}//if one time
if (adjG->m_edge->source() == vG) outCount++;
else inCount++;
}//if opposite active
}//foralladj
v->m_indeg = inCount;
v->m_outdeg = outCount;
}//for nodes
// create edges
SListConstIterator it;
for(it = edges.begin(); it.valid(); ++it)
{
edge eG = *it;
node v = mapNode[eG->source()];
node w = mapNode[eG->target()];
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjSrc);
//v->m_outdeg++;
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
w->m_adjEdges.pushBack(adjTgt);
//w->m_indeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
++m_nEdges;
m_edges.pushBack(e);
mapEdge[eG] = adjSrc->m_edge = adjTgt->m_edge = e;
}
// set size of associated arrays and reinitialize all (we have now a
// completely new graph)
m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}//constructinitbyactivenodes
//------------------
node Graph::newNode()
{
++m_nNodes;
if (m_nodeIdCount == m_nodeArrayTableSize) {
m_nodeArrayTableSize <<= 1;
for(ListIterator it = m_regNodeArrays.begin();
it.valid(); ++it)
{
(*it)->enlargeTable(m_nodeArrayTableSize);
}
}
#ifdef OGDF_DEBUG
node v = OGDF_NEW NodeElement(this,m_nodeIdCount++);
#else
node v = OGDF_NEW NodeElement(m_nodeIdCount++);
#endif
m_nodes.pushBack(v);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->nodeAdded(v);
return v;
}
//what about negative index numbers?
node Graph::newNode(int index)
{
++m_nNodes;
if(index >= m_nodeIdCount) {
m_nodeIdCount = index+1;
if(index >= m_nodeArrayTableSize) {
m_nodeArrayTableSize = nextPower2(m_nodeArrayTableSize,index);
for(ListIterator it = m_regNodeArrays.begin();
it.valid(); ++it)
{
(*it)->enlargeTable(m_nodeArrayTableSize);
}
}
}
#ifdef OGDF_DEBUG
node v = OGDF_NEW NodeElement(this,index);
#else
node v = OGDF_NEW NodeElement(index);
#endif
m_nodes.pushBack(v);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->nodeAdded(v);
return v;
}
node Graph::pureNewNode()
{
++m_nNodes;
#ifdef OGDF_DEBUG
node v = OGDF_NEW NodeElement(this,m_nodeIdCount++);
#else
node v = OGDF_NEW NodeElement(m_nodeIdCount++);
#endif
m_nodes.pushBack(v);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->nodeAdded(v);
return v;
}
// IMPORTANT:
// The indices of the two adjacency entries pointing to an edge differ
// only in the last bit (adjSrc/2 == adjTgt/2)
//
// This can be useful sometimes in order to avoid visiting an edge twice.
edge Graph::createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt)
{
if (m_edgeIdCount == m_edgeArrayTableSize) {
m_edgeArrayTableSize <<= 1;
for(ListIterator it = m_regEdgeArrays.begin();
it.valid(); ++it)
{
(*it)->enlargeTable(m_edgeArrayTableSize);
}
for(ListIterator itAdj = m_regAdjArrays.begin();
itAdj.valid(); ++itAdj)
{
(*itAdj)->enlargeTable(m_edgeArrayTableSize << 1);
}
}
adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
m_edges.pushBack(e);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->edgeAdded(e);
return e;
}
edge Graph::newEdge(node v, node w, int index)
{
OGDF_ASSERT(v != 0 && w != 0);
OGDF_ASSERT(v->graphOf() == this && w->graphOf() == this);
++m_nEdges;
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjSrc);
v->m_outdeg++;
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
w->m_adjEdges.pushBack(adjTgt);
w->m_indeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
if(index >= m_edgeIdCount) {
m_edgeIdCount = index+1;
if(index >= m_edgeArrayTableSize) {
m_edgeArrayTableSize = nextPower2(m_edgeArrayTableSize,index);
for(ListIterator it = m_regEdgeArrays.begin();
it.valid(); ++it)
{
(*it)->enlargeTable(m_edgeArrayTableSize);
}
for(ListIterator itAdj = m_regAdjArrays.begin();
itAdj.valid(); ++itAdj)
{
(*itAdj)->enlargeTable(m_edgeArrayTableSize << 1);
}
}
}
adjTgt->m_id = (adjSrc->m_id = index/*m_edgeIdCount*/ << 1) | 1;
edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,index);
m_edges.pushBack(e);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->edgeAdded(e);
return adjSrc->m_edge = adjTgt->m_edge = e;
}
edge Graph::newEdge(node v, node w)
{
OGDF_ASSERT(v != 0 && w != 0);
OGDF_ASSERT(v->graphOf() == this && w->graphOf() == this);
++m_nEdges;
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjSrc);
v->m_outdeg++;
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
w->m_adjEdges.pushBack(adjTgt);
w->m_indeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
edge e = createEdgeElement(v,w,adjSrc,adjTgt);
return adjSrc->m_edge = adjTgt->m_edge = e;
}
edge Graph::newEdge(adjEntry adjStart, adjEntry adjEnd, Direction dir)
{
OGDF_ASSERT(adjStart != 0 && adjEnd != 0)
OGDF_ASSERT(adjStart->graphOf() == this && adjEnd->graphOf() == this);
++m_nEdges;
node v = adjStart->theNode(), w = adjEnd->theNode();
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
if(dir == ogdf::after) {
w->m_adjEdges.insertAfter(adjTgt,adjEnd);
v->m_adjEdges.insertAfter(adjSrc,adjStart);
} else {
w->m_adjEdges.insertBefore(adjTgt,adjEnd);
v->m_adjEdges.insertBefore(adjSrc,adjStart);
}
w->m_indeg++;
v->m_outdeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
edge e = createEdgeElement(v,w,adjSrc,adjTgt);
return adjSrc->m_edge = adjTgt->m_edge = e;
}
edge Graph::newEdge(node v, adjEntry adjEnd)
{
OGDF_ASSERT(v != 0 && adjEnd != 0)
OGDF_ASSERT(v->graphOf() == this && adjEnd->graphOf() == this);
++m_nEdges;
node w = adjEnd->theNode();
AdjElement *adjTgt = OGDF_NEW AdjElement(w);
w->m_adjEdges.insertAfter(adjTgt,adjEnd);
w->m_indeg++;
AdjElement *adjSrc = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjSrc);
v->m_outdeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
edge e = createEdgeElement(v,w,adjSrc,adjTgt);
return adjSrc->m_edge = adjTgt->m_edge = e;
}//newedge
//copy of above function with edge ending at v
edge Graph::newEdge(adjEntry adjStart, node v)
{
OGDF_ASSERT(v != 0 && adjStart != 0)
OGDF_ASSERT(v->graphOf() == this && adjStart->graphOf() == this);
++m_nEdges;
node w = adjStart->theNode();
AdjElement *adjSrc = OGDF_NEW AdjElement(w);
w->m_adjEdges.insertAfter(adjSrc, adjStart);
w->m_outdeg++;
AdjElement *adjTgt = OGDF_NEW AdjElement(v);
v->m_adjEdges.pushBack(adjTgt);
v->m_indeg++;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
edge e = createEdgeElement(w,v,adjSrc,adjTgt);
return adjSrc->m_edge = adjTgt->m_edge = e;
}//newedge
void Graph::move(edge e,
adjEntry adjSrc,
Direction dirSrc,
adjEntry adjTgt,
Direction dirTgt)
{
OGDF_ASSERT(e->graphOf() == this);
OGDF_ASSERT(adjSrc->graphOf() == this && adjTgt->graphOf() == this);
OGDF_ASSERT(adjSrc != e->m_adjSrc && adjSrc != e->m_adjTgt);
OGDF_ASSERT(adjTgt != e->m_adjSrc && adjTgt != e->m_adjTgt);
node v = adjSrc->m_node, w = adjTgt->m_node;
adjEntry adj1 = e->m_adjSrc, adj2 = e->m_adjTgt;
e->m_src->m_adjEdges.move(adj1,v->m_adjEdges,adjSrc,dirSrc);
e->m_tgt->m_adjEdges.move(adj2,w->m_adjEdges,adjTgt,dirTgt);
e->m_src->m_outdeg--;
e->m_tgt->m_indeg--;
adj1->m_node = e->m_src = v;
adj2->m_node = e->m_tgt = w;
v->m_outdeg++;
w->m_indeg++;
}
void Graph::moveTarget(edge e, node v)
{
OGDF_ASSERT(e->graphOf() == this);
OGDF_ASSERT(v->graphOf() == this);
adjEntry adj = e->m_adjTgt;
e->m_tgt->m_adjEdges.move(adj,v->m_adjEdges);
e->m_tgt->m_indeg--;
adj->m_node = e->m_tgt = v;
v->m_indeg++;
}
void Graph::moveTarget(edge e, adjEntry adjTgt, Direction dir)
{
node v = adjTgt->theNode();
OGDF_ASSERT(e->graphOf() == this);
OGDF_ASSERT(v->graphOf() == this);
adjEntry adj = e->m_adjTgt;
e->m_tgt->m_adjEdges.move(adj,v->m_adjEdges, adjTgt, dir);
e->m_tgt->m_indeg--;
adj->m_node = e->m_tgt = v;
v->m_indeg++;
}
// By Leipert
void Graph::moveSource(edge e, node v)
{
OGDF_ASSERT(e->graphOf() == this);
OGDF_ASSERT(v->graphOf() == this);
adjEntry adj = e->m_adjSrc;
e->m_src->m_adjEdges.move(adj,v->m_adjEdges);
e->m_src->m_outdeg--;
adj->m_node = e->m_src = v;
v->m_outdeg++;
}
void Graph::moveSource(edge e, adjEntry adjSrc, Direction dir)
{
node v = adjSrc->theNode();
OGDF_ASSERT(e->graphOf() == this);
OGDF_ASSERT(v->graphOf() == this);
adjEntry adj = e->m_adjSrc;
e->m_src->m_adjEdges.move(adj,v->m_adjEdges, adjSrc, dir);
e->m_src->m_outdeg--;
adj->m_node = e->m_src = v;
v->m_outdeg++;
}
edge Graph::split(edge e)
{
OGDF_ASSERT(e != 0 && e->graphOf() == this);
++m_nEdges;
node u = newNode();
u->m_indeg = u->m_outdeg = 1;
adjEntry adjTgt = OGDF_NEW AdjElement(u);
adjTgt->m_edge = e;
adjTgt->m_twin = e->m_adjSrc;
e->m_adjSrc->m_twin = adjTgt;
// adapt adjacency entry index to hold invariant
adjTgt->m_id = e->m_adjTgt->m_id;
u->m_adjEdges.pushBack(adjTgt);
adjEntry adjSrc = OGDF_NEW AdjElement(u);
adjSrc->m_twin = e->m_adjTgt;
u->m_adjEdges.pushBack(adjSrc);
int oldId = e->m_adjTgt->m_id;
edge e2 = createEdgeElement(u,e->m_tgt,adjSrc,e->m_adjTgt);
resetAdjEntryIndex(e->m_adjTgt->m_id,oldId);
e2->m_adjTgt->m_twin = adjSrc;
e->m_adjTgt->m_edge = adjSrc->m_edge = e2;
e->m_tgt = u;
e->m_adjTgt = adjTgt;
return e2;
}
void Graph::unsplit(node u)
{
edge eIn = u->firstAdj()->theEdge();
edge eOut = u->lastAdj()->theEdge();
if (eIn->target() != u)
swap(eIn,eOut);
unsplit(eIn,eOut);
}
void Graph::unsplit(edge eIn, edge eOut)
{
node u = eIn->target();
// u must be a node with exactly one incoming edge eIn and one outgoing
// edge eOut
OGDF_ASSERT(u->graphOf() == this && u->indeg() == 1 &&
u->outdeg() == 1 && eOut->source() == u);
// none of them is a self-loop!
OGDF_ASSERT(eIn->isSelfLoop() == false && eOut->isSelfLoop() == false);
// we reuse these adjacency entries
adjEntry adjSrc = eIn ->m_adjSrc;
adjEntry adjTgt = eOut->m_adjTgt;
eIn->m_tgt = eOut->m_tgt;
// adapt adjacency entry index to hold invariant
resetAdjEntryIndex(eIn->m_adjTgt->m_id,adjTgt->m_id);
adjTgt->m_id = eIn->m_adjTgt->m_id; // correct id of adjacency entry!
eIn->m_adjTgt = adjTgt;
adjSrc->m_twin = adjTgt;
adjTgt->m_twin = adjSrc;
adjTgt->m_edge = eIn;
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->edgeDeleted(eOut);
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->nodeDeleted(u);
// remove structures that are no longer used
m_edges.del(eOut);
m_nodes.del(u);
--m_nNodes;
--m_nEdges;
}
void Graph::delNode(node v)
{
OGDF_ASSERT(v != 0 && v->graphOf() == this)
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->nodeDeleted(v);
--m_nNodes;
GraphList &adjEdges = v->m_adjEdges;
AdjElement *adj;
while((adj = adjEdges.begin()) != 0)
delEdge(adj->m_edge);
m_nodes.del(v);
}
void Graph::delEdge(edge e)
{
OGDF_ASSERT(e != 0 && e->graphOf() == this)
// notify all registered observers
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it) (*it)->edgeDeleted(e);
--m_nEdges;
node src = e->m_src, tgt = e->m_tgt;
src->m_adjEdges.del(e->m_adjSrc);
src->m_outdeg--;
tgt->m_adjEdges.del(e->m_adjTgt);
tgt->m_indeg--;
m_edges.del(e);
}
void Graph::clear()
{
//tell all structures to clear their graph-initialized data
for(ListIterator it = m_regStructures.begin();
it.valid(); ++it)
{
(*it)->cleared();
}//for
for (node v = m_nodes.begin(); v; v = v->succ()) {
v->m_adjEdges.~GraphList();
}
m_nodes.clear();
m_edges.clear();
m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
reinitArrays();
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void Graph::reverseEdge(edge e)
{
OGDF_ASSERT(e != 0 && e->graphOf() == this)
node &src = e->m_src, &tgt = e->m_tgt;
swap(src,tgt);
swap(e->m_adjSrc,e->m_adjTgt);
src->m_outdeg++; src->m_indeg--;
tgt->m_outdeg--; tgt->m_indeg++;
}
void Graph::reverseAllEdges()
{
for (edge e = m_edges.begin(); e; e = e->succ())
reverseEdge(e);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}
void Graph::reverseAdjEdges()
{
node v;
forall_nodes(v,*this)
reverseAdjEdges(v);
}
node Graph::chooseNode() const
{
if (m_nNodes == 0) return 0;
int k = ogdf::randomNumber(0,m_nNodes-1);
node v = firstNode();
while(k--) v = v->succ();
return v;
}
edge Graph::chooseEdge() const
{
if (m_nEdges == 0) return 0;
int k = ogdf::randomNumber(0,m_nEdges-1);
edge e = firstEdge();
while(k--) e = e->succ();
return e;
}
edge Graph::searchEdge(node v, node w) const
{
OGDF_ASSERT(v != 0 && v->graphOf() == this)
OGDF_ASSERT(w != 0 && w->graphOf() == this)
adjEntry adj;
forall_adj(adj,v) {
if(adj->twinNode() == w) return adj->twin()->theEdge();
}
return 0;
}
void Graph::hideEdge(edge e)
{
OGDF_ASSERT(e != 0 && e->graphOf() == this)
--m_nEdges;
node src = e->m_src, tgt = e->m_tgt;
src->m_adjEdges.delPure(e->m_adjSrc);
src->m_outdeg--;
tgt->m_adjEdges.delPure(e->m_adjTgt);
tgt->m_indeg--;
m_edges.move(e, m_hiddenEdges);
}
void Graph::restoreEdge(edge e)
{
++m_nEdges;
node v = e->m_src;
v->m_adjEdges.pushBack(e->m_adjSrc);
++v->m_outdeg;
node w = e->m_tgt;
w->m_adjEdges.pushBack(e->m_adjTgt);
++w->m_indeg;
m_hiddenEdges.move(e, m_edges);
}
void Graph::restoreAllEdges()
{
edge e, ePrev;
for(e = m_hiddenEdges.rbegin(); e != 0; e = ePrev) {
ePrev = e->pred();
restoreEdge(e);
}
}
int Graph::genus() const
{
if (m_nNodes == 0) return 0;
int nIsolated = 0;
node v;
forall_nodes(v,*this)
if (v->degree() == 0) ++nIsolated;
NodeArray component(*this);
int nCC = connectedComponents(*this,component);
AdjEntryArray visited(*this,false);
int nFaceCycles = 0;
forall_nodes(v,*this) {
adjEntry adj1;
forall_adj(adj1,v) {
if (visited[adj1]) continue;
adjEntry adj = adj1;
do {
visited[adj] = true;
adj = adj->faceCycleSucc();
} while (adj != adj1);
++nFaceCycles;
}
}
return (m_nEdges - m_nNodes - nIsolated - nFaceCycles + 2*nCC) / 2;
}
ListIterator Graph::registerArray(
NodeArrayBase *pNodeArray) const
{
return m_regNodeArrays.pushBack(pNodeArray);
}
ListIterator Graph::registerArray(
EdgeArrayBase *pEdgeArray) const
{
return m_regEdgeArrays.pushBack(pEdgeArray);
}
ListIterator Graph::registerArray(
AdjEntryArrayBase *pAdjArray) const
{
return m_regAdjArrays.pushBack(pAdjArray);
}
ListIterator Graph::registerStructure(
GraphObserver *pStructure) const
{
return m_regStructures.pushBack(pStructure);
}//registerstructure
void Graph::unregisterArray(ListIterator it) const
{
m_regNodeArrays.del(it);
}
void Graph::unregisterArray(ListIterator it) const
{
m_regEdgeArrays.del(it);
}
void Graph::unregisterArray(ListIterator it) const
{
m_regAdjArrays.del(it);
}
void Graph::unregisterStructure(ListIterator it) const
{
m_regStructures.del(it);
}
void Graph::reinitArrays()
{
ListIterator itNode = m_regNodeArrays.begin();
for(; itNode.valid(); ++itNode)
(*itNode)->reinit(m_nodeArrayTableSize);
ListIterator itEdge = m_regEdgeArrays.begin();
for(; itEdge.valid(); ++itEdge)
(*itEdge)->reinit(m_edgeArrayTableSize);
ListIterator itAdj = m_regAdjArrays.begin();
for(; itAdj.valid(); ++itAdj)
(*itAdj)->reinit(m_edgeArrayTableSize << 1);
}
void Graph::reinitStructures()
{
//is there a challenge?
ListIterator itGS = m_regStructures.begin();
for (;itGS.valid(); ++itGS)
(*itGS)->reInit();
}
void Graph::resetAdjEntryIndex(int newIndex, int oldIndex)
{
ListIterator itAdj = m_regAdjArrays.begin();
for(; itAdj.valid(); ++itAdj)
(*itAdj)->resetIndex(newIndex,oldIndex);
}
int Graph::nextPower2(int start, int idCount)
{
while (start <= idCount)
start <<= 1;
return start;
}
bool Graph::readGML(const char *fileName)
{
ifstream is(fileName);
return readGML(is);
}
bool Graph::readGML(istream &is)
{
GmlParser gml(is);
if (gml.error()) return false;
bool result = gml.read(*this);
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return result;
}
void Graph::writeGML(const char *fileName) const
{
ofstream os(fileName);
writeGML(os);
}
void Graph::writeGML(ostream &os) const
{
NodeArray id(*this);
int nextId = 0;
os << "Creator \"ogdf::Graph::writeGML\"\n";
os << "graph [\n";
os << " directed 1\n";
node v;
forall_nodes(v,*this) {
os << " node [\n";
os << " id " << (id[v] = nextId++) << "\n";
os << " ]\n"; // node
}
edge e;
forall_edges(e,*this) {
os << " edge [\n";
os << " source " << id[e->source()] << "\n";
os << " target " << id[e->target()] << "\n";
os << " ]\n"; // edge
}
os << "]\n"; // graph
}
// read graph in LEDA format from file fileName
bool Graph::readLEDAGraph(const char *fileName)
{
ifstream is(fileName);
return readLEDAGraph(is);
}
bool Graph::readToEndOfLine(istream &is)
{
int c;
do {
if (is.eof()) return false;
c = is.get();
} while(c != '\n');
return true;
}
// read graph in LEDA format from input stream is
bool Graph::readLEDAGraph(istream &is)
{
clear();
// the first three strings in the LEDA format describe the type of the
// format, of nodes and of edges. We simply ignore the additional node/
// edge attributes
String formatType, nodeType, edgeType;
is >> formatType;
is >> nodeType;
is >> edgeType;
if (formatType != "LEDA.GRAPH")
return false;
// number of nodes
int n;
is >> n >> std::ws;
// create n nodes and ignore n lines
Array nodes(1,n);
int i;
for(i = 1; i <= n; ++i) {
if (readToEndOfLine(is) == false)
return false;
nodes[i] = newNode();
}
// number of edges
int m;
is >> m;
for(i = 1; i <= m; ++i) {
// read index of source and target node
int src, tgt;
is >> src >> tgt;
// indices valid?
if (src < 1 || n < src || tgt < 1 || n < tgt)
return false;
newEdge(nodes[src],nodes[tgt]);
// ignore rest of line
if (readToEndOfLine(is) == false)
return false;
}
OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
return true;
}
bool Graph::consistencyCheck() const
{
int n = 0;
node v;
forall_nodes(v,*this) {
#ifdef OGDF_DEBUG
if (v->graphOf() != this)
return false;
#endif
n++;
int in = 0, out = 0;
adjEntry adj;
forall_adj(adj,v) {
edge e = adj->m_edge;
if (adj->m_twin->m_edge != e)
return false;
if (e->m_adjSrc == adj)
out++;
else if (e->m_adjTgt == adj)
in++;
else
return false;
if (adj->m_node != v)
return false;
#ifdef OGDF_DEBUG
if (adj->graphOf() != this)
return false;
#endif
}
if (v->m_indeg != in)
return false;
if (v->m_outdeg != out)
return false;
}
if (n != m_nNodes)
return false;
int m = 0;
edge e;
forall_edges(e,*this) {
#ifdef OGDF_DEBUG
if (e->graphOf() != this)
return false;
#endif
m++;
if (e->m_adjSrc == e->m_adjTgt)
return false;
if (e->m_adjSrc->m_edge != e)
return false;
if (e->m_adjTgt->m_edge != e)
return false;
if (e->m_adjSrc->m_node != e->m_src)
return false;
if (e->m_adjTgt->m_node != e->m_tgt)
return false;
}
if (m != m_nEdges)
return false;
return true;
}
void Graph::resetEdgeIdCount(int maxId)
{
m_edgeIdCount = maxId+1;
#ifdef OGDF_DEBUG
if (ogdf::debugLevel >= int(ogdf::dlConsistencyChecks)) {
edge e;
forall_edges(e,*this)
{
// if there is an edge with higer index than maxId, we cannot
// set the edge id count to maxId+1
if (e->index() > maxId)
OGDF_ASSERT(false);
}
}
#endif
}
node Graph::splitNode(adjEntry adjStartLeft, adjEntry adjStartRight)
{
OGDF_ASSERT(adjStartLeft != 0 && adjStartRight != 0);
OGDF_ASSERT(adjStartLeft->graphOf() == this && adjStartRight->graphOf() == this);
OGDF_ASSERT(adjStartLeft->theNode() == adjStartRight->theNode());
node w = newNode();
adjEntry adj, adjSucc;
for(adj = adjStartRight; adj != adjStartLeft; adj = adjSucc) {
adjSucc = adj->cyclicSucc();
moveAdj(adj,w);
}
newEdge(adjStartLeft, adjStartRight, ogdf::before);
return w;
}
node Graph::contract(edge e)
{
adjEntry adjSrc = e->adjSource();
adjEntry adjTgt = e->adjTarget();
node v = e->source();
node w = e->target();
adjEntry adjNext;
for(adjEntry adj = adjTgt->cyclicSucc(); adj != adjTgt; adj = adjNext)
{
adjNext = adj->cyclicSucc();
edge eAdj = adj->theEdge();
if(w == eAdj->source())
moveSource(eAdj, adjSrc, before);
else
moveTarget(eAdj, adjSrc, before);
}
delNode(adjTgt->theNode());
return v;
}
void Graph::moveAdj(adjEntry adj, node w)
{
node v = adj->m_node;
v->m_adjEdges.move(adj,w->m_adjEdges);
adj->m_node = w;
edge e = adj->m_edge;
if(v == e->m_src) {
--v->m_outdeg;
e->m_src = w;
++w->m_outdeg;
} else {
--v->m_indeg;
e->m_tgt = w;
++w->m_indeg;
}
}
ostream &operator<<(ostream &os, ogdf::node v)
{
if (v) os << v->index(); else os << "nil";
return os;
}
ostream &operator<<(ostream &os, ogdf::edge e)
{
if (e) os << "(" << e->source() << "," << e->target() << ")";
else os << "nil";
return os;
}
ostream &operator<<(ostream &os, ogdf::adjEntry adj)
{
if (adj) {
ogdf::edge e = adj->theEdge();
if (adj == e->adjSource())
os << e->source() << "->" << e->target();
else
os << e->target() << "->" << e->source();
} else os << "nil";
return os;
}
} // end namespace ogdf