// recursively write clusters and nodes
static void write_ogml_graph(const ClusterGraphAttributes &A, cluster c, int level, ostream &os)
{
	if(level > 0) {
		GraphIO::indent(os,2+level) << "<node id=\"c" << c->index() << "\">\n";
		if (A.has(GraphAttributes::nodeLabel)) {
			GraphIO::indent(os,4) << "<label id=\"lc" << c->index() << "\">\n";
			GraphIO::indent(os,5) << "<content>" << formatLabel(A.label(c)) << "</content>\n";
			GraphIO::indent(os,4) << "</label>\n";
		}
	}

	ListConstIterator<node> itn;
	for (itn = c->nBegin(); itn.valid(); ++itn) {
		node v = *itn;
		GraphIO::indent(os,3+level) << "<node id=\"n" << v->index() << "\">\n";
		if (A.has(GraphAttributes::nodeLabel)) {
			GraphIO::indent(os,4) << "<label id=\"ln" << v->index() << "\">\n";
			GraphIO::indent(os,5) << "<content>" << formatLabel(A.label(v)) << "</content>\n";
			GraphIO::indent(os,4) << "</label>\n";
		}
		GraphIO::indent(os,3+level) << "</node>\n";
	}

	for (cluster child : c->children) {
		write_ogml_graph(child, level+1, os);
	}

	if(level > 0) {
		GraphIO::indent(os,2+level) << "</node>\n";
	}
}

static void writeCluster(
	std::ostream &out, int depth,
	const ClusterArray < std::vector<edge> > &edgeMap,
	const ClusterGraph &C, const ClusterGraphAttributes *CA, const cluster &c,
	int &clusterId)
{
	if(C.rootCluster() == c) {
		writeHeader(out, depth++, CA);
	} else {
		GraphIO::indent(out, depth++) << "subgraph cluster" << clusterId
		                              << " {\n";
	}
	clusterId++;

	bool whitespace; // True if a whitespace should printed (readability).

	whitespace = false;
	if(CA) {
		writeAttributes(out, depth, *CA, c);
		whitespace = true;
	}

	if(whitespace) {
		out << "\n";
	}

	// Recursively export all subclusters.
	whitespace = false;
	for(ListConstIterator<cluster> cit = c->cBegin(); cit.valid(); ++cit) {
		writeCluster(out, depth, edgeMap, C, CA, *cit, clusterId);
		whitespace = true;
	}

	if(whitespace) {
		out << "\n";
	}

	// Then, print all nodes whithout an adjacent edge.
	whitespace = false;
	for(ListConstIterator<node> nit = c->nBegin(); nit.valid(); ++nit) {
		whitespace |= writeNode(out, depth, CA, *nit);
	}

	if(whitespace) {
		out << "\n";
	}

	// Finally, we print all edges for this cluster (ugly version for now).
	const std::vector<edge> &edges = edgeMap[c];
	whitespace = false;
	for(size_t i = 0; i < edges.size(); i++) {
		whitespace |= writeEdge(out, depth, CA, edges[i]);
	}

	GraphIO::indent(out, --depth) << "}\n";
}

void ClusterGraphCopy::createClusterTree(cluster cOrig)
{
	cluster c = m_copy[cOrig];

	ListConstIterator<cluster> itC;
	for(itC = cOrig->cBegin(); itC.valid(); ++itC) {
		cluster child = newCluster(c);
		m_copy    [*itC]  = child;
		m_original[child] = *itC;

		createClusterTree(*itC);
	}

	ListConstIterator<node> itV;
	for(itV = cOrig->nBegin(); itV.valid(); ++itV) {
		reassignNode(m_pH->copy(*itV), c);
	}
}

	forall_clusters(c,CG) {
		if(c != CG.rootCluster()) {
			cluster u = c->parent();

			newEdge(m_topNode[u], m_topNode[c]);
			newEdge(m_bottomNode[c], m_bottomNode[u]);

			newEdge(m_topNode[c], m_bottomNode[c]);
		}
	}

//returns list of all clusters in subtree at c in bottom up order
void MaximumCPlanarSubgraph::getBottomUpClusterList(const cluster c, List< cluster > & theList)
{
	ListConstIterator<cluster> it = c->cBegin();
	while (it.valid())
	{
		getBottomUpClusterList((*it), theList);
		it++;
	}
	theList.pushBack(c);
}

/*
 * Just a helper method to avoid ugly code in Parser#readEdges method. It just
 * populates \a nodes list with either a given \a v node (if not nullptr) or all
 * nodes in certain cluster found by performing a lookup with given \a id in
 * \a clusterId association.
 */
