# 编辑sources.list文件,更换镜像源
sudo nano /etc/apt/sources.list
# 改成如下内容,使用kali官方的镜像源。保存并退出。
deb http://http.kali.org/kali kali-rolling main non-free contrib
# 更新包列表
sudo apt-get update
# 搜索可用的版本:可以使用apt-cache search libigraph命令来查找可用的igraph相关的软件包。然后,根据搜索结果,你可以选择要安装的软件包。
apt-cache search libigraph
# 有这些
libigraph-dev - library for creating and manipulating graphs - development files
libigraph-doc - library for creating and manipulating graphs - reference manual
libigraph-examples - transitional package
libigraph3 - library for creating and manipulating graphs
# 我打算下载安装其中的libigraph3和libigraph-dev。其他你也可以安装一下。
sudo apt-get install libigraph3 --fix-missing
sudo apt-get install libigraph-dev --fix-missing
# 检查是否安装成功
dpkg -l | grep igraph
# 查看g++版本
┌──(root?kali)-[~]
└─# g++ --version 1 ⚙
g++ (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
# 编译一个单文件ig.cpp
g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph
//ig.cpp
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<igraph.h>
using vect = std::vector<int>;
constexpr int MAXDIRECT=100;
constexpr int PRINTNODES=1;
std::set<int> avoid{};
igraph_t graph;
std::vector<vect> distance_vectors{};
int count;
int close_h(const vect &a, const vect &b ){
// check one direction of the closeness condition
for(auto i=a.begin(), j=b.begin(); i!=a.end(); i++,j++)
if ( (*i > *j) || (*j > 2 * *i))
return 0;
return 1;
}
int close(const vect &a, const vect &b ){
return close_h(a,b) || close_h(b,a);
}
vect distances(int n, int p, int t){
vect res{};
for (int i=0; i<n; ++i){
int count = 0;
for (int j=0; j<n; ++j)
count += 1 & ((p>>j)^(t>>j));
res.push_back(count);
t >>= 1;
}
return res;
}
void print_vect( vect &v ){
std::cout << "(";
auto i=v.begin();
std::cout << *i++;
for( ; i!=v.end(); ++i)
std::cout << "," << *i ;
std::cout << ")\n";
}
void use_node( int n ){
if(PRINTNODES)
print_vect( distance_vectors[n] );
++count;
avoid.insert( n );
igraph_vector_t neighs;
igraph_vector_init( &neighs, 0 );
igraph_neighbors( &graph , &neighs, n, IGRAPH_OUT );
for(int i=0; i<igraph_vector_size( &neighs ); ++i)
avoid.insert( VECTOR(neighs)[i] );
igraph_vector_destroy( &neighs );
}
void construct(int n){
std::set<vect> dist_vects;
for(int p=0; p>>n == 0; ++p)
for(int t=0; t>>(2*n-2) == 0; ++t) // sic! (because 0/1-symmetry)
dist_vects.insert(distances(n,p,t));
int nodes = dist_vects.size();
std::cout << "distinct distance vectors: " << nodes << "\n";
distance_vectors.clear();
distance_vectors.reserve(nodes);
std::copy(dist_vects.begin(), dist_vects.end(),
back_inserter(distance_vectors));
igraph_vector_t edges;
igraph_vector_init( &edges, 0 );
igraph_vector_t reversed;
igraph_vector_init_seq( &reversed, 0, nodes-1 );
for (int i=0; i<nodes-1; ++i){
vect &x = distance_vectors[i];
vect xr ( x.rbegin(), x.rend() );
for(int j=i+1; j<nodes; ++j){
vect &y = distance_vectors[j];
if( xr==y ){
VECTOR(reversed)[i] = j;
VECTOR(reversed)[j] = i;
}else if( close( x, y ) || close( xr, y) ){
igraph_vector_push_back(&edges,i);
igraph_vector_push_back(&edges,j);
}
}
}
std::cout << "edges: " << igraph_vector_size(&edges)/2 << "\n";
igraph_create( &graph, &edges, nodes, IGRAPH_UNDIRECTED);
igraph_vector_destroy( &edges );
igraph_cattribute_VAN_setv( &graph, "r", &reversed );
igraph_vector_destroy( &reversed );
igraph_vector_t names;
igraph_vector_init_seq( &names, 0, nodes-1 );
igraph_cattribute_VAN_setv( &graph, "n", &names );
igraph_vector_destroy( &names );
}
void max_independent( igraph_t *g ){
igraph_vector_ptr_t livs;
igraph_vector_ptr_init( &livs , 0 );
igraph_largest_independent_vertex_sets( g, &livs );
igraph_vector_t *nodes = (igraph_vector_t *) VECTOR(livs)[0];
igraph_vector_t names;
igraph_vector_init( &names, 0 );
igraph_cattribute_VANV( g, "n", igraph_vss_vector( nodes ), &names );
for(int i=0; i<igraph_vector_size(&names); ++i)
use_node( VECTOR(names)[i] );
igraph_vector_destroy( &names );
igraph_vector_ptr_destroy_all( &livs );
}
void independent_comp( igraph_t *g );
void independent( igraph_t *g ){
if(igraph_vcount( g ) < MAXDIRECT){
max_independent( g );
return;
}
igraph_vector_ptr_t components;
igraph_vector_ptr_init( &components, 0 );
igraph_decompose( g, &components, IGRAPH_WEAK, -1, 1);
for(int i=0; i<igraph_vector_ptr_size( &components ); ++i)
independent_comp( (igraph_t *) VECTOR(components)[i] );
igraph_decompose_destroy( &components );
}
void independent_comp( igraph_t *g ){
if (igraph_vcount( g ) < MAXDIRECT){
max_independent( g );
return;
}
igraph_vector_t degs;
igraph_vector_init( °s, 0 );
igraph_degree( g, °s, igraph_vss_all(), IGRAPH_OUT, 1 );
int maxpos = igraph_vector_which_max( °s );
igraph_vector_destroy( °s );
int name = igraph_cattribute_VAN( g, "n", maxpos );
int revname = igraph_cattribute_VAN( g, "r", maxpos );
int rev = -1;
if(name!=revname){
igraph_vector_ptr_t reversed_candidates_singleton;
igraph_vector_ptr_init( &reversed_candidates_singleton, 0 );
igraph_neighborhood( g, &reversed_candidates_singleton,
igraph_vss_1(maxpos), 2, IGRAPH_OUT );
igraph_vector_t * reversed_candidates =
(igraph_vector_t *) VECTOR(reversed_candidates_singleton)[0];
igraph_vector_t names;
igraph_vector_init( &names, 0 );
igraph_cattribute_VANV( g, "n", igraph_vss_vector( reversed_candidates ),
&names );
long int pos;
igraph_vector_search( &names, 0, revname, &pos );
rev = VECTOR(*reversed_candidates)[pos];
igraph_vector_destroy( &names );
igraph_vector_ptr_destroy( &reversed_candidates_singleton );
}
igraph_vs_t delnodes;
igraph_vs_vector_small( &delnodes, maxpos, rev, -1 );
igraph_delete_vertices( g, delnodes );
igraph_vs_destroy( &delnodes );
independent( g );
}
void handle(int n){
std::cout << "n=" << n << "\n";
avoid.clear();
count = 0;
construct( n );
independent( &graph );
// try all nodes again:
for(int node=0; node<igraph_vcount( &graph ); ++node)
if(avoid.count(node)==0)
use_node(node);
std::cout << "result: " << count << "\n\n";
igraph_destroy( &graph );
}
int main(){
igraph_i_set_attribute_table( &igraph_cattribute_table );
for(int i=1; i<6; ++i)
handle(i);
}