//is only called when CC not connected => m_eTreeArray is initialized
void PlanRepInc::deleteTreeConnection(int i, int j, CombinatorialEmbedding &E)
{

	edge e = m_eTreeArray(i, j);
	if (e == nullptr) return;
	edge nexte = nullptr;
	OGDF_ASSERT(e);
	OGDF_ASSERT(m_treeEdge[e]);
	//we have to take care of treeConnection edges that
	//are already crossed
	while ((e->target()->degree() == 4) &&
		m_treeEdge[e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge()])
	{
		nexte = e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge();
		OGDF_ASSERT(original(nexte) == 0)
		E.joinFaces(e);
		e = nexte;
	}
	E.joinFaces(e);
	m_eTreeArray(i, j) = nullptr;
	m_eTreeArray(j, i) = nullptr;

	OGDF_ASSERT(isConnected(*this));

}//deleteTreeConnection

//gives each edge in m_G a random edgeSubGraphs value
//works with two graphs
void SimDrawCreator::randomESG2(int doubleESGProbability)
{
	OGDF_ASSERT( doubleESGProbability <= 100 );
	OGDF_ASSERT( doubleESGProbability >= 0 );

	clearESG();

	for(edge e : m_G->edges)
	{
		//all edges have a chance of doubleESGProbability (in percent)
		//to belong to both input graphs
		int doubleESGRandom = rand() % 100;
		if(doubleESGRandom < doubleESGProbability)
		{
			m_GA->addSubGraph(e, 0);
			m_GA->addSubGraph(e, 1);
		}
		else
		{
			// all edges, which do not belong to both input graphs
			// have a 50/50 chance to belong to graph 0 or to graph 1
			int singleESGRandom = rand() % 2;
			m_GA->addSubGraph(e, singleESGRandom);
		}
	}
}

void LCA::buildTable()
{
	for (int i = 0; i < m_len - 1; ++i) {
		sparseTable(i, 1) = (m_level[i] < m_level[i+1] ? i : i+1);
	}
	sparseTable(m_len - 1, 1) = m_len - 1;

	for (int j = 2; j <= m_rangeJ; ++j) {
		for (int i = 0; i < m_len; ++i) {
			int &tn = sparseTable(i, j);
			int &t1 = sparseTable(i, j - 1);
			OGDF_ASSERT(t1 >= 0);
			OGDF_ASSERT(t1 < m_len);
			int ri = i + (1 << (j-1));
			if (ri < m_len) {
				int &t2 = sparseTable(ri, j - 1);
				OGDF_ASSERT(t2 >= 0);
				OGDF_ASSERT(t2 < m_len);
				if (m_level[t1] < m_level[t2]) {
					tn = t1;
				} else {
					tn = t2;
				}
			} else {
				tn = t1;
			}
		}
	}
}

void LCA::dfs(const Graph &G, node root)
{
	OGDF_ASSERT(isSimple(G));
	OGDF_ASSERT(isArborescence(G));
	List< std::pair<node,int> > todo;
	List< adjEntry > adjStack;
	int dfscounter = 0;
	todo.pushBack(std::pair<node,int>(root, 0));
	adjStack.pushBack(root->firstAdj());

	while (!todo.empty()) {
		const node u = todo.back().first;
		const int level = todo.back().second;
		adjEntry adj = adjStack.popBackRet();

		m_euler[dfscounter] = u;
		m_level[dfscounter] = level;
		m_representative[u] = dfscounter;

		while (adj && adj->theEdge()->source() != u) {
			adj = adj->succ();
		}
		if (adj) {
			node v = adj->twinNode();
			adjStack.pushBack(adj->succ());
			todo.pushBack(std::pair<node,int>(v, level + 1));
			adjStack.pushBack(v->firstAdj());
		} else {
			todo.popBack();
		}
		++dfscounter;
	}
}

UpwardPlanRep::UpwardPlanRep(const GraphCopy &GC, ogdf::adjEntry adj_ext) :
	GraphCopy(GC),
	isAugmented(false),
	t_hat(nullptr),
	extFaceHandle(nullptr),
	crossings(0)
{
	OGDF_ASSERT(adj_ext != nullptr);
	OGDF_ASSERT(hasSingleSource(*this));

	m_isSourceArc.init(*this, false);
	m_isSinkArc.init(*this, false);
	hasSingleSource(*this, s_hat);
	m_Gamma.init(*this);

	//compute the ext. face;
	node v = copy(GC.original(adj_ext->theNode()));
	extFaceHandle = copy(GC.original(adj_ext->theEdge()))->adjSource();
	if (extFaceHandle->theNode() != v)
		extFaceHandle = extFaceHandle->twin();
	m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));

	for(adjEntry adj : s_hat->adjEntries)
		m_isSourceArc[adj->theEdge()] = true;

	computeSinkSwitches();
}

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->entries.m_adjFirst == adj)
			fOld->entries.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());
}

// 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;
	}
}

	// this returns the rectangle defined by the intersection of this and ir. If the intersection
	// is empty, an empty rectangle is returned.
	IntersectionRectangle IntersectionRectangle::intersection(
		const IntersectionRectangle &ir) const
	{
		double top1    = m_p2.m_y;
		double bottom1 = m_p1.m_y;
		double left1   = m_p1.m_x;
		double right1  = m_p2.m_x;

		double top2    = ir.m_p2.m_y;
		double bottom2 = ir.m_p1.m_y;
		double left2   = ir.m_p1.m_x;
		double right2  = ir.m_p2.m_x;

		OGDF_ASSERT(top1 >= bottom1);
		OGDF_ASSERT(left1 <= right1);
		OGDF_ASSERT(top2 >= bottom2);
		OGDF_ASSERT(left2 <= right2);

		double bottomInter = max(bottom1,bottom2);
		double topInter    = min(top1,top2);
		double leftInter   = max(left1,left2);
		double rightInter  = min(right1,right2);

		if(bottomInter > topInter)   return IntersectionRectangle();
		if(leftInter   > rightInter) return IntersectionRectangle();

		return IntersectionRectangle(DPoint(leftInter,bottomInter),DPoint(rightInter,topInter));
	}

// keeps Changes
// keeps Node and Edge Associations
// deletes Nodes and Eges from Graph
// deletes Attributes
std::vector<MultilevelGraph *> MultilevelGraph::splitIntoComponents()
{
	std::vector<MultilevelGraph *> components;

	NodeArray<int> componentNumbers(*m_G);
	int numComponents = connectedComponents(*m_G, componentNumbers);
	if (numComponents == 0) {
		return components;
	}

	std::vector< std::vector<node> > componentArray;
	componentArray.resize(numComponents);
	for(node v : m_G->nodes) {
		componentArray[componentNumbers[v]].push_back(v);
	}

	for (auto componentSubArray : componentArray) {
		MultilevelGraph * component = removeOneCC(componentSubArray);
		components.push_back(component);
	}

	OGDF_ASSERT(m_G->numberOfNodes() == 0);
	OGDF_ASSERT(m_G->numberOfEdges() == 0);

	m_radius.init(*m_G);
	m_weight.init(*m_G);

	return components;
}

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);
		}
	}

}

//this is the main optimization routine with the loop that lowers the temperature
//and the disk radius geometrically until the temperature is zero. For each
//temperature, a certain number of new positions for a random vertex are tried
void DavidsonHarel::call(GraphAttributes &AG)
{
	initParameters();

	m_shrinkingFactor = m_shrinkFactor;

	OGDF_ASSERT(!m_energyFunctions.empty());

	const Graph &G = AG.constGraph();
	//compute the list of vertices with degree greater than zero
	G.allNodes(m_nonIsolatedNodes);
	ListIterator<node> it,itSucc;
	for(it = m_nonIsolatedNodes.begin(); it.valid(); it = itSucc) {
		itSucc = it.succ();
		if((*it)->degree() == 0) m_nonIsolatedNodes.del(it);
	}
	if(G.numberOfEdges() > 0) { //else only isolated nodes
		computeFirstRadius(AG);
		computeInitialEnergy();
		if(m_numberOfIterations == 0)
			m_numberOfIterations = m_nonIsolatedNodes.size() * m_iterationMultiplier;
		//this is the main optimization loop
		while(m_temperature > 0) {
			//iteration loop for each temperature
			for(int ic = 1; ic <= m_numberOfIterations; ic ++) {
				DPoint newPos;
				//choose random vertex and new position for vertex
				node v = computeCandidateLayout(AG,newPos);
				//compute candidate energy and decide if new layout is chosen
				ListIterator<double> it2 = m_weightsOfEnergyFunctions.begin();
				double newEnergy = 0.0;
				for(EnergyFunction *f : m_energyFunctions) {
					newEnergy += f->computeCandidateEnergy(v,newPos) * (*it2);
					++it2;
				}
				OGDF_ASSERT(newEnergy >= 0.0);
				//this tests if the new layout is accepted. If this is the case,
				//all energy functions are informed that the new layout is accepted
				if(testEnergyValue(newEnergy)) {
					for(EnergyFunction *f : m_energyFunctions)
						f->candidateTaken();
					AG.x(v) = newPos.m_x;
					AG.y(v) = newPos.m_y;
					m_energy = newEnergy;
				}
			}
			//lower the temperature and decrease the disk radius
			m_temperature = (int)floor(m_temperature*m_coolingFactor);
			m_diskRadius *= m_shrinkingFactor;
		}
	}
	//if there are zero degree vertices, they are placed using placeIsolatedNodes
	if(m_nonIsolatedNodes.size() != G.numberOfNodes())
		placeIsolatedNodes(AG);
}

