Stocker la structure des nœuds en C ++ à partir du format de fichier NetworkX

Un graphe est l'une des structures de données générales construites par les arêtes des points. Dans des exemples familiers, les réseaux d'amis et les pages Web peuvent également être représentés sous forme de graphiques.

Aujourd'hui, Networkx de Python est un outil très utile pour traiter des graphiques. Une bibliothèque très pratique, facile à écrire et facile à écrire. Si vous voulez traiter des graphiques, il semble bon de l'essayer d'abord.

• [Python] Résumé de l'utilisation de base de Network X 2.0
• Introduction à NetworkX en Python

Cependant, NetworkX a le problème qu'il est très lourd pour les grands graphiques.

Par conséquent, dans cet article, nous allons présenter comment utiliser C ++, qui est un processus à grande vitesse, pour obtenir des informations sur la construction de graphes en C ++ tel qu'il est au format de fichier lors de la construction de graphiques dans NetworkX.

En tant que condition préalable, il est supposé que vous savez écrire en C ++. Il existe une description de Networkx, mais il n'y a pas de problème même si vous ne connaissez pas NetworkX.

Nœud de format réseau X

Dans NetworkX, les points d'origine des sommets sont écrits avec un délimiteur d'espace pour chaque sommet de chaque ligne.

• Cette fois, j'étais particulier sur le format de fichier réseau X, mais si vous modifiez le délimiteur de la fonction de fractionnement décrite plus tard, vous pouvez également prendre en charge le format csv. Voir cet article pour une liste d'arêtes ici Facebook Utilisez le graphique de. (Le fichier correspondant est "facebook_combined.txt.gz" en bas de la page liée)

Le fichier est dans ce format.

facebook_combined.txt

0 1
0 2
0 3
0 4
0 5
0 6
︙

Le format est (id du noeud du point de départ) (id du noeud du point final).

Network X peut gérer ces informations de nœud en un instant, mais C ++ nécessite beaucoup de travail. En tant que procédure réelle

1. Lisez le fichier
2. Chaîne divisée
3. Affectation au vecteur

Je vais expliquer dans l'ordre.

Lire le fichier

	string path = argv[1];
	string num_nodes = stoi(argv[2]);
	ifstream ifs(path);

	vector<vector<int>> nodes;
	nodes = vector<vector<int>>(num_nodes);

Fonction de division de chaîne

vector<string> split(string& input, char delimiter){
    istringstream stream(input);
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

Il s'agit d'une fonction de fractionnement de chaîne courante en C ++. Il prend la chaîne cible et le caractère fractionné comme arguments, sépare la chaîne avec le caractère fractionné et renvoie un vecteur.

Lisez le fichier ligne par ligne, divisez-le, puis attribuez-le au vecteur

assignment

	string str;
	int from, to;

	while(getline(ifs, str)){
		//Fractionner par délimiteur d'espace
		vector<string> strvec = split(str, ' ');
		from = stoi(strvec.at(0));
        to = stoi(strvec.at(1));
		nodes[from].push_back(to);
	}

La fonction getline lit le fichier ligne par ligne et la fonction split est utilisée pour interpréter les lignes séparées par des espaces. Remplacez les informations de l'identifiant du nœud de point de départ et de l'identifiant du nœud de point final renvoyées comme résultat dans le vecteur. De cette manière, les informations structurelles du nœud pourraient être stockées dans le vecteur.

Vérification

	for(int i = 0; i < num_nodes; i++){
		cout << i << "->";
		for(int j = 0; j < nodes[i].size(); j++){
			cout << nodes[i][j];
			if(j != nodes[i].size()-1)cout << ",";
		}
		cout << endl;
	}

résultat

1->48,53,54,73,88,92,119,126,133,194,236,280,299,315,322,346
2->20,115,116,149,226,312,326,333,343
3->9,25,26,67,72,85,122,142,170,188,200,228,274,280,283,323
4->78,152,181,195,218,273,275,306,328
︙

De cette manière, vous pouvez vérifier les informations de bord du nœud. C'est difficile à faire jusqu'ici.