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 edges are equal=============================
- bool edgesareequal(Graph const& g1,edge_iter const& e1,Graph const& g2,edge_iter const& e2){
- vertex_t frome1 = source(*e1, g1);
- vertex_t toe1 = target(*e1, g1);
- edge_t edg1 = edge(frome1, toe1, g1);
- int label1 =g1[edg1.first].label;
- vertex_t frome2 = source(*e2, g2);
- vertex_t toe2 = target(*e2, g2);
- edge_t edg2 = edge(frome2, toe2, g2);
- int label2 =g2[edg2.first].label;
- return((frome1==frome2)&&(toe1==toe2)&&(label1==label2));
- }
- //===============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);
- }
- //===========================================================
- bool edgeexistinavector(Graph const& g1,edge_iter const& e,Graph const& g2,std::vector<edge_iter> const& v){
- int cpt=0;
- for(auto x:v) {if(edgesareequal(g1,e,g2,x)){cpt++;}
- }
- return(cpt!=0);
- }
- //===========================================================
- std::vector<int*> edgesdiff(Graph const& g1,Graph const& g2){
- std::vector<edge_iter> v1;
- std::vector<edge_iter> v2;
- //std::vector<int [3]> result;
- std::vector<int*> result = std::vector<int*>();
- 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);}
- cout<<"***Insertion diff***"<<endl;
- for(auto x:v1){if(!edgeexistinavector(g1,x,g2,v2)){
- int t[3];
- vertex_t from = source(*x, g1);
- t[0]=g1[from].id;
- cout<<"g1[from].id="<<g1[from].id<<endl;
- vertex_t to = target(*x, g1);
- t[1]=g1[to].id;
- cout<<"g1[to].id="<<g1[to].id<<endl;
- edge_t edg = edge(from, to, g1);
- t[2]=g1[edg.first].label;
- cout<<"g1[edg.first].label="<<g1[edg.first].label<<endl;
- result.push_back(t);
- }
- }
- 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("test2.txt", length)));
- if (!dataG.empty())
- {
- auto const& g1 = dataG[0]; // firslt graph in G_list
- auto const& g2 = dataG[1]; // firslt graph in G_list
- /*
- auto ep = edges(g1).first; // first edge in gr
- std::vector<edge_iter> vec;
- edge_iter ei, ei_end;
- for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei){vec.push_back(ei);}
- cout<<edgeexistinavector(g1,ep,g2,vec)<<endl;
- */
- std::vector<int*> diff=edgesdiff(g1,g2);
- cout<<"\n\n***AFFICHAGE***"<<endl;
- for(auto d:diff)
- {
- for(int i=0;i<3;i++)
- {
- cout<<d[i]<<" ";
- }
- cout<<endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement