void SubgraphPlanarizer::CrossingStructure::restore(PlanRep &PG, int cc)
{
	//PG.initCC(cc);
	
	Array<node> id2Node(0,m_numCrossings-1,0);
	
	SListPure<edge> edges;
	PG.allEdges(edges);

	for(SListConstIterator<edge> itE = edges.begin(); itE.valid(); ++itE)
	{
		edge ePG = *itE;
		edge e = PG.original(ePG);
		
		SListConstIterator<int> it;
		for(it = m_crossings[e].begin(); it.valid(); ++it)
		{
			node x = id2Node[*it];
			edge ePGOld = ePG;
			ePG = PG.split(ePG);
			node y = ePG->source();
			
			if(x == 0) {
				id2Node[*it] = y;
			} else {
				PG.moveTarget(ePGOld, x);
				PG.moveSource(ePG, x);
				PG.delNode(y);
			}
		}
	}
}

// extracts and adds external subgraph from stopnode to ancestors of the node with dfi root
// to edgelist, nodeMarker is used as a visited flag. returns the endnode with lowest dfi.
void FindKuratowskis::extractExternalSubgraph(
			const node stop,
			int root,
			SListPure<int>& externalStartnodes,
			SListPure<node>& externalEndnodes)
{
	int lowpoint;
	ListConstIterator<node> it;

	if (m_leastAncestor[stop] < root) {
		externalStartnodes.pushBack(m_dfi[stop]);
		externalEndnodes.pushBack(m_nodeFromDFI[m_leastAncestor[stop]]);
	}

	// descent to external active child bicomps of stopnode
	node temp;
	for (it = m_separatedDFSChildList[stop].begin(); it.valid(); ++it) {
		temp = *it;
		lowpoint = m_lowPoint[temp];
		if (lowpoint >= root) break;

		externalStartnodes.pushBack(m_dfi[temp]);
		externalEndnodes.pushBack(m_nodeFromDFI[lowpoint]);
	}
}

// compute the separated DFS children for all nodes in ascending order of
// their lowpoint values in linear time
void BoyerMyrvoldInit::computeDFSChildLists() {
	// Bucketsort by lowpoint values
	BucketLowPoint blp(m_lowPoint);

	// copy all non-virtual nodes in a list and sort them with Bucketsort
	SListPure<node> allNodes;
	for (node v : m_g.nodes) {
		if (m_dfi[v] > 0)
			allNodes.pushBack(v);
	}
	allNodes.bucketSort(1, m_nodeFromDFI.high(), blp);

	// build DFS-child list
	for (node v : allNodes) {
		OGDF_ASSERT(m_dfi[v] > 0);

		// if node is not root: insert node after last element of parent's DFSChildList
		// to achieve constant time deletion later:
		// set a pointer for each node to predecessor of his representative in the list
		if (m_adjParent[v] != nullptr) {
			OGDF_ASSERT(m_realVertex[m_adjParent[v]->theNode()] != nullptr);

			m_pNodeInParent[v] = m_separatedDFSChildList[m_realVertex[m_adjParent[v]->theNode()]].pushBack(v);

			OGDF_ASSERT(m_pNodeInParent[v].valid());
			OGDF_ASSERT(v == *m_pNodeInParent[v]);
		}
		else m_pNodeInParent[v] = nullptr;
	}
}

// Reduction reduced a set of leaves determined by their keys stored
// in leafKeys. Integer redNumber is for debugging only.
bool EmbedPQTree::Reduction(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
{
	SListPure<PQLeafKey<edge, IndInfo*, bool>*> castLeafKeys;
	for (PlanarLeafKey<IndInfo*> *key : leafKeys)
		castLeafKeys.pushBack(static_cast<PQLeafKey<edge, IndInfo*, bool>*>(key));

	return PQTree<edge, IndInfo*, bool>::Reduction(castLeafKeys);
}

// Initializes a PQTree by a set of leaves that will korrespond to
// the set of Keys stored in leafKeys.
int PlanarPQTree::Initialize(SListPure<PlanarLeafKey<IndInfo*>*> &leafKeys)
{
	SListIterator<PlanarLeafKey<IndInfo*>* >  it;
	SListPure<PQLeafKey<edge,IndInfo*,bool>*> castLeafKeys;
	for (it = leafKeys.begin(); it.valid(); ++it)
		castLeafKeys.pushBack((PQLeafKey<edge,IndInfo*,bool>*) *it);

	return PQTree<edge,IndInfo*,bool>::Initialize(castLeafKeys);
}

// Reduction reduced a set of leaves determined by their keys stored 
// in leafKeys. Integer redNumber is for debugging only.
bool PlanarPQTree::Reduction(SListPure<PlanarLeafKey<indInfo*>*> &leafKeys)
{
	SListIterator<PlanarLeafKey<indInfo*>* >  it;
	SListPure<PQLeafKey<edge,indInfo*,bool>*> castLeafKeys;
	for (it = leafKeys.begin(); it.valid(); ++it)
		castLeafKeys.pushBack((PQLeafKey<edge,indInfo*,bool>*) *it);

	return PQTree<edge,indInfo*,bool>::Reduction(castLeafKeys);
}

void parallelFreeSort(const Graph &G, SListPure<edge> &edges)
{
    G.allEdges(edges);

    BucketSourceIndex bucketSrc;
    edges.bucketSort(0,G.maxNodeIndex(),bucketSrc);

    BucketTargetIndex bucketTgt;
    edges.bucketSort(0,G.maxNodeIndex(),bucketTgt);
}

void UpwardPlanarSubgraphSimple::call(const Graph &G, List<edge> &delEdges)
{
	delEdges.clear();

	// We construct an auxiliary graph H which represents the current upward
	// planar subgraph.
	Graph H;
	NodeArray<node> mapToH(G);

	for(node v : G.nodes)
		mapToH[v] = H.newNode();


	// We currently support only single-source acyclic digraphs ...
	node s;
	hasSingleSource(G,s);

	OGDF_ASSERT(s != 0);
	OGDF_ASSERT(isAcyclic(G));

	// We start with a spanning tree of G rooted at the single source.
	NodeArray<bool> visitedNode(G,false);
	SListPure<edge> treeEdges;
	dfsBuildSpanningTree(s,treeEdges,visitedNode);


	// Mark all edges in the spanning tree so they can be skipped in the
	// loop below and add (copies of) them to H.
	EdgeArray<bool> visitedEdge(G,false);
	SListConstIterator<edge> it;
	for(it = treeEdges.begin(); it.valid(); ++it) {
		edge eG = *it;
		visitedEdge[eG] = true;
		H.newEdge(mapToH[eG->source()],mapToH[eG->target()]);
	}


	// Add subsequently the remaining edges to H and test if the resulting
	// graph is still upward planar. If not, remove the edge again from H
	// and add it to delEdges.

	for(edge eG : G.edges)
	{
		if(visitedEdge[eG] == true)
			continue;

		edge eH = H.newEdge(mapToH[eG->source()],mapToH[eG->target()]);

		if (UpwardPlanarity::isUpwardPlanar_singleSource(H) == false) {
			H.delEdge(eH);
			delEdges.pushBack(eG);
		}
	}

}

void FaceSinkGraph::doInit()
{
	const ConstCombinatorialEmbedding &E = *m_pE;

	NodeArray<node> sinkSwitch(E,nullptr); // corresponding node in F (if any)
	NodeArray<bool> isSinkSwitch(E,true);

	NodeArray<int> visited(E,-1);
	int faceNo = -1;
	for(face f : E.faces)
	{
		faceNo++;
		node faceNode = newNode();
		m_originalFace[faceNode] = f;

		SListPure<node> nodesInF;

		adjEntry adj1 = f->firstAdj(), adj = adj1;
		do {
			node v = adj->theNode();
			// if the graph is not biconnected, then node v can visited more than once
			if (visited[v] != faceNo) {
				nodesInF.pushBack(v);
				visited[v] = faceNo;
			}

			if (v == m_source)
				m_containsSource[faceNode] = true;

			isSinkSwitch[adj->theEdge()->source()] = false;

			adj = adj->twin()->cyclicPred();
		} while (adj != adj1);

		SListConstIterator<node> it;
		for(it = nodesInF.begin(); it.valid(); ++it)
		{
			node v = *it;
			if(isSinkSwitch[v])	{
				if (sinkSwitch[v] == nullptr) {
					node vF = newNode();
					m_originalNode[vF] = v;
					sinkSwitch[v] = vF;
				}

				newEdge(faceNode,sinkSwitch[v]);
			}
		}

		for(it = nodesInF.begin(); it.valid(); ++it)
			isSinkSwitch[*it] = true;
	}
}

// The function front scans the frontier of nodePtr. It returns the keys
// of the leaves found in the frontier of nodePtr in a SListPure.
// These keys include keys of direction indicators detected in the frontier.
//
// No direction is assigned to the direction indicators.
//
void EmbedPQTree::getFront(
	PQNode<edge,IndInfo*,bool>* nodePtr,
	SListPure<PQBasicKey<edge,IndInfo*,bool>*> &keys)
{
	ArrayBuffer<PQNode<edge,IndInfo*,bool>*> S;
	S.push(nodePtr);

	while (!S.empty())
	{
		PQNode<edge,IndInfo*,bool> *checkNode = S.popRet();

		if (checkNode->type() == PQNodeRoot::PQNodeType::Leaf)
			keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) checkNode->getKey());
		else
		{
			PQNode<edge,IndInfo*,bool>* firstSon  = nullptr;
			if (checkNode->type() == PQNodeRoot::PQNodeType::PNode)
			{
				firstSon = checkNode->referenceChild();
			}
			else if (checkNode->type() == PQNodeRoot::PQNodeType::QNode)
			{
				firstSon = checkNode->getEndmost(PQNodeRoot::SibDirection::Right);
				// By this, we make sure that we start on the left side
				// since the left endmost child will be on top of the stack
			}

			if (firstSon->status() == PQNodeRoot::PQNodeStatus::Indicator)
			{
				keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) firstSon->getNodeInfo());
			}
			else
				S.push(firstSon);

			PQNode<edge,IndInfo*,bool> *nextSon = firstSon->getNextSib(nullptr);
			PQNode<edge,IndInfo*,bool> *oldSib = firstSon;
			while (nextSon && nextSon != firstSon)
			{
				if (nextSon->status() == PQNodeRoot::PQNodeStatus::Indicator)
					keys.pushBack((PQBasicKey<edge,IndInfo*,bool>*) nextSon->getNodeInfo());
				else
					S.push(nextSon);

				PQNode<edge,IndInfo*,bool> *holdSib = nextSon->getNextSib(oldSib);
				oldSib = nextSon;
				nextSon = holdSib;
			}
		}
	}
}

// The function front scans the frontier of nodePtr. It returns the keys 
// of the leaves found in the frontier of nodePtr in a SListPure. 
// These keys include keys of direction indicators detected in the frontier.
//
// No direction is assigned to the direction indicators.
//
void EmbedPQTree::getFront(
	PQNode<edge,indInfo*,bool>* nodePtr,
	SListPure<PQBasicKey<edge,indInfo*,bool>*> &keys)
{   
	Stack<PQNode<edge,indInfo*,bool>*> S;
	S.push(nodePtr);
  
	while (!S.empty())
	{
		PQNode<edge,indInfo*,bool> *checkNode = S.pop();

		if (checkNode->type() == PQNodeRoot::leaf)
			keys.pushBack((PQBasicKey<edge,indInfo*,bool>*) checkNode->getKey());      
		else
		{
			PQNode<edge,indInfo*,bool>* firstSon  = 0;
			if (checkNode->type() == PQNodeRoot::PNode)
			{  
				firstSon = checkNode->referenceChild();
			}
 			else if (checkNode->type() == PQNodeRoot::QNode)
			{
				firstSon = checkNode->getEndmost(RIGHT);
				// By this, we make sure that we start on the left side
				// since the left endmost child will be on top of the stack
			}

			if (firstSon->status() == INDICATOR)
			{
				keys.pushBack((PQBasicKey<edge,indInfo*,bool>*) firstSon->getNodeInfo());
			}
			else
				S.push(firstSon);

			PQNode<edge,indInfo*,bool> *nextSon = firstSon->getNextSib(0);
			PQNode<edge,indInfo*,bool> *oldSib = firstSon;
			while (nextSon && nextSon != firstSon)
			{
				if (nextSon->status() == INDICATOR)
					keys.pushBack((PQBasicKey<edge,indInfo*,bool>*) nextSon->getNodeInfo());
				else
					S.push(nextSon);

				PQNode<edge,indInfo*,bool> *holdSib = nextSon->getNextSib(oldSib);
				oldSib = nextSon;
				nextSon = holdSib;
			}
		}
	}
}

// extract and add external subgraph from stopnode to ancestors of the node with dfi root
// to edgelist, nodeMarker is used as a visited flag. returns the endnode with lowest dfi.
void FindKuratowskis::extractExternalSubgraphBundles(
			const node stop,
			int root,
			SListPure<edge>& externalSubgraph,
			int nodeMarker)
{
	node v,temp;
	adjEntry adj;

	#ifdef OGDF_DEBUG
	forall_nodes(v,m_g) OGDF_ASSERT(m_wasHere[v]!=nodeMarker);
	#endif

	StackPure<node> stack; // stack for dfs-traversal
	ListConstIterator<node> it;
	stack.push(stop);
	while (!stack.empty()) {
		v = stack.pop();
		if (m_wasHere[v]==nodeMarker) continue;
		// mark visited nodes
		m_wasHere[v]=nodeMarker;

		// search for unvisited nodes and add them to stack
		forall_adj(adj,v) {
			temp = adj->twinNode();
			if (m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED) continue;

			// go along backedges to ancestor (ignore virtual nodes)
			if (m_dfi[temp] < root && m_dfi[temp] > 0) {
				OGDF_ASSERT(m_edgeType[adj->theEdge()]==EDGE_BACK);
				externalSubgraph.pushBack(adj->theEdge());
			} else if (v != stop && m_dfi[temp]>=m_dfi[v]) {
				// set flag and push unvisited nodes
				OGDF_ASSERT(m_edgeType[adj->theEdge()]==EDGE_BACK ||
							m_edgeType[adj->theEdge()]==EDGE_DFS ||
							m_edgeType[adj->theEdge()]==EDGE_BACK_DELETED);
				externalSubgraph.pushBack(adj->theEdge());
				if (m_wasHere[temp] != nodeMarker) stack.push(temp);
			}
		}

		// descent to external active child bicomps
		for (it = m_separatedDFSChildList[v].begin(); it.valid(); ++it) {
			temp = *it;
			if (m_lowPoint[temp] >= root) break;
			stack.push(m_nodeFromDFI[-m_dfi[temp]]);
		}
	}

void FaceSinkGraph::doInit()
{
	const ConstCombinatorialEmbedding &E = *m_pE;

	NodeArray<node> sinkSwitch(E,0); // corresponding node in F (if any)
	NodeArray<bool> isSinkSwitch(E,true);

	face f;
	forall_faces(f,E)
	{
		node faceNode = newNode();
		m_originalFace[faceNode] = f;

		SListPure<node> nodesInF;

		adjEntry adj1 = f->firstAdj(), adj = adj1;
		do {
			node v = adj->theNode();
			nodesInF.pushBack(v);

			if (v == m_source)
				m_containsSource[faceNode] = true;

			isSinkSwitch[adj->theEdge()->source()] = false;

			adj = adj->twin()->cyclicPred();
		} while (adj != adj1);

		SListConstIterator<node> it;
		for(it = nodesInF.begin(); it.valid(); ++it)
		{
			node v = *it;
			if(isSinkSwitch[v])	{
				if (sinkSwitch[v] == 0) {
					node vF = newNode();
					m_originalNode[vF] = v;
					sinkSwitch[v] = vF;
				}

				newEdge(faceNode,sinkSwitch[v]);
			}
		}

		for(it = nodesInF.begin(); it.valid(); ++it)
			isSinkSwitch[*it] = true;
	}

bool isParallelFree(const Graph &G)
{
    if (G.numberOfEdges() <= 1) return true;

    SListPure<edge> edges;
    parallelFreeSort(G,edges);

    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it, e;
    for(it = ++it; it.valid(); ++it, ePrev = e) {
        e = *it;
        if (ePrev->source() == e->source() && ePrev->target() == e->target())
            return false;
    }

    return true;
}

KuratowskiConstraint::KuratowskiConstraint(ABA_MASTER *master, int nEdges, SListPure<nodePair> &ks) :
	ABA_CONSTRAINT(master, 0, ABA_CSENSE::Less, nEdges-1, true, false, true)
{
	SListConstIterator<nodePair> it;
	for (it = ks.begin(); it.valid(); ++it) {
		m_subdivision.pushBack(*it);
	}
}

bool isParallelFreeUndirected(const Graph &G)
{
    if (G.numberOfEdges() <= 1) return true;

    SListPure<edge> edges;
    EdgeArray<int> minIndex(G), maxIndex(G);
    parallelFreeSortUndirected(G,edges,minIndex,maxIndex);

    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it, e;
    for(it = ++it; it.valid(); ++it, ePrev = e) {
        e = *it;
        if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e])
            return false;
    }

    return true;
}

int numParallelEdges(const Graph &G)
{
    if (G.numberOfEdges() <= 1) return 0;

    SListPure<edge> edges;
    parallelFreeSort(G,edges);

    int num = 0;
    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it, e;
    for(it = ++it; it.valid(); ++it, ePrev = e) {
        e = *it;
        if (ePrev->source() == e->source() && ePrev->target() == e->target())
            ++num;
    }

    return num;
}

// builds expansion graph of i-th biconnected component of the original graph
void ExpansionGraph::init(int i)
{
	OGDF_ASSERT(0 <= i);
	OGDF_ASSERT(i <= m_component.high());

	// remove previous component
	for(node v : nodes) {
		node vOrig = m_vOrig[v];
		if (vOrig)
			m_vCopy[vOrig] = nullptr;
	}
	clear();


	// create new component
	SListConstIterator<edge> it;
	for(it = m_component[i].begin(); it.valid(); ++it)
	{
		edge e = *it;

		edge eCopy = newEdge(getCopy(e->source()),getCopy(e->target()));
		m_eOrig[eCopy] = e;
	}

	// expand vertices
	for(node v : nodes)
	{
		if (original(v) && v->indeg() >= 1 && v->outdeg() >= 1) {
			node vPrime = newNode();
			m_vRep[vPrime] = m_vOrig[v];

			SListPure<edge> edges;
			v->outEdges(edges);

			SListConstIterator<edge> it;
			for(it = edges.begin(); it.valid(); ++it)
				moveSource(*it,vPrime);

			newEdge(v,vPrime);
		}
	}
}

// test if graphAcyclicTest plus edges in tmpAugmented is acyclic
// removes added edges again
bool UpwardPlanarSubgraphSimple::checkAcyclic(
	GraphCopySimple &graphAcyclicTest,
	SList<Tuple2<node,node> > &tmpAugmented)
{
	SListPure<edge> added;

	SListConstIterator<Tuple2<node,node> > it;
	for(it = tmpAugmented.begin(); it.valid(); ++it)
		added.pushBack(graphAcyclicTest.newEdge(
			graphAcyclicTest.copy((*it).x1()),
			graphAcyclicTest.copy((*it).x2())));

	bool acyclic = isAcyclic(graphAcyclicTest);

	SListConstIterator<edge> itE;
	for(itE = added.begin(); itE.valid(); ++itE)
		graphAcyclicTest.delEdge(*itE);

	return acyclic;
}

//in ClusterGraph??
//is not yet recursive!!!
node collapseCluster(ClusterGraph& CG, cluster c, Graph& G)
{
	OGDF_ASSERT(c->cCount() == 0)

	ListIterator<node> its;
	SListPure<node> collaps;

	//we should check here if not empty
	node robinson = (*(c->nBegin()));

	for (its = c->nBegin(); its.valid(); its++)
		collaps.pushBack(*its);

	CG.collaps(collaps, G);

	if (c != CG.rootCluster())
		CG.delCluster(c);

	return robinson;
}