Apr 21, 2014 at 5:09pm UTC
Hey guys i have a problem with function number of components, i need to count them but i have no idea how, can somebody help me? this is my code so far
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
FILE *otvor_subor(){
FILE *fr;
fr=fopen("graf1.txt", "r") ;
return fr;
}
class vertex{
public:
string name;
set<vertex*> neighbours;
void add_neighbour(vertex * n){
neighbours.insert(n);
}
void print_neighbours(){
cout << "vertex:" << name << " neighbours: ";
for(set<vertex*>::iterator it = neighbours.begin(); it != neighbours.end(); it++)
{
cout << (*it)->name << " ";
}
cout << endl;
}
vertex(string name = ""){
this->name = name;
}
};
class graph{
public:
set<vertex*> vertices;
map<string,vertex*> name_to_vertex;
void print_names(){
cout << "vertices: ";
for(set<vertex*>::iterator it = vertices.begin(); it != vertices.end(); it++)
{
cout << (*it)->name << " ";
}
cout << endl;
}
void add_edge(string v1, string v2){
vertex *p1, *p2;
if( name_to_vertex.find(v1) == name_to_vertex.end())
{
p1 = new vertex(v1);
name_to_vertex[v1] = p1;
vertices.insert(p1);
}
if( name_to_vertex.find(v2) == name_to_vertex.end())
{
p2 = new vertex(v2);
name_to_vertex[v2] = p2;
vertices.insert(p2);
}
p1 = name_to_vertex[v1];
p2 = name_to_vertex[v2];
p1->add_neighbour(p2);
p2->add_neighbour(p1);
}
char *load(FILE *fr){
int n=1;
char znak;
string orol,hviezda;
char * pole=(char*)malloc(n*sizeof(char));
while(fscanf(fr,"%c",&znak)!=EOF)
{
pole=(char*)realloc(pole,(++n)*sizeof(char));
pole[n-1]=znak;
}
pole[0]=n-1;
for(int p=3;p<n;p=p+3)
{
orol=pole[p+1];
hviezda=pole[p+2];
add_edge(orol,hviezda);
}
double f=n;
printf("\n");
fclose(fr);
return pole;
}
void clear(){}
//vrat pocet komponent grafu
int number_of_components(vertex* temp1,vertex* temp2){
set<vertex*> visited;
queue<vertex*> na_prejdenie;
na_prejdenie.push(temp1); //daj zaciatocny vrchol do neprejdenych
vertex *prvy_prvok_fronty;
set<vertex*>::iterator it;
//vertex* znak=temp1;
}
//exituje cesta?
bool Is_path(string start, string end){
int counter=0;
for(set<vertex*>::iterator it = vertices.begin(); it != vertices.end(); it++)
{
if((*it)->name==start || (*it)->name==end)
counter++;
}
if(counter==2)
{
printf("pravda\n");
return true;
}
else
{
printf("nepravda\n");
return -1;
}
}
//aka je najkratsia dlzka cesty
int path_size(vertex* start, vertex* end){ }
//vrat najkratsiu cestu
vector<vertex*> path(vertex* start, vertex* end){ }
};
void main(){
graph G;
/*G.add_edge("A","B");
G.add_edge("A","C");
G.add_edge("B","D");
G.add_edge("D","A");
G.add_edge("C","E");
G.add_edge("E","F");*/
G.load(otvor_subor());
G.Is_path("P","L");
G.print_names();
G.name_to_vertex["R"]->print_neighbours();
}