| 2012-11-02 16:10:38 |
Dimitris Diochnos |
description |
Might be related to this bug: https://bugs.launchpad.net/igraph/+bug/1073800
- igraph version: 0.6
Summary
We load an undirected graph with self-loops. There is a very dense subgraph where there are many cliques (I do not know the exact number; I obtained this from a much larger dataset). Somehow, the self-loops trigger a bug. In the attached example I check one by one for the existence of all the edges among 12 nodes and all of them are part of the input (I have verified this by hand as well). However, the built-in functions for the size of the largest clique or the maximal cliques return different numbers when we include self-loops or not in the input. This is true both in C and in Python; I believe it is also true in R.
Example: Input Description
- 18 nodes, 133 edges, 8 self loops
- Has a clique of size at least 12
- I do not know how many maximal cliques there are
Attachment
One source file in Python and two different input files with lists of edges. One of the files with the lists of edges includes self-loops, the other one does not.
Example: Output
$ ./cliques.py edgesSmall.txt
IGRAPH U--- 18 133 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 11
-------------------------------------------------------
There are 12 maximal cliques
$ ./cliques.py edgesSmallNoLoops.txt
IGRAPH U--- 18 125 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 12
-------------------------------------------------------
There are 10 maximal cliques
$ |
Might be related to this bug: https://bugs.launchpad.net/igraph/+bug/1073800
- igraph version: 0.6
Summary
We load an undirected graph with self-loops. There is a very dense subgraph where there are many cliques (I do not know the exact number; I obtained this from a much larger dataset). Somehow, the self-loops trigger a bug. In the attached example I check one by one for the existence of all the edges among 12 nodes and all of them are part of the input (I have verified this by hand as well). However, the built-in functions for the size of the largest clique or the maximal cliques return different numbers when we include self-loops or not in the input. This is true both in C and in Python; I believe it is also true in R.
Example: Input Description
- 18 nodes, 133 edges, 8 self loops
- Has a clique of size at least 12 among the nodes:
[0, 3, 5, 6, 7, 9, 10, 11, 14, 15, 16, 17]
- I do not know how many maximal cliques there are
Example: Attachment
One source file in Python and two different input files with lists of edges. One of the files with the lists of edges includes self-loops, the other one does not.
Example: Output
$ ./cliques.py edgesSmall.txt
IGRAPH U--- 18 133 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 11
-------------------------------------------------------
There are 12 maximal cliques
$ ./cliques.py edgesSmallNoLoops.txt
IGRAPH U--- 18 125 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 12
-------------------------------------------------------
There are 10 maximal cliques
$ |
|
| 2012-11-02 16:11:51 |
Dimitris Diochnos |
description |
Might be related to this bug: https://bugs.launchpad.net/igraph/+bug/1073800
- igraph version: 0.6
Summary
We load an undirected graph with self-loops. There is a very dense subgraph where there are many cliques (I do not know the exact number; I obtained this from a much larger dataset). Somehow, the self-loops trigger a bug. In the attached example I check one by one for the existence of all the edges among 12 nodes and all of them are part of the input (I have verified this by hand as well). However, the built-in functions for the size of the largest clique or the maximal cliques return different numbers when we include self-loops or not in the input. This is true both in C and in Python; I believe it is also true in R.
Example: Input Description
- 18 nodes, 133 edges, 8 self loops
- Has a clique of size at least 12 among the nodes:
[0, 3, 5, 6, 7, 9, 10, 11, 14, 15, 16, 17]
- I do not know how many maximal cliques there are
Example: Attachment
One source file in Python and two different input files with lists of edges. One of the files with the lists of edges includes self-loops, the other one does not.
Example: Output
$ ./cliques.py edgesSmall.txt
IGRAPH U--- 18 133 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 11
-------------------------------------------------------
There are 12 maximal cliques
$ ./cliques.py edgesSmallNoLoops.txt
IGRAPH U--- 18 125 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 12
-------------------------------------------------------
There are 10 maximal cliques
$ |
Might be related to this bug: https://bugs.launchpad.net/igraph/+bug/1073800
- igraph version: 0.6
Summary
We load an undirected graph with self-loops. There is a very dense subgraph where there are many cliques (I do not know the exact number; I obtained this from a much larger dataset). Somehow, the self-loops trigger a bug. In the attached example I check one by one for the existence of all the edges among 12 nodes and all of them are part of the input (I have verified this by hand as well). However, the built-in functions for the size of the largest clique or the maximal cliques return different numbers when we include self-loops or not in the input. This is true both in C and in Python; I believe it is also true in R.
Example: Input Description
- 18 nodes, 133 edges, 8 self loops.
- Has a clique of size at least 12 among the nodes:
[0, 3, 5, 6, 7, 9, 10, 11, 14, 15, 16, 17]
- I do not know how many maximal cliques there are.
Example: Attachment
One source file in Python and two different input files with lists of edges. One of the files with the lists of edges includes self-loops, the other one does not.
Example: Output
$ ./cliques.py edgesSmall.txt
IGRAPH U--- 18 133 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 11
-------------------------------------------------------
There are 12 maximal cliques
$ ./cliques.py edgesSmallNoLoops.txt
IGRAPH U--- 18 125 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 12
-------------------------------------------------------
There are 10 maximal cliques
$ |
|
