# Fatal Error, how to optimize Maximal Cliques

**URL:** <https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103>\
**Category:** Usage\
**Tags:** Python\
**Created:** [16 February 2022 10:05 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103 "2022-02-16T10:05:47Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [16 February 2022 10:05 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/1 "2022-02-16T10:05:47Z")

</div>

Hi There,

I am trying to find the maximum amount of cliques that have at least a distance of 75 from eachother.  
I have a TXT file with XY coordinates that are read in by the program as edges

```auto
#!/usr/bin/python
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np
import igraph as ig

dist = 75

File_data = np.loadtxt("TEST.txt", dtype=int)

points = File_data
Npoints = len(points)
G = ig.Graph()
G.add_vertices(Npoints)

Newlist=[]

for i in range(Npoints - 1):
    print (str((i/Npoints)*100) + "%")
    for j in range(i + 1, Npoints):
         if np.hypot(points[i, 0] - points[j, 0], points[i, 1] - points[j, 1]) >= dist:
            Newlist.append([i,j])

#append all values greater than dist to a new list

G.add_edges(Newlist)
# The graph G now contains an edge between nodes [i,j] if the distance between those two points is >= 75

H = G.maximal_cliques()[0]
# H is a list of all nodes in G that are in a maximum graph of G.

(fig, ax) = plt.subplots(1, 1, figsize=(12, 8))
ax.set_aspect('equal')

for i in range(Npoints):
    ax.scatter(points[i, 0], points[i, 1], c=('g' if i in H else 'r'),
               s=(25 if i in H else 16), marker='x')
    if i in H:
        c = plt.Circle((points[i, 0], points[i, 1]), dist, ec='k',
                       lw=1, fill=False)
        ax.add_patch(c)

plt.savefig('example.pdf', bbox_inches='tight')

```

But the program crashes as I add all the edges.  
The TXT file contains around 9500 xy coordinates, but the program crashes with a fatal error at G.add\_edges(Newlist)

Is there some way to make the performance better? Am I doing something wrong?

Thanks in advance!

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [16 February 2022 13:13 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/2 "2022-02-16T13:13:17Z")

</div>

Can you come up with a _minimal reproducible example_, ideally without relying on external files? See [How to create a Minimal, Reproducible Example - Help Center - Stack Overflow](https://stackoverflow.com/help/minimal-reproducible-example) and [http://sscce.org/](http://sscce.org/) for guidance.

What is your igraph version, where did you obtain it from, and what is your OS?

How large is `Newlist`?

What do you mean by “the program crashes”? Can you post the full output?

---

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [16 February 2022 13:56 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/3 "2022-02-16T13:56:26Z")

</div>

Hi szhorvat,

Thanks for the reply.

I’ve got the python-igraph 0.9.9 wheel version : igraph-0.9.9-cp310-cp310-win\_amd64.whl and installed it via pip install.  
OS is windows 10 pro, Python 3.10

The TEXT.txt files has 9458 lines, with XY coordinates. The size seems to be part of the problem, because with smaller files the program works fine. I’ve uploaded the TXT file and made the code more compressed.

[TEST.txt](https://igraph.discourse.group/uploads/short-url/tOLM2ubdtojOS7NjLdSIdZmbEW3.txt) (83.1 KB)

```auto
#!/usr/bin/python
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np
import igraph as ig

File_data = np.loadtxt("TEST.txt", dtype=int)

points = File_data
Npoints = len(points)
G = ig.Graph()
G.add_vertices(Npoints)

Newlist=[]

for i in range(Npoints - 1):
    for j in range(i + 1, Npoints):
         if np.hypot(points[i, 0] - points[j, 0], points[i, 1] - points[j, 1]) >= 75:
            Newlist.append((i,j))

G.add_edges(Newlist)

H = G.maximal_cliques()[0]

```

---

<div class="post-metadata">

**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\
**Post date:** [16 February 2022 14:22 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/4 "2022-02-16T14:22:57Z")

</div>

How big is `Newlist` after you have constructed it? I haven’t even finished constructing the `Newlist`, but it’s now already up to more than 16 million entries. Are you sure it’s only crashing upon calling `G.add_edges` and not before?

You are probably going to be better of using `scipy` or `sklearn` for the construction of the pairwise distances. You are now constructing the `Newlist` in pure python, which most likely takes up quite some memory.

Edit: Indeed constructing the list is much faster (and presumably a lot more memory efficient) by doing this

```python
from scipy.spatial import distance_matrix
D = distance_matrix(x=points, y=points)

edges = np.array(np.where(D > 75))

```

This results in 68,492,582 edges.

You can then easily construct the graph using `G = ig.Graph(edges.T)`.

---

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [16 February 2022 15:41 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/5 "2022-02-16T15:41:05Z")

</div>

Hi vtraag,

Your solution is way faster indeed. Thanks a lot for that. It seems that creating the list was indeed the problem.

Finding the maximal cliques ( `H = G.maximal_cliques()[0]` )still takes a long while; I haven’t seen it finish on my test.txt file

My current code is as follows:

```auto
#!/usr/bin/python
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np
import igraph as ig
from scipy.spatial import distance_matrix

File_data = np.loadtxt("TEST.txt", dtype=int)
points = File_data
D = distance_matrix(x=points, y=points)

Npoints = len(points)
edges = np.array(np.where(D > 75))

G = ig.Graph(edges.T)

H = G.maximal_cliques()[0]
    
(fig, ax) = plt.subplots(1, 1, figsize=(12, 8))
ax.set_aspect('equal')

for i in range(Npoints):
    ax.scatter(points[i, 0], points[i, 1], c=('g' if i in H else 'r'),
               s=(25 if i in H else 16), marker='x')
    if i in H:
        c = plt.Circle((points[i, 0], points[i, 1]), 75, ec='k',
                       lw=1, fill=False)
        ax.add_patch(c)

plt.savefig('example.pdf', bbox_inches='tight')

```

Is it impossible to find the maximal cliques with 68 million edges on 8GB ram? Or is there even more to tidy up and make the process faster?

Thanks

Edit:

A fatal error occurs unfortunately when trying to find the maximal cliques:  
`Fatal error at src/core/vector.c:378 : Assertion Failed: v!=0`

---

<div class="post-metadata">

**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\
**Post date:** [16 February 2022 16:18 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/6 "2022-02-16T16:18:00Z")

</div>

> [@Deva](#):
>
> Is it impossible to find the maximal cliques with 68 million edges on 8GB ram? Or is there even more to tidy up and make the process faster?

Difficult to say. The memory is probably not the problem directly, but I’m not sure. The overall runtime might be a problem in this case since this is quite a dense graph.

> [@Deva](#):
>
> A fatal error occurs unfortunately when trying to find the maximal cliques:  
> `Fatal error at src/core/vector.c:378 : Assertion Failed: v!=0`

This is something that should not happen. Just to make sure, can you double check you are on `python-igraph` version 0.9.9? Because `vector.c:378` seems to refer to this line of code:

> <https://github.com/igraph/igraph/blob/2fe8640888d19c146e4c8970478a3485a3e485e3/src/core/vector.c#L378>

which shouldn’t trigger this assertion error.

Possibly, it is an out-of-memory error, in which case a more informative error should be thrown, but it is not immediately clear.

---

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [17 February 2022 12:08 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/7 "2022-02-17T12:08:38Z")

</div>

Hi vtraag.

The version is 0.9.9:

```auto
>>> import igraph
>>> print(igraph. __version__ )
0.9.9

```

And the error still occurs unfortunately.

Do you think upgrading to a higher amount of RAM (like adding another 16GB of RAM) will prevent the memory failure (I do think it is a memory issue, because the error happens when the memory is peaking and my screen freezes when the error occurs)? I don’t know whether there is a rule of thumb for the amount of RAM necessary in relation to the amount of edges in a graph or something…

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [17 February 2022 13:55 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/8 "2022-02-17T13:55:06Z")

</div>

> [@Deva](#):
>
> A fatal error occurs unfortunately when trying to find the maximal cliques:  
> `Fatal error at src/core/vector.c:378 : Assertion Failed: v!=0`

Can you provide a complete minimal example (without relying on any datafiles) that reproduces this issue?

Can you double-check that the error message is really this, character for character? Did you change anything in it? It could be:

```auto
Fatal error at src/core/vector.pmt:378 : Assertion Failed: v != 0

```

Notice that this is different: `vector.pmt` and `v != 0` has spaces. Then it would come from here:

> <https://github.com/igraph/igraph/blob/0.9.6/src/core/vector.pmt#L378>

Or maybe MSVC handles filenames differently when `#include` is used …

* * *

This could be the result of a combination of an out-of-memory error and an error handling bug in igraph. It’s hard to tell. If it is, that bug might have already gotten fixed on the `develop` branch during the transition from `vector_ptr` to `vector_list`.

However, finding maximal cliques in such a huge graph is likely to be extremely slow … I’m not sure that it would be feasible even with more memory.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [17 February 2022 13:56 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/9 "2022-02-17T13:56:36Z")

</div>

> [@Deva](#):
>
> `H = G.maximal_cliques()[0]`

Do you need a single maximal clique only?

Note that `maximal_cliques()` find _maximal_ cliques, not _largest_ cliques. It does not seem to make sense to find only one.

@vtraag It would still be nice to be able to find only a single clique or only a few. This functionality already exists in the C library, in the form of the “callback” functions, but not in Python. It would be nice to expose this in Python as well.

---

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [17 February 2022 14:28 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/10 "2022-02-17T14:28:59Z")

</div>

Hi szhorvat,

Thanks for the reply.

I think I need to give some background information on the case that I am using this for.  
I want to maximise the amount of points with a certain diameter in a field.  
The higher the amount of green coordinates, the better the result is for me.

As an example, see below:

 ![Naamloos](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/55fefa1b908747b650a30472395066accea7aa11.jpeg)

That is why I thought using the maximal clique is the way to go.

Edit:  
using the 13 xy coordinates I gave in the example above in my code, the answer is indeed 5:  
 ![Figure 2022-02-17 154310](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/799f03f6a1c281e2041f2baf2602a8a9a8aca5fe.png)

---

<div class="post-metadata">

**Author:** ![Deva](https://avatars.discourse-cdn.com/v4/letter/d/7cd45c/32.png) [@Deva](https://igraph.discourse.group/u/Deva)\
**Post date:** [18 February 2022 11:00 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/11 "2022-02-18T11:00:07Z")

</div>

Is there maybe a way to use the igraph C function:

```auto
igraph_maximal_cliques_file

```

I think writing the cliques to a file will overcome the memory issue right?

---

<div class="post-metadata">

**Author:** ![tamas](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/tamas/32/1261_2.png) [@tamas](https://igraph.discourse.group/u/tamas)\
**Post date:** [25 February 2022 14:58 UTC](https://igraph.discourse.group/t/fatal-error-how-to-optimize-maximal-cliques/1103/12 "2022-02-25T14:58:57Z")

</div>

First of all, let me explain the difference between _maximal_ cliques and _largest_ cliques. _Maximal_ cliques are cliques that cannot be extended further, but they can still be much smaller than the largest possible cliques in the graph. _Largest_ cliques are cliques of size _k_ such that there exists no clique of size _k+1_ or larger in the graph. Every largest clique is maximal, but not all maximal cliques are largest (in fact, most of them aren’t).

To illustrate the difference, consider the union of a full graph of size 5 and 1 million additional isolated edges. This graph has 1 million plus one maximal cliques (the clique of size 5 is a maximal clique, and each additional isolated edge is a maximal clique of size 5), but it has only one largest clique (the clique of size 5).

I think that due to the triangle inequality, there will be lots and lots of maximal cliques in your particular graph in 2D, most of which would be irrelevant to the problem, but I’m not sure if I understand the original problem correctly. Let me try to rephrase the problem a bit. You are given _N_ points in two dimensional space and a radius _r_. You need to select as few points as possible such that for every point there is at least one selected point within radius _r_. Is that correct, is this what you need?