graph-tool issueshttps://git.skewed.de/count0/graph-tool/-/issues2024-03-14T11:15:10Zhttps://git.skewed.de/count0/graph-tool/-/issues/774get_all_neighbors (and others) cause segmentation fault instead of error when...2024-03-14T11:15:10ZLuca Pion-Tonachiniget_all_neighbors (and others) cause segmentation fault instead of error when called with nonexistant vertexWhen calling `Graph.get_all_neighbors` on a graph instance and passing an index to a non-existent vertex, it causes a segmentation fault where raising a python exception would be much more appropriate.
Example leading to segmentation fa...When calling `Graph.get_all_neighbors` on a graph instance and passing an index to a non-existent vertex, it causes a segmentation fault where raising a python exception would be much more appropriate.
Example leading to segmentation fault:
```python
import graph_tool as gt
g = gt.Graph() # nothing changes if directed=True
g.get_all_edges(0)
```
produces
```
Segmentation fault (core dumped)
```
Curiously, if `Graph.vertex` called on the instance first, then it no long prints as it it wer segfaulting but perhaps still is.
Please replace this section with a brief summary of your issue.
Example leading to possible silent segmentation fault:
```python
import graph_tool as gt
g = gt.Graph()
print("get first vertex")
g.vertex(0)
print("get first vertex edges")
g.get_all_edges(0)
```
produces
```
get first vertex
Traceback (most recent call last):
File "vargas_island/tests/graph_tool_error.py", line 5, in <module>
g.vertex(0)
File "/usr/lib/python3/dist-packages/graph_tool/__init__.py", line 2000, in vertex
raise ValueError("Invalid vertex index: %d" % int(i))
ValueError: Invalid vertex index: 0
```
Notice the lack of output from `print("get first vertex edges")`, so perhaps `Graph.vertex` raises a python error and then still causing a fault. I also tried replacing `get_all_neighbors` with `get_all_edges` to the same result, so it is likely a more widespread issue.
## Environment
I'm using graph-tool installed through `apt`
```
python3-graph-tool/focal,now 2.59 amd64 [installed]
```
in a docker containers running Ubuntu 20.04:
```
Distributor ID: Ubuntu
Description: Ubuntu 20.04.6 LTS
Release: 20.04
Codename: focal
```
with python 3.8
```
Python 3.8.10
```https://git.skewed.de/count0/graph-tool/-/issues/773Typo in demo documentation for model selection2024-02-01T09:11:00ZFelipe VacaTypo in demo documentation for model selectionThere are two typos in the "Model Selection" demo section that appears in the following link:
https://graph-tool.skewed.de/static/doc/demos/inference/inference.html#model-selection
1) It says:
[...] the particular non-degree-corrected f...There are two typos in the "Model Selection" demo section that appears in the following link:
https://graph-tool.skewed.de/static/doc/demos/inference/inference.html#model-selection
1) It says:
[...] the particular non-degree-corrected fit is around e^{37.9} times more likely than the non-degree corrected one.
It should say:
[...] than the degree corrected one.
2) It says:
Hence, with a posterior odds ratio of \lambda \approx e^{-47} in favor of the non-degree-corrected model [...].
It should say:
[...] in favor of the degree-corrected model [...].https://git.skewed.de/count0/graph-tool/-/issues/772Potential bug in the clustering.motif_significance function2023-11-01T11:49:08ZOgnyan SimeonovPotential bug in the clustering.motif_significance function# Bug report: Potential bug in the clustering.motif_significance function
## Please follow the general troubleshooting steps first:
- [X] Are you running the latest `graph-tool` version?
- [X] Do you observe the problem with the curren...# Bug report: Potential bug in the clustering.motif_significance function
## Please follow the general troubleshooting steps first:
- [X] Are you running the latest `graph-tool` version?
- [X] Do you observe the problem with the current git version?
- [ ] Are you using Macports or Homebrew? If yes, please submit an issue there instead: https://github.com/Homebrew/brew/issues and https://trac.macports.org/newticket
- [ ] Did you compile `graph-tool` manually?
- [ ] If you answered yes above, did you use the exact same compiler to build `graph-tool`, `boost-python` and `Python`?
Report:
I am analyzing the motifs in a network with self-loops. I ran the clustering.motif function which identifies the motifs and the respective counts for each motif. Then, I looked at the clustering.motif_significance function and the full output also includes motifs and counts (along with zscores, sample counts and sample sd).
However, the lengths of the motif arrays produced by the functions are different, even though in the documentation it is written that the two functions produce the same motif output. Additionally, the counts array generated by clustering.motif_significance contains 0 values at the end, but I think those values correspond to motifs in a different part in the motif array (and should probably not be there if the motif occurs 0 times).
There, are also nan values in the zscores array, potentially caused by the self loops.
In the example below, I added a short for loop that checks the isomorphism of the motifs generated by the two functions and at some points the indices of the isomorphic pairs do not coincide.
Your exact graph-tool version: 2.58
Your operating system: MacOS
Python Version: 3.11.6 | packaged by conda-forge
A minimal working example that shows the problem:
```python
from graph_tool import all as gt
gt.seed_rng(42)
g = gt.random_graph(100, lambda: (5,5), self_loops=True)
motifs_1, counts_1 = gt.motifs(g, 3)
motifs_2, zscores, counts_2, s_counts, s_dev = gt.motif_significance(g, 3, self_loops = True, full_output = True)
#Print motif lengths and counts
print(f"Motif_1 array length: {len(motifs_1)}")
print(f"Motif_2 array length: {len(motifs_2)}")
print(counts_1)
print(counts_2)
#Print Z-Scores
print(f"Z-Scores:{zscores}")
#Graph with index 18 is different in the two motif arrays but the count is the same
gt.graph_draw(motifs_1[18], vertex_font_size=12, edge_pen_width=1.5,
output_size=(1000, 1000), vertex_color="black",
edge_font_size=10, edge_text_color="red")
print(counts_1[18])
gt.graph_draw(motifs_2[18], vertex_font_size=12, edge_pen_width=1.5,
output_size=(1000, 1000), vertex_color="black",
edge_font_size=10, edge_text_color="red")
print(counts_2[18])
# Initialize a list to store isomorphic pairs
isomorphic_pairs = []
# Iterate through the graphs in motifs_array1
for index, graph in enumerate(motifs_1):
# Iterate through the graphs in motifs_1
for s_index, s_graph in enumerate(motifs_2):
# Check if the current graph in motifs_array2 is isomorphic to the current graph in motifs_1
if gt.isomorphism(graph, s_graph):
isomorphic_pairs.append((index, s_index))
# Print the isomorphic pairs
if isomorphic_pairs:
for motif_index, s_index in isomorphic_pairs:
print(f"motif_1 index: {motif_index}, motif_2 index: {s_index}")
else:
print("No isomorphic pairs found.")
```https://git.skewed.de/count0/graph-tool/-/issues/771problem with compilation2023-10-27T09:11:26ZJakub Krajniakproblem with compilation# Bug reports:
## Please follow the general troubleshooting steps first:
- [x] Are you running the latest `graph-tool` version?
- [x] Do you observe the problem with the current git version?
- [ ] Are you using Macports or Homebrew? If...# Bug reports:
## Please follow the general troubleshooting steps first:
- [x] Are you running the latest `graph-tool` version?
- [x] Do you observe the problem with the current git version?
- [ ] Are you using Macports or Homebrew? If yes, please submit an issue there instead: https://github.com/Homebrew/brew/issues and https://trac.macports.org/newticket
- [x] Did you compile `graph-tool` manually?
- [x] If you answered yes above, did you use the exact same compiler to build `graph-tool`, `boost-python` and `Python`?
Please replace this section with a brief summary of your issue.
## Do **not** forget to supply the following information:
- [ ] **A _minimal_ and _self-contained_ example that shows the problem.**
- [x] Your operating system. Linux
- [x] The Python version you are using. 3.9
- [x] If you compiled graph-tool manually: Your compiler version, as well as the version of Boost being used. gcc9, boost 1.83
- [ ] If you are reporting a compilation error, please provide the **entire** `./configure` output, as well as the **entire** contents of the `config.log` file and the **entire** compilation output.
Do not forget to add code snippets and error messages using [Markdown](/help/user/markdown.md), i.e.
```
Graph-tool compilation error
src/graph/inference/blockmodel/../support/graph_state.hh:198:13: required from 'static void graph_tool::StateWrap<Factory, TRS>::dispatch(boost::python::api::object&, F&&, bool) [with TS = {boost::any&, boost::any&, boost::any&, boost::checked_vector_property_map<int, boost::adj_edge_index_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::checked_vector_property_map<std::vector<double, std::allocator<double> >, boost::typed_identity_property_map<long unsigned int> >, std::vector<double, std::allocator<double> >&, bool, std::vector<int, std::allocator<int> >, std::vector<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> >, std::allocator<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> > > >, std::vector<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> >, std::allocator<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> > > >, std::vector<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> >, std::allocator<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> > > >, std::vector<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> >, std::allocator<boost::checked_vector_property_map<double, boost::adj_edge_index_property_map<long unsigned int> > > >, boost::checked_vector_property_map<double, boost::typed_identity_property_map<long unsigned int> >, std::vector<std::vector<double, std::allocator<double> >, std::allocator<std::vector<double, std::allocator<double> > > >&, std::vector<double, std::allocator<double> >&, std::vector<double, std::allocator<double> >&, std::vector<double, std::allocator<double> >&}; F = do_gibbs_sweep(boost::python::api::object, boost::python::api::object, rng_t&)::<lambda(auto:207&)>&; Factory = graph_tool::StateFactory<graph_tool::BlockState>; TRS = {graph_tool::detail::all_graph_views, boost::mpl::vector1<std::integral_constant<bool, true> >, boost::mpl::vector2<std::integral_constant<bool, true>, std::integral_constant<bool, false> >, boost::mpl::vector1<std::integral_constant<bool, false> >}]'
src/graph/inference/blockmodel/graph_blockmodel_gibbs.cc:31:1: required from 'static void block_state::dispatch(boost::python::api::object, F&&, bool) [with F = do_gibbs_sweep(boost::python::api::object, boost::python::api::object, rng_t&)::<lambda(auto:207&)>&]'
src/graph/inference/blockmodel/graph_blockmodel_gibbs.cc:55:49: required from here
src/graph/inference/blockmodel/graph_blockmodel_emat.hh:121:12: error: 'graph_tool::EHash<boost::undirected_adaptor<boost::adj_list<long unsigned int> > >::ehash_t' {aka 'class gt_hash_map<long unsigned int, boost::detail::adj_edge_descriptor<long unsigned int>, std::hash<long unsigned int>, std::equal_to<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::adj_edge_descriptor<long unsigned int> > > >'} has no member named 'min_load_factor'; did you mean 'max_load_factor'?
121 | _h.min_load_factor(.25);
| ~~~^~~~~~~~~~~~~~~
| max_load_factor
make[1]: *** [Makefile:3907: src/graph/inference/blockmodel/graph_blockmodel_gibbs.lo] Error 1
make[1]: Leaving directory '/work/06148/vsc31483/ls6/software/src/graph-tool'
make: *** [Makefile:2067: all] Error 2
```
_You can erase any parts of this template not applicable to your Issue._
Please note we may immediately close your issue without comment if you do not fill out the issue template and provide the requested information.https://git.skewed.de/count0/graph-tool/-/issues/768segfault by is_planar() function on graph view2023-09-22T18:37:29ZDenis Koshelevsegfault by is_planar() function on graph view# Bug reports:
I was trying to analyze certain graph instances, in particular their connected components isolated. However, in one case while checking planarity I encounter segfault.
System info:
- macOS Monterey 12.5
- Python 3.11.3
...# Bug reports:
I was trying to analyze certain graph instances, in particular their connected components isolated. However, in one case while checking planarity I encounter segfault.
System info:
- macOS Monterey 12.5
- Python 3.11.3
I attach a graph instance itself for the production:
[heuristic_014.gr](/uploads/56896e1cfa6791ec1ff6524e9df1d6c4/heuristic_014.gr)
Here is minimal code for reproducing:
```
import sys
import graph_tool as gt
import graph_tool.topology as topology
def read_graph(file_path):
with open(file_path, 'r') as f:
lines = f.readlines()
vertices, edges = map(int, lines[0].split()[2:])
adj_list = {i: [] for i in range(1, vertices + 1)}
for line in lines[1:]:
if line.strip() and line[0] != 'p':
u, v = map(int, line.split())
adj_list[u].append(v)
adj_list[v].append(u)
return vertices, edges, adj_list
def build_graph_tool_graph(vertices, edges, adj_list):
g = gt.Graph(directed=False)
g.add_vertex(vertices)
edge_list = [(u - 1, v - 1) for u, neighbors in adj_list.items() for v in neighbors if u < v]
g.add_edge_list(edge_list)
return g
def analyze_component(graph, component_filter, component_idx=None):
filtered_graph = gt.GraphView(graph, vfilt=component_filter)
is_planar = topology.is_planar(filtered_graph)
return {
'component': component_idx if component_idx else 'original',
'planarity': is_planar,
}
if __name__ == "__main__":
graph_file = sys.argv[1]
vertices, edges, adj_list = read_graph(graph_file)
graph_tool_graph = build_graph_tool_graph(vertices, edges, adj_list)
comp, hist = topology.label_components(graph_tool_graph)
if len(hist) > 1: # multiple components
results = []
for idx, component in enumerate(hist):
component_filter = comp.a == idx
results.append(analyze_component(graph_tool_graph, component_filter, idx))
else:
results = [analyze_component(graph_tool_graph, None)]
```https://git.skewed.de/count0/graph-tool/-/issues/767'graph_tool' has no attribute 'graph_draw'2023-09-06T07:29:14ZEbrahim Aly'graph_tool' has no attribute 'graph_draw'# Bug reports:
## Please follow the general troubleshooting steps first:
- [ ] Are you running the latest `graph-tool` version?
- [ ] Do you observe the problem with the current git version?
- [ ] Are you using Macports or Homebrew? If...# Bug reports:
## Please follow the general troubleshooting steps first:
- [ ] Are you running the latest `graph-tool` version?
- [ ] Do you observe the problem with the current git version?
- [ ] Are you using Macports or Homebrew? If yes, please submit an issue there instead: https://github.com/Homebrew/brew/issues and https://trac.macports.org/newticket
- [ ] Did you compile `graph-tool` manually?
- [ ] If you answered yes above, did you use the exact same compiler to build `graph-tool`, `boost-python` and `Python`?
Please replace this section with a brief summary of your issue.
## Do **not** forget to supply the following information:
- [ ] **A _minimal_ and _self-contained_ example that shows the problem.**
- [ ] Your operating system.
- [ ] The Python version you are using.
I have installed graph_tool(v 2.58) through conda (python 3.11.4) on macOS 13.5.1,
when I try to run the following code:
```
import graph_tool as gt
g = gt.Graph([('retrieve', 'demonstrate'), ('retrieve', 'play'), ('demonstrate', 'play'), ('play', 'return')],
hashed= True)
gt.graph_draw(g)
```
I get the following error:
`AttributeError: module 'graph_tool' has no attribute 'graph_draw'`
same error occurs when i import using `from graph_tool import *`https://git.skewed.de/count0/graph-tool/-/issues/765ImportError from draw after openmp_set_num_threads2023-09-17T18:44:56ZSilmathoronImportError from draw after openmp_set_num_threads```python
>>> import graph_tool
>>> graph_tool.openmp_set_num_threads(1)
>>> from graph_tool.draw import graph_draw
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ImportError: cannot import name 'graph_draw' from ...```python
>>> import graph_tool
>>> graph_tool.openmp_set_num_threads(1)
>>> from graph_tool.draw import graph_draw
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ImportError: cannot import name 'graph_draw' from 'graph_tool.draw' (/usr/lib/python3/dist-packages/graph_tool/draw/__init__.py)
```
Obviously import works fine without the call to ``openmp_set_num_threads``.
Tested on Python 3.10.12 with version 2.58 (commit 187fb477, Thu Aug 17 23:44:58 2023 +0200), installed via the PPA on an Ubuntu 22.04 LTS.https://git.skewed.de/count0/graph-tool/-/issues/763[Feature request] Calculate the extended clustering coefficient for a subset ...2023-08-11T13:18:55Zgiacomozonneveld[Feature request] Calculate the extended clustering coefficient for a subset of nodesIt would be great to have an option enabling coefficients computation for a subset of nodes of a graph. This would reduce computation time in scenarios where coefficients are needed only for some nodes of a large graphIt would be great to have an option enabling coefficients computation for a subset of nodes of a graph. This would reduce computation time in scenarios where coefficients are needed only for some nodes of a large graphhttps://git.skewed.de/count0/graph-tool/-/issues/762graph-tool docs2023-08-07T15:50:13ZRolf Sandergraph-tool docsAs already mentioned at https://forum.skewed.de/t/graph-tool-docs/1491, I suggest a few minor bug fixes in the docs:
- In the description of "class GraphWidget" on the webpage https://graph-tool.skewed.de/static/doc/_modules/graph_tool/...As already mentioned at https://forum.skewed.de/t/graph-tool-docs/1491, I suggest a few minor bug fixes in the docs:
- In the description of "class GraphWidget" on the webpage https://graph-tool.skewed.de/static/doc/_modules/graph_tool/draw/gtk_draw.html, highlight_color" is not explained in the docstring.
- On the same web page, the parameter "eprops" in the function
"interactive_window" is described as "Dictionary with the vertex
properties". I guess this should be EDGE properties.
- On
https://graph-tool.skewed.de/static/doc/autosummary/graph_tool.draw.GraphWidget.html,
"pos" is not explained for layout_callback and key_press_callback.https://git.skewed.de/count0/graph-tool/-/issues/753minimize_nested_blockmodel_dl getting stuck with weighted graph2023-04-03T15:02:01ZDominik Schlechtwegminimize_nested_blockmodel_dl getting stuck with weighted graphI am running the following code:
```
import graph_tool.all as gt
g = gt.collection.ns["foodweb_baywet"]
for i in range(100):
state = gt.minimize_nested_blockmodel_dl(g, state_args=dict(recs=[g.ep.weight], rec_types=["real-normal"]...I am running the following code:
```
import graph_tool.all as gt
g = gt.collection.ns["foodweb_baywet"]
for i in range(100):
state = gt.minimize_nested_blockmodel_dl(g, state_args=dict(recs=[g.ep.weight], rec_types=["real-normal"]),
multilevel_mcmc_args=dict(entropy_args=dict(adjacency=False, degree_dl=False))
)
```
After some iterations the process gets stuck in minimize_nested_blockmodel_dl().
I'm using Python 3.11.0 with Anaconda version 4.11.0 on a Linux server. I installed and activated graph-tool as described [here](https://git.skewed.de/count0/graph-tool/-/wikis/installation-instructions) with these commands:
```
conda create --name gt -c conda-forge graph-tool
conda activate gt
```
OS info:
LSB Version: :core-4.1-amd64:core-4.1-noarch
Distributor ID: Fedora
Description: Fedora release 35 (Thirty Five)https://git.skewed.de/count0/graph-tool/-/issues/739[Feature request] Truss decomposition2022-06-17T19:47:36Zddkda[Feature request] Truss decompositionK-trusses are a weakening of k-cliques. By analogy with `kcore_decomposition` I'm requesting a `ktruss_decomposition` which returns an EdgePropertyMap with each edge's truss number.
Open-source implementations exist https://github.com/K...K-trusses are a weakening of k-cliques. By analogy with `kcore_decomposition` I'm requesting a `ktruss_decomposition` which returns an EdgePropertyMap with each edge's truss number.
Open-source implementations exist https://github.com/KarypisLab/K-Truss
NetworkX has related functionality: it returns the k-truss subgraph https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.core.k_truss.html for a specific khttps://git.skewed.de/count0/graph-tool/-/issues/718Get partitions from NestedBlockState2021-09-17T14:02:55ZHaiko LietzGet partitions from NestedBlockStateHi Tiago,
the get_bs() method for a NestedBlockState object returns a list of array objects. In many cases it would be very convenient to also get a list of vertex property maps where each list item is a property map for a non-trivial l...Hi Tiago,
the get_bs() method for a NestedBlockState object returns a list of array objects. In many cases it would be very convenient to also get a list of vertex property maps where each list item is a property map for a non-trivial level of the NestedBlockState. Would you consider adding such a method?
I am using this one -- feel free to use or edit it (I'm also curious how you would implement this):
```
def NestedBlockState_get_partitions(state):
'''
Description: Returns the partition of building blocks per level given a nested blockmodel.
Inputs:
state: Nested blockmodel (graph-tool NestedBlockState object).
Output:
partitions: List of partitions (graph-tool property maps) with as many partitions as the hierarchy is deep.
'''
levels = state.get_levels()
depth = 0
for s in levels:
depth += 1
if s.get_N() == 1:
break
partitions = []
for level in range(len(levels)-(depth-1), len(levels)):
partition = []
for v in range(state.g.num_vertices()):
r = levels[0].get_blocks()[v]
l = 1
while l < len(levels)-level:
r = levels[l].get_blocks()[r]
l += 1
partition.append(r)
vp_partition = state.g.new_vertex_property('int')
vp_partition.a = partition
partitions.append(vp_partition)
return partitions
```https://git.skewed.de/count0/graph-tool/-/issues/714Differences between linux and os x (possibly numpy related?)2021-09-02T08:26:25ZDavide CittaroDifferences between linux and os x (possibly numpy related?)I have found an inconsistent behaviour with graph_tool version 2.43 on two different systems. In both cases I have installed via conda-forge. On the linux system I have
```
import graph_tool.all as gt
gt.__version__
'2.43 (commit 5778eb...I have found an inconsistent behaviour with graph_tool version 2.43 on two different systems. In both cases I have installed via conda-forge. On the linux system I have
```
import graph_tool.all as gt
gt.__version__
'2.43 (commit 5778eb10, )'
```
for python 3.8, numpy 1.21.2
On os x I have
```
import graph_tool.all as gt
gt.__version__
'2.43 (commit , )'
```
for python 3.8 and numpy 1.21.2 again.
I have tried a simple code (following #713 ) which is returning two different errors on both systems.
On OSX I have
```
g = gt.collection.ns["new_guinea_tribes"]
state = gt.minimize_nested_blockmodel_dl(g,
state_args=dict(base_type=gt.LayeredBlockState,
state_args=dict(ec=g.ep.weight, layers=True)))
missing = [(0, 6, 1), (0, 6, -1)]
state.get_edges_prob(missing)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-3-fadd85695711> in <module>
5
6 missing = [(0, 6, 1), (0, 6, -1)]
----> 7 state.get_edges_prob(missing)
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/nested_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
441 lstate._state.clear_egroups()
442
--> 443 L += lstate.get_edges_prob(missing, spurious, entropy_args=eargs)
444 if isinstance(self.levels[0], LayeredBlockState):
445 missing = [(lstate.b[u], lstate.b[v], l_) for u, v, l_ in missing]
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
788
789 nes.append((u, v, (l, False)))
--> 790 nes.append((self._get_lvertex(u, l),
791 self._get_lvertex(v, l), (l, True)))
792
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in _get_lvertex(self, v, l)
748 def _get_lvertex(self, v, l):
749 i = numpy.searchsorted(self.vc[v].a, l)
--> 750 if i >= len(self.vc[v]) or l != self.vc[v][i]:
751 raise ValueError("vertex %d not present in layer %d" % (v, l))
752 u = self.vmap[v][i]
TypeError: Invalid index type
```
whereas on linux I have
```
g = gt.collection.ns["new_guinea_tribes"]
state = gt.minimize_nested_blockmodel_dl(g,
state_args=dict(base_type=gt.LayeredBlockState,
state_args=dict(ec=g.ep.weight, layers=True)))
missing = [(0, 6, 1), (0, 6, -1)]
state.get_edges_prob(missing)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/beegfs/scratch/tmp/ipykernel_16854/740866967.py in <module>
5
6 missing = [(0, 6, 1), (0, 6, -1)]
----> 7 state.get_edges_prob(missing)
~/miniforge3/envs/singlecell/lib/python3.8/site-packages/graph_tool/inference/nested_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
441 lstate._state.clear_egroups()
442
--> 443 L += lstate.get_edges_prob(missing, spurious, entropy_args=eargs)
444 if isinstance(self.levels[0], LayeredBlockState):
445 missing = [(lstate.b[u], lstate.b[v], l_) for u, v, l_ in missing]
~/miniforge3/envs/singlecell/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
789 nes.append((u, v, (l, False)))
790 nes.append((self._get_lvertex(u, l),
--> 791 self._get_lvertex(v, l), (l, True)))
792
793 edge_list = nes
~/miniforge3/envs/singlecell/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in _get_lvertex(self, v, l)
749 i = numpy.searchsorted(self.vc[v].a, l)
750 if i >= len(self.vc[v]) or l != self.vc[v][i]:
--> 751 raise ValueError("vertex %d not present in layer %d" % (v, l))
752 u = self.vmap[v][i]
753 return u
ValueError: vertex 6 not present in layer 1
```
which is the correct behaviour (at least for the intent of this bug report).https://git.skewed.de/count0/graph-tool/-/issues/713Error with get_edges_prob() for LayeredBlockState2021-09-02T08:13:41ZDavide CittaroError with get_edges_prob() for LayeredBlockStateI am playing with edge prediction in particular with LayeredBlockState class. However, a simple example raises a TypeError. Here I'm using the same dataset indicated in the documentation
```
import graph_tool.all as gt
g = gt.collection...I am playing with edge prediction in particular with LayeredBlockState class. However, a simple example raises a TypeError. Here I'm using the same dataset indicated in the documentation
```
import graph_tool.all as gt
g = gt.collection.ns["new_guinea_tribes"]
state = gt.minimize_nested_blockmodel_dl(g,
state_args=dict(base_type=gt.LayeredBlockState,
state_args=dict(ec=g.ep.weight, layers=True)))
missing = [(0, 6, 1), (0, 6, -1)]
state.get_edges_prob(missing)
```
which raises this error
```
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-1-7a8e892c69fa> in <module>
6
7 missing = [(0, 6, 1), (0, 6, -1)]
----> 8 state.get_edges_prob(missing)
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/nested_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
441 lstate._state.clear_egroups()
442
--> 443 L += lstate.get_edges_prob(missing, spurious, entropy_args=eargs)
444 if isinstance(self.levels[0], LayeredBlockState):
445 missing = [(lstate.b[u], lstate.b[v], l_) for u, v, l_ in missing]
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args)
788
789 nes.append((u, v, (l, False)))
--> 790 nes.append((self._get_lvertex(u, l),
791 self._get_lvertex(v, l), (l, True)))
792
~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/layered_blockmodel.py in _get_lvertex(self, v, l)
748 def _get_lvertex(self, v, l):
749 i = numpy.searchsorted(self.vc[v].a, l)
--> 750 if i >= len(self.vc[v]) or l != self.vc[v][i]:
751 raise ValueError("vertex %d not present in layer %d" % (v, l))
752 u = self.vmap[v][i]
TypeError: Invalid index type
```
I'm using graph_tool version 2.43https://git.skewed.de/count0/graph-tool/-/issues/707Overlap of nested partitions with different depths2021-07-01T15:22:48ZHaiko LietzOverlap of nested partitions with different depths`nested_partition_overlap_center()` crashes when it receives a list of nested partitions with different depths (gt 2.37, conda-forge).
```
a = [[0, 1, 2, 3], [0, 0, 1, 1], [0, 0]]
b = [[0, 0, 1, 1], [0, 0]]
gt.nested_partition_overlap_c...`nested_partition_overlap_center()` crashes when it receives a list of nested partitions with different depths (gt 2.37, conda-forge).
```
a = [[0, 1, 2, 3], [0, 0, 1, 1], [0, 0]]
b = [[0, 0, 1, 1], [0, 0]]
gt.nested_partition_overlap_center([a, a]) # this works
gt.nested_partition_overlap_center([a, b]) # this crashes
```
The problem arises, e.g., when the consensus partition for a list of partitions from multiple runs of a nested SBM is sought.https://git.skewed.de/count0/graph-tool/-/issues/704Problems with boost 1.76.02021-06-25T12:26:17ZGerion EProblems with boost 1.76.0Not sure, if this a fixable in a proper way but I want to mention it.
When using graph-tool as a C++ library, there is a problem with boost 1.76 and include order.
I have created a minimal problem to demonstrate the problem (the exampl...Not sure, if this a fixable in a proper way but I want to mention it.
When using graph-tool as a C++ library, there is a problem with boost 1.76 and include order.
I have created a minimal problem to demonstrate the problem (the example is not runnable, it has nothing to do with python, etc. It's just for demonstrating a compilation warning):
main.cc
```c++
#include <boost/graph/filtered_graph.hpp>
#include <graph_tool.hh>
int main() {}
```
meson.build
```meson
project('graph-tool-test', 'cpp',
version : '0.1',
default_options : ['warning_level=3', 'cpp_std=c++14'])
py3_mod = import('python')
py3_inst = py3_mod.find_installation('python3', modules: ['pydot', 'graph_tool'])
graph_tool_dep = dependency('graph-tool-py' + py3_inst.language_version(), include_type: 'system')
executable('graph-tool-test',
'main.cc',
dependencies: graph_tool_dep)
```
Building:
```
$ meson build; cd build; ninja -v
The Meson build system
Version: 0.58.1
Source dir: /home/ci3nt/test/graph-tool-test
Build dir: /home/ci3nt/test/graph-tool-test/build
Build type: native build
Project name: graph-tool-test
Project version: 0.1
C++ compiler for the host machine: ccache c++ (gcc 10.3.0 "c++ (Gentoo 10.3.0 p1) 10.3.0")
C++ linker for the host machine: c++ ld.bfd 2.34
Host machine cpu family: x86_64
Host machine cpu: x86_64
Program python3 (pydot, graph_tool) found: YES (/usr/bin/python3) modules: pydot, graph_tool
Found pkg-config: /usr/bin/pkg-config (0.29.2)
Run-time dependency graph-tool-py3.9 found: YES 2.37
Build targets in project: 1
Found ninja-1.10.1 at /usr/bin/ninja
[1/2] ccache c++ -Igraph-tool-test.p -I. -I.. -fdiagnostics-color=always -D_FILE_OFFSET_BITS=64 -Wall -Winvalid-pch -Wnon-virtual-dtor -Wextra -Wpedantic -std=c++14 -g -pthread -isystem/usr/lib/python3.9/site-packages/graph_tool/include -isystem/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround -isystem/usr/lib/python3.9/site-packages/graph_tool/include/pcg-cpp -isystem/usr/lib/python3.9/site-packages/cairo/include -isystem/usr/include/python3.9 -isystem/usr/lib/python3.9/site-packages/numpy/core/include -MD -MQ graph-tool-test.p/main.cc.o -MF graph-tool-test.p/main.cc.o.d -o graph-tool-test.p/main.cc.o -c ../main.cc
FAILED: graph-tool-test.p/main.cc.o
ccache c++ -Igraph-tool-test.p -I. -I.. -fdiagnostics-color=always -D_FILE_OFFSET_BITS=64 -Wall -Winvalid-pch -Wnon-virtual-dtor -Wextra -Wpedantic -std=c++14 -g -pthread -isystem/usr/lib/python3.9/site-packages/graph_tool/include -isystem/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround -isystem/usr/lib/python3.9/site-packages/graph_tool/include/pcg-cpp -isystem/usr/lib/python3.9/site-packages/cairo/include -isystem/usr/include/python3.9 -isystem/usr/lib/python3.9/site-packages/numpy/core/include -MD -MQ graph-tool-test.p/main.cc.o -MF graph-tool-test.p/main.cc.o.d -o graph-tool-test.p/main.cc.o -c ../main.cc
In Datei, eingebunden von /usr/include/boost/graph/filtered_graph.hpp:15,
von ../main.cc:1:
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:48:33: Fehler: »iterator_traits« in Namensraum »boost::detail« bezeichnet keinen Templatetyp
48 | typename boost::detail::iterator_traits< OutEdgeIter >::difference_type
| ^~~~~~~~~~~~~~~
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:48:48: Fehler: expected unqualified-id before »<« token
48 | typename boost::detail::iterator_traits< OutEdgeIter >::difference_type
| ^
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:52:61: Fehler: »difference_type« wurde in diesem Gültigkeitsbereich nicht definiert
52 | typedef adjacency_iterator< Graph, Vertex, OutEdgeIter, difference_type >
| ^~~~~~~~~~~~~~~
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:52:77: Fehler: Templateargument 4 ist ungültig
52 | typedef adjacency_iterator< Graph, Vertex, OutEdgeIter, difference_type >
| ^
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:84:33: Fehler: »iterator_traits« in Namensraum »boost::detail« bezeichnet keinen Templatetyp
84 | typename boost::detail::iterator_traits< InEdgeIter >::difference_type
| ^~~~~~~~~~~~~~~
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:84:48: Fehler: expected unqualified-id before »<« token
84 | typename boost::detail::iterator_traits< InEdgeIter >::difference_type
| ^
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:88:64: Fehler: »difference_type« wurde in diesem Gültigkeitsbereich nicht definiert
88 | typedef inv_adjacency_iterator< Graph, Vertex, InEdgeIter, difference_type >
| ^~~~~~~~~~~~~~~
/usr/lib/python3.9/site-packages/graph_tool/include/boost-workaround/boost/graph/adjacency_iterator.hpp:88:80: Fehler: Templateargument 4 ist ungültig
88 | typedef inv_adjacency_iterator< Graph, Vertex, InEdgeIter, difference_type >
| ^
ninja: build stopped: subcommand failed.
```
When switching both of the include lines, the example compiles well.
Is this, because boost already loads the boost::detail namespace and [this](https://git.skewed.de/count0/graph-tool/-/blob/master/src/graph/graph.hh#L22) won't work anymore?https://git.skewed.de/count0/graph-tool/-/issues/697Getting marginals for nested PartitionModeState2021-04-27T09:19:10ZDavide CittaroGetting marginals for nested PartitionModeStateThe PartitionModeState functions allow to get the 2D matrix of marginals given the models used to create the object. When it is built using NestedBlockState instances, the marginals are only returned for the deepest BlockState in the hie...The PartitionModeState functions allow to get the 2D matrix of marginals given the models used to create the object. When it is built using NestedBlockState instances, the marginals are only returned for the deepest BlockState in the hierarchy. Would it be possible to implement a strategy to get the marginals of the blocks at higher levels (i.e. the marginals for blocks at level x to belong to blocks at level x + 1)?https://git.skewed.de/count0/graph-tool/-/issues/695dfs/bfs seem to have overhead depending on total graph size2021-03-03T12:25:17ZMy-Tien Nguyendfs/bfs seem to have overhead depending on total graph sizeHi all,
I’ve got a very large undirected graph (407 mil vertices, 522 mil edges, 2 vertex properties: int64_t and vector<int64_t>) that consists of multiple connected components (ccs).
I noticed that when I call e.g. dfs_iterator or d...Hi all,
I’ve got a very large undirected graph (407 mil vertices, 522 mil edges, 2 vertex properties: int64_t and vector<int64_t>) that consists of multiple connected components (ccs).
I noticed that when I call e.g. dfs_iterator or dfs_search on a source vertex, it takes around **1 – 2 seconds** to return. The upper bound is depending on the component’s size, but the lower bound seems to be the same for all components.
I have created a test graph with only a subset of the ccs of the large graph. Iterating the same cc in the test graph takes **only a couple of milliseconds instead of ≥ 1 s**. This tells me, that the dfs/bfs iterators have some kind of overhead depending on the complete graph size.
I wrote a DFSVisitor that collects some timings during iteration to better see which steps consume time. Here are the results (rounded for readability):
In [30]: test_dfs(graph, graph.vertex(0))
# first time the function is entered
visitor.start_vertex_t 2.3e-05 s
visitor.first_discover_vertex_t 0.18 s
visitor.first_examine_edge_t 0.18 s
visitor.first_tree_edge_t 0.63 s
visitor.first_finish_vertex_t 0.63 s
# average time between last 2 calls of the function
visitor.discover_vertex_t 0.002 s
visitor.examine_edge_t 0.001 s
visitor.tree_edge_t 0.001 s
visitor.finish_vertex_t 0.001 s
# last time finished() is called
visitor.finished 1.3 s
# number of times the functions were called
visitor.discovered_vertices 565
visitor.examined_edges 1978
visitor.tree_edges 564
visitor.finished_vertices 565
took 1.38 s
As you can see, start_vertex is called immediately, but then it takes a very long time until the other Visitor functions are called for the first time after which the calls are faster again, but still quite slow. On the test graph I think I can see the same trend with smaller numbers because the graph is smaller:
```
In [30]: test_dfs(test_graph, test_graph.vertex(0))
# first time the function is entered
visitor.start_vertex_t 2e-05 s
visitor.first_discover_vertex_t 0.0007 s
visitor.first_examine_edge_t 0.0007 s
visitor.first_tree_edge_t 0.0016 s
visitor.first_finish_vertex_t 0.0015 s
# average time between last 2 calls of the function
visitor.discover_vertex_t 1.6e-05 s
visitor.examine_edge_t 3.7e-06 s
visitor.tree_edge_t 1.4e-05 s
visitor.finish_vertex_t 1.4e-05 s
# last time finished() is called
visitor.finished 0.01 s
# number of times the functions were called
visitor.discovered_vertices 565
visitor.examined_edges 1978
visitor.tree_edges 564
visitor.finished_vertices 565
took 0.01 s
```
I also noticed that when I remove all vertex properties from the large graph, the minimum runtime of dfs_search is reduced by 0.7 s.
As it is, iterating small ccs in the large graph using pure python is much much faster than using graph-tool. It takes only a couple of milliseconds:
def dfs(graph, vertex_idx):
t = time.time()
todo = {vertex_idx}
visited = set()
while len(todo) > 0:
next_vertex = todo.pop()
visited.add(next_vertex)
todo |= set(graph.iter_all_neighbors(graph.vertex(next_vertex))) - visited
print(f'dfs took {time.time() - t} s')
return visited
In [38]: d = dfs(graph, 0)
dfs took 0.01653146743774414 s
Because of graph-tool’s slowness for small ccs, my current workaround was to write a heuristic that always attempts a naive python dfs first, but aborts if 1 second is exceeded and only then does the graph_tool dfs.
Anyone know what’s going on here?
Best
My-Tienhttps://git.skewed.de/count0/graph-tool/-/issues/694Residual flow larger than capacity for boykov_kolmogorov_max_flow2021-02-19T19:28:59ZmatteodellamicoResidual flow larger than capacity for boykov_kolmogorov_max_flowI'm running the debian/ubuntu 2.37 graph-tool package (after installing a dummy package to work around issue 690). Python 3.8.6, Ubuntu 20.10 "groovy".
When I use `boykov_kolmogorov_max_flow`, I get residual flow larger than capacity on...I'm running the debian/ubuntu 2.37 graph-tool package (after installing a dummy package to work around issue 690). Python 3.8.6, Ubuntu 20.10 "groovy".
When I use `boykov_kolmogorov_max_flow`, I get residual flow larger than capacity on some edges. I understand that shouldn't happen. Here's a snippet that reproduces the problem.
```
import random
from graph_tool import collection, flow
g = collection.data['pgp-strong-2009']
capacity = g.new_edge_property('float', 1)
while True:
s, t = random.sample(range(g.num_vertices()), 2)
residual = flow.boykov_kolmogorov_max_flow(g, s, t, capacity)
for n1, n2, c, r in g.iter_edges([capacity, residual]):
assert r <= c, (c, r)
```
The output I get is
```
Traceback (most recent call last):
File "test_residual.py", line 12, in <module>
assert r <= c, (c, r)
AssertionError: (1.0, 2.0)
```https://git.skewed.de/count0/graph-tool/-/issues/693Debian packages at downloads.skewed.de can't be mirrored over rsync2021-02-05T17:26:12ZAlex HenrieDebian packages at downloads.skewed.de can't be mirrored over rsyncI would like to mirror http://downloads.skewed.de/apt/ onto a server hosted in the USA, but I'd really want to sync the files over rsync instead of http. Could you please turn rsync on for the download server? Assuming that the server is...I would like to mirror http://downloads.skewed.de/apt/ onto a server hosted in the USA, but I'd really want to sync the files over rsync instead of http. Could you please turn rsync on for the download server? Assuming that the server is running Debian, the steps to do so are:
1. Run `apt install rsync`
2. Run `cp /usr/share/doc/rsync/examples/rsyncd.conf /etc`
3. Edit `/etc/rsyncd.conf`, changing `[ftp]` to `[apt]` and `path = /var/www/pub` to the `apt` directory that contains the graph-tool packages
4. Run `systemctl enable --now rsync`
At this point, running a command such as `rsync -r rsync://downloads.skewed.de/apt mirror` should create a copy of the graph-tool packages in a directory named `mirror`.