Help! Error Again Assertion `no < 100’ failed in igraph 0.8.3

Hi, I asked a similar problem days ago and the error is solved by updating the igraph to 0.8.3.

Yesterday I change my code and this error appear again, I try to minimize the problem and reproduce it with a simple iterative graph building code and I attach it here for your testing

Environment: Visual Studio 2019 16.7.3, std=c++14, igraph 0.8.3

Problem: I failed at gCount=44, or the 45 rounds, exactly same error with this: Need help with igraph error:[ igraph_error.c:186: Assertion `no < 100’ failed.’]. but with 0.8.3:

Assertion failed: no < 100, file D:\igraph-0.8.3-msvc\src\igraph_error.c, line 186

sample code: run igraph_debug_test(). Sorry I extract the code from a long pipeline in a hurry, you may need OpenCV for it, or you can change my code to replace that cv::DMatch which is just a matching id storage object.

PS: If anyone can help adjusting the format, I try every option on editor none of them format the code properly.

bool extend1to2(igraph_t& sourceGraph, igraph_t& extendGraph, std::vector <cv::DMatch>& matches) {

	if (matches.size() == 0) {
		std::cerr << "graph.extend1to2: matches size is zero, invalid extention! return source graph instead!\n";
		return true;
	}

	int n_source_vertices = GAN(&sourceGraph, "n_vertices");
	int n_exd_vertices = GAN(&extendGraph, "n_vertices");
	std::unique_ptr<igraph_vector_t, void(*)(igraph_vector_t*)> 
		source_label(new igraph_vector_t(), &igraph_vector_destroy),
		exd_label(new igraph_vector_t(), &igraph_vector_destroy),
		source_edge_weight(new igraph_vector_t(), &igraph_vector_destroy),
		exd_edge_weight(new igraph_vector_t(), &igraph_vector_destroy);

	igraph_vector_init(source_label.get(),0);
	igraph_vector_init(exd_label.get(), 0);
	igraph_vector_init(source_edge_weight.get(), 0);
	igraph_vector_init(exd_edge_weight.get(), 0);
	VANV(&sourceGraph, "label",source_label.get());
	VANV(&extendGraph, "label", exd_label.get());
	EANV(&sourceGraph, "weight", source_edge_weight.get());
	EANV(&extendGraph, "weight", exd_edge_weight.get());

	igraph_t union_graph;
	igraph_disjoint_union(&union_graph, &sourceGraph, &extendGraph);
	igraph_vector_append(source_label.get(), exd_label.get());
	igraph_vector_append(source_edge_weight.get(), exd_edge_weight.get());
	SETVANV(&union_graph, "label", source_label.get());
	SETEANV(&union_graph, "weight", source_edge_weight.get());
	igraph_vector_t	contract_vertices_list;
	std::vector<igraph_real_t> vertices_ids(igraph_vcount(&union_graph),-1);
	for (int k = 0; k < matches.size(); k++) {
		vertices_ids[matches[k].queryIdx + n_source_vertices] = matches[k].trainIdx;
	}
	int count = 0;
	for (int i = 0; i < vertices_ids.size(); i++) {
		if (vertices_ids[i] == -1.0) {
			vertices_ids[i] = count;
			count++;
		}
	}

	igraph_vector_view(&contract_vertices_list, vertices_ids.data(), vertices_ids.size());
	igraph_attribute_combination_t comb;
	igraph_attribute_combination(&comb,
		"weight", IGRAPH_ATTRIBUTE_COMBINE_SUM,
		"", IGRAPH_ATTRIBUTE_COMBINE_FIRST,
		IGRAPH_NO_MORE_ATTRIBUTES);
	igraph_contract_vertices(&union_graph, &contract_vertices_list, &comb);
	igraph_simplify(&union_graph, 1, 1, &comb);
	SETGAN(&union_graph, "n_vertices", igraph_vcount(&union_graph));
	SETGAS(&union_graph, "name", GAS(&sourceGraph, "name"));
	sourceGraph = union_graph; 
}

bool buildFull(std::vector<DMatch>& matches, std::vector<KeyPoint>& kpts, igraph_t& mygraph) {

	igraph_init::attri_init();
	igraph_integer_t n_vertices = matches.size();
	igraph_bool_t loops = false;
	if (matches.size() == 0) {
		igraph_empty(&mygraph, 0, IGRAPH_UNDIRECTED);
		SETGAN(&mygraph, "n_vertices", 0);
		SETGAS(&mygraph, "name", "UNDEFINED");
		std::cout << "graph.build: warning: zero matches empty graph returned" << std::endl;
		return true;
	}

	int status = igraph_full(&mygraph, n_vertices, false, loops);
	SETGAS(&mygraph, "name", "fullgraph"); 
	SETGAN(&mygraph, "n_vertices", n_vertices); 

	if (status == IGRAPH_EINVAL) {
		std::cout << "build full graph: Invalid number of graph vertices" << std::endl;
		return false;
	}

	std::vector<igraph_real_t> labs(n_vertices);
	igraph_real_t* labels = labs.data();
	for (size_t i = 0; i < n_vertices; i++) {
		labs[i] = matches[i].trainIdx;
	}

	igraph_vector_t lab_vec;
	igraph_vector_view(&lab_vec, labels, n_vertices);
	
	SETVANV(&mygraph, "label", &lab_vec);

	igraph_simplify(&mygraph, 1, 1, 0);
	int n_edges = igraph_ecount(&mygraph);
	std::vector<igraph_real_t> w(n_edges);
	igraph_real_t* weights = w.data();
	for (size_t i = 0; i < n_edges; i++) {
		w[i] = 1.0;
	}
	igraph_vector_t weight_vec;
	igraph_vector_view(&weight_vec, weights, n_edges);
	SETEANV(&mygraph, "weight", &weight_vec);
	igraph_attribute_combination_destroy(&comb);*/
	return true;
}

void igraph_debug_test() {

	int gCount = 0;
	while (gCount != 50) {
		for(int i=0;i<1;i++){
			int total_num_feats_i = 100;
			std::vector<cv::DMatch> dbmatches;
			for (int i = 0; i < 100; i++) {
				dbmatches.push_back(cv::DMatch(i, i, -1, 0));
			}
			igraph_t base_graph;
			std::vector<cv::KeyPoint> pts;
			buildFull(dbmatches, pts, base_graph);
			if (GAN(&base_graph, "n_vertices") == 0) {
				std::cerr << "nbhdGraph.Next: error: base graph is empty!\n";
				break;
			}
			//extend the graph
			for(int j=0;j<2;j++){
				std::vector<cv::DMatch> exdmatches;
				for (int k = 0; k < 100; k++) {
					exdmatches.push_back(cv::DMatch(k, k + 80, -1, 0));
				}
				igraph_t exd_graph;
				std::vector<cv::KeyPoint> pts;
				buildFull(exdmatches, pts, exd_graph);
				if (GAN(&exd_graph, "n_vertices") == 0) {
					std::cerr << "nbhdGraph.Next: error: extend graph is empty!\n";
					break;
				}
				std::vector < cv::DMatch> newMatches;
				newMatches.reserve(20);
				for (int k = 0; k < 20; k++) {
					newMatches.push_back(cv::DMatch(k, k + 80, -1, 0));
				}
				if (!extend1to2(base_graph, exd_graph, newMatches)) {
					std::cerr << "nbhdGraph: error: graph extention failed! with img id " << i << "\n";
					break;
				}
				igraph_destroy(&exd_graph);
			}
			igraph_destroy(&base_graph);
		}
		std::cout << "\ngcount: " << gCount;
		gCount++;
	}
	return;
}

Hello, is there any update? can you confirm that this is bug from igraph? If the bug fixing is time consuming, I may have to consider an alternative solution for my project.

It is possible that this does constitute a bug. If you could report a Minimal Working Example that reproduces the problem, that would greatly help in identifying a possible bug. At the moment your code is a bit long, and I haven’t yet managed to get it to run after installing OpenCV.

Edit: it now seems I got OpenCV running (you are using OpenCV things without the namespace, and the poper includes are missing, I think opencv2/core.hpp is sufficient). However, the code you posted is missing igraph_init::attri_init();.

sorry, it is a initalization:
igraph_i_set_attribute_table(&igraph_cattribute_table).
I will simplify my code now.

Using that (and removing the line with igraph_attribute_combination_destroy(&comb);*/) I get the output:

nbhdGraph: error: graph extention failed! with img id 0

gcount: 0nbhdGraph: error: graph extention failed! with img id 0

gcount: 1nbhdGraph: error: graph extention failed! with img id 0

gcount: 2nbhdGraph: error: graph extention failed! with img id 0

gcount: 3nbhdGraph: error: graph extention failed! with img id 0

