Линейные алгоритмы для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов

graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j);

}

j--;

}

}

}

/*

cout " "NEW NEW NEW TEMP" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

std::cout " i " "->" " graphTemp[i][j] " "=" " graphEdgeTemp[i][j] " endl;

}

}

*/

}

int MyGraph::cmp(const void * a, const void * b)

{

edge_t *c = (edge_t*)a, *d = (edge_t*)b;

return c->w - d->w;

}

int MyGraph::getColor(int n)

{

int c;

if (nodes[n] < 0)

return nodes[last_n = n];

c = getColor(nodes[n]);

nodes[n] = last_n;

return c;

}

MyGraph::MyGraph()

{

}

MyGraph::~MyGraph()

{

}

void MyGraph::generate(int nVert, int nEdge)

{

srand(time(NULL));

bool planar = false;

while (not planar)

{

graph.clear();

graphEdge.clear();

graph.resize(nVert);

graphEdge.resize(nVert);

graphEdgeFrom.clear();

graphEdgeTo.clear();

graphEdgeFrom.resize(nVert);

graphEdgeTo.resize(nVert);

set<int> edgeWeight;

set<int> vertL3;

set<int> vertL2;

vertL3.clear();

vertL2.clear();

edgeWeight.clear();

for (int i = 1; i < nVert; i++)

{

graph[i].reserve(2 * nEdge);

int n1 = rand() % i;

while ((graph[n1].size() >= 3) && (vertL3.size() == 4) && (vertL3.find(n1) == vertL3.end())||

(graph[n1].size() >= 2) && (vertL2.size() == 5) && (vertL2.find(n1) == vertL2.end()))

{

n1 = rand() % i;

}

if (graph[n1].size() >= 2)

{

vertL2.insert(n1);

}

if (graph[n1].size() >= 3)

{

vertL3.insert(n1);

}

int weight = 1 + rand() % (100 * nEdge);

while (edgeWeight.find(weight) != edgeWeight.end())

{

weight = 1 + rand() % (100 * nEdge);

}

edgeWeight.insert(weight);

graph[i].push_back(n1);

graphEdge[i].push_back(weight);

graphEdgeFrom[i].push_back(i);

graphEdgeTo[i].push_back(n1);

graph[n1].push_back(i);

graphEdge[n1].push_back(weight);

graphEdgeFrom[n1].push_back(n1);

graphEdgeTo[n1].push_back(i);

}

for (int i = nVert; i < nEdge + 1; i++)

{

int n1 = rand() % nVert;

while ((graph[n1].size() >= 3) && (vertL3.size() == 4) && (vertL3.find(n1) == vertL3.end()) ||

(graph[n1].size() >= 2) && (vertL2.size() == 5) && (vertL2.find(n1) == vertL2.end()))

{

n1 = rand() % nVert;

}

if (graph[n1].size() >= 2)

{

vertL2.insert(n1);

}

if (graph[n1].size() >= 3)

{

vertL3.insert(n1);

}

int n2 = n1;

while ((n2 == n1)|| ((graph[n2].size() >= 3) && (vertL3.size() == 4) && (vertL3.find(n2) == vertL3.end()) ||

(graph[n2].size() >= 2) && (vertL2.size() == 5) && (vertL2.find(n2) == vertL2.end())))

{

n2 = rand() % nVert;

}

if (graph[n2].size() > 1)

{

vertL2.insert(n2);

}

if (graph[n2].size() > 2)

{

vertL3.insert(n2);

}

int weight = 1 + rand() % (100 * nEdge);

while (edgeWeight.find(weight) != edgeWeight.end())

{

weight = 1 + rand() % (100 * nEdge);

}

edgeWeight.insert(weight);

graph[n2].push_back(n1);

graphEdge[n2].push_back(weight);

graphEdgeFrom[n2].push_back(n2);

graphEdgeTo[n2].push_back(n1);

graph[n1].push_back(n2);

graphEdge[n1].push_back(weight);

graphEdgeFrom[n1].push_back(n1);

graphEdgeTo[n1].push_back(n2);

}

int nl3 = 0;

int nl2 = 0;

for (int i = 0; i < graph.size(); i++)

{

if (graph[i].size() > 3)

{

nl3++;

}

if (graph[i].size() > 2)

{

nl2++;

}

}

cout " nl2 " " " " nl3 " endl;

if (not((nl2 > 5) || (nl3 > 4)))

{

planar = true;

}

}

}

vector<vector<int" MyGraph::getGraph()

{

return graph;

}

vector<vector<int" MyGraph::getEdges()

{

return graphEdge;

}

void MyGraph::Alg1()

{

graphTemp = graph;

graphEdgeTemp = graphEdge;

graphEdgeTempFrom = graphEdgeFrom;

graphEdgeTempTo = graphEdgeTo;

MSTEDGE.clear();

MSTFROM.clear();

MSTTo.clear();

//int iter = 0;

while (graphTemp.size() > 1)

{

//cout "endl" "ITER #" " iter " endl " endl;

//iter++;

findMins();

name.clear();

for (int i = 0; i < graphG.size(); i++)

{

name.push_back(i);

}

for (int i = 0; i < graphG.size(); i++)

{

int n1 = i;

while (n1 != name[n1])

{

n1 = name[n1];

}

for (int j = 0; j < graphG[i].size(); j++)

{

while (n1 != name[n1])

{

n1 = name[n1];

}

int n2 = graphG[i][j];

while (n2 != name[n2])

{

n2 = name[n2];

}

if (n1 < n2)

{

connect(n1, n2);

}

else if (n2 < n1)

{

connect(n2, n1);

}

}

}

/*

std::cout " "TEMP" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

std::cout " i " "->" " graphTemp[i][j] " "=" " graphEdgeTemp[i][j] " endl;

}

}*/

clear();

}

int total = 0;

//cout "endl" "MST" " endl;

for (int i = 0; i < MSTEDGE.size(); i++)

{

//cout " MSTFROM[i] " "->" " MSTTo[i] " "=" " MSTEDGE[i] " endl;

total += MSTEDGE[i];

}

cout " endl " "total weight=" " total " endl " endl;

}

void MyGraph::Alg2()

{

graphTemp = graph;

graphEdgeTemp = graphEdge;

graphEdgeTempFrom = graphEdgeFrom;

graphEdgeTempTo = graphEdgeTo;

MSTEDGE.clear();

MSTFROM.clear();

MSTTo.clear();

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

int min = j;

for (int k = j + 1; k < graphTemp[i].size(); k++)

{

if (graphTemp[i][k] < graphTemp[i][min])

{

min = k;

}

}

swap(graphTemp[i][j], graphTemp[i][min]);

swap(graphEdgeTemp[i][j], graphEdgeTemp[i][min]);

swap(graphEdgeTempFrom[i][j], graphEdgeTempFrom[i][min]);

swap(graphEdgeTempTo[i][j], graphEdgeTempTo[i][min]);

}

for (int j = 1; j < graphTemp[i].size(); j++)

{

if (graphTemp[i][j] == graphTemp[i][j - 1])

{

if (graphEdgeTemp[i][j] < graphEdgeTemp[i][j - 1])

{

graphTemp[i].erase(graphTemp[i].begin() + j - 1); graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j - 1); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j - 1);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j - 1);

}

else

{

graphTemp[i].erase(graphTemp[i].begin() + j); graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j);

}

j--;

}

}

}

name.clear();

for (int i = 0; i < graphTemp.size(); i++)

{

name.push_back(i);

}

//int iter = 0;

while (graphTemp.size() > 1)

{

name.clear();

for (int i = 0; i < graphTemp.size(); i++)

{

name.push_back(i);

}

//cout " endl " "INTER #" " iter " endl;

//iter++;

float m = 0;

for (int i=0; i < graphTemp.size() ;i++)

{

m += graphTemp[i].size();

}

m /= 2;

float ro = m / float(graphTemp.size());

vector<int> vertList;

vertList.clear();

//cout " "List" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

if (graphTemp[i].size() <= int(4 * int (ro+0.99)))

{

vertList.push_back(i);

//cout " i " " ";

}

}

//cout " endl;

for (int i = 0; i < vertList.size(); i++)

