Graph-Algorithms-Task4/consistent.cpp at master · werweg/Graph-Algorithms-Task4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "consistent.h"
#include <iostream>


Consistent::Consistent(bool** adjacencyMatrix, const int verticesNumber)
{
    for(int i = 1; i <= verticesNumber; i++)
    {
        Vertex* vertex = new Vertex();
        vertex->SetID(i);
        this->_adjacencyList.push_back(vertex);
    }

    for(int i=0; i<verticesNumber; i++)
    {
        for(int j=i; j<verticesNumber; j++)
        {
            if(adjacencyMatrix[i][j] == true)
            {
                Vertex* u = this->_adjacencyList[i];
                Vertex* v = this->_adjacencyList[j];

                u->AddToAjacencyArray(v);
                v->AddToAjacencyArray(u);
            }
        }
    }

    Vertex* vertexS;

    for(int i=0; i<verticesNumber; i++)
    {
        std::vector<int> currentConsistent;
        Vertex* vertexX = this->_adjacencyList[i];
        if(vertexX->GetColor() == WHITE)
        {
            vertexS = vertexX;
            vertexS->SetColor(GRAY);
            std::queue<Vertex*> vertexQueue;
            vertexQueue.push(vertexS);
            while(vertexQueue.size() != 0)
            {
               Vertex* vertexU = vertexQueue.front();
               for(int j=0; j<vertexU->GetAdjacencyNumber(); j++)
               {
                    Vertex* vertexV = vertexU->GetAdjacentVertex(j);
                    if(vertexV->GetColor() == WHITE)
                    {
                        vertexV->SetColor(GRAY);
                        vertexQueue.push(vertexV);
                    }
               }
               vertexQueue.pop();
               vertexU->SetColor(BLACK);
               currentConsistent.push_back(vertexU->GetID());
            }
        }
        if(this->getMaxConsistentArray().size() < currentConsistent.size())
        {
            this->_maxConsistentArray = currentConsistent;
        }
    }
}

std::vector<int> Consistent::getMaxConsistentArray() const
{
    return this->_maxConsistentArray;
}

std::vector<int> Consistent::getMaxConsistent(bool** adjacencyMatrix, const int verticesNumber)
{
    Consistent consistent(adjacencyMatrix, verticesNumber);
    return consistent.getMaxConsistentArray();
}