// Transforms KuratowskiWrapper in KuratowskiSubdivision
void BoyerMyrvold::transform(
	const KuratowskiWrapper& source,
	KuratowskiSubdivision& target,
	NodeArray<int>& count,
	EdgeArray<int>& countEdge)
{
	// init linear counting structure
	node kn[6];
	int p = 0;
	SListConstIterator<edge> itE;
	for (itE = source.edgeList.begin(); itE.valid(); ++itE) {
		const edge& e(*itE);
		OGDF_ASSERT(!countEdge[e]);
		countEdge[e] = 1;
		if (++count[e->source()] == 3) kn[p++] = e->source();
		if (++count[e->target()] == 3) kn[p++] = e->target();
	}

	// transform edgelist of KuratowskiSubdivision to KuratowskiWrapper
	OGDF_ASSERT(p==5 || p==6);
	node n;
	edge e,f,h;
	List<edge> L;
	if (p==5) { // K5
		kn[5] = 0;
		target.init(10);
		for (int k = 0; k<5; k++) {
			forall_adj_edges(e,kn[k]) {
				if (!countEdge[e]) continue;
				n = kn[k];
				f = e;
				// traverse degree-2-path
				while (count[n = f->opposite(n)] == 2) {
					L.pushBack(f);
					forall_adj_edges(h,n) {
						if (countEdge[h] && h != f) {
							f = h;
							break;
						}
					}
				}
				L.pushBack(f);
				int i = 0;
				while (kn[i] != n) i++;
				if (i > k) {
					if (k==0) i--;
					else if (k==1) i+=2;
					else i += k+2;
					target[i].conc(L);
				} else L.clear();
			}
		}
	} else { // k33

//---------------------------------------------------------
// actual call (called by all variations of call)
//   crossing of generalizations is forbidden if forbidCrossingGens = true
//   edge costs are obeyed if costOrig != 0
//
Module::ReturnType FixedEmbeddingInserter::doCall(
	PlanRep &PG,
	const List<edge> &origEdges,
	bool forbidCrossingGens,
	const EdgeArray<int>  *costOrig,
	const EdgeArray<bool> *forbiddenEdgeOrig,
	const EdgeArray<unsigned int> *edgeSubGraph)
{
  
	double T;
	usedTime(T);
	
	ReturnType retValue = retFeasible;
	m_runsPostprocessing = 0;

	PG.embed(); 
	OGDF_ASSERT(PG.representsCombEmbedding() == true);

	if (origEdges.size() == 0)
		return retOptimal;  // nothing to do

#ifdef OGDF_DEBUG
	// Check if no edge in the list origEdges is forbidden
	if(forbiddenEdgeOrig != 0) {
		ListConstIterator<edge> itTemp;
		for(itTemp = origEdges.begin(); itTemp.valid(); ++itTemp)
			OGDF_ASSERT((*forbiddenEdgeOrig)[*itTemp] == false);
	}
#endif

	// initialization
	CombinatorialEmbedding E(PG);  // embedding of PG

	m_dual.clear();
	m_primalAdj.init(m_dual);
	m_nodeOf.init(E);

	// construct dual graph
	m_primalIsGen.init(m_dual,false);

	OGDF_ASSERT(forbidCrossingGens == false || forbiddenEdgeOrig == 0);

	if(forbidCrossingGens)
		constructDualForbidCrossingGens((const PlanRepUML&)PG,E);
	else
		constructDual(PG,E,forbiddenEdgeOrig);

#ifdef OGDF_DEBUG
	if(forbiddenEdgeOrig != 0) {
		edge e;
		forall_edges(e,m_dual) {
			OGDF_ASSERT((*forbiddenEdgeOrig)[PG.original(m_primalAdj[e]->theEdge())] == false);
		}

//*************************************************************
//gives each edge a random edgeSubgraph value
//works with graphNumber number of graphs
void SimDrawCreator::randomESG(int graphNumber)
{
	OGDF_ASSERT(0 < graphNumber);
	OGDF_ASSERT(graphNumber < 32);

	int max = (int)pow((double)2,graphNumber+1)-1;
	for(edge e : m_G->edges)
	{
		int randomESGValue = 1 + rand() % max;
		m_GA->subGraphBits(e) = randomESGValue;
	}

}//end randomESG

adjEntry UpwardPlanRep::getAdjEntry(const CombinatorialEmbedding &Gamma, node v, face f) const {
	adjEntry adjFound = nullptr;
	for(adjEntry adj : v->adjEntries) {
		if (Gamma.rightFace(adj) == f) {
			adjFound = adj;
			break;
		}
	}
	OGDF_ASSERT(adjFound != nullptr);
	OGDF_ASSERT(Gamma.rightFace(adjFound) == f);

	return adjFound;
}

TricComp::TricComp (const Graph& G) :
	m_ESTACK(G.numberOfEdges())
{
	m_pGC = new GraphCopySimple(G);
	GraphCopySimple &GC = *m_pGC;

	const int n = GC.numberOfNodes();
	const int m = GC.numberOfEdges();

#ifdef TRIC_COMP_OUTPUT
	cout << "Dividing G into triconnected components.\n" << endl;
	cout << "n = " << n << ", m = " << m << endl << endl;
#endif

	m_component = Array<CompStruct>(3*m-6);
	m_numComp = 0;

	// special cases
	OGDF_ASSERT(n >= 2);
	OGDF_ASSERT_IF(dlExtendedChecking, isBiconnected(G));

	if (n <= 2) {
		OGDF_ASSERT(m >= 3);
		CompStruct &C = newComp();
		edge e;
		forall_edges(e,GC)
			C << e;
		C.m_type = bond;
		return;
	}

	m_TYPE.init(GC,unseen);
	splitMultiEdges();

	// initialize arrays
	m_NUMBER.init(GC,0); m_LOWPT1.init(GC);
	m_LOWPT2.init(GC);   m_FATHER.init(GC,0);
	m_ND    .init(GC);   m_DEGREE.init(GC);
	m_TREE_ARC.init(GC,0);
	m_NODEAT = Array<node>(1,n);

	m_numCount = 0;
	m_start = GC.firstNode();
	DFS1(GC,m_start,0);

	edge e;
	forall_edges(e,GC) {
		bool up = (m_NUMBER[e->target()] - m_NUMBER[e->source()] > 0);
		if ((up && m_TYPE[e] == frond) || (!up && m_TYPE[e] == tree))
			GC.reverseEdge(e);
	}

//inserts copy for original edge eOrig preserving the embedding
edge PlanRep::newCopy(node v, adjEntry adAfter, edge eOrig, CombinatorialEmbedding &E)
{
	OGDF_ASSERT(eOrig->graphOf() == &(original()))
	OGDF_ASSERT(m_eCopy[eOrig].size() == 0)

	edge e;
	//GraphCopy checks direction for us
	e = GraphCopy::newEdge(v, adAfter, eOrig, E);
	//set type of copy
	if (m_pGraphAttributes != nullptr)
		setCopyType(e, eOrig);

	return e;
}

// 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 getEntriesAppend(const char *dirName,
		FileType t,
		List<string> &entries,
		const char *pattern)
{
	OGDF_ASSERT(isDirectory(dirName));

	string filePattern = string(dirName) + "\\" + pattern;

	WIN32_FIND_DATA findData;
	HANDLE handle = FindFirstFile(filePattern.c_str(), &findData);

	if (handle != INVALID_HANDLE_VALUE)
	{
		do {
			DWORD isDir = (findData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY);
			if(isDir && (
				strcmp(findData.cFileName,".") == 0 ||
				strcmp(findData.cFileName,"..") == 0)
			)
				continue;

			if (t == FileType::Entry || (t == FileType::File && !isDir) ||
				(t == FileType::Directory && isDir))
			{
				entries.pushBack(findData.cFileName);
			}
		} while(FindNextFile(handle, &findData));

		FindClose(handle);
	}
}

void RadialTreeLayout::call(GraphAttributes &AG)
{
	const Graph &tree = AG.constGraph();
	if(tree.numberOfNodes() == 0) return;

	if (!isArborescence(tree))
		OGDF_THROW_PARAM(PreconditionViolatedException, pvcForest);

	OGDF_ASSERT(m_levelDistance > 0);

	// determine root of tree (m_root)
	FindRoot(tree);

	// compute m_level[v], m_parent[v], m_leaves[v], m_numLevels
	ComputeLevels(tree);

	// computes diameter of each node
	ComputeDiameters(AG);

	// computes m_angle[v] and m_wedge[v]
	ComputeAngles(tree);

	// computes final coordinates of nodes
	ComputeCoordinates(AG);
}