Skip to content

Instantly share code, notes, and snippets.

@jaromirmuller

jaromirmuller/MatchingVertices.cpp

Last active December 18, 2015 22:28
Show Gist options
  • Save jaromirmuller/5854249 to your computer and use it in GitHub Desktop.
Save jaromirmuller/5854249 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
main.cpp
/*
* File: main.cpp
* Author: zu
*
* Created on 4. červenec 2012, 1:21
*/
#include <stdio.h>
#include <stdlib.h> /* required for atoi */
#include <iostream> /* required for getline */
#include <fstream>
#include <string> /* required for find, substr */
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include "nausparse.h" /* which includes nauty.h */
#include "naugroup.h"
#include <ext/functional>
//#define VYPIS
using namespace std;
class Node {
private:
public:
int id;
int size;
int *out;
int *in;
int frequency;
bool isGraph;
vector<Node *> children;
vector<std::set< pair<int, int> > > conditions;
public:
Node();
Node(int size);
Node(const Node * T);
//Node &operator=(const Node &node);
~Node();
void InsertChild(Node * T);
void AddConditions(std::set< pair<int, int> > C, int order);
bool GraphConditionsRespected(vector<int> * V);
int Labelmin(vector<int> * V);
void Print();
void Print2();
void Destroy();
};
Node::Node() { //konstruktory
this->id = 0;
this->size = 0;
this->out = new int[size];
this->in = new int[size];
this->frequency = 0;
this->isGraph = false;
}
Node::Node(int size) {
this->id = 0;
this->size = size;
this->out = new int[size];
this->in = new int[size];
this->frequency = 0;
this->isGraph = false;
}
Node::Node(const Node * T) {
this->id = T->id;
this->size = T->size;
this->out = new int[size];
this->in = new int[size];
for (int i = 0; i < size; i++) {
this->out[i] = T->out[i];
this->in[i] = T->in[i];
}
this->frequency = T->frequency;
this->isGraph = T->isGraph;
this->children = T->children;
this->conditions = T->conditions;
}
/*
Node &operator=(const Node &node)
{
Node tmp(node);
swap(id, tmp.id);
swap(size, tmp.size);
swap(out, tmp.out);
swap(in, tmp.in);
swap(frequency, tmp.frequency);
swap(isGraph, tmp.isGraph);
swap(children, tmp.children);
return *this;
}
*/
Node::~Node() { //destruktor (upravit smazani vektoru)
delete [] this->out;
delete [] this->in;
this->children.clear();
this->conditions.clear();
}
int predani_id = 1;
void Node::InsertChild(Node * T) {
T->id = predani_id;
predani_id++;
this->children.push_back(T);
printf("Uzel %d je %d. potomkem uzlu %d.\n ", T->id, (int) this->children.size(), this->id);
}
void Node::AddConditions(std::set< pair<int, int> > C, int order) {
//copy(C.begin(), C.end(), inserter(this->conditions, this->conditions.begin()));
//vector<std::set< pair<int, int> > *>::iterator it_v;
vector<std::set< pair<int, int> > >::iterator it;
std::set< pair<int, int> >::iterator it_s, it_t, it_v;
bool test = 0;
for (it = this->conditions.begin(); it != this->conditions.end(); it++) {
if ((*it).empty())
test = 1;
}
if (test == 0) {
if (C.empty()) {
while (!this->conditions.empty()) {
this->conditions.pop_back();
}
this->conditions.push_back(C);
} else {
this->conditions.push_back(C);
for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end(); it_s++) {
if (((*it_s).first >= order) || ((*it_s).second >= order)) {
this->conditions.back().erase(it_s);
}
}
if ((int) this->conditions.back().size() > 1) {
it_t = it_s = this->conditions.back().begin();
it_t++;
while (it_t != this->conditions.back().end()) {
//for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end()-1; it_s++) {
if ((*it_s).first == (*it_t).first) {
it_v=this->conditions.back().find(pair<int, int> ((*it_s).second, (*it_t).second));
if (it_v != this->conditions.back().end()) {
this->conditions.back().erase(it_t);
it_t = it_s = this->conditions.back().begin();
it_t++;
}
}
else {
it_s++;
it_t++;
}
}
}
}
}
/*
this->conditions.push_back(C);
for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end(); it_s++) {
if (((*it_s).first >= order) || ((*it_s).second >= order)) {
this->conditions.back().erase(it_s);
}
}
//for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end(); it_s++) {
// printf("C %d < %d\n",(*it_s).first,(*it_s).second);
//}
if ((int) this->conditions.back().size() > 1) {
it_t = it_s = this->conditions.back().begin();
it_t++;
while (it_t != this->conditions.back().end()) {
//for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end()-1; it_s++) {
if ((*it_s).first == (*it_t).first) {
it_v=this->conditions.back().find(pair<int, int> ((*it_s).second, (*it_t).second));
if (it_v != this->conditions.back().end()) {
this->conditions.back().erase(it_t);
it_t = it_s = this->conditions.back().begin();
it_t++;
}
}
else {
it_s++;
it_t++;
}
}
}
for (it_s = this->conditions.back().begin(); it_s != this->conditions.back().end(); it_s++) {
printf("Cnew %d < %d\n",(*it_s).first,(*it_s).second);
}
}*/
}
bool Node::GraphConditionsRespected(vector<int> * V) {
bool test;
vector<std::set< pair<int, int> > >::iterator it_v;
std::set< pair<int, int> >::iterator it_s;
//int size = (int) V->size();
/*for (it_v = this->conditions.begin(); it_v != this->conditions.end(); it_v++) {
for ( it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
printf("%d < %d\n", (*it_s).first, (*it_s).second);
}
}*/
for (it_v = this->conditions.begin(); it_v != this->conditions.end(); it_v++) {
test = 1;
for ( it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
if (!(((*it_s).first < size) && ((*it_s).second < size) && ((V->at((*it_s).first) < V->at((*it_s).second))))) {
//if (!(V->at((*it_s).first) < V->at((*it_s).second))) {
test = 0;
break;
//} else {
//printf("XX\n%d < %d\n%d < %d\n%d < %d\n\n", (*it_s).first, size, (*it_s).second, size, V->at((*it_s).first), V->at((*it_s).second));
}
}
}
return test;
}
int Node::Labelmin(vector<int> * V) {
int label;
int labelmin = 1000;
vector<std::set< pair<int, int> > >::iterator it_v;
std::set< pair<int, int> >::iterator it_s;
int size = (int) V->size();
for (it_v = this->conditions.begin(); it_v != this->conditions.end(); it_v++) {
label = 0;
//if ((*it_v).empty()) {
// label = 0;
//} else {
for ( it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
if ((*it_s).second == size) {
if (V->at((*it_s).first) > label) {
label = V->at((*it_s).first);
}
}
}
//}
if (label<labelmin) {
labelmin = label;
}
}
//printf("labelmin = %d", labelmin);
return labelmin;
}
void Node::Destroy() {
int i;
for (i = 0; i < (int) this->children.size(); i++) {
this->children[i]->Destroy();
}
delete this;
return;
}
void Node::Print() {
int i;
vector<std::set< pair<int, int> > >::iterator it_v;
std::set< pair<int, int> >::iterator it_s;
printf("\nID %d\tpocet potomku: %d\n", this->id, (int) this->children.size());
for (it_v = this->conditions.begin(); it_v != this->conditions.end(); it_v++) {
for (it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
printf("C %d < %d\n",(*it_s).first,(*it_s).second);
}
}
for (i = 0; i < (int) this->children.size(); i++) {
this->children[i]->Print();
}
}
void Node::Print2() {
int i;
if (this->isGraph) {
printf("frekvence vyskytu uzlu %d: %d\n", this->id, this->frequency);
}
for (i = 0; i < (int) this->children.size(); i++) {
this->children[i]->Print2();
}
}
bool Autbool = 0;
int n_g, n_net, citac, iterace = 1;
bool * visit, *artic_p, *labeled;
int * parent, *d, *hloubka, *Low, *currdeg, *lastdeg, *globdeg, *grafDin, *grafD, *grafV, *relabeling/*, *f*/;
int ** adj;
vector<int> * grafE;
vector< vector<int>* > * Aut;
void Writeautom(permutation *p, int n) {
/* Called by allgroup. Just writes the permutation p. */
int i;
vector<int> * temp = new vector<int>;
for (i = 0; i < n; i++) {
temp->push_back(p[i]);
//printf("%2d ", p[i]);
}
//printf("\n");
Aut->push_back(temp);
}
void Init(int np); //prototypy
void DFSVisit(int u, int np);
void ArticPoint(int u, int np);
void Relabeling(int u, int np);
void InsertRecursive(int **M, Node *T, int k, int np, std::set< pair<int, int> > C);
void GTrieInsert(Node *T);
int** NetworkInsert();
int** CanonicalLabeling(int * arrayE, int * arrayV, int * arrayD, int * arrayDin, int cgvn, int np, int dep);
std::set< pair<int, int> > GTrieConditions();
void GTrieMatch(int **G, Node *T);
void Match(int **G, Node *T, vector<int> *V_used);
vector<int>* MatchingVertices(int **G, Node *T, vector<int> *V_used);
int main(int argc, char *argv[]) {
Node * root = new Node();
GTrieInsert(root);
printf("pruchod:\n");
root->Print();
GTrieMatch(NetworkInsert(), root);
root->Print2();
root->Destroy();
return 0;
}
void Init(int np) {
int i, j;
for (i = 0; i < np; i++) {
visit[i] = 0;
parent[i] = -1;
hloubka[i] = 0;
for (j = 0; j < np; j++) {
adj[i][j] = 0;
}
}
for (i = 0; i < np; i++) {
for (j = grafV[i]; j < grafV[i + 1]; j++) {
if ((labeled[i] != 1) && (labeled[grafE->at(j)] != 1)) {
adj[i][grafE->at(j)] = 1;
adj[grafE->at(j)][i] = 1;
}
}
}
citac = 0;
}
void DFSVisit(int u, int np) {
int v = 0;
visit[u] = 1;
Low[u] = d[u] = ++citac;
#ifdef VYPIS
printf("%d ", u);
#endif
for (v = 0; v < np; v++) {
if (adj[u][v] == 1) {
if (visit[v] == 0) {
parent[v] = u;
hloubka[v] = hloubka[u] + 1;
DFSVisit(v, np);
Low[u] = min(Low[u], Low[v]);
} else if (v != parent[u]) {
Low[u] = min(Low[u], d[v]);
}
}
}
/*f[u] = ++citac;*/
}
void ArticPoint(int u, int np) {
int v = 0;
int y = 0;
if (hloubka[u] == 0) { //pokud jde o koren s vice nez dvema sousedy
for (v = 0; v < np; v++) {
if (u == parent[v]) {
y++;
}
}
if (y > 1) {
artic_p[u] = 1;
}
} else {
for (v = 0; v < np; v++) {
if ((adj[u][v] == 1) && (Low[v] >= d[u])) {
artic_p[u] = 1;
}
}
}
}
void Relabeling(int u, int np) {
int i, j, h, k, s, t, v, pom, pom2;
s = t = v = 2 * (np - 1);
pom = pom2 = 0;
//int t = 2*(np-1);
//int v = 2*(np-1);
int * arraycurr = new int[np];
int * arraylast = new int[np];
for (i = 0; i < np; i++) {
arraycurr[i] = 0;
arraylast[i] = 0;
}
#ifdef VYPIS
printf("\nmozne vrcholy: ");
#endif
for (i = 0; i < np; i++) {
if ((labeled[i] == 0) && (artic_p[i] == 0)) {
if (currdeg[i] < s) {
s = currdeg[i];
}
if (currdeg[i] == s) {
arraycurr[pom] = i;
#ifdef VYPIS
printf("%d ", i);
#endif
pom++;
}
}
}
#ifdef VYPIS
printf("\n");
#endif
if (pom == 1) {
k = arraycurr[0];
} else if (pom > 1) {
for (i = 0; i < pom; i++) {
if (lastdeg[arraycurr[i]] < t) {
t = lastdeg[arraycurr[i]];
}
}
for (i = 0; i < pom; i++) {
if (lastdeg[arraycurr[i]] == t) {
arraylast[pom2] = arraycurr[i];
pom2++;
}
}
if (pom2 == 1) {
k = arraylast[0];
} else if (pom2 > 1) {
for (i = 0; i < pom2; i++) {
if (globdeg[arraylast[i]] < v) {
v = globdeg[arraylast[i]];
}
}
for (i = 0; i < pom2; i++) {
if (globdeg[arraylast[i]] == v) {
k = arraylast[i];
}
}
}
}
labeled[k] = 1;
relabeling[k] = u;
#ifdef VYPIS
printf("k = %d\n", k);
#endif
vector<int> pomocneE;
int * pomocneV = new int[np + 1];
int * pomocneD = new int[np];
for (i = 0; i < (int) grafE->size(); i++) {
pomocneE.push_back(grafE->at(i));
}
for (i = 0; i < np + 1; i++) { //ulozeni grafu do novych promennych pro dalsi preznackovani
pomocneV[i] = grafV[i];
}
for (i = 0; i < np; i++) { //ulozeni grafu do novych promennych pro dalsi preznackovani
pomocneD[i] = grafD[i];
}
/*update currdegree removing umin connections*/
/*upravime grafV, grafD a grafDin tam, kde v grafE ubirame hrany DO k*/
for (i = 0; i < np; i++) {
for (j = pomocneV[i]; j < pomocneV[i + 1]; j++) {
if (pomocneE[j] == k) {
grafD[i] -= 1;
for (h = i; h < np; h++) {
grafV[h + 1] -= 1;
}
}
}
}
grafDin[k] = 0;
/*adekvatne upravime grafV, grafD a grafDin tam, kde v grafE ubirame hrany Z k*/
for (j = k + 1; j < np + 1; j++) { /*vsechny pozice v grafV od k vcetne se zmensi o grafD[k]*/
grafV[j] = grafV[j] - pomocneD[k];
}
/*snizime grafDin vrcholu, do nichz hrany vchazeji Z k*/
for (i = 0; i < np; i++) {
for (j = pomocneV[k]; j < pomocneV[k + 1]; j++) {
if (pomocneE[j] == i) {
grafDin[i] -= 1;
}
}
}
grafD[k] = 0;
/*z grafE ubirame hrany DO k*/
for (i = pomocneE.size() - 1; i >= 0; i--) {
if (pomocneE[i] == k) {
grafE->erase(grafE->begin() + i);
}
}
/*vyskrtame z grafE vsechny hrany Z k*/
grafE->erase(grafE->begin() + grafV[k], grafE->begin() + grafV[k] + pomocneD[k]);
h = 0;
for (i = 0; i < np; i++) {
for (j = pomocneV[i]; j < pomocneV[i + 1]; j++) {
if (pomocneE[i] == k) {
h++;
}
}
}
for (i = 0; i < np; i++) {
currdeg[i] = grafD[i] + grafDin[i];
}
#ifdef VYPIS
printf("\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tsousedni");
printf("\nNode\tLow[u]\td[u]\thloubka[u]\tGraf %d\t [i]\tartic_p\tcurrdeg\tlastdeg\tglobdeg\trelabeling\t\t[i]\td_in\td_out\tcurrdeg\tgrafV\tvrcholy\n", u);
printf("-----------------------------------\t----------------------------------------------------------\t\t-----------------------------------------------------------");
for (i = 0; i < np; i++) {
printf("\n %d\t%d\t%d\t%d\t", i, Low[i], d[i], hloubka[i]);
printf("\t\t [%d]\t%d\t%d\t%d\t%d\t%d", i, artic_p[i], currdeg[i], lastdeg[i], globdeg[i], relabeling[i]);
printf("\t\t\t[%d]\t%d\t%d\t%d\t%d\t", i, grafDin[i], grafD[i], currdeg[i], grafV[i]);
for (j = grafV[i]; j < grafV[i + 1]; j++) {
printf("%d ", grafE->at(j));
}
}
printf("\n\n");
#endif
for (i = 0; i < np; i++) {
lastdeg[i] = currdeg[i];
}
delete [] arraycurr;
delete [] arraylast;
delete [] pomocneV;
delete [] pomocneD;
pomocneE.clear();
}
void InsertRecursive(int **M, Node * T, int k, int np, std::set< pair<int, int> > C) {
vector<std::set< pair<int, int> > >::iterator it_v;
std::set< pair<int, int> >::iterator it_s;
int i, j, l = 0;
bool kontrola;
if (k == np) {
T->isGraph = 1;
} else {
if ((int) T->children.size() > 0) {
for (i = 0; i < (int) T->children.size(); i++) {
kontrola = true;
for (j = 0; j < k + 1; j++) {
if (!((T->children[i]->out[j] == M[k][j]) && (T->children[i]->in[j] == M[j][k]))) {
kontrola = false;
break;
}
}
if (kontrola == true) {
#ifdef VYPIS
printf("\nstary uzel\n");
for (j = 0; j < k+1; j++) {
printf("%d ", T->children[i]->in[j]);
}
printf("\n");
for (j = 0; j < k+1; j++) {
printf("%d ", T->children[i]->out[j]);
}
printf("\n");
#endif
T->children[i]->AddConditions(C, k+1);
#ifdef VYPIS
printf("k = %d", k+1);
printf("\nC T:\n");
for (it_v = T->children[i]->conditions.begin(); it_v != T->children[i]->conditions.end(); it_v++) {
for (it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
printf("%d < %d, ", (*it_s).first, (*it_s).second);
}
printf("\n");
}
#endif
InsertRecursive(M, T->children[i], k + 1, np, C);
l++;
break;
}
}
}
if (l == 0) {
Node * nc = new Node(k + 1);
for (j = 0; j < k + 1; j++) {
nc->in[j] = M[j][k];
nc->out[j] = M[k][j];
}
nc->AddConditions(C, k+1);
T->InsertChild(nc);
#ifdef VYPIS
printf("\nnovy uzel\n");
for (j = 0; j < k + 1; j++) {
printf("%d ", nc->in[j]);
}
printf("\n");
for (j = 0; j < k + 1; j++) {
printf("%d ", nc->out[j]);
}
printf("\n");
printf("k+1 = %d", k + 1);
printf("\nC nc:\n");
/*
for (it_v = nc->conditions.begin(); it_v != nc->conditions.end(); it_v++) {
for (it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
printf("%d < %d\n", (*it_s).first, (*it_s).second);
}
printf("\n");
}*/
#endif
InsertRecursive(M, nc, k + 1, np, C);
}
}
}
void GTrieInsert(Node * T) {
string str, str1, str2;
size_t pos1, pos2;
int de, m, i, j = 0, k = 0, l = 0;
multimap<int, int> mymultimap;
multimap<int, int>::iterator it;
vector< vector<int>* >::iterator it_vv;
vector<int>::iterator it_v;
string cs("malloc"); //kvuli kombinaci c a c++ v programu
char * cstr = new char [cs.size() + 1];
strcpy(cstr, cs.c_str());
DYNALLSTAT(int, lab, lab_sz);
DYNALLSTAT(int, ptn, ptn_sz);
DYNALLSTAT(int, orbits, orbits_sz);
DYNALLSTAT(setword, workspace, workspace_sz);
static DEFAULTOPTIONS_SPARSEGRAPH(options);
statsblk stats;
sparsegraph sg, cg; /* Declare sparse graph structures*/
/* Select option for canonical labelling */
options.getcanon = TRUE;
options.digraph = TRUE;
/* Initialise sparse graph structure. */
SG_INIT(sg);
SG_INIT(cg);
ifstream sourcetree("input/graphs3.txt");
if (sourcetree.is_open()) {
while (getline(sourcetree, str)) {
pos1 = str.find(' ', 0);
pos2 = str.find(' ', pos1 + 1);
str1 = str.substr(0, pos1);
str2 = str.substr(pos1 + 1, pos2 - (pos1 + 1));
n_g = atoi(str1.c_str());
de = atoi(str2.c_str());
i = pos2 + 1;
while (j < de) {
pos1 = str.find(' ', i);
pos2 = str.find(' ', pos1 + 1);
str1 = str.substr(i, pos1 - i);
str2 = str.substr(pos1 + 1, pos2 - (pos1 + 1));
mymultimap.insert(pair<int, int>(atoi(str1.c_str()), atoi(str2.c_str())));
i = pos2 + 1;
j++;
}
m = (n_g + WORDSIZE - 1) / WORDSIZE;
nauty_check(WORDSIZE, m, n_g, NAUTYVERSIONID);
DYNALLOC1(int, lab, lab_sz, n_g, cstr);
DYNALLOC1(int, ptn, ptn_sz, n_g, cstr);
DYNALLOC1(int, orbits, orbits_sz, n_g, cstr);
DYNALLOC1(setword, workspace, workspace_sz, 50 * m, cstr); //?2*m
/* Now make the graph */
SG_ALLOC(sg, n_g, de, cstr);
sg.nv = n_g;
sg.nde = de;
for (it = mymultimap.begin(); it != mymultimap.end(); it++) {
sg.e[k] = (*it).second;
k++;
}
for (k = 0; k < n_g; k++) {
sg.d[k] = (int) mymultimap.count(k);
}
sg.v[0] = 0;
for (k = 0; k < n_g - 1; k++) {
sg.v[k + 1] = l + sg.d[k];
l += sg.d[k];
}
mymultimap.clear();
int pom_sgvn = sg.v[n_g - 1] + sg.d[n_g - 1]; //sg.v[n]=sg.v[n-1]+sg.d[n-1];
nauty((graph*) & sg, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n_g, (graph*) & cg);
int pom_cgvn = cg.v[n_g - 1] + cg.d[n_g - 1]; //cg.v[n]=cg.v[n-1]+cg.d[n-1];
int sgdin[n_g], cgdin[n_g];
#ifdef VYPIS
printf("\nSekvence preznackovani\n");
for (i = 0; i < n_g; i++) { //(zakladni kanonicky labelling) tisk
printf("%d ", lab[i]);
}
printf("\n");
#endif
for (i = 0; i < n_g; i++) { //in degree grafu sg
sgdin[i] = 0;
for (j = 0; j < de; j++) {
if (sg.e[j] == i) {
sgdin[i]++;
}
}
}
for (i = 0; i < n_g; i++) { //in degree grafu cg
cgdin[i] = 0;
for (j = 0; j < de; j++) {
if (cg.e[j] == i) {
cgdin[i]++;
}
}
}
#ifdef VYPIS
printf("\nGraf SG: [i]\td_in\td_out\tsousedni vrcholy\tGraf CG: [i]\td_in\td_out\tsousedni vrcholy\n"); //sg a cg graf tisk
printf("------------------------------------------------\t------------------------------------------------");
for (i = 0; i < n_g - 1; i++) {
printf("\n\t [%d]\t%d\t%d\t", i, sgdin[i], sg.d[i]);
for (j = sg.v[i]; j < sg.v[i + 1]; j++) {
printf("%d ", sg.e[j]);
}
printf("\t\t\t\t [%d]\t%d\t%d\t", i, cgdin[i], cg.d[i]);
for (j = cg.v[i]; j < cg.v[i + 1]; j++) {
printf("%d ", cg.e[j]);
}
}
printf("\n\t [%d]\t%d\t%d\t", n_g - 1, sgdin[n_g - 1], sg.d[n_g - 1]);
for (j = sg.v[n_g - 1]; j < pom_sgvn; j++) {
printf("%d ", sg.e[j]);
}
printf("\t\t\t\t [%d]\t%d\t%d\t", n_g - 1, cgdin[n_g - 1], cg.d[n_g - 1]);
for (j = cg.v[n_g - 1]; j < pom_cgvn; j++) {
printf("%d ", cg.e[j]);
}
printf("\n\n");
#endif
printf("\nITERACE %d\n\n", iterace++);
int ** A = CanonicalLabeling(cg.e, cg.v, cg.d, cgdin, pom_cgvn, n_g, de);
std::set< pair<int, int> > C = GTrieConditions();
InsertRecursive(A, T, 0, n_g, C);
j = l = k = 0;
}
} else {
cout << "Unable to open file sourcetree.\n";
}
sourcetree.close();
//outfile.close();
}
int** NetworkInsert() {
int de, m, i = 0, j = -1, k = 0;
char * part;
FILE * source;
source = fopen("input/vstuptest7.txt", "r");
fscanf(source, "%d\n%d", &n_net, &de);
char str[n_net];
Autbool = 1;
DYNALLSTAT(int, lab, lab_sz);
DYNALLSTAT(int, ptn, ptn_sz);
DYNALLSTAT(int, orbits, orbits_sz);
DYNALLSTAT(setword, workspace, workspace_sz);
static DEFAULTOPTIONS_SPARSEGRAPH(options);
statsblk stats;
sparsegraph sg, cg; /* Declare sparse graph structures*/
/* Select option for canonical labelling */
options.getcanon = TRUE;
options.digraph = TRUE;
/* Initialise sparse graph structure. */
SG_INIT(sg);
SG_INIT(cg);
m = (n_net + WORDSIZE - 1) / WORDSIZE;
nauty_check(WORDSIZE, m, n_net, NAUTYVERSIONID);
string cs("malloc"); //kvuli kombinaci c a c++ v programu
char * cstr = new char [cs.size() + 1];
strcpy(cstr, cs.c_str());
DYNALLOC1(int, lab, lab_sz, n_net, cstr);
DYNALLOC1(int, ptn, ptn_sz, n_net, cstr);
DYNALLOC1(int, orbits, orbits_sz, n_net, cstr);
DYNALLOC1(setword, workspace, workspace_sz, 50 * m, cstr); //?2*m_net
/* Now make the graph */
SG_ALLOC(sg, n_net, de, cstr);
sg.nv = n_net;
sg.nde = de;
while (fgets(str, n_net, source) != NULL) {
if (j == -1) { //provizorium aby nepreskakoval prvni radky - opravit!!
j++;
continue;
}
sg.v[j] = i;
part = strtok(str, "\n ");
while (part != NULL) {
sg.e[i] = atoi(part);
part++;
part = strtok(NULL, "\n ");
i++;
}
sg.d[j] = i - k;
k = i;
j++;
}
fclose(source);
int pom_sgvn = sg.v[n_net - 1] + sg.d[n_net - 1]; //sg.v[n]=sg.v[n-1]+sg.d[n-1];
nauty((graph*) & sg, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n_net, (graph*) & cg);
int pom_cgvn = cg.v[n_net - 1] + cg.d[n_net - 1]; //cg.v[n]=cg.v[n-1]+cg.d[n-1];
int sgdin[n_net], cgdin[n_net];
#ifdef VYPIS
printf("\nSekvence preznackovani\n");
for (i = 0; i < n_net; i++) { //(zakladni kanonicky labelling) tisk
printf("%d ", lab[i]);
}
printf("\n");
#endif
for (i = 0; i < n_net; i++) { //in degree grafu sg
sgdin[i] = 0;
for (j = 0; j < de; j++) {
if (sg.e[j] == i) {
sgdin[i]++;
}
}
}
for (i = 0; i < n_net; i++) { //in degree grafu cg
cgdin[i] = 0;
for (j = 0; j < de; j++) {
if (cg.e[j] == i) {
cgdin[i]++;
}
}
}
#ifdef VYPIS
printf("\nGraf SG: [i]\td_in\td_out\tsousedni vrcholy\tGraf CG: [i]\td_in\td_out\tsousedni vrcholy\n"); //sg a cg graf tisk
printf("------------------------------------------------\t------------------------------------------------");
for (i = 0; i < n_net - 1; i++) {
printf("\n\t [%d]\t%d\t%d\t", i, sgdin[i], sg.d[i]);
for (j = sg.v[i]; j < sg.v[i + 1]; j++) {
printf("%d ", sg.e[j]);
}
printf("\t\t\t\t [%d]\t%d\t%d\t", i, cgdin[i], cg.d[i]);
for (j = cg.v[i]; j < cg.v[i + 1]; j++) {
printf("%d ", cg.e[j]);
}
}
printf("\n\t [%d]\t%d\t%d\t", n_net - 1, sgdin[n_net - 1], sg.d[n_net - 1]);
for (j = sg.v[n_net - 1]; j < pom_sgvn; j++) {
printf("%d ", sg.e[j]);
}
printf("\t\t\t\t [%d]\t%d\t%d\t", n_net - 1, cgdin[n_net - 1], cg.d[n_net - 1]);
for (j = cg.v[n_net - 1]; j < pom_cgvn; j++) {
printf("%d ", cg.e[j]);
}
#endif
printf("\n\nNETWORK\n");
return CanonicalLabeling(cg.e, cg.v, cg.d, cgdin, pom_cgvn, n_net, de);
}
int** CanonicalLabeling(int * arrayE, int * arrayV, int * arrayD, int * arrayDin, int cgvn, int np, int dep) {
int i, j;
adj = new int*[np]; //pole ukazatelu na zacatky radku
for (i = 0; i < np; i++) {
adj[i] = new int[np]; //dereference, do kazdeho "radku" ulozim misto pro n intu
}
visit = new bool[np];
artic_p = new bool[np];
labeled = new bool[np];
parent = new int[np];
d = new int[np]; //vstup do uzlu
hloubka = new int[np];
Low = new int[np];
currdeg = new int[np];
lastdeg = new int[np];
globdeg = new int[np];
relabeling = new int[np];
grafD = new int[np];
grafDin = new int[np];
grafE = new vector<int>();
grafV = new int[np + 1];
for (i = 0; i < np; i++) { //ulozeni grafu do novych promennych pro dalsi preznackovani
grafDin[i] = arrayDin[i];
grafD[i] = arrayD[i];
grafV[i] = arrayV[i];
}
grafV[np] = cgvn;
for (i = 0; i < dep; i++) {
grafE->push_back(arrayE[i]);
}
for (i = 0; i < np; i++) {
labeled[i] = 0;
currdeg[i] = grafD[i] + grafDin[i];
globdeg[i] = lastdeg[i] = currdeg[i];
relabeling[i] = 0;
}
for (j = np - 1; j > 0; j--) {
Init(np);
#ifdef VYPIS
printf("Discovering Sequence:\n");
#endif
for (i = 0; i < np; i++) {
if (visit[i] == 0) {
DFSVisit(i, np);
}
}
for (i = 0; i < np; i++) {
artic_p[i] = 0;
ArticPoint(i, np);
}
Relabeling(j, np);
}
for (int i = 0; i < np; i++) {
delete [] adj[i];
}
delete [] adj;
delete [] visit;
delete [] artic_p;
delete [] labeled;
delete [] parent;
delete [] d;
delete [] Low;
delete [] hloubka;
delete [] currdeg;
delete [] lastdeg;
delete [] globdeg;
delete [] grafV;
delete [] grafD;
delete [] grafDin;
/*vysledna matice*/
grafE->clear();
grafE->insert(grafE->begin(), dep, 0);
for (i = 0; i < dep; i++) {
for (j = 0; j < np; j++) {
if (arrayE[i] == j) {
grafE->at(i) = relabeling[j];
break;
}
}
}
/*mam to tu mazat???*/
int ** adj_result = new int*[np]; //pole ukazatelu na zacatky radku
for (i = 0; i < np; i++) {
adj_result[i] = new int[np]; //dereference, do kazdeho "radku" ulozim misto pro n intu
}
for (i = 0; i < np; i++) {
for (j = 0; j < np; j++) {
adj_result[i][j] = 0;
}
}
for (i = 0; i < np - 1; i++) {
for (j = arrayV[i]; j < arrayV[i + 1]; j++) {
adj_result[relabeling[i]][grafE->at(j)] = 1;
}
}
for (j = arrayV[np - 1]; j < cgvn; j++) {
adj_result[relabeling[np - 1]][grafE->at(j)] = 1;
}
delete [] relabeling;
grafE->clear();
delete grafE;
for (i = 0; i < np; i++) {
for (j = 0; j < np; j++) {
printf("%d ", adj_result[i][j]);
}
printf("\n");
}
printf("\n");
if (Autbool == 0) {
int m,k=0;
string cs("malloc"); //kvuli kombinaci c a c++ v programu
char * cstr = new char [cs.size() + 1];
strcpy(cstr, cs.c_str());
DYNALLSTAT(int, lab, lab_sz);
DYNALLSTAT(int, ptn, ptn_sz);
DYNALLSTAT(int, orbits, orbits_sz);
DYNALLSTAT(setword, workspace, workspace_sz);
static DEFAULTOPTIONS_SPARSEGRAPH(options);
statsblk stats;
sparsegraph tg; /* Declare sparse graph structures*/
grouprec *group;
options.digraph = TRUE;
options.userautomproc = groupautomproc;
options.userlevelproc = grouplevelproc;
/* Initialise sparse graph structure. */
SG_INIT(tg);
m = (np + WORDSIZE - 1) / WORDSIZE;
nauty_check(WORDSIZE, m, np, NAUTYVERSIONID);
DYNALLOC1(int, lab, lab_sz, np, cstr);
DYNALLOC1(int, ptn, ptn_sz, np, cstr);
DYNALLOC1(int, orbits, orbits_sz, np, cstr);
DYNALLOC1(setword, workspace, workspace_sz, 50 * m, cstr); //?2*m
/* Now make the graph */
SG_ALLOC(tg, np, dep, cstr);
tg.nv = np;
tg.nde = dep;
//printf("\ntg.d ");
for (i = 0; i < np; i++) {
tg.d[i]=0;
for (j = 0; j < np; j++) {
tg.d[i] += adj_result[i][j];
}
//printf("%d ", tg.d[i]);
}
for (i = 0; i < np; i++) {
for (j = 0; j < np; j++) {
if (adj_result[i][j] == 1) {
tg.e[k] = j;
k++;
}
}
}
/*printf("\ntg.e ");
for (i = 0; i < dep; i++) {
printf("%d ", tg.e[i]);
}*/
k=0;
tg.v[0] = 0;
for (i = 0; i < np-1; i++) {
tg.v[i+1] = k+tg.d[i];
k += tg.d[i];
}
/*printf("\ntg.v ");
for (i = 0; i < np; i++) {
printf("%d ", tg.v[i]);
}
printf("\n");*/
nauty((graph*) & tg, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, np, NULL);
Aut = new vector< vector<int>* >;
/* Get a pointer to the structure in which the group information
has been stored. If you use TRUE as an argument, the
structure will be "cut loose" so that it won't be used
again the next time nauty() is called. Otherwise, as
here, the same structure is used repeatedly. */
group = groupptr(FALSE);
/* Expand the group structure to include a full set of coset
representatives at every level. This step is necessary
if allgroup() is to be called. */
makecosetreps(group);
/* Call the procedure writeautom() for every element of the group.
The first call is always for the identity. */
allgroup(group, Writeautom);
vector< vector<int>* >::iterator it_vv;
vector<int>::iterator it_v;
printf("Aut:\n");
for (it_vv = Aut->begin(); it_vv != Aut->end(); it_vv++) {
//it is now a pointer to a vector<int>
for (it_v = (*it_vv)->begin(); it_v != (*it_vv)->end(); it_v++) {
// it_v is now a pointer to an integer.
printf("%2d ", *it_v);
}
printf("\n");
}
}
return adj_result; //jak smazat?
}
std::set< pair<int, int> > GTrieConditions() {
int i, j;
std::set< pair<int, int> > Conditions;
std::set< pair<int, int> >::iterator it_s;
vector< vector<int>* >::iterator it_vv;
vector<int>::iterator it_v;
if ((int) Aut->size() > 1) {
vector< vector<int>* > Aut_temp(*Aut);
vector<int> Vec_temp;
while ((int) Aut_temp.size() > 1) {
for (it_vv = Aut_temp.begin(); it_vv != Aut_temp.end() - 1; it_vv++) {
if (lexicographical_compare((*it_vv)->begin(), (*it_vv)->end(), (*(it_vv + 1))->begin(), (*(it_vv + 1))->end())) {
Aut_temp.erase(it_vv + 1);
} else {
Aut_temp.erase(it_vv);
}
break;
}
}
Vec_temp.assign(Aut_temp.front()->begin(), Aut_temp.front()->end());
for (i = 0; i < (int) Vec_temp.size(); i++) {
for (it_vv = Aut->begin(); it_vv != Aut->end(); it_vv++) {
if ((*it_vv)->at(i) != Vec_temp.at(i)) {
//printf("i %d\n", i);
//printf("(*it_vv)->at(i) %d\n", (*it_vv)->at(i));
//printf("Vec_temp.at(i) %d\n", Vec_temp.at(i));
it_v = find((*it_vv)->begin(), (*it_vv)->end(), Vec_temp.at(i));
j = (int) (it_v - (*it_vv)->begin());
//printf("j %d\n", j);
//printf("%d < %d\n", min(i, j), max(i, j));
Conditions.insert(pair<int, int> (min(i, j), max(i, j)));
//Conditions.insert(pair<int, int> (min((*it_vv)->at(i), Vec_temp.at(i)), max((*it_vv)->at(i), Vec_temp.at(i))));
}
}
}
Aut->clear();
Aut->push_back(Aut_temp.front());
Aut_temp.clear();
Vec_temp.clear();
}
printf("Conditions:\n");
for (it_s = Conditions.begin(); it_s != Conditions.end(); it_s++) {
printf("%d < %d\n", (*it_s).first, (*it_s).second);
}
printf("\n");
return Conditions;
}
void GTrieMatch(int **G, Node *T) {
int i;
vector<int> V_u;
for (i = 0; i < (int) T->children.size(); i++) {
Match(G, T->children[i], &V_u);
}
}
void Match(int **G, Node * T, vector<int> * V_used) {
vector<std::set< pair<int, int> > >::iterator it_v;
std::set< pair<int, int> >::iterator it_s;
int i, j;
vector<int> * V = MatchingVertices(G, T, V_used); // JARO FIX2
for (i = 0; i < (int) V->size(); i++) {
V_used->push_back(V->at(i));
std::cout << "V_used contains: ";
for (std::vector<int>::iterator it = V_used->begin() ; it != V_used->end(); ++it) {
std::cout << *it << ' ';
std::cout << std::endl;
}
std::cout << std::endl;
// printf("YY %d\n", V->at(i));
// printf("\nXXXXX\n");
// for (j = 0; j < (int) V_used->size(); j++) {
// printf(" %d", V_used->at(j));
// }
// printf("\n");
if (T->GraphConditionsRespected(V_used) == 1) {
if (T->isGraph) {
/*for (it_v = T->conditions.begin(); it_v != T->conditions.end(); it_v++) {
for (it_s = (*it_v).begin(); it_s != (*it_v).end(); it_s++) {
printf("%d < %d\n", (*it_s).first, (*it_s).second);
}
printf("\n");
}*/
printf("FOUND_MATCH:");
for (j = 0; j < (int) V_used->size(); j++) {
printf(" %d", V_used->at(j));
}
printf("\nUzel %d\n", T->id);
T->frequency++;
}
for (j = 0; j < (int) T->children.size(); j++) {
Match(G, T->children[j], V_used);
}
}
V_used->pop_back();
std::cout << "V_used contains: ";
for (std::vector<int>::iterator it = V_used->begin() ; it != V_used->end(); ++it) {
std::cout << *it << ' ';
std::cout << std::endl;
}
std::cout << std::endl;
}
delete V; // JARO FIX2
}
vector<int>* MatchingVertices(int **G, Node *T, vector<int> *V_used) {
int i, j, k, deg, DEG = 2 * (n_net - 1);
vector<int> V_cand;
vector<int>::iterator it_v_used;
vector<int>::iterator it_v_cand;
vector<int> * Vertices = new vector<int>();
// Vertices->clear();
vector<std::set< pair<int, int> > >::iterator it_cv;
std::set< pair<int, int> >::iterator it_cs;
int label_min, L;
vector<int> V_label;
if (! T->GraphConditionsRespected(V_used)) {
return Vertices;
}
for (it_cv = T->conditions.begin(); it_cv != T->conditions.end(); it_cv++) {
L=0;//, U=n_net;
for ( it_cs = (*it_cv).begin(); it_cs != (*it_cv).end(); it_cs++) {
if ((*it_cv).empty()) {
L = 0;
break;
/*} else if ((*it_cs).first == V_used.size()) {
if (V_used->at((*it_cs).second) < U) {
U = V_used->at((*it_cs).second);
}*/
} else if ((*it_cs).second == (int) V_used->size()) {
if (V_used->at((*it_cs).first) > L) {
L = V_used->at((*it_cs).first);
}
}
}
V_label.push_back(L);
}
sort(V_label.begin(), V_label.end());
for (i = 0; i < (int) V_label.size(); i++) {
printf("%d, ",V_label.at(i));
}
printf("\n");
label_min = V_label.at(0);
if (V_used->empty()) {
for (i = label_min; i < n_net; i++) {//T->Labelmin(V_used)
V_cand.push_back(i);
}
} else {
vector<int> V_conn;
printf("\nV_conn obsahuje:");
for (i = 0; i < (int) V_used->size(); i++) { //V_conn obsahuje vrcholy z okoli vrcholu z V_used
for (j = label_min; j < n_net; j++) {
if ((G[V_used->at(i)][j] == 1) || (G[j][V_used->at(i)] == 1)) {
V_conn.push_back(j);
printf(" %d", j);
}
}
}
printf("\n");
multimap<int, int> m_candidate;
//multimap<int, int> m;
multimap<int, int>::iterator it_m;
for (i = 0; i < (int) V_conn.size(); i++) {
deg = 0;
for (j = 0; j < n_net; j++) {
if ((G[V_conn.at(i)][j] == 1) ^ (G[j][V_conn.at(i)] == 1)) { //V_m obsahuje vrcholy V_conn serazene podle jejich stupne Dout+Din
deg++;
} else if ((G[V_conn.at(i)][j] == 1) && (G[j][V_conn.at(i)] == 1)) {
deg=deg+2;
}
}
m_candidate.insert(pair<int, int>(deg, V_conn.at(i)));
if (deg < DEG) {
DEG = deg;
}
}
V_conn.clear();
vector<int> V_m;
/*for (it_m = m_candidate.begin(); it_m != m_candidate.end(); it_m++) {
if ((*it_m).first == DEG) {
m.insert (pair<int,int>((*it_m).first,(*it_m).second));
}
}*/
transform(m_candidate.begin(), m_candidate.end(),
back_inserter(V_m), __gnu_cxx::select2nd<pair<int, int> >());
// note: select2nd is an SGI extension.
printf("multimap:\n");
for (it_m = m_candidate.begin(); it_m != m_candidate.end(); it_m++) {
printf(" %d -> %d\n", (*it_m).first, (*it_m).second);
}
printf("\n");
m_candidate.clear();
//m.clear();
printf("V_m.at(i):");
for (i = 0; i < (int) V_m.size(); i++) {
printf(" %d", V_m.at(i));
}
printf("\n");
for (i = 0; i < (int) V_m.size(); i++) { //V_cand obsahuje vrcholy z okoli vrcholu m, ktery ma nejnizsi stupen a neni z V_used
for (j = 0; j < n_net; j++) {
for (k = 0; k < (int) V_used->size(); k++) {
if ((V_used->at(k) != j) && (((G[V_m.at(0)][j] == 1) || (G[j][V_m.at(0)] == 1)) ^ (((G[V_m.at(0)][j] == 1) && (G[j][V_m.at(0)] == 1))))) {
V_cand.push_back(j);
printf("%d: %d\n",V_m.at(i), j);
}
}
}
if ((int) V_cand.size() > 0) {
printf("--> %d\n",V_cand.at(0));
break;
}
else {
V_cand.clear();
}
}
}
bool status;
for (i = 0; i < (int) V_cand.size(); i++) {
status = 1;
for (j = 0; j < (int) V_used->size(); j++) {
if ((((T->in[j] == 1) && (G[V_used->at(j)][V_cand.at(i)] == 1)) || (T->in[j] == 0)) && (((T->out[j] == 1) && (G[V_cand.at(i)][V_used->at(j)] == 1)) || (T->out[j] == 0))) {
//if (((T->in[j] == 1) && (G[V_used->at(j)][V_cand.at(i)] == 1)) && ((T->out[j] == 1) && (G[V_cand.at(i)][V_used->at(j)] == 1))) {
status = 1;
} else {
status = 0;
break;
}
}
if (status == 1){
Vertices->push_back(V_cand.at(i));
}
}
V_cand.clear();
/*printf("\nVertices:");
for (i = 0; i < (int) Vertices->size(); i++) {
printf(" %d", Vertices->at(i));
}
printf("\n");*/
return Vertices;
//}
}
Raw
MatchingVertices.cpp
vector<int>* MatchingVertices(int **G, Node *T, vector<int> *V_used) {
int i, j, k, deg, DEG = 2 * (n_net - 1);
vector<int> V_cand;
vector<int> V_label;
vector<int>::iterator it, itx;
vector<int> * Vertices = new vector<int>();
vector<std::set< pair<int, int> > >::iterator it_cv;
std::set< pair<int, int> >::iterator it_cs;
int label_min, L;
printf("MATCHING VERTICES");
if (! T->GraphConditionsRespected(V_used)) {
return Vertices;
}
for (it_cv = T->conditions.begin(); it_cv != T->conditions.end(); it_cv++) {
L = 0;//, U=n_net;
for ( it_cs = (*it_cv).begin(); it_cs != (*it_cv).end(); it_cs++) {
if ((*it_cv).empty()) {
L = 0;
break;
/*} else if ((*it_cs).first == V_used.size()) {
if (V_used->at((*it_cs).second) < U) {
U = V_used->at((*it_cs).second);
}*/
} else if ((*it_cs).second == (int) V_used->size()) {
if (V_used->at((*it_cs).first) > L) {
L = V_used->at((*it_cs).first);
}
}
}
V_label.push_back(L);
}
sort(V_label.begin(), V_label.end());
label_min = V_label.at(0);
V_label.clear();
if (V_used->empty()) {
for (i = label_min; i < n_net; i++) {//T->Labelmin(V_used)
V_cand.push_back(i);
}
} else {
////////////////////////
for (i = 0; i < (int) V_used->size(); i++) { //V_conn obsahuje vrcholy z okoli vrcholu z V_used
for (j = 0; j < n_net; j++) {//T->Labelmin(V_used)
it = find(V_used->begin(), V_used->end(), j);
itx = find(V_cand.begin(), V_cand.end(), j);
if ((it == V_used->end()) && (itx == V_cand.end())) {
if ((G[V_used->at(i)][j] == 1) || (G[j][V_used->at(i)] == 1)) {
V_cand.push_back(j);
//printf(" %d", j);
}
}
}
}
/////////////////////////
/*vector<int> V_conn;
printf("V_conn:");
for (i = 0; i < (int) V_used->size(); i++) { //V_conn obsahuje vrcholy z okoli vrcholu z V_used
for (j = label_min; j < n_net; j++) {
it = find (V_conn.begin(), V_conn.end(), j);
itx = find (V_used->begin(), V_used->end(), j);
if ((it == V_conn.end()) && (itx == V_used->end())) {
if ((G[V_used->at(i)][j] == 1) || (G[j][V_used->at(i)] == 1)) {
V_conn.push_back(j);
printf(" %d", j);
}
}
}
}
printf("\n");
multimap<int, int> m_candidate;
multimap<int, int> m;
multimap<int, int>::iterator it_m;
for (i = 0; i < (int) V_conn.size(); i++) {
deg = 0;
for (j = 0; j < n_net; j++) {
if ((G[V_conn.at(i)][j] == 1) ^ (G[j][V_conn.at(i)] == 1)) { //V_m obsahuje vrcholy V_conn serazene podle jejich stupne Dout+Din
deg++;
} else if ((G[V_conn.at(i)][j] == 1) && (G[j][V_conn.at(i)] == 1)) {
deg=deg+2;
}
}
m_candidate.insert(pair<int, int>(deg, V_conn.at(i)));
if (deg < DEG) {
DEG = deg;
}
}
V_conn.clear();
vector<int> V_m;
for (it_m = m_candidate.begin(); it_m != m_candidate.end(); it_m++) {
//if ((*it_m).first == DEG) {
m.insert (pair<int,int>((*it_m).first,(*it_m).second));
//}
}
transform(m.begin(), m.end(),
back_inserter(V_m), __gnu_cxx::select2nd<pair<int, int> >());
// note: select2nd is an SGI extension.
printf("multimap:\n");
for (it_m = m.begin(); it_m != m.end(); it_m++) {
printf(" %d -> %d\n", (*it_m).first, (*it_m).second);
}
printf("\n");
m_candidate.clear();
m.clear();
for (i = 0; i < (int) V_m.size(); i++) { //V_cand obsahuje vrcholy z okoli vrcholu m, ktery ma nejnizsi stupen a neni z V_used
for (j = 0; j < n_net; j++) {
it = find (V_used->begin(), V_used->end(), j);
if (it == V_used->end()) {
if (((G[V_m.at(i)][j] == 1) || (G[j][V_m.at(i)] == 1))) {// || (((G[V_m.at(i)][j] == 1) && (G[j][V_m.at(i)] == 1))))) {
V_cand.push_back(j);
//printf("%d: %d\n",V_m.at(i), j);
}
}
}
//if ((int) V_cand.size() > 0) {
// break;
//}
}*/
}
/*printf("V_cand: ");
for (i = 0; i < (int) V_cand.size(); i++) {
printf("%d ",V_cand.at(i));
}
printf("\n");*/
int status;
int pom, pomel;
pp = 0;
for (i = 0; i < (int) V_cand.size(); i++) {
status = 2;
pomel = 0;
pom = 0;
for (j = 0; j < (int) V_used->size(); j++) {
if ((((T->in[j] == 1) && (G[V_used->at(j)][V_cand.at(i)] == 1)) || (T->in[j] == 0)) && (((T->out[j] == 1) && (G[V_cand.at(i)][V_used->at(j)] == 1)) || (T->out[j] == 0))) {
if ((T->in[j] == 0) || (T->out[j] == 0)) {
status = 1;
pom = 1;
}
} else {
status = 0;
break;
}
pomel += pom;
}
if (status == 2){
Vertices->push_back(V_cand.at(i));
} else if (status == 1){
Vertices->push_back(V_cand.at(i));
pp += pomel;
}
}
V_cand.clear();
printf("\nVertices:");
for (i = 0; i < (int) Vertices->size(); i++) {
printf(" %d", Vertices->at(i));
}
printf("\n");
if (pp > 0) {
T->index = 1;
printf("Uzel %d\tindex %d\n", T->id, T->index);
}
return Vertices;
}
Raw
return_vector_example.cpp
#include <iostream>
#include <vector>
std::vector<int> * fn(int parametr) {
std::vector<int> *V = new std::vector<int>();
for (int i=1; i<=parametr; i++) {
V->push_back(i*parametr);
}
return V;
}
void funkce (int a, int * b) {
if ( a > 10 ) return;
std::vector<int> * V = fn(a);
int _b = b[0] + 1;
funkce(a+1, &_b);
b[0] ++;
std::cout << a << ": " << b[0] << std::endl;
std::cout << "V contains: ";
for (std::vector<int>::iterator it = V->begin() ; it != V->end(); ++it) {
std::cout << a << ": " << *it;
std::cout << std::endl;
}
std::cout << std::endl;
delete V;
return;
}
int main(int argc, char**argv) {
int b = 1;
funkce(1, &b);
return 0;
}
Raw
vstup.dot
digraph G {
0 -> 1;
0 -> 13;
1 -> 0;
1 -> 2;
1 -> 3;
2 -> 0;
2 -> 12;
3 -> 4;
4 -> 3;
5 -> 4;
5 -> 7;
6 -> 5;
6 -> 9;
7 -> 8;
7 -> 11;
8 -> 6;
9 -> 6;
10 -> 0;
}
Raw
vysek.cpp
vector<int> * MatchingVertices(int **G, Node *T, vector<int> *V_used);
vector<int>* MatchingVertices(int **G, Node *T, vector<int> *V_used) {
vector<int> * Vertices = new vector<int>();
// ... bla bla
return Vertices;
}
void Match(int **G, Node * T, vector<int> * V_used) {
vector<int> * V = MatchingVertices(G, T, V_used);
for (i = 0; i < (int) V->size(); i++) {
V_used->push_back(V->at(i));
// ... bla bla
// ... bla bla
}
delete V;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment