Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности

{

return left. index < right. index;

}

};

struct Node

{

vector <Adjacent> edgeEnds;

COLOR color;

Node ()

{

edgeEnds = vector <Adjacent> ();

color = WHITE;

}

};

class Graph

{

public:

Graph (int _maxHalfPathLength = 5, int _vertexWeight = 1, int _edgeWeight = 3);

string Fill (ifstream& INPUT_GRAPH);

void FindPatterns ();

void Output ();

~Graph () {}

private:

void DFSsearch (int currentVertex, int previousVertex, vector<DIRECTION> coveredWay);

vector <Node> nodes;

PatternTree insidePatternTree;

int maxHalfPathLength;

int edgesNumber;

};

#endif

__________________________________________________________________

graphPath. cpp

#include <iostream>

using std:: cin;

using std:: cout;

using std:: endl;

#include <iomanip>

using std:: setw;

#include <vector>

using std:: vector;

#include <algorithm>

#include <numeric>

#include "graphPath. h"

Graph:: Graph (int _maxHalfPathLength, int _vertexWeight, int _edgeWeight)

: maxHalfPathLength (_maxHalfPathLength), edgesNumber (0)

{

if (_maxHalfPathLength < 0 || _vertexWeight < 0 || _edgeWeight < 0)

throw xParams ();

insidePatternTree = PatternTree (_maxHalfPathLength, _vertexWeight, _edgeWeight);

insidePatternTree. buildTree ();

};

string Graph:: Fill (ifstream& INPUT_GRAPH)

{

char nextSymbol;

string graphName, fullGraphName;

do {

if (INPUT_GRAPH >> graphName) {

INPUT_GRAPH. get (nextSymbol);

fullGraphName += graphName;

if (nextSymbol! = '\n')

fullGraphName += " ";

}

else

return "";

}

while (nextSymbol! = '\n');

int verticesNumber;

INPUT_GRAPH >> verticesNumber;

nodes. resize (verticesNumber + 1);

int number;

int start, end;

start = 1;

int lineEnd = 0;

while (lineEnd < verticesNumber) {

INPUT_GRAPH >> number;

if (number == 0)

++start;

else {

end = number;

nodes. at (start). edgeEnds. push_back (Adjacent (end, OUT));

nodes. at (end). edgeEnds. push_back (Adjacent (start, IN));

++edgesNumber;

}

INPUT_GRAPH. get (nextSymbol);

if (nextSymbol == '\n')

++lineEnd;

}

INPUT_GRAPH >> nextSymbol; // Звездочка

for (vector<Node>:: iterator it = nodes. begin () +1; it! = nodes. end (); ++it)

{

std:: sort (it->edgeEnds. begin (), it->edgeEnds. end (), Compare ());

}

return fullGraphName;

}

void Graph:: DFSsearch (int currentVertex, int startVertex, vector<DIRECTION> coveredWay)

{

if (coveredWay. size () < maxHalfPathLength)

{

nodes. at (currentVertex). color = BLACK; // вершины красим черным, дуги серым

for (int next = 0; next < nodes. at (currentVertex). edgeEnds. size (); ++next) {

int oneMoreVertex = nodes. at (currentVertex). edgeEnds. at (next). index;

if (nodes. at (currentVertex). edgeEnds. at (next). visitColor == WHITE && nodes. at (oneMoreVertex). color == WHITE) {

vector<DIRECTION> coveredWayIncreased = coveredWay;

DIRECTION added = nodes. at (currentVertex). edgeEnds. at (next). direct;

coveredWayIncreased. push_back (added);

nodes. at (currentVertex). edgeEnds. at (next). visitColor = GRAY;

int oneMoreVertexEdgeEndIndex = - 1;

for (int count = 0; count < nodes. at (oneMoreVertex). edgeEnds. size (); ++count) {

if (nodes. at (oneMoreVertex). edgeEnds. at (count). index == currentVertex) {

oneMoreVertexEdgeEndIndex = count;

nodes. at (oneMoreVertex). edgeEnds. at (count). visitColor = GRAY;

break;

}

}

DFSsearch (oneMoreVertex, startVertex, coveredWayIncreased);

nodes. at (currentVertex). edgeEnds. at (next). visitColor = WHITE;

nodes. at (oneMoreVertex). edgeEnds. at (oneMoreVertexEdgeEndIndex). visitColor = WHITE;

}

}

nodes. at (currentVertex). color = WHITE;

}

if (coveredWay. size ()! = this->edgesNumber) // сам полупуть не нужно еще раз подсчитывать

insidePatternTree. definePattern (coveredWay);

}

