Nbob
BAN USERUsing BFS on the constructed graph and maintaining a level value internally in the object on the fly.
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>
using namespace std;
class Member {
public:
Member(string name, string email) {
m_name = name;
m_email = email;
m_level = 0;
}
void AddFriend(Member* m) {
m_friends.push_back(m);
}
int NumberOfFriends() {
m_friends.size();
}
void GetAllFriends(vector<Member*>& f) {
f = m_friends;
}
int GetLevel() {
return m_level;
}
string name() {
return m_name;
}
void PrintSocialGraph() {
queue<Member*> q;
q.push(this);
while (!q.empty()) {
Member* m = q.front();
q.pop();
cout << "Level:" << m->GetLevel() << "--->" << m->name() << '\n';
vector<Member*> f;
vector<Member*>::iterator it;
m->GetAllFriends(f);
int level = m->GetLevel();
for (it = f.begin(); it != f.end(); it++) {
q.push(*it);
(*it)->SetLevel(level+1);
}
}
}
void SetLevel(int level) {
m_level = level;
}
private:
vector<Member*> m_friends;
string m_name;
string m_email;
int m_level;
};
int main() {
Member m1(string("A"), string("A@gmail.com"));
Member m2(string("B1"), string("B1@gmail.com"));
Member m3(string("C1"), string("C1@gmail.com"));
Member m4(string("D1"), string("D1@gmail.com"));
Member m5(string("E2"), string("E2@gmail.com"));
Member m6(string("F2"), string("F2@gmail.com"));
Member m7(string("G2"), string("G2@gmail.com"));
Member m8(string("H2"), string("H2@gmail.com"));
Member m9(string("I2"), string("I2@gmail.com"));
Member m10(string("J2"), string("J2@gmail.com"));
Member m11(string("K2"), string("K2@gmail.com"));
Member m12(string("L2"), string("L2@gmail.com"));
Member m13(string("M2"), string("M2gmail.com"));
Member m14(string("N3"), string("N3@gmail.com"));
Member m15(string("O3"), string("O3@gmail.com"));
Member m16(string("P3"), string("P3@gmail.com"));
Member m17(string("Q3"), string("Q3@gmail.com"));
Member m18(string("R3"), string("R3@gmail.com"));
// Add friends of M1.
m1.AddFriend(&m2);
m1.AddFriend(&m3);
m1.AddFriend(&m4);
// Add m2 firnds
m2.AddFriend(&m5);
m2.AddFriend(&m6);
m2.AddFriend(&m7);
// Add m3 friends
m3.AddFriend(&m8);
m3.AddFriend(&m9);
m3.AddFriend(&m10);
// Add m4 friends
m4.AddFriend(&m11);
m4.AddFriend(&m12);
m4.AddFriend(&m13);
// Add m5 friends
m5.AddFriend(&m14);
m5.AddFriend(&m14);
m5.AddFriend(&m16);
// Add m6 friends
m6.AddFriend(&m17);
m6.AddFriend(&m18);
m1.PrintSocialGraph();
return 1;
}
A basic c++ implementation using containers
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<fstream>
#include<map>
using namespace std;
// Use quick sort to sort the strings.
void quicksort(string& str, int low, int high) {
char pivot = str[(low+high)/2];
int i = low;
int j = high;
while (i <= j) {
while (str[j] > pivot)
j--;
while(str[i] < pivot)
i++;
if(i <= j) {
char temp;
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}
if (j > low)
quicksort(str, low, j);
if (i < high)
quicksort(str,i,high);
}
// Longest match algotithm.
void longestmatch(map<string,string>& mymap) {
string matcher("aeffgirq");
vector<string> final_list;
map<string,string>::iterator it;
for (it = mymap.begin(); it != mymap.end(); ++it) {
string str = it->second;
int i = 0;
int j = 0;
bool is_match = false;
while(true) {
if((i == matcher.length()) && (j < str.length()))
break;
if (matcher[i] == str[j]) {
i++;
j++;
} else {
i++;
}
if (j == str.length()) {
is_match = true;
break;
}
}
if (is_match) {
string first = it->first;
final_list.push_back(first);
}
}
// Iterator over the final list of all the words that
// match our criterion and then print the one with
// highest length
vector<string>::iterator it1;
int maxlength = 0;
string final_string;
for(it1 = final_list.begin();it1 != final_list.end();++it1) {
string tmp = *it1;
int length = tmp.length();
if (length > maxlength) {
final_string.replace(final_string.begin(), final_string.end(), tmp);
}
}
cout << "The longest string:" << final_string << '\n';
}
int main() {
vector<string> list;
ifstream in_stream;
string line;
in_stream.open("file.txt");
map<string,string> my_map;
// Read the words into a vector
while(in_stream.is_open())
{
while (in_stream.good()) {
getline(in_stream, line);
list.push_back(line);
}
in_stream.close();
}
// Sort the words in the vector and put the sorted
// words in a map with their keys as original words.
vector<string>::iterator it;
for (it=list.begin();it!=list.end(); ++it) {
string str = *it;
string sorted_str = *it;
int length = str.length();
quicksort(sorted_str,0,length-1);
my_map[str] = sorted_str;
}
// Clear this memory. No use now.
list.clear();
// Get the longest match.
longestmatch(my_map);
// clear the map
my_map.clear();
}
The above code in main method is effectively as good as nothing since main function is not re entrant . It is called only once per process.
- Nbob June 01, 2013