graph_similarity.hh 3.32 KB
 Tiago Peixoto committed Aug 24, 2011 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 ``````// Copyright (C) 2008 Tiago de Paula Peixoto // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 3 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see . #ifndef GRAPH_SIMILARITY_HH #define GRAPH_SIMILARITY_HH #if (GCC_VERSION >= 40400) # include #else # include #endif namespace graph_tool { using namespace std; using namespace boost; template size_t intersection_size(Keys& ks, Set& s1, Set& s2) { size_t s = 0; for (typeof(ks.begin()) k = ks.begin(); k != ks.end(); ++k) { int c1 = s1.count(*k); int c2 = s2.count(*k); s += max(c1, c2) - abs(c1 - c2); } return s; } struct get_similarity { template void operator()(const Graph1& g1, const Graph2* g2p, LabelMap l1, any l2a, size_t& s) const { LabelMap l2 = any_cast(l2a); const Graph2& g2 = *g2p; typedef typename property_traits::value_type label_t; tr1::unordered_map::vertex_descriptor> lmap1; tr1::unordered_map::vertex_descriptor> lmap2; typename graph_traits::vertex_iterator v1, v1_end; for (tie(v1, v1_end) = vertices(g1); v1 != v1_end; ++v1) lmap1[get(l1, *v1)] = *v1; typename graph_traits::vertex_iterator v2, v2_end; for (tie(v2, v2_end) = vertices(g2); v2 != v2_end; ++v2) lmap2[get(l2, *v2)] = *v2; s = 0; for (typeof(lmap1.begin()) li = lmap1.begin(); li != lmap1.end(); ++li) { typename graph_traits::vertex_descriptor v1 = li->second; typeof(lmap2.begin()) li2 = lmap2.find(li->first); if (li2 == lmap2.end()) continue; typename graph_traits::vertex_descriptor v2 = li2->second; tr1::unordered_set keys; tr1::unordered_multiset adj1; tr1::unordered_multiset adj2; typename graph_traits::adjacency_iterator a1, a1_end; for(tie(a1, a1_end) = adjacent_vertices(v1, g1); a1 != a1_end; ++a1) { adj1.insert(get(l1, *a1)); keys.insert(get(l1, *a1)); } typename graph_traits::adjacency_iterator a2, a2_end; for(tie(a2, a2_end) = adjacent_vertices(v2, g2); a2 != a2_end; ++a2) { adj2.insert(get(l2, *a2)); keys.insert(get(l2, *a2)); } s += intersection_size(keys, adj1, adj2); } } }; } // graph_tool namespace #endif // GRAPH_SIMILARITY_HH``````