I doubt that this was the intention?

This will be very helpful to track down the (possible) bug.

Sorry, I found that my first test code is definitely not readable. I created that code inside my project and that definitely a mistake.
I write the new code in a new project and it should only depends on igraph now.

I simplify it as far as I can think:

#include <iostream>
#define IGRAPH_STATIC 1
#include "igraph.h"
#include <vector>
struct Dmatch{
	Dmatch(int query_Idx, int train_Idx) { queryIdx = query_Idx, trainIdx = train_Idx; }
	int trainIdx;
	int queryIdx;
};
bool extend1to2(igraph_t& sourceGraph, igraph_t& extendGraph, std::vector <Dmatch>& matches) {

	int n_source_vertices = GAN(&sourceGraph, "n_vertices");
	int n_exd_vertices = GAN(&extendGraph, "n_vertices");
	std::unique_ptr<igraph_vector_t, void(*)(igraph_vector_t*)>
		source_label(new igraph_vector_t(), &igraph_vector_destroy),
		exd_label(new igraph_vector_t(), &igraph_vector_destroy),
		source_edge_weight(new igraph_vector_t(), &igraph_vector_destroy),
		exd_edge_weight(new igraph_vector_t(), &igraph_vector_destroy);

	igraph_vector_init(source_label.get(), 0);
	igraph_vector_init(exd_label.get(), 0);
	igraph_vector_init(source_edge_weight.get(), 0);
	igraph_vector_init(exd_edge_weight.get(), 0);
	VANV(&sourceGraph, "label", source_label.get());
	VANV(&extendGraph, "label", exd_label.get());
	EANV(&sourceGraph, "weight", source_edge_weight.get());
	EANV(&extendGraph, "weight", exd_edge_weight.get());

	igraph_t union_graph;
	igraph_disjoint_union(&union_graph, &sourceGraph, &extendGraph);
	igraph_vector_append(source_label.get(), exd_label.get());
	igraph_vector_append(source_edge_weight.get(), exd_edge_weight.get());
	SETVANV(&union_graph, "label", source_label.get());
	SETEANV(&union_graph, "weight", source_edge_weight.get());
	igraph_vector_t	contract_vertices_list;
	std::vector<igraph_real_t> vertices_ids(igraph_vcount(&union_graph), -1);
	for (int k = 0; k < matches.size(); k++) {
		vertices_ids[matches[k].queryIdx + n_source_vertices] = matches[k].trainIdx;
	}
	int count = 0;
	for (int i = 0; i < vertices_ids.size(); i++) {
		if (vertices_ids[i] == -1.0) {
			vertices_ids[i] = count;
			count++;
		}
	}

	igraph_vector_view(&contract_vertices_list, vertices_ids.data(), vertices_ids.size());
	igraph_attribute_combination_t comb;
	igraph_attribute_combination(&comb,
		"weight", IGRAPH_ATTRIBUTE_COMBINE_SUM,
		"", IGRAPH_ATTRIBUTE_COMBINE_FIRST,
		IGRAPH_NO_MORE_ATTRIBUTES);
	igraph_contract_vertices(&union_graph, &contract_vertices_list, &comb);
	igraph_simplify(&union_graph, 1, 1, &comb);
	SETGAN(&union_graph, "n_vertices", igraph_vcount(&union_graph));
	SETGAS(&union_graph, "name", GAS(&sourceGraph, "name"));
	sourceGraph = union_graph;
}

bool buildFull(std::vector<Dmatch>& matches, igraph_t& mygraph) {
	igraph_i_set_attribute_table(&igraph_cattribute_table);
	igraph_integer_t n_vertices = matches.size();
	igraph_bool_t loops = false;

	int status = igraph_full(&mygraph, n_vertices, false, loops);
	SETGAS(&mygraph, "name", "fullgraph");
	SETGAN(&mygraph, "n_vertices", n_vertices);

	std::vector<igraph_real_t> labs(n_vertices);
	igraph_real_t* labels = labs.data();
	for (size_t i = 0; i < n_vertices; i++) {
		labs[i] = matches[i].trainIdx;
	}

	igraph_vector_t lab_vec;
	igraph_vector_view(&lab_vec, labels, n_vertices);

	SETVANV(&mygraph, "label", &lab_vec);

	igraph_simplify(&mygraph, 1, 1, 0);
	int n_edges = igraph_ecount(&mygraph);
	std::vector<igraph_real_t> w(n_edges);
	igraph_real_t* weights = w.data();
	for (size_t i = 0; i < n_edges; i++) {
		w[i] = 1.0;
	}
	igraph_vector_t weight_vec;
	igraph_vector_view(&weight_vec, weights, n_edges);
	SETEANV(&mygraph, "weight", &weight_vec);
	return true;
}

