graph1.txt: 6 8 Write a program to compute the Jaccard similarity between two ve
ID: 3793523 • Letter: G
Question
graph1.txt:
6 8
Write a program to compute the Jaccard similarity between two vertices in an undirected, unweighted graph. Recall that Jaccard(u, v) JS n T1/ SUT, where S is the set of neighbors of u and Tis the set of neighbors of v. Note that v may or may not be a member of S and u may or may not be a member of T.) Your program should take three command line arguments: the name of a graph file followed by the indices of two vertices. It should outpu the Jaccard similarity between the two vertices. The output should look very similar to the following two examples /i a card graph1. txt 0 1 0.25 jac card graph 1. txt 1 2 0.333 33 33 3333Explanation / Answer
#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <algorithm>
#include <set>
void read_and_process_input(const char* fname, int u, int v){
std::ifstream ifs(fname);
int N;
int M;
ifs >> N >> M;
std::set<int> uV;
std::set<int> vV;
for(int i = 0; i < M; ++i){
int P, Q;
ifs >> P >> Q;
if(P==u){
uV.insert(Q);
}
if(Q==u){
uV.insert(P);
}
if(P==v){
vV.insert(Q);
}
if(Q==v){
vV.insert(P);
}
}
std::set<int> U;
U.insert(uV.begin(), uV.end());
U.insert(vV.begin(), vV.end());
std::set<int> intersect;
std::set_intersection(uV.begin(),uV.end(),vV.begin(),vV.end(),
std::inserter(intersect,intersect.begin()));
std::cout << 1.0*intersect.size()/U.size() << std::endl;
}
int main(int argc, char* argv[]){
if(argc!=4){
std::cerr <<"./jaccard <filename> <vertex id> <vertex id>" << std::endl;
return 0;
}
read_and_process_input(argv[1], std::stoi(argv[2]), std::stoi(argv[3]));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.