Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/vf2_sub_graph_iso.hpp>
- #include <boost/algorithm/string/split.hpp>
- #include <boost/algorithm/string/classification.hpp>
- #include <fstream>
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <ctime>
- #include <queue> // std::queue
- //for mmap:
- #include <sys/mman.h>
- #include <sys/stat.h>
- #include <fcntl.h>
- using namespace std;
- using namespace boost;
- //==========STRUCTURES==========
- // vertex
- struct VertexProperties {
- int id;
- int label;
- VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
- };
- // edge
- struct EdgeProperties {
- unsigned id;
- unsigned label;
- EdgeProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
- };
- // Graph
- struct GraphProperties {
- unsigned id;
- unsigned label;
- GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
- };
- // adjency list
- typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
- GraphProperties> Graph;
- // descriptors
- typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
- // iterators
- typedef graph_traits<Graph>::vertex_iterator vertex_iter;
- typedef graph_traits<Graph>::edge_iterator edge_iter;
- typedef std::pair<edge_iter, edge_iter> edge_pair;
- //=================callback used fro subgraph_iso=================================================================
- struct my_callback {
- template <typename CorrespondenceMap1To2, typename CorrespondenceMap2To1>
- bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const {
- return false;
- }
- };
- //==========handle_error==========
- void handle_error(const char *msg) {
- perror(msg);
- exit(255);
- }
- //============READ ALL THE FILE AND RETURN A STRING===================
- const char *readfromfile(const char *fname, size_t &length) {
- int fd = open(fname, O_RDONLY);
- if (fd == -1)
- handle_error("open");
- // obtain file size
- struct stat sb;
- if (fstat(fd, &sb) == -1)
- handle_error("fstat");
- length = sb.st_size;
- const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
- if (addr == MAP_FAILED)
- handle_error("mmap");
- // TODO close fd at some point in time, call munmap(...)
- return addr;
- }
- //==========SPLIT THE STRING BY NEWLINE (\n) ==========
- vector<string> splitstringtolines(string const& str) {
- vector<string> split_vector;
- split(split_vector, str, is_any_of("\n"));
- return split_vector;
- }
- //============Get a string starting from pos============
- string getpos(int const& pos, string const& yy) {
- size_t i = pos;
- string str;
- for (; yy[i] != ' ' && i < yy.length(); i++)
- str += yy[i];
- return str;
- }
- //==================read string vector and return graphs vector===================
- std::vector<Graph> creategraphs(std::vector<string> const& fichlines) {
- std::vector<Graph> dataG;
- int compide = 0; // compteur de id edge
- for (string yy : fichlines) {
- switch (yy[0]) {
- case 't': {
- string str2 = getpos(4, yy);
- unsigned gid = atoi(str2.c_str());
- dataG.emplace_back(GraphProperties(gid, gid));
- compide = 0;
- } break;
- case 'v': {
- assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
- // cout<<yy<<endl;
- int vId, vLabel;
- string vvv = getpos(2, yy);
- vId = atoi(vvv.c_str());
- string vvvv = getpos((int)vvv.length() + 3, yy);
- // cout<<vvvv<<endl;
- vLabel = atoi(vvvv.c_str());
- boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
- }
- break;
- case 'e': { // cout<<yy<<endl;
- assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
- int fromId, toId, eLabel;
- string eee = getpos(2, yy);
- // cout<<eee<<endl;
- fromId = atoi(eee.c_str());
- string eee2 = getpos((int)eee.length() + 3, yy);
- // cout<<eee2<<endl;
- toId = atoi(eee2.c_str());
- int c = (int)eee.length() + (int)eee2.length() + 4;
- // cout<<c<<endl;
- string eee3 = getpos(c, yy);
- // cout<<eee3<<endl;
- eLabel = atoi(eee3.c_str());
- boost::add_edge(fromId, toId, EdgeProperties(compide, eLabel), dataG.back());
- compide++;
- } break;
- }
- }
- return dataG;
- }
- //============test if the graph is empty========================================================
- bool emptygraph(Graph const& g) {
- return ((num_edges(g)==0)&&(num_vertices(g)==0));
- }
- //============test if the graph connectivity========================================================
- bool graphconnexe(Graph const& g) {
- return num_edges(g) >= num_vertices(g) - 1;
- }
- //====================print the graph information========================================================
- void printgraph(Graph const& gr) {
- typedef std::pair<edge_iter, edge_iter> edge_pair;
- std::cout <<"=================================="<<endl;
- std::cout <<" contains " << num_vertices(gr) << " vertices, and " << num_edges(gr) << " edges " << std::endl;
- if (graphconnexe(gr)) {
- // Vertex list
- if (num_vertices(gr) != 0) {
- std::cout << " Vertex list: " << std::endl;
- for (size_t i = 0; i < num_vertices(gr); ++i) // size_t vertice number in the graph
- {
- std::cout << " ID: " << gr[i].id << ", Label: " << gr[i].label << std::endl;
- }
- }
- // Edge list
- if (num_edges(gr) != 0) {
- std::cout << " Edge list: " << std::endl;
- edge_pair ep;
- for (ep = edges(gr); ep.first != ep.second; ++ep.first) // ep edge number
- {
- vertex_t from = source(*ep.first, gr);
- vertex_t to = target(*ep.first, gr);
- edge_t edg = edge(from, to, gr);
- std::cout << " e(" << gr[from].id << "," << gr[to].id << ") ID: " << gr[edg.first].id
- << " , Label: " << gr[edg.first].label << std::endl;
- }
- }
- std::cout<<endl;
- } else {
- cout << "Please check this graph connectivity." << endl;
- }
- }
- //=================test if the given vertice exist in the graph=========================
- bool verticeexist(Graph const& g, int const& vId, int const& vlabel) {
- int cpt = 0;
- for (size_t i = 0; i < num_vertices(g); ++i) // size_t vertice number in the graph
- {
- if ((g[i].id == vId) && (g[i].label == vlabel)) {
- cpt++;
- }
- }
- return cpt != 0;
- }
- //======================================================================
- bool idverticeexist(Graph const& g, int const& vId) {
- int cpt = 0;
- if (num_edges(g) != 0) {
- for (size_t i = 0; i < num_vertices(g); ++i) // size_t vertice number in the graph
- {
- if (g[i].id == vId) {
- cpt++;
- }
- }
- }
- return cpt != 0;
- }
- //=======get vertice label label============================
- int getvlabel(Graph const& M,int const& id){
- int cpt=-1;
- for (size_t i = 0; i < num_vertices(M); ++i){
- if (M[i].id == id) {
- cpt=M[i].label;
- }
- }
- return cpt;
- }
- //=============test if the given edge exist in the graph===========================
- bool edgeexist(Graph const& g, int const& fromid, int const& toid, unsigned const& elabel) {
- int bn = 0;
- if (graphconnexe(g)) {
- if (num_edges(g) != 0) {
- edge_pair ep;
- for (ep = edges(g); ep.first != ep.second; ++ep.first) // ep edge number
- {
- vertex_t from = source(*ep.first, g);
- vertex_t to = target(*ep.first, g);
- edge_t edg = edge(from, to, g);
- if ((g[from].id == fromid) && (g[to].id == toid) && (g[edg.first].label == elabel)) {
- bn++;
- }
- }
- }
- }
- return (bn != 0);
- }
- // =============test if thoses vertices are neighbours============================
- bool verticesareneighbours(Graph const& g, int const& a, int const& b) {
- int bn = 0;
- if (graphconnexe(g)) {
- if (num_edges(g) != 0) {
- edge_pair ep;
- for (ep = edges(g); ep.first != ep.second; ++ep.first) // ep edge number
- {
- vertex_t from = source(*ep.first, g);
- vertex_t to = target(*ep.first, g);
- if (((g[from].id == a) || (g[to].id == a)) && ((g[from].id == b) || (g[to].id == b))) {
- bn++;
- }
- }
- }
- }
- return (bn != 0);
- }
- //=============test if those edges are neighbours=============================
- template <typename Graph, typename E = typename boost::graph_traits<Graph>::edge_descriptor>
- bool edgesareneighbours(Graph const& g, E e1, E e2) {
- std::set<vertex_t> vertex_set {
- source(e1, g), target(e1, g),
- source(e2, g), target(e2, g),
- };
- return graphconnexe(g) && vertex_set.size() < 4;
- }
- //===============if the graph is empty add the edge with vertices===========================
- void emptygraphaddedge(Graph& testg,std::vector<Graph> dataG) {
- if (!dataG.empty()) {
- auto const& gr = dataG.front(); // firslt graph in G_list
- auto ep = edges(gr).first; // first edge in gr
- vertex_t from = source(*ep, gr);
- vertex_t to = target(*ep, gr);
- //int cpt=0;
- boost::add_vertex(VertexProperties(gr[from].id, gr[from].label),testg);
- //boost::add_vertex(VertexProperties(cpt, gr[from].label),testg);
- boost::add_vertex(VertexProperties(gr[to].id, gr[to].label),testg);
- //boost::add_vertex(VertexProperties(cpt+1, gr[to].label),testg);
- if(verticeexist(testg,gr[from].id,gr[from].label)&&verticeexist(testg,gr[to].id,gr[to].label))
- {
- int cpt=0;
- Graph::edge_descriptor copied_edge = boost::add_edge(cpt, cpt++, gr[*ep],testg).first;
- testg[source(copied_edge, gr)] = gr[from];
- testg[target(copied_edge,gr)] = gr[to];
- cout<<"e ("<<testg[source(copied_edge, gr)].id<<","<<testg[target(copied_edge, gr)].id<<") Added successfully."<<endl;
- }
- else{cout<<"vertices doesn't exist ! "<<endl;}
- }
- }
- //======================================================
- float frequency(Graph const& g1,std::vector<Graph> dataG)
- {
- int iso=0;
- if(emptygraph(g1)){return 1;}
- else{
- for (Graph g2: dataG)
- {
- if(vf2_subgraph_iso(g1,g2,my_callback())){iso++;}
- }
- return (iso/dataG.size());
- }
- }
- //==========test if the edge is connexe with the graph=============
- bool graphconnexewithedge(Graph g, int const& fromid, int const& toid) {
- return (idverticeexist(g,fromid)|| idverticeexist(g,toid));
- }
- //=========test if the aumentation is is a subgraph of the original graph=================================
- void augmentation(Graph &M, Graph &g, int const& fromid, int const& toid, unsigned const& elabel, unsigned const& edgeid) {
- if(!idverticeexist(g,fromid)){ int vlabel=getvlabel(M,fromid);
- boost::add_vertex(VertexProperties(fromid, vlabel), g);
- }
- if(!idverticeexist(g,toid)){ int vlabel=getvlabel(M,toid);
- boost::add_vertex(VertexProperties(toid, vlabel), g);
- }
- boost::add_edge(fromid, toid, EdgeProperties(edgeid, elabel), g);
- }
- //===========================================================
- std::vector<edge_iter> edgesdiff(Graph const& g1,Graph const& g2){
- std::vector<edge_iter> v1;
- std::vector<edge_iter> v2;
- std::vector<edge_iter> result;
- typedef graph_traits<Graph>::edge_iterator edge_iter;
- std::pair<edge_iter, edge_iter> ep;
- edge_iter ei, ei_end;
- for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei){v1.push_back(ei);}
- for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei){v2.push_back(ei);}
- /* d i f f e r e n c e*/
- return result;
- }
- //==============================M A I N P R O G R A M =======================================
- int main() {
- //clock_t start = std::clock();
- size_t length;
- std::vector<Graph> dataG =creategraphs(splitstringtolines(readfromfile("5.txt", length)));
- //cout<<"getvlabel(dataG[0],7)="<<getvlabel(dataG[0],7)<<endl;
- cout<<edgesdiff(dataG[0],dataG[1]).size()<<endl;
- /*
- cout<<"\n\n\n****testg****"<<endl;
- Graph testg;
- cout<<"frequency(testg,dataG)="<<frequency(testg,dataG)<<endl;
- emptygraphaddedge(testg,dataG);
- printgraph(testg);
- cout<<"frequency(dataG[0],dataG)="<<frequency(dataG[0],dataG)<<endl;
- cout << "FILE Contains " << dataG.size() << " graphs.\nTIME: " << (std::clock() - start) / (double)CLOCKS_PER_SEC<< "s" << endl; // fin du programme.
- */
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement