graph-tool issueshttps://git.skewed.de/count0/graph-tool/-/issues2020-11-06T10:25:14Zhttps://git.skewed.de/count0/graph-tool/-/issues/686[Feature Request] Output dominator tree as GraphView2020-11-06T10:25:14ZGerion E[Feature Request] Output dominator tree as GraphViewI already requested this on the mailing list and was told to put it here, so I will copy it:
The dominator_tree function in `graph_tool.topology` outputs a vertex property map that codifies a graph.
To use the other graph_tool algorithm...I already requested this on the mailing list and was told to put it here, so I will copy it:
The dominator_tree function in `graph_tool.topology` outputs a vertex property map that codifies a graph.
To use the other graph_tool algorithms, it would be beneficial to get the dominator_tree back as Graph (or better GraphView).
Is there already a way to do this? Otherwise, how do you like the idea to implement it?
A possible use case is it to check, if a dominates b.
This would be the pseudo code, if dominator_tree returns a graph like object:
```
dom_tree = graph_tool.topology.dominator_tree(graph, start, as_graph=True)
try:
next(graph_tool.topology.all_paths(a, b))
return True
except StopIteration:
return False
```
This is without (the path search runs in Python, not that much LOCs but more difficult to understand in my opinion):
```
dom_tree = graph_tool.topology.dominator_tree(graph, start)
while b:
if a == b:
return True
b = dom_tree[b]
return False
```https://git.skewed.de/count0/graph-tool/-/issues/681graph_tool.load: RuntimeError: Wanted "graph" or "digraph" (token is "<eof> ''")2020-09-27T13:27:45ZS Egbertgraph_tool.load: RuntimeError: Wanted "graph" or "digraph" (token is "<eof> ''")# Bug reports:
Attempting to open a '`.dot`' file resulted in a strange error:
```console
$ python3.7 /tmp/graph_load.py
Traceback (most recent call last):
File "/tmp/graph_load.py", line 5, in <module>
g.load("/tmp/x.dot", 'do...# Bug reports:
Attempting to open a '`.dot`' file resulted in a strange error:
```console
$ python3.7 /tmp/graph_load.py
Traceback (most recent call last):
File "/tmp/graph_load.py", line 5, in <module>
g.load("/tmp/x.dot", 'dot')
File "/usr/lib/python3/dist-packages/graph_tool/__init__.py", line 2889, in load
ignore_ep, ignore_gp)
RuntimeError: Wanted "graph" or "digraph" (token is "<eof> ''")
$
```
Source code `graph_load.py` contains 6 lines:
```python
#!/usr/bin/python3
from graph_tool.all import *
g = Graph()
g.load("/tmp/x.dot", 'dot')
```
Example '`/tmp/x.dot`' is a dot digraph, is attached to this issue but below are the first few lines:
```dot
// Generated by GNU Bison 3.3.2.
// Report bugs to <bug-bison@gnu.org>.
// Home page: <http://www.gnu.org/software/bison/>.
digraph "parser_bison.ypp"
{
rankdir=LR;
node [fontname = courier, shape = box, colorscheme = paired6]
edge [fontname = courier]
0 [label="State 0\n\l 0 $accept: . input \"end of file\"\l"]
0 -> 1 [style=dashed label="input"]
0 -> "0R1" [style=solid]
"0R1" [label="R1", fillcolor=3, shape=diamond, style=filled]
1 [label="State 1\n\l 0 $accept: input . \"end of file\"\l 2 input: input .
line\l"]
1 -> 2 [style=solid label="\"end of file\""]
1 -> 3 [style=dotted]
1 -> 4 [style=solid label="\"newline\""]
1 -> 5 [style=solid label="\"semicolon\""]
1 -> 6 [style=solid label="\"include\""]
1 -> 7 [style=solid label="\"define\""]
1 -> 8 [style=solid label="\"redefine\""][x.dot](/uploads/9dfbd88f70e3cd57096012f404888712/x.dot)
...
}
```
On Debian buster package 2.35 (commit a06d49a6, Wed Sep 16 18:34:19 2020 +0200) on Debian 10 (Buster).
OS `uname -a`:
Linux 4.19.0-10-amd64 #1 SMP Debian 4.19.132-1 (2020-07-24) x86_64 GNU/Linux
Debian package used:
```console
$ apt show -a python3-graph-tool
Package: python3-graph-tool
Version: 2.35
Priority: extra
Section: python
Maintainer: Tiago de Paula Peixoto <tiago@skewed.de>
Installed-Size: 318 MB
Depends: libboost-context1.67.0, libboost-coroutine1.67.0, libboost-iostreams1.67.0, libboost-python1.67.0, libboost-regex1.67.0 (>= 1.67.0-10), libc6 (>= 2.23), libcairo2 (>= 1.2.4), libcairomm-1.0-1v5 (>= 1.12.0), libexpat1 (>= 2.0.1), libgcc1 (>= 1:3.4), libgmp10, libgomp1 (>= 4.9), libpython3.7 (>= 3.7.0), libsigc++-2.0-0v5 (>= 2.2.0), libstdc++6 (>= 5.2), python3-scipy
Recommends: libgv-python, python-matplotlib, python-cairo, python-gi-cairo, python-gi, gir1.2-gtk-3.0
Homepage: http://graph-tool.skewed.de
Download-Size: 40.1 MB
APT-Manual-Installed: yes
APT-Sources: https://downloads.skewed.de/apt buster/main amd64 Packages
Description: graph-tool is an efficient python module for manipulation and statistical analysis of graphs
```
## 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`?https://git.skewed.de/count0/graph-tool/-/issues/676[Feature Request] add support for computing nodally-disjoint paths (e.g. Suur...2020-07-31T15:26:41ZJordan[Feature Request] add support for computing nodally-disjoint paths (e.g. Suurballe's algorithm)Hi,
I'm looking to see if graph-tool can add support for computing nodally-disjoint paths (e.g. Suurballe's algorithm). I don't see it as an option currently, but it is useful in selecting optimal routes with protected backup paths.
T...Hi,
I'm looking to see if graph-tool can add support for computing nodally-disjoint paths (e.g. Suurballe's algorithm). I don't see it as an option currently, but it is useful in selecting optimal routes with protected backup paths.
Thankshttps://git.skewed.de/count0/graph-tool/-/issues/672[Feature Request] LatentMultigraphBlockState() for weighted graph2020-07-17T20:12:09ZDominik Schlechtweg[Feature Request] LatentMultigraphBlockState() for weighted graphit would be nice to be able to use LatentMultigraphBlockState() with a weighted graph.it would be nice to be able to use LatentMultigraphBlockState() with a weighted graph.https://git.skewed.de/count0/graph-tool/-/issues/671[Feature Request] sampling from weighted SBM2020-07-23T10:28:46ZDominik Schlechtweg[Feature Request] sampling from weighted SBMIt would be nice to be able to sample from a fitted weighted model, also according to the inferred edge covariate distributions between groups.It would be nice to be able to sample from a fitted weighted model, also according to the inferred edge covariate distributions between groups.https://git.skewed.de/count0/graph-tool/-/issues/666Error computing `shortest_distance()` when vertex missing from GraphView2021-09-08T13:16:21ZDanielaError computing `shortest_distance()` when vertex missing from GraphView- [X] 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/bre...- [X] 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`?
When computing `shortest_distance()` (possibly other functions as well but haven't tested), if the graph supplied is a GraphView and the source vertex was filtered out of the view, an error occurs (as expected). However, the error seems to come from the C/C++ bindings and is not very easy to track to the actual problem being raised.
My operating system is Ubuntu 16.04.2 LTS and I'm running the latest version of graph tool in a conda environment. Below is a code snippet to reproduce the error.
```python
from graph_tool import Graph, GraphView
from graph_tool.topology import shortest_distance
g = Graph()
vprop = g.new_vertex_property("string")
g.vertex_properties["foo"] = vprop
v1 = g.add_vertex()
g.vp["foo"][v1] = "boo"
v2 = g.add_vertex()
view = GraphView(g, directed=False, vfilt=lambda x:g.vp["foo"][x] == "boo")
shortest_distance(view, source=v2)
```
The above snippet gives the error
```
*** Error in `/path/to/bin/python': double free or corruption (out): 0x000055ba82d6d420 ***
```
I believe that instead of a low-level error the function should raise a high-level exception that the requested vertex doesn't exist in the provided graph.https://git.skewed.de/count0/graph-tool/-/issues/663[feature request] General reduce function on multiple edges2020-06-05T12:37:23ZCarlo Nicolini[feature request] General reduce function on multiple edgesHere I am attaching the same content as from the mailing list.
The idea is to implement a general scheme for map-reduce operation on edges or vertices, in an efficient ways, and more generically than what is done with `gt.condensation_gr...Here I am attaching the same content as from the mailing list.
The idea is to implement a general scheme for map-reduce operation on edges or vertices, in an efficient ways, and more generically than what is done with `gt.condensation_graph`.
I have a graph in graph-tool with parallel edges. All parallel edges are assigned an `EdgePropertyMap` representing their weight with a double. I would like to return a graph where the edges are condensed into a single edge where a custom reduce operation on these weights is performed. For example:
H = gt.Graph(directed=True)
H.add_edge(0,1) # edge 0
H.add_edge(0,1) # edge 1
H.add_edge(0,1) # edge 2
H.add_edge(1,0) # edge 3
H.add_edge(0,2) # edge 4
ew = H.new_edge_property("double")
ew[list(H.edges())[0]]=1.2
ew[list(H.edges())[1]]=2.3
ew[list(H.edges())[2]]=-4.2
ew[list(H.edges())[3]]=5.8
ew[list(H.edges())[3]]=1.0
H.ep['weights'] = ew
In this case the edge (0,1), with a reduce function "sum", should have total weight 1.2+2.3-4.2= -0.7 while the remaining edges should keep the same weight (i.e. edge 3 should keep weight 5.8 and edge 4 should maintain weight 1.0).
Using `gt.condensation_graph` seems to do the trick, but only sum operation can be performed. To do this we need to use `H.vertex_index` as vertex property:
Hcond, prop, vcount, ecount, v_avg, edge_avg = gt.condensation_graph(H,prop=H.vertex_index, aeprops=[H.ep['weights']])
Unfortunately this function only allows sum operation to be performed. What about using a different "reduce" function, like for example max? What about operations on non-numeric types of edges?
It would greatly help carrying complex operations directly in Graph-tool, even if the value type of edges property is different than numeric.
More generally, what about introducing a split-apply-reduce framework to vertices and edges, or is it already possible with some modifications to `gt.condensation_graph`?
Many thankshttps://git.skewed.de/count0/graph-tool/-/issues/662Setting `bfield` in upper levels of NestedBlockstate does not work as expected2020-06-09T17:41:43ZAle AbdoSetting `bfield` in upper levels of NestedBlockstate does not work as expectedNi! Oiê.
Tested with current git version compiled on Fedora 32, python-3.8, gcc-10.1.1, boost-1.69.0. Also tested with 2.31.
This assumes `bfield` was intended to be settable at upper levels. Sorry if I'm mistaken, still, in that case,...Ni! Oiê.
Tested with current git version compiled on Fedora 32, python-3.8, gcc-10.1.1, boost-1.69.0. Also tested with 2.31.
This assumes `bfield` was intended to be settable at upper levels. Sorry if I'm mistaken, still, in that case, would it be feasible and, if not, perhaps add a warning?
The expected behavior is to freeze part of the vertices and blocks at all levels, leaving the rest free to move but not into the frozen blocks.
A minimal self-contained example is attached: [test_bfield_mcmc.py](/uploads/ae316fdfe973046e00ca5b7995d7e910/test_bfield_mcmc.py)
In the example, frozen vertices and blocks respect `bfield` as expected, and free vertices respect the constraint that they do not enter frozen blocks. However, free blocks do move into upper blocks they are not supposed to, such as occupying block `0` despite the fact they start at block `1` and their bfield is `[-inf, 0.]`.
I'll try to debug once confirmed that this is supposed to work. In that case, any ideas on where to look for the issue?
[Possibly off-topic]: To the same end I had been using the `vertices` parameter with a small tweak to `_h_sweep_gen` that transposed it across levels. I came back to `bfield` in the hopes of using multiflip, and because my tweak stopped working in recent versions. This is only important if it would be easier to make `vertices` work with multiflip across levels, rather than `bfield`.
Cheers.https://git.skewed.de/count0/graph-tool/-/issues/659Distinctiveness Centrality [feature request]2020-05-23T07:40:46ZAndrea Fronzetti ColladonDistinctiveness Centrality [feature request]We recently developed a new metric of Social Network Analysis, named **Distinctiveness Centrality**.
The metric gives importance to nodes with distinctive/non-redundant network ties, and is fully described in this paper: https://doi.org/...We recently developed a new metric of Social Network Analysis, named **Distinctiveness Centrality**.
The metric gives importance to nodes with distinctive/non-redundant network ties, and is fully described in this paper: https://doi.org/10.1371/journal.pone.0233276
Distinctiveness also has a very reasonable computational complexity.
We are not expert programmers so, for now, we were just able to develop a Python package that calculates Distinctiveness and is built upon Networkx: https://github.com/iandreafc/distinctiveness
However, we would love to also use it through graph-tool, which we always use with large networks.
It would be great if you could help us integrate it in your library!https://git.skewed.de/count0/graph-tool/-/issues/652Max flow segfaults with source=target2020-04-23T19:52:00ZSteve HarenbergMax flow segfaults with source=targetgraph-tool is segfaulting when running maxflow with source=target
version: '2.29 (commit d4154c6c, Tue Aug 27 13:21:10 2019 +0000)'
python version: 3.7.5
```python
import graph_tool as gt
import graph_tool.flow as gtf
g = gt.Graph()
v...graph-tool is segfaulting when running maxflow with source=target
version: '2.29 (commit d4154c6c, Tue Aug 27 13:21:10 2019 +0000)'
python version: 3.7.5
```python
import graph_tool as gt
import graph_tool.flow as gtf
g = gt.Graph()
v1 = g.add_vertex()
v2 = g.add_vertex()
e = g.add_edge(v1, v2)
cap = g.new_edge_property("double", val=1)
result = gtf.edmonds_karp_max_flow(g, source=v1, target=v1, capacity=cap)
```https://git.skewed.de/count0/graph-tool/-/issues/626Drawing more than 2 graphs in a window2020-01-28T02:26:09ZXinlong YinDrawing more than 2 graphs in a window![Screenshot_from_2020-01-27_21-17-30](/uploads/3a4cec1d0f85e55ccd41a1acae19aae4/Screenshot_from_2020-01-27_21-17-30.png)
I am trying to do an animation of several graphs in one window. When I try to add more than 2 GraphWidgets in a win...![Screenshot_from_2020-01-27_21-17-30](/uploads/3a4cec1d0f85e55ccd41a1acae19aae4/Screenshot_from_2020-01-27_21-17-30.png)
I am trying to do an animation of several graphs in one window. When I try to add more than 2 GraphWidgets in a window, only the first 2 can be rendered, and the others just show a black rectangle. However, the simulation seems to be fine, because the plots seem to be normal. Is this a bug of the library or there's something wrong in my code?
[myTest.py](/uploads/bad2e728e055020cf9b3e93aa982f7e0/myTest.py)https://git.skewed.de/count0/graph-tool/-/issues/600[feature request] Structural Holes Constraint2019-07-27T08:09:02ZAndrea Fronzetti Colladon[feature request] Structural Holes ConstraintIt would be great to have a graph-tool function to calculate Structural Holes, i.e. the Constraint theorized by Burt.
Networkx does it, but it is deadly slow: https://networkx.github.io/documentation/stable/reference/algorithms/generated...It would be great to have a graph-tool function to calculate Structural Holes, i.e. the Constraint theorized by Burt.
Networkx does it, but it is deadly slow: https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.structuralholes.constraint.html#networkx.algorithms.structuralholes.constrainthttps://git.skewed.de/count0/graph-tool/-/issues/573Support yum package manager2019-03-27T08:40:57ZRegev SchweigerSupport yum package managerPlease add support for the yum package manager. This is mainly useful for installing on the default Amazon AWS image.Please add support for the yum package manager. This is mainly useful for installing on the default Amazon AWS image.https://git.skewed.de/count0/graph-tool/-/issues/506Extract change point information2018-09-20T07:34:24ZHaiko LietzExtract change point informationgt allows inferring change points in layered graphs when time is passed as an edge property (Peixoto (2015). Inferring the mesoscale structure of layered, edge-valued, and time-varying networks. https://doi.org/10.1103/PhysRevE.92.042807...gt allows inferring change points in layered graphs when time is passed as an edge property (Peixoto (2015). Inferring the mesoscale structure of layered, edge-valued, and time-varying networks. https://doi.org/10.1103/PhysRevE.92.042807). But extracting the bin / change point information from the SBM is not automatized in gt. The goal is to produce a figures as in figure 8 of the referenced paper. Help is truly appreciated...https://git.skewed.de/count0/graph-tool/-/issues/491[feature request] Weighted diameter and average distance2018-07-08T21:45:35ZFabrício[feature request] Weighted diameter and average distanceI am working with large graphs calculating diameter and average path length. I am using the `shortest_distance()` function with weights which returns the dist_map then I use the `get_2d_array()` to convert to a `np.array` and calculate t...I am working with large graphs calculating diameter and average path length. I am using the `shortest_distance()` function with weights which returns the dist_map then I use the `get_2d_array()` to convert to a `np.array` and calculate the diameter (np.max) and the average distance (np.mean). The problem is that the `shortest_distance()` is taking around 6 minutes but the `get_2d_array()` is taking much more than that, which is strange. I wonder if maybe having both average distance and diameter implemented C++ wouldn't provide a huge performance boost.
Is there any other alternative for what I am trying to do? I can provide the graph in `.graphml` if it can be of any help.https://git.skewed.de/count0/graph-tool/-/issues/463[feature requrest] Rich-club coefficient2018-05-01T18:19:07ZAlain Fonhof[feature requrest] Rich-club coefficient@count0 I was wondering if you ever got around to implementing the rich-club coefficient algorithm as discussed in this thread: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Rich-club-td4025697.html
Just fo...@count0 I was wondering if you ever got around to implementing the rich-club coefficient algorithm as discussed in this thread: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Rich-club-td4025697.html
Just for reference this is the algorithm I would love to see in graph-tool: https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.richclub.rich_club_coefficient.html#networkx.algorithms.richclub.rich_club_coefficient
I made a small start but I am not quiet sure how to implement the normalization with graph-tool.
```
def rich_club_coefficient(g):
deghist = gt.vertex_hist(g, 'total')[0]
total = sum(deghist)
rc = {}
# Compute the number of nodes with degree greater than `k`, for each
# degree `k` (omitting the last entry, which is zero).
nks = (total - cs for cs in np.cumsum(deghist) if total - cs > 1)
deg = g.degree_property_map('total')
for k, nk in enumerate(nks):
if nk == 0:
continue
sub_g = gt.GraphView(g, vfilt=lambda v: deg[v] > k)
ek = sub_g.num_edges()
rc[k] = 2 * ek / (nk * (nk - 1))
return rc
```https://git.skewed.de/count0/graph-tool/-/issues/460[feature request] Implement 2-edge-connected components2018-04-26T13:46:47ZAndre Vieira[feature request] Implement 2-edge-connected componentsAs recommended, I am opening an issue suggesting the addition of an algorithm that labels the 2-edge-connected components of an undirected graph.
Cheers,
Andre.As recommended, I am opening an issue suggesting the addition of an algorithm that labels the 2-edge-connected components of an undirected graph.
Cheers,
Andre.https://git.skewed.de/count0/graph-tool/-/issues/452get_edges_prob() alters state entropy with real-normal edge covariates2018-03-26T15:27:40ZKatharina Baumget_edges_prob() alters state entropy with real-normal edge covariates# Bug report:
Experienced in version 2.26, under Python 2.7 and 3.6 as well as using the latest Docker image (18-03-26).
## Bug description
Calling get_edges_prob() alters the state object and gives inconsistent results if using a rea...# Bug report:
Experienced in version 2.26, under Python 2.7 and 3.6 as well as using the latest Docker image (18-03-26).
## Bug description
Calling get_edges_prob() alters the state object and gives inconsistent results if using a real-normal edge prior (apparently not for real-exponential prior or models without edge covariates).
## Example illustrating the problem
```python
import graph_tool.all as gt
g=gt.collection.data['celegansneural']
state=gt.minimize_blockmodel_dl(g,state_args=dict(recs=[g.ep.value],rec_types=['real-normal']))
original_entropy=state.entropy()
edge_prob=[]
for i in range(10000): edge_prob.append(state.get_edges_prob(missing=[],spurious=[(0,2)]))
original_entropy-state.entropy() #this is not zero...
edge_prob[0]-edge_prob[-1] #this is not zero...
```https://git.skewed.de/count0/graph-tool/-/issues/428graph_draw not mapping integer props correctly2017-12-02T20:33:15ZTiemengraph_draw not mapping integer props correctlyI'm not sure if this is intended behaviour of graph_tool.draw.graph_draw, but it seems erroneous. If I add an edge property as an 'int' with some values (e.g. 1 and 11) they are **color**mapped differently as opposed to 'float' with the ...I'm not sure if this is intended behaviour of graph_tool.draw.graph_draw, but it seems erroneous. If I add an edge property as an 'int' with some values (e.g. 1 and 11) they are **color**mapped differently as opposed to 'float' with the same values.
Perhaps conversion to (normalized) floats is essential for the mapping to work out, but I feel this is something that should be covered behind the scenes. For instance, if you would like to map according to vertex degree, you would have to convert your property to float first, because it would otherwise be mapped with bogus colors (they seemingly do something, which could be even worse).
## Bug reports:
* I'm running graph_tool 2.25 on Ubuntu 16.04, Python 3.6.2, not manually compiled.
- Do you observe the problem with the current git version?
* I see no relevant changes in the files and cannot build from source sadly.
```python
import numpy as np
import graph_tool.all as gt
from graph_tool.draw import graph_draw
g = gt.Graph()
# Edge prop
adj = g.new_ep('int') # CHANGE TO FLOAT FOR CORRECT BEHAVIOUR
g.ep['adj'] = adj
# Populate
a = np.array([[0, 1, 11], [1, 0, 1]])
g.add_edge_list(a, eprops=[adj])
# Names
vnames = g.new_vp('string', vals=['A', 'B'])
g.vp['vnames'] = vnames
# Draw
graph_draw(g,edge_color=adj, vertex_text=vnames, edge_pen_width=6.0, output='test_int.png')
```
## Integer result (wrong!)
![test_int](/uploads/af3f9075e3717f2f180ce1a98c08e2ad/test_int.png)
## Float result (correct)
![test_float](/uploads/b3e27aba17381e462117bfb9a89094ca/test_float.png)https://git.skewed.de/count0/graph-tool/-/issues/417Implementation of sub-graph centrality2017-10-02T14:17:33ZEmilio BertiImplementation of sub-graph centralityI would like to use the subgraph centrality index as defined in Estrada E. 2007
Link to article: http://www.estradalab.org/wp-content/uploads/2015/10/paper-951.pdf
Did someone already implement it?I would like to use the subgraph centrality index as defined in Estrada E. 2007
Link to article: http://www.estradalab.org/wp-content/uploads/2015/10/paper-951.pdf
Did someone already implement it?