c++ - Bipartite Undirected Graph Test: Converting to check nodes with strings instead of integers -
i'm working on bipartite test undirected graphs, using adjacency-list representation. user inputs nodes , connect to, each line being pair. example:
0 1 2 3 1 2 0 3 means 0 connected 1 , 3, 2 connected 1 , 3, etc. algorithm bfs, coloring nodes goes, , seeing if can bipartite. in addition seeing if graph bipartite, stores , outputs nodes belong group in sorted order. following previous example, 1 , 3 in group a, 2 , 0 group b. sample output be:
group a: 0 2 group b: 1 3 as best can tell, current algorithm works fine, has little no problem, save few "messy" code bits here , there cleaned up. here's entire program:
#include <iostream> #include<vector> #include<queue> #include<map> #include<list> #include<algorithm> #include<set> #include <stdio.h> #include <stdlib.h> using namespace std; vector<int>vec[50]; map<int,int>color; queue<int>q; vector<int> b; vector<int> h; bool check(int n, int src){ q.push(src); int i; color[src]=1; while(!q.empty()){ src = q.front(); q.pop(); for(i=0;i<vec[src].size();i++){ if(color[vec[src][i]]==-1){ //vec[src][i] = data; color[src] = color; color[vec[src][i]]= 1 - color[src]; q.push(vec[src][i]); if (color[src] == 0 , find(b.begin(), b.end(), vec[src][i]) == b.end() , find(h.begin(), h.end(), vec[src][i]) == h.end()){ b.push_back(vec[src][i]); } else if (color[src] == 1 , find(b.begin(), b.end(), vec[src][i]) == b.end() , find(h.begin(), h.end(), vec[src][i]) == h.end()){ h.push_back(vec[src][i]); } } else if(color[vec[src][i]]== color[src]){ return 0; } else{ if(find(b.begin(), b.end(), vec[src][i]) != b.end()){ break; } else if(find(h.begin(), h.end(), vec[src][i]) != h.end()){ break; } else{ b.push_back(vec[src][i]); } } } } return 1; } int distinct(const vector<int>& v){ set<int> distinct_container; for(auto curr_int = v.begin(), end = v.end(); curr_int != end; ++curr_int){ distinct_container.insert(*curr_int); } return distinct_container.size(); } int main() { int inp; int index = 0; vector<int> input; while (cin >> inp){ input.push_back(inp); } int points = distinct(input); while(index < points){ color[index]= - 1; index++; } index = 0; while(index < input.size()){ vec[input[index]].push_back(input[index + 1]); vec[input[index + 1]].push_back(input[index]); index += 2; } bool res = 1; index = 0; for(int = 0; < points; i++){ if(color[i]==-1){ res = res && check(points, i); } } if(res){ sort(b.begin(), b.end()); sort(h.begin(), h.end()); cout << "group a:\n"; int x = 0; while (x < b.size()){ cout << b[x] << "\n"; x++; } cout << "group b:\n"; int y = 0; while (y < h.size()){ cout << h[y] << "\n"; y++; } } else{ cout << "impossible"; } return 0; } now, problem i'm having have convert nodes have string data, rather integer. instead of pairing numbers 1 , 2, want pair names jane , frank, following same input syntax previous example: single white space between them indicates pairing. still testing nodes if they're bipartisan, coloring them in search, adding them vectors output later in respective groups. changing data type of input. , i've made no progress in attempts.
any tremendously appreciated. i'm looking fix on data types, i'll take criticism , recommendations on of it. please give me more work with. thank in advance.
edit: following idea laid out me kraskevich, think have going. i've run 2 new problems: getting maps @ end output names, , current algorithm, not matter input, returns impossible.
new code: main changed, , global declarations of more vectors.
map<string, int> tonum; vector<string> numtostring; vector<int> bn; vector<int> hn; vector<string> bs; vector<string> hs; ................ int main(){ string s; vector<int> input; int edges = 0; while (cin >> s){ edges++; } int id; int index = 0; int points = 0; if (tonum.find(s) != tonum.end()){ id = tonum[s]; } else{ numtostring.push_back(s); tonum.insert( pair<int, string>(numtostring.size() - 1, s)); id = numtostring.size() - 1; ++points; input.push_back(id); } while(index < points){ color[index]= - 1; index++; } index = 0; while(index < numtostring.size()){ vec[input[index]].push_back(input[index + 1]); vec[input[index + 1]].push_back(input[index]); index += 2; } bool res = 1; index = 0; for(int = 0; < points; i++){ if(color[i]==-1){ res = res && check(points, i); } } if(res){ index = 0; int key = 0; string name; while (index < bn.size()){ name = tonum[bn[index]]; bs.push_back(name); index++; } index = 0; while (index < hn.size()){ name = tonum[bn[index]]; hs.push_back(name); index++; } sort(bs.begin(), bs.end()); sort(hs.begin(), hs.end()); cout << "group a\n"; int x = 0; while (x < bs.size()){ cout << bs[x] << "\n"; x++; } cout << "group b\n"; int y = 0; while (y < hs.size()){ cout << hs[y] << "\n"; y++; } } else{ cout << "impossible"; } return 0; }
i not change implementation of breadth first search. instead, can map strings numbers, run existing implementation , them map numbers strings.
how preform mapping? that:
// mapping strings ids. std::map<std::string, int> tonum; // mapping ids strings. std::vector<std::string> numtostring; ... std::string s; std::cin >> s; int id; if (tonum.find(s) != tonum.end()) { id = tonum[s]; } else { numtostring.push_back(s); id = numtostring.size() - 1; tonum[s] = id; }
Comments
Post a Comment