{

//cout""!!!!!"" vertList[i] "endl;

int min = 0;

int n1 = vertList[i];

//int n1T = n1;

if (graphTemp[n1].size() > 0)

{

for (int j = 1; j < graphTemp[n1].size(); j++)

{

if (graphEdgeTemp[n1][j] < graphEdgeTemp[n1][min])

{

min = j;

}

int n2 = graphTemp[n1][min];

while (n1 != name[n1])

{

n1 = name[n1];

}

while (n2 != name[n2])

{

n2 = name[n2];

}

if (n1 > n2)

{

MSTEDGE.push_back(graphEdgeTemp[vertList[i]][min]);

MSTFROM.push_back(graphEdgeTempFrom[vertList[i]][min]);

MSTTo.push_back(graphEdgeTempTo[vertList[i]][min]);

connect(n2, n1);

}

else if (n1 < n2)

{

MSTEDGE.push_back(graphEdgeTemp[vertList[i]][min]); MSTFROM.push_back(graphEdgeTempFrom[vertList[i]][min]); MSTTo.push_back(graphEdgeTempTo[vertList[i]][min]);

connect(n1, n2);

}

}

}

//cout " "OK!" " endl;

clear();

//cout " "wait" " endl;

}

int total = 0;

//cout " endl " "MST" " endl;

for (int i = 0; i < MSTEDGE.size(); i++)

{

//cout " MSTFROM[i] " "->" " MSTTo[i] " "=" " MSTEDGE[i] " endl;

total += MSTEDGE[i];

}

cout " endl " "total weight=" " total " endl " endl;

}

void MyGraph::AlgPrim()

{

graphTemp = graph;

graphEdgeTemp = graphEdge;

graphEdgeTempFrom = graphEdgeFrom;

graphEdgeTempTo = graphEdgeTo;

MSTEDGE.clear();

MSTFROM.clear();

MSTTo.clear();

for (int i = 0; i < graph.size() - 1; i++)

{

name.clear();

for (int j = 0; j < graphTemp.size(); j++)

{

name.push_back(j);

}

int min = 0;

for (int j = 0; j < graphTemp[0].size(); j++)

{

if (graphEdgeTemp[0][j] < graphEdgeTemp[0][min])

{

min = j;

}

}

MSTEDGE.push_back(graphEdgeTemp[0][min]);

MSTFROM.push_back(graphEdgeTempFrom[0][min]);

MSTTo.push_back(graphEdgeTempTo[0][min]);

connect(0, graphTemp[0][min]);

clear();

}

int total = 0;

cout " endl " "MST" " endl;

for (int i = 0; i < MSTEDGE.size(); i++)

{

cout " MSTFROM[i] " "->" " MSTTo[i] " "=" " MSTEDGE[i] " endl;

total += MSTEDGE[i];

}

cout " endl " "total weight=" " total " endl " endl;

}

void MyGraph::AlgKruskal()

{

graphTemp = graph;

graphEdgeTemp = graphEdge;

graphEdgeTempFrom = graphEdgeFrom;

graphEdgeTempTo = graphEdgeTo;

MSTEDGE.clear();

MSTFROM.clear();

MSTTo.clear();

int NV = graphTemp.size();

vector<edge_t> edges; // Ребра графа

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

int min = j;

for (int k = j + 1; k < graphTemp[i].size(); k++)

{

if (graphTemp[i][k] < graphTemp[i][min])

{

min = k;

}

}

swap(graphTemp[i][j], graphTemp[i][min]);

swap(graphEdgeTemp[i][j], graphEdgeTemp[i][min]);

swap(graphEdgeTempFrom[i][j], graphEdgeTempFrom[i][min]);

swap(graphEdgeTempTo[i][j], graphEdgeTempTo[i][min]);

}

for (int j = 1; j < graphTemp[i].size(); j++)

{

if (graphTemp[i][j] == graphTemp[i][j - 1])

{

if (graphEdgeTemp[i][j] < graphEdgeTemp[i][j - 1])

{

graphTemp[i].erase(graphTemp[i].begin() + j - 1); graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j - 1); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j - 1);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j - 1);

}

else

{

graphTemp[i].erase(graphTemp[i].begin() + j);

graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j);

graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j);

}

j--;

}

}

}

int NE = 0;

for (int i = 0; i < graphTemp.size(); i++)

{

NE += graphEdgeTemp[i].size();

}

NE /= 2;

edges.resize(NE);

int iTemp = 0;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

if (graphEdgeTempFrom[i][j] < graphEdgeTempTo[i][j])

{

edges[iTemp].n1 = graphEdgeTempFrom[i][j];

edges[iTemp].n2 = graphEdgeTempTo[i][j];

edges[iTemp].w = graphEdgeTemp[i][j];

iTemp++;

}

}

}