void Graph:: FindPatterns ()

{

for (int index = 1; index < nodes. size (); ++index)

{

vector<DIRECTION> coveredWay;

DFSsearch (index, index, coveredWay);

}

for (int index = 2; index < insidePatternTree. P. size (); ++index)

{

insidePatternTree. P. at (index) /= 2;

}

}

void Graph:: Output ()

{

insidePatternTree. ShowBasesScheme ();

ofstream outfile1 ("DESCR. TXT");

ofstream outfile2 ("OUTPUT. TXT");

int sum = 0;

outfile2 << insidePatternTree. P. size () - 1 << endl; // pss_output block

for (int index = 1; index < insidePatternTree. P. size (); ++index)

{

int currentNumber = insidePatternTree. P. at (index) * insidePatternTree. ISC. at (index);

sum += currentNumber;

outfile1 << currentNumber;

outfile2 << insidePatternTree. P. at (index); // pss_output block

if (index! = insidePatternTree. P. size () - 1)

{

outfile1 << " ";

// outfile2 << " "; // remove when pss_output, cindex_output

outfile2 << endl; // pss_output block

}

}

outfile1 << endl << sum << endl;

// outfile2 << endl; // remove when pss_output, cindex_output

// outfile2 << sum << endl; // cindex_output block

outfile1. close ();

outfile2. close ();

}

__________________________________________________________________

driver. cpp

#include "enums. h"

#include "patternTree. h"

#include "graphPath. h"

#include "xFile. h"

#include "txtProcessor. h"

#include <ctype. h>

#include <string>

using std:: string;

#include <fstream>

using std:: ifstream;

using std:: ofstream;

#include <iostream>

using std:: endl;

using std:: cin;

using std:: cout;

const string input_graph = "INPUT. txt";

const string params_file = "Params. txt";

const int HALF_PATH_LENGTH = 5; // значения по умолчанию

const int VERTEX_WEIGHT = 1;

const int EDGE_WEIGHT = 3;

void assignParameters (const vector<int>& _params, int& _halfPathLength, int& _vertexWeight, int& _edgeWeight)

{

for (int paramIndex = 0; paramIndex < _params. size (); ++paramIndex) {

int nextParam = _params. at (paramIndex);

switch (paramIndex) {

case 0:

_halfPathLength = nextParam;

break;

case 1:

_vertexWeight = nextParam;

break;

case 2:

_edgeWeight = nextParam;

break;

default:

break;

}

}

}

int main ()

{

try

{

string nextGraphName;

vector<int> params = txtProc:: getParamsFromFile (params_file);

int halfPathLength = HALF_PATH_LENGTH; // присваиваем значения по умолчанию. Если заданы параметрами - потом меняем.

int vertexWeight = VERTEX_WEIGHT;

int edgeWeight = EDGE_WEIGHT;

assignParameters (params, halfPathLength, vertexWeight, edgeWeight);

ifstream INPUT_GRAPH (input_graph);

Graph ourGraph (halfPathLength, vertexWeight, edgeWeight);

nextGraphName = ourGraph. Fill (INPUT_GRAPH);

ourGraph. FindPatterns ();

ourGraph. Output ();

INPUT_GRAPH. close ();

}

catch (xFile e)

{

int c;

cout << "Unable to find file: " << e. GetFilename () << endl << "press any key to continue." << endl;

cin >> c;

exit (EXIT_FAILURE);

}

catch (xParams e) {

cout << "BadParameterValue in Params. txt" << endl << "press any key to continue." << endl;

int c; cin >> c; exit (EXIT_FAILURE);

}

return 0;

}

__________________________________________________________________

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