static inline bool edgeNodes(
	node v,
	const std::string &id,
	const HashArray<std::string, cluster> &clusterId,
	List<node> &nodes)
{
	if(v) {
		nodes.clear();
		nodes.pushBack(v);
	} else {
		const cluster c = clusterId[id];
		if(!c) {
			return false;
		}

		c->getClusterNodes(nodes);
	}

	return true;
}

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

static void writeCluster(
	std::ostream &out, int depth,
	const ClusterGraph &C, const ClusterGraphAttributes *CA, cluster c)
{
	if(C.rootCluster() != c) {
		GraphIO::indent(out, depth) << "<node "
		                            << "id=\"cluster" << c->index() << "\""
		                            << ">\n";
	} else {
		const std::string dir =
			(CA && !CA->directed()) ? "undirected" : "directed";
		GraphIO::indent(out, depth) << "<graph "
		                            << "mode=\"static\""
		                            << "defaultedgetype=\"" << dir << "\""
		                            << ">\n";

		if(CA) {
			defineAttributes(out, depth + 1, *CA);
		}
	}

	GraphIO::indent(out, depth + 1) << "<nodes>\n";

	for(ListConstIterator<cluster> cit = c->cBegin(); cit.valid(); ++cit) {
		writeCluster(out, depth + 2, C, CA, *cit);
	}

	for(ListConstIterator<node> nit = c->nBegin(); nit.valid(); ++nit) {
		writeNode(out, depth + 2, CA, *nit);
	}

	GraphIO::indent(out, depth + 1) << "</nodes>\n";

	if(C.rootCluster() != c) {
		GraphIO::indent(out, depth) << "</node>\n";
	} else {
		writeEdges(out, C.constGraph(), CA);
		GraphIO::indent(out, depth) << "</graph>\n";
	}
}

void kmedians::calculate_median(cluster & current_cluster, point & median) {
    const dataset & data = *m_ptr_data;
    const std::size_t dimension = data[0].size();

    for (size_t index_dimension = 0; index_dimension < dimension; index_dimension++) {
        std::sort(current_cluster.begin(), current_cluster.end(), 
            [this](std::size_t index_object1, std::size_t index_object2) 
        {
            return (*m_ptr_data)[index_object1] > (*m_ptr_data)[index_object2];
        });

        std::size_t relative_index_median = (std::size_t) (current_cluster.size() - 1) / 2;
        std::size_t index_median = current_cluster[relative_index_median];

        if (current_cluster.size() % 2 == 0) {
            std::size_t index_median_second = current_cluster[relative_index_median + 1];
            median[index_dimension] = (data[index_median][index_dimension] + data[index_median_second][index_dimension]) / 2.0;
        }
        else {
            median[index_dimension] = data[index_median][index_dimension];
        }
    }
}

void agglomerative::calculate_center(const cluster & cluster, point & center) {
    const std::vector<point> & data = *m_ptr_data;

    const size_t dimension = data[0].size();

    center.resize(dimension, 0.0);

    for (auto index_point : cluster) {
        for (size_t index_dimension = 0; index_dimension < dimension; index_dimension++) {
            center[index_dimension] += data[index_point][index_dimension];
        }
    }

    for (size_t index_dimension = 0; index_dimension < dimension; index_dimension++) {
        center[index_dimension] /= cluster.size();
    }
}

double kmeans::update_center(const cluster & p_cluster, point & p_center) {
    point total(p_center.size(), 0.0);

    /* for each object in cluster */
    for (auto object_index : p_cluster) {
        /* for each dimension */
        for (size_t dimension = 0; dimension < total.size(); dimension++) {
            total[dimension] += (*m_ptr_data)[object_index][dimension];
        }
    }

    /* average for each dimension */
    for (size_t dimension = 0; dimension < total.size(); dimension++) {
        total[dimension] = total[dimension] / p_cluster.size();
    }

    const double change = m_metric(p_center, total);

    p_center = std::move(total);
    return change;
}