int main() {
	int gCount = 0;
	while (gCount != 50) {
		for (int i = 0; i < 1; i++) {
			int total_num_feats_i = 100;
			std::vector<Dmatch> dbmatches;
			for (int i = 0; i < 100; i++) {
				dbmatches.push_back(Dmatch(i, i));
			}
			igraph_t base_graph;
			buildFull(dbmatches,base_graph);
			if (GAN(&base_graph, "n_vertices") == 0) {
				break;
			}
			//extend the graph
			for (int j = 0; j < 2; j++) {
				std::vector<Dmatch> exdmatches;
				for (int k = 0; k < 100; k++) {
					exdmatches.push_back(Dmatch(k, k + 80));
				}
				igraph_t exd_graph;
				buildFull(exdmatches, exd_graph);
				std::vector <Dmatch> newMatches;
				newMatches.reserve(20);
				for (int k = 0; k < 20; k++) {
					newMatches.push_back(Dmatch(k, k + 80));
				}
				if (!extend1to2(base_graph, exd_graph, newMatches)) {
					break;
				}
				igraph_destroy(&exd_graph);
			}
			igraph_destroy(&base_graph);
		}
		std::cout << "\ngcount: " << gCount;
		gCount++;
	}
	return 0;
}

my result is also listed below:

Edit:
I can explain what I’m doing here: I create a source fully-connected undirected graph with 100 vertices, and vertices with “label” 1-100, each edge with weight 1. Then I create a same type exd_graph with 100 vertices, with “label” 80-179 and edge weight 1. Then the matching should be a 20 vector with vertices id [80-100].

Then I union the two graphs, contract the vertices with corresponding ids, and add edge weight together, which is defined in the igraph combination object. I repeat twice and extend two graphs to the source one. At final, I delete all graphs.

I repeat this process 50 times, it crashed at 44 round.

Thank you for reporting this, it indeed revealed a bug.

I opened an issue on GitHub here and pushed a fix in PR #1485. If you really need the corrected code immediately, and you cannot wait before it is merged, you can simply fetch the code from my fix branch.

@vtraag
Edit: Test with your branck ( igraph-fix-1484)
same error with attribute query function VAN and report attributes lost.

Hi, thanks for the fix. I think this is for the latest branch right? I check the fix and it is three line changes in cattributes.c:

//IGRAPH_FINALLY_CLEAN(2);
igraph_i_cattribute_permute_free(new_val);
IGRAPH_FINALLY_CLEAN(3);

so I change the source code and recomplie, but another error is occurred:

Error at D:\thesis\igraph-0.8.3-msvc\src\cattributes.c:2381 :Unknown attribute, Invalid value

error is at the line:

I track the bug, the code failed at the second graph extention (j=1), which I guess igraph_contract_vertices in the j=0 loop may fail to keep the vertices “label” attributes after contraction.

of course I’m in the release version 0.8.3, I will test you version.

This is rather unexpected. I tested the exact code you provided, and this works without any problems with the fix. I have tested up to gCount == 500, and didn’t encounter any problem. Perhaps you want to double check whether everything is correctly compiled.

By the way, the PR is merged in the master branch of the igraph repo, so you can also simply pull from there. Just to make sure: when building from GitHub the instructions are slightly different: see here for instructions.

It might be that this is a specific issue for Windows (I am working on Ubuntu myself), but I doubt whether that is the case.

Yes, I followed the instruction and build the msvc project from the code, all works.

Besides, I have tried reverse the code ( comment the new lines and use the IGRAPH_FINALLY_CLEAN(2)) , the same IGRAPH_FINALLY_CALL error can be reproduced and crashed at 44th round, which means the VAN works normally and these two lines may accidently release the attributes? This might still be a igraph problem.

Hmm, you might actually be right. It seems that the fix actually removed the new values. I am not sure why I didn’t receive an error on my end, but this might just be luck.

Could you please check my fix branch again?

Change the source code according to your fix, test on the example code and on my project, works perfect, thanks. Great to know it is finally fixed, I don’t need to rewrite my whole project now :smile:

1 Like