nodes.resize(NV);

for (int i = 0; i < NV; i++) nodes[i] = -1 - i;

for (int i = 0; i < NE; i++)

{

int min = i;

for (int j = i + 1; j < NE; j++)

{

if (edges[j].w < edges[min].w)

{

min = j;

}

}

swap(edges[i], edges[min]);

}

for (int i = 0; i < NE; i++)

{ // пока не прошли все ребра

int c2 = getColor(edges[i].n2);

if (getColor(edges[i].n1) != c2) {

// Если ребро соединяет вершины различных цветов-мы его добавляем

// и перекрашиваем вершины

MSTEDGE.push_back(edges[i].w);

MSTFROM.push_back(edges[i].n1);

MSTTo.push_back(edges[i].n2);

nodes[last_n] = edges[i].n2;

}

}

int total = 0;

//cout " endl " "MST" " endl;

for (int i = 0; i < MSTEDGE.size(); i++)

{

//cout " MSTFROM[i] " "->" " MSTTo[i] " "=" " MSTEDGE[i] " endl;

total += MSTEDGE[i];

}

cout " endl " "total weight=" " total " endl " endl;

}

int MyGraph::BRfind(struct BRsubset subsets[], int i)

{

// find root and make root as parent of i

// (path compression)

if (subsets[i].parent != i)

subsets[i].parent =

BRfind(subsets, subsets[i].parent);

return subsets[i].parent;

}

void MyGraph::BRUnion(struct BRsubset subsets[], int x, int y)

{

int xroot = BRfind(subsets, x);

int yroot = BRfind(subsets, y);

// Attach smaller rank tree under root of high

// rank tree (Union by Rank)

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and

// increment its rank by one

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

}

void MyGraph::AlgBoruvka()

{

graphTemp = graph;

graphEdgeTemp = graphEdge;

graphEdgeTempFrom = graphEdgeFrom;

graphEdgeTempTo = graphEdgeTo;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

int min = j;

for (int k = j + 1; k < graphTemp[i].size(); k++)

{

if (graphTemp[i][k] < graphTemp[i][min])

{

min = k;

}

}

swap(graphTemp[i][j], graphTemp[i][min]);

swap(graphEdgeTemp[i][j], graphEdgeTemp[i][min]);

swap(graphEdgeTempFrom[i][j], graphEdgeTempFrom[i][min]);

swap(graphEdgeTempTo[i][j], graphEdgeTempTo[i][min]);

}

for (int j = 1; j < graphTemp[i].size(); j++)

{

if (graphTemp[i][j] == graphTemp[i][j - 1])

{

if (graphEdgeTemp[i][j] < graphEdgeTemp[i][j - 1])

{

graphTemp[i].erase(graphTemp[i].begin() + j - 1);

graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j - 1);

graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j - 1);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j - 1);

}

else

{

graphTemp[i].erase(graphTemp[i].begin() + j);

graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j);

graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j);

}

j--;

}

}

}

/*

cout " "BRTEMP" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

std::cout " i " "->" " graphTemp[i][j] " "=" " graphEdgeTemp[i][j] " endl;

}

}

*/

int E = 0;

for (int i = 0; i < graphTemp.size(); i++)

{

E += graphEdgeTemp[i].size();

}

E /= 2;

BRGraph *graph;

graph = new BRGraph;

graph->V = graphTemp.size();

graph->E = E ;

graph->edge = new BREdge[E];

int iTemp = 0;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

if (graphEdgeTempFrom[i][j] < graphEdgeTempTo[i][j])

{

graph->edge[iTemp].src = graphEdgeTempFrom[i][j];

graph->edge[iTemp].dest = graphEdgeTempTo[i][j];

graph->edge[iTemp].weight = graphEdgeTemp[i][j];

iTemp++;

}

}

}

/*

cout " endl;

for (int i = 0; i < E; i++)

{

cout " graph->edge[i].src""-"" graph->edge[i].dest ""=""graph->edge[i].weight"endl;

}*/

// Get data of given graph

int V = graph->V;

E = graph->E;

BREdge *edge = graph->edge;

struct BRsubset *subsets = new BRsubset[V];

int *cheapest = new int[V];

for (int v = 0; v < V; ++v)