//todo: is called only once, but could be sped up the same way as the co-conn check
void MaxCPlanarMaster::clusterConnection(cluster c, GraphCopy &gc, double &upperBoundC) {
	// For better performance, a node array is used to indicate which nodes are contained
	// in the currently considered cluster.
	NodeArray<bool> vInC(gc,false);
	// First check, if the current cluster \a c is a leaf cluster.
	// If so, compute the number of edges that have at least to be added
	// to make the cluster induced graph connected.
	if (c->cCount()==0) { 	//cluster \a c is a leaf cluster
		GraphCopy *inducedC = new GraphCopy((const Graph&)gc);
		List<node> clusterNodes;
		c->getClusterNodes(clusterNodes); // \a clusterNodes now contains all (original) nodes of cluster \a c.
		for (node w : clusterNodes) {
			vInC[gc.copy(w)] = true;
		}

		// Delete all nodes from \a inducedC that do not belong to the cluster,
		// in order to obtain the cluster induced graph.
		node v = inducedC->firstNode();
		while (v!=nullptr)  {
			node w = v->succ();
			if (!vInC[inducedC->original(v)]) inducedC->delNode(v);
			v = w;
		}

		// Determine number of connected components of cluster induced graph.
		//Todo: check could be skipped
		if (!isConnected(*inducedC)) {

			NodeArray<int> conC(*inducedC);
			int nCC = connectedComponents(*inducedC,conC);
			//at least #connected components - 1 edges have to be added.
			upperBoundC -= (nCC-1)*m_largestConnectionCoeff;
		}
		delete inducedC;
	// Cluster \a c is an "inner" cluster. Process all child clusters first.
	} else {	//c->cCount is != 0, process all child clusters first

		for (cluster ci : c->children) {
			clusterConnection(ci, gc, upperBoundC);
		}

		// Create cluster induced graph.
		GraphCopy *inducedC = new GraphCopy((const Graph&)gc);
		List<node> clusterNodes;
		c->getClusterNodes(clusterNodes); //\a clusterNodes now contains all (original) nodes of cluster \a c.
		for (node w : clusterNodes) {
			vInC[gc.copy(w)] = true;
		}
		node v = inducedC->firstNode();
		while (v!=nullptr)  {
			node w = v->succ();
			if (!vInC[inducedC->original(v)]) inducedC->delNode(v);
			v = w;
		}

		// Now collapse each child cluster to one node and determine #connected components of \a inducedC.
		List<node> oChildClusterNodes;
		List<node> cChildClusterNodes;
		for (cluster ci : c->children) {
			ci->getClusterNodes(oChildClusterNodes);
			// Compute corresponding nodes of graph \a inducedC.
			for (node u : oChildClusterNodes) {
				node copy = inducedC->copy(gc.copy(u));
				cChildClusterNodes.pushBack(copy);
			}
			inducedC->collapse(cChildClusterNodes);
			oChildClusterNodes.clear();
			cChildClusterNodes.clear();
		}
		// Now, check \a inducedC for connectivity.
		if (!isConnected(*inducedC)) {

			NodeArray<int> conC(*inducedC);
			int nCC = connectedComponents(*inducedC,conC);
			//at least #connected components - 1 edges have to added.
			upperBoundC -= (nCC-1)*m_largestConnectionCoeff;
		}
		delete inducedC;
	}
}//clusterConnection

	forall_clusters(workc, cGraph)
	{
		resultCluster[workc] = workc; //will be set to copy if non-c-planar
		orCluster[workc] = workc;
		originalClId[workc] = workc->index();
	}

// Recursive call for testing c-planarity of the clustered graph
// that is induced by cluster act
bool CconnectClusterPlanar::planarityTest(
	ClusterGraph &C,
	cluster &act,
	Graph &G)
{
	// Test children first
	ListConstIterator<cluster> it;
	for (it = act->cBegin(); it.valid();)
	{
		ListConstIterator<cluster> succ = it.succ();
		cluster next = (*it);
		if (!planarityTest(C,next,G))
			return false;
		it = succ;
	}

	// Get induced subgraph of cluster act and test it for planarity

	List<node> subGraphNodes;
	for (node s : act->nodes)
		subGraphNodes.pushBack(s);

	Graph subGraph;
	NodeArray<node> table;
	inducedSubGraph(G,subGraphNodes.begin(),subGraph,table);


	// Introduce super sink and add edges corresponding
	// to outgoing edges of the cluster

	node superSink = subGraph.newNode();
	EdgeArray<node> outgoingTable(subGraph,nullptr);


	for (node w : act->nodes)
	{
		//adjEntry adj = w->firstAdj();
		for(adjEntry adj : w->adjEntries)
		{
			edge e = adj->theEdge();
			edge cor = nullptr;
			if (table[e->source()] == nullptr) // edge is connected to a node outside the cluster
			{
				cor = subGraph.newEdge(table[e->target()],superSink);
				outgoingTable[cor] = e->source();
			}
			else if (table[e->target()] == nullptr) // dito
			{
				cor = subGraph.newEdge(table[e->source()],superSink);
				outgoingTable[cor] = e->target();
			}

			// else edge connects two nodes of the cluster
		}
	}
	if (superSink->degree() == 0) // root cluster is not connected to outside clusters
	{
		subGraph.delNode(superSink);
		superSink = nullptr;
	}


	bool cPlanar = preparation(subGraph,act,superSink);


	if (cPlanar && act != C.rootCluster())
	{
		// Remove induced subgraph and the cluster act.
		// Replace it by a wheel graph
		while (!subGraphNodes.empty())
		{
			node w = subGraphNodes.popFrontRet();
//			C.unassignNode(w);
			G.delNode(w);
		}

		cluster parent = act->parent();

		if (superSink && m_clusterPQTree[act])
			constructWheelGraph(C,G,parent,m_clusterPQTree[act],outgoingTable);

		C.delCluster(act);
		if (m_clusterPQTree[act] != nullptr) // if query necessary for clusters with just one child
		{
			m_clusterPQTree[act]->emptyAllPertinentNodes();
			delete m_clusterPQTree[act];
		}

	}
	else if (!cPlanar)
		{
			m_errorCode = nonCPlanar;
		}//if not cplanar

	return cPlanar;

}

//compute bag affiliation for all vertices
//store result in m_bagindex
void ClusterAnalysis::computeBags() {
	const Graph &G = m_C->constGraph();

	// Storage structure for results
	m_bagindex.init(G);
	// We use Union-Find for chunks and bags
	DisjointSets<> uf;
	NodeArray<int> setid(G); // Index mapping for union-find
#if 0
	node* nn = new node[G.numberOfNodes()]; // dito
#endif

	// Every cluster gets its index
	ClusterArray<int> cind(*m_C);
	// We store the lists of cluster vertices
	List<node>* clists = new List<node>[m_C->numberOfClusters()];
	int i = 0;

	// Store index and detect the current leaf clusters
	List<cluster> ccleafs;
	ClusterArray<int> unprocessedChildren(*m_C); //processing below: compute bags
	for(cluster c : m_C->clusters)
	{
		cind[c] = i++;
		if (c->cCount() == 0) ccleafs.pushBack(c);
		unprocessedChildren[c] = c->cCount();
	}


	// Now we run through all vertices, storing them in the parent lists,
	// at the same time, we initialize m_bagindex
	for(node v : G.nodes)
	{
		// setid is constant in the following
		setid[v] = uf.makeSet();
		// Each vertex v gets its own ClusterArray that stores v's bag index per cluster.
		// See comment on use of ClusterArrays above
		m_bagindex[v] = new ClusterArray<int>(*m_C,DefaultIndex, m_C->maxClusterIndex()+1);//m_C->numberOfClusters());
		cluster c = m_C->clusterOf(v);
		// Push vertices in parent list
		clists[cind[c]].pushBack(v);
	}

	// Now each clist contains the direct vertex descendants
	// We process the clusters bottom-up, compute the chunks
	// of the leafs first. At each level, for a cluster the
	// vertex lists of all children are concatenated
	// (could improve this by having an array of size(#leafs)
	// and concatenating only at child1), then the bags are
	// updated as follows: chunks may be linked by exactly
	// the edges with lca(c) ie the ones in m_lcaEdges[c],
	// and bags may be built by direct child clusters that join chunks.
	// While concatenating the vertex lists, we can check
	// for the vertices in each child if the uf number is the same
	// as the one of a first initial vertex, otherwise we join.

	// First, lowest level clusters are processed: All chunks are bags


	OGDF_ASSERT(!ccleafs.empty());

	while (!ccleafs.empty()){
		const cluster c = ccleafs.popFrontRet();
		Skiplist<int*> cbags; //Stores bag indexes ocurring in c

		auto storeResult = [&] {
			for (node v : clists[cind[c]]) {
				int theid = uf.find(setid[v]);
				(*m_bagindex[v])[c] = theid;
				if (!cbags.isElement(&theid)) {
					cbags.add(new int(theid));
				}
				// push into list of outer active vertices
				if (m_storeoalists && isOuterActive(v, c)) {
					(*m_oalists)[c].pushBack(v);
				}
			}
			(*m_bags)[c] = cbags.size(); // store number of bags of c
		};

		if (m_storeoalists){
			//no outeractive vertices detected so far
			(*m_oalists)[c].clear();
		}

		//process leafs separately
		if (c->cCount() == 0) {


			//Todo could use lcaEdges list here too, see below
			for (node u : c->nodes)
			{
				for(adjEntry adj : u->adjEntries) {
					node w = adj->twinNode();
					if (m_C->clusterOf(w) == c)
					{
						uf.link(uf.find(setid[u]),uf.find(setid[w]));
					}
//.........这里部分代码省略.........