完全图所有子图算法

#include

#include

#include

#include

#include

using namespace std;

void genSubgraphs(struct Graph*);

//generate subgraphs

void combination(int, int,int**);

//get the C(n, k) combinations and store in int**

int factorial(int n);

void getIndex(int, int&, int&);

//get the factorial value of n

//used when getting combinations of edges

//print the subgraphs to a txt file

//calculate the value of C(n, k)

void printGraph(struct Graph*);

int calc_cv(int, int);

struct Graph

{

int vernum;

int *vertices;

int **edges;

};

int main(int argc, char *argv[])

{

int vernum;

cou t<<

请输入完全图的顶点数

cin>>vernum;

//set values to origional graph

struct Graph* origGraph = new Graph;

origGraph->vernum = vernum;

int *vertices = new int[vernum];

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

{

vertices[i-1] = i;

}

int **edges = new int*[vernum];

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

{

edges[i] = new int[vernum];

}

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

for(int j = 0; j < vernum; j++)

{

if(i == j) edges[i][j] = 0;

else edges[i][j] = 1;

}

origGraph->vertices = vertices;

origGraph->edges = edges;

//generate subgraphs

genSubgraphs(origGraph);

//free memory

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

delete(origGraph->edges[i]);

delete(origGraph->edges);

delete(origGraph->vertices);

delete(origGraph);

system(

return EXIT_SUCCESS;

}

void genSubgraphs(struct Graph* graph)

{

int vernum = graph->vernum;

int count=0;

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

{

Graph* subgraph = new Graph;

subgraph->vernum = i;

//initialize the edges

int** edges = new int*[i];

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

edges[row] = new int[i];

subgraph->edges = edges;

//get all the combination of i vertices

int m=calc_cv(vernum,i);

int** vcombs = new int*[m];

for(int l = 0; l < m; l++)

vcombs[l] = new int[i];

combination(vernum,i,vcombs);

for(int j = 0; j < m; j++)

{

subgraph->vertices = vcombs[j];

//

记录非空子图的个数

//get all the conbinations of edges

int edgenum = i*(i-1)/2;

for(int edge_k = 0; edge_k <= edgenum; edge_k++)

{

//set the edges

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

{

}

if(edge_k == 0)

{

}

printGraph(subgraph);

count++;

continue;

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

edges[row][col] = 0;

//select edges

int combnum = calc_cv(edgenum,edge_k);

int** ecombs = new int*[combnum];

for(int l = 0; l < combnum; l++)

ecombs[l] = new int[edge_k];

combination(edgenum,edge_k,ecombs);

for(int k = 0; k < combnum; k++)

{

//set the edges

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

{

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

edges[row][col] = 0;

}

for(int index = 0; index < edge_k; index++)

{

}

//get the vertices of the selected edges

int row, col;

getIndex(ecombs[k][index],row,col);

edges[row][col] = 1;

edges[col][row] = 1;

printGraph(subgraph);

count++;

delete(ecombs[k]);

}

delete(ecombs);