{

subsets[v].parent = v;

subsets[v].rank = 0;

cheapest[v] = -1;

}

// Initially there are V different trees.

// Finally there will be one tree that will be MST

int numTrees = V;

int MSTweight = 0;

// Keep combining components (or sets) until all

// compnentes are not combined into single MST.

while (numTrees > 1)

{

// Everytime initialize cheapest array

for (int v = 0; v < V; ++v)

{

cheapest[v] = -1;

}

// Traverse through all edges and update

// cheapest of every component

for (int i = 0; i < E; i++)

{

// Find components (or sets) of two corners

// of current edge

int set1 = BRfind(subsets, edge[i].src);

int set2 = BRfind(subsets, edge[i].dest);

// If two corners of current edge belong to

// same set, ignore current edge

if (set1 == set2)

continue;

// Else check if current edge is closer to previous

// cheapest edges of set1 and set2

else

{

if (cheapest[set1] == -1 ||

edge[cheapest[set1]].weight > edge[i].weight)

cheapest[set1] = i;

if (cheapest[set2] == -1 ||

edge[cheapest[set2]].weight > edge[i].weight)

cheapest[set2] = i;

}

}

for (int i = 0; i < V; i++)

{

if (cheapest[i] != -1)

{

int set1 = BRfind(subsets, edge[cheapest[i]].src);

int set2 = BRfind(subsets, edge[cheapest[i]].dest);

if (set1 == set2)

continue;

MSTweight += edge[cheapest[i]].weight;

//printf("Edge %d-%d included in MST\n",

//edge[cheapest[i]].src, edge[cheapest[i]].dest);

BRUnion(subsets, set1, set2);

numTrees--;

}

}

}

cout " endl;

printf("Weight of MST is %d\n", MSTweight);

return;

}

MyGraph.h

#pragma once

#include <vector>

using namespace std;

class MyGraph

{

private:

vector<vector<int" graph, graphEdge,graphMST, graphMSTEdge, graphG, graphGEdge, graphTemp,graphEdgeTemp, graphEdgeTempFrom, graphEdgeTempTo, graphEdgeFrom, graphEdgeTo;

vector<int> name, MSTTo, MSTFROM, MSTEDGE;

void findMins();

void connect(int n1, int n2);

void clear();

struct BREdge

{

int src, dest, weight;

};

struct BRGraph

{

int V, E;

BREdge* edge;

};

struct BRsubset

{

int parent;

int rank;

};

int BRfind(struct BRsubset subsets[], int i);

void BRUnion(struct BRsubset subsets[], int x, int y);

struct edge_t {

int n1, n2; // направление

int w; // вес ребра

};

vector<int> nodes;

int cmp(const void *a, const void *b);

int last_n;

int getColor(int n);

public:

MyGraph();

~MyGraph();

void generate(int nVert,int nEdge);

vector<vector<int" getGraph();

vector<vector<int" getEdges();

void Alg1();

void Alg2();

void AlgPrim();

void AlgKruskal();

void AlgBoruvka();

};

ConsoleApplication.cpp

#include "pch.h"

#include <iostream>

#include "MyGraph.h"

#include <time.h>

int main()

{

std::cout " "GRAPH!\n";

MyGraph myGr;

myGr.generate(5,10);

vector<vector<int" a = myGr.getGraph();

vector<vector<int" b = myGr.getEdges();

for (int i = 0; i < a.size(); i++)

{

for (int j = 0; j < a[i].size(); j++)

{

std::cout " i " "->" " a[i][j] " "=" " b[i][j]"endl;

}

}

int t1 = clock();

myGr.Alg1();

int t2 = clock();

cout " endl;

int t3 = clock();

myGr.Alg2();

int t4 = clock();

int t5 = clock();

myGr.AlgPrim();

int t6 = clock();

int t7 = clock();

myGr.AlgKruskal();

int t8 = clock();

int t9 = clock();

myGr.AlgBoruvka();

int t10 = clock();

cout " endl " "Time ALG1 " " (t2 - t1) " endl;

cout " "Time ALG2 " " (t4 - t3) " endl;

cout " "Time AlgPrim " " (t6 - t5) " endl;

cout " "Time AlgKruskal " " (t8 - t7) " endl;

cout " "Time AlgBoruvka " " (t10 - t9) " endl;

}

Размещено на Allbest.ru