graph-tool issueshttps://git.skewed.de/count0/graph-tool/-/issues2017-09-24T07:44:20Zhttps://git.skewed.de/count0/graph-tool/-/issues/414Documentation for deg_sampler in generation.random_graph2017-09-24T07:44:20ZSnehal ShekatkarDocumentation for deg_sampler in generation.random_graphThe documentation for deg_sampler function from random_graph says:
A degree sampler function which is called without arguments, and returns a tuple of ints representing the in and out-degree of a given vertex (or a single int for un...The documentation for deg_sampler function from random_graph says:
A degree sampler function which is called without arguments, and returns a tuple of ints representing the in and out-degree of a given vertex (or a single int for undirected graphs, representing the out-degree). This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph.
Optionally, you can also pass a function which receives one or two arguments. If block_membership is None, the single argument passed will be the index of the vertex which will receive the degree. If block_membership is not None, the first value passed will be the vertex index, and the second will be the block value of the vertex.
We have already discussed this issue in the past and then you had replied saying that "The function random_graph() will look at how many parameters the deg_sampler takes, and this will trigger different behaviors. Although it is in fact documented, I agree this is confusing and unexpected. Please open an issue in the website, and this will be improved in the future."
I request you to kindly make the necessary improvements whenever it would be possible for you.https://git.skewed.de/count0/graph-tool/-/issues/398Minimum spanning arborescence?2017-09-14T18:09:47ZXiao HanMinimum spanning arborescence?Hi,
I find algorithms for minimum spanning arborescence (MST for directed graph) are missing.
It would be good if they can be considered in the future.
Thanks!
HanHi,
I find algorithms for minimum spanning arborescence (MST for directed graph) are missing.
It would be good if they can be considered in the future.
Thanks!
Hanhttps://git.skewed.de/count0/graph-tool/-/issues/390Feature request - unsigned integer data types.2021-05-17T09:45:44ZAlfredo MazzinghiFeature request - unsigned integer data types.I am trying to store a python integer as a _uint64_t_ in a property map, however the current integral data types supported only include signed data types.
This leaves me with the only option of storing the _uint64_t_ values in a propert...I am trying to store a python integer as a _uint64_t_ in a property map, however the current integral data types supported only include signed data types.
This leaves me with the only option of storing the _uint64_t_ values in a property map with type _object_, however this is suboptimal as the storage required for the graph increases.
I made a simple test with two graphs of a million nodes with random 64-bit integers values attached to the nodes, comparing the graph size in the case of _int64_t_ and _object_ property maps. My results show that in the former case the graph (gt format) takes up about 16MiB while in the latter case it takes 37MiB.
I have not test load times but I suspect that it may have an impact there as well.
I am wondering why unsigned data types have not been provided, but if the task is not too difficult it would be nice to have.https://git.skewed.de/count0/graph-tool/-/issues/377LINKFORSHARED is broken; replace with python-config2017-07-10T12:50:57ZGeoffrey FairchildLINKFORSHARED is broken; replace with python-configAs discussed in https://github.com/Homebrew/homebrew-science/issues/5198, it appears that `LINKFORSHARED` is broken and should instead be replaced with `python-config` so that graph-tool can be built for Python 3.6.As discussed in https://github.com/Homebrew/homebrew-science/issues/5198, it appears that `LINKFORSHARED` is broken and should instead be replaced with `python-config` so that graph-tool can be built for Python 3.6.https://git.skewed.de/count0/graph-tool/-/issues/356using cairocffi instead of pycairo2017-07-10T12:50:57ZVincent Gauthierusing cairocffi instead of pycairoThe Pycairo library is now outdated It hasn't been updated since 2011. In the other hand, Cairocffi is a CFFI-based drop-in replacement for Pycairo, which is well maintained. Moreover, you can easily switch one with the other with a mini...The Pycairo library is now outdated It hasn't been updated since 2011. In the other hand, Cairocffi is a CFFI-based drop-in replacement for Pycairo, which is well maintained. Moreover, you can easily switch one with the other with a minimal change in your code.
```Python
import cairocffi
cairocffi.install_as_pycairo()
import cairo
assert cairo is cairocffi
```
I hope this can help
regards,
Vincenthttps://git.skewed.de/count0/graph-tool/-/issues/355motif on large scale (about 1 milion nodes and 10 milion edges)2017-07-10T12:50:57ZRoimotif on large scale (about 1 milion nodes and 10 milion edges)i have a problem to run motif on large scale cause it take alot of memory and crush:
1. motif_size = 3 (it take 10G ram and hold)
2. motif_size =4 (it crush when it about 30G..)
i use the function
result = gt.clustering.motifs(ggt,...i have a problem to run motif on large scale cause it take alot of memory and crush:
1. motif_size = 3 (it take 10G ram and hold)
2. motif_size =4 (it crush when it about 30G..)
i use the function
result = gt.clustering.motifs(ggt, motif_list=motifs_veriations, k=4, return_maps=True)
do you have an idea to help?https://git.skewed.de/count0/graph-tool/-/issues/328[request for feature] Bi-directional Dijkstra2018-04-04T08:02:42ZFrançois Kawala[request for feature] Bi-directional Dijkstra
# Motivation
In #259 we propose to implement hierarchical contractions. With this feature the standard way to speed up shortest path computation in road-like network is to use a bi-directional Dijkstra. This bi-directional Dijkstra i...
# Motivation
In #259 we propose to implement hierarchical contractions. With this feature the standard way to speed up shortest path computation in road-like network is to use a bi-directional Dijkstra. This bi-directional Dijkstra is applied to two distinct graph views. The first graph view has downward (ie. according to a given node order) edges disabled. The second graph view has upward edges disabled.
# Overview
See [slides](http://ad-teaching.informatik.uni-freiburg.de/route-planning-ss2012/lecture-6.pdf) and [video](http://ad-teaching.informatik.uni-freiburg.de/route-planning-ss2012/get-video.php?file=lecture-6) from Prof. Dr. Hannah Bast's [lectures](https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012).
# Implementation proposal:
Implementation should use boost coroutines as proposed by Daniel J. H. in his C++now tutorial. See [video](https://www.youtube.com/watch?v=3SvkWY7JSeY) and [sources] (https://github.com/daniel-j-h/cppnow2016). https://git.skewed.de/count0/graph-tool/-/issues/327Make the installation easier?2020-05-28T19:55:59ZAlexandre DecanMake the installation easier?As a researcher in software ecosystems, I recently encountered performance issues on (quite) large graphs with NetworkX. I then considered using graph-tool.
However, as a Fedora user, I had great difficulty in finding an easy solution t...As a researcher in software ecosystems, I recently encountered performance issues on (quite) large graphs with NetworkX. I then considered using graph-tool.
However, as a Fedora user, I had great difficulty in finding an easy solution to install graph-tool. I didn't find any package targeting Fedora/CentOS, I didn't manage to turn the provided .deb into a valid .rpm, and I didn't want to spend too much time compiling graph-tool and its dependencies.
I then moved on to igraph and its Python binding which were fine for my purposes, but I felt that I should give it a try with graph-tool. I think you should consider making the installation easier for (some) Linux users. The first solution is to **provide packages targeting Fedora/CentOS**, which is quite a major distribution nowadays. The second solution is to **provide wheels for (major) architectures on PyPI**, which can be quite a difficult (and annoying) task. The third one, which could be easier for you, is to **consider Conda and, more specifically, the open-source Conda-Forge** (see https://conda-forge.github.io) that provides a very simple mechanism for developers to have their package automatically build against the three major operating systems.
Btw, thanks for your job. I hadn't a chance yet to test graph-tool, but I enjoyed reading the documentation and I hope I'll be able to perform some research with it (I've to admit I really don't like the API of igraph's python binding nor its documentation).https://git.skewed.de/count0/graph-tool/-/issues/306problem with importing .all when compiled with --disable-cairo2017-07-10T12:50:57ZDarkoproblem with importing .all when compiled with --disable-cairoAs it's said in the title, after compiling graph-tool with --disable-cairo, importing all modules yields this error:
```python
In [1]: import graph_tool.all
.../python_modules/graph_tool/draw/cairo_draw.py:96: RuntimeWarning: Error im...As it's said in the title, after compiling graph-tool with --disable-cairo, importing all modules yields this error:
```python
In [1]: import graph_tool.all
.../python_modules/graph_tool/draw/cairo_draw.py:96: RuntimeWarning: Error importing cairo-based drawing library. Was graph-tool compiled with cairomm support?
warnings.warn(msg, RuntimeWarning)
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
<ipython-input-1-72f7eb0cb2e1> in <module>()
----> 1 import graph_tool.all
.../python_modules/graph_tool/all.py in <module>()
33 import graph_tool.centrality
34 try:
---> 35 from graph_tool.draw import *
36 import graph_tool.draw
37 except ImportError as e:
.../python_modules/graph_tool/draw/__init__.py in <module>()
803
804 try:
--> 805 from .cairo_draw import graph_draw, cairo_draw, get_hierarchy_control_points, default_cm
806 except ImportError:
807 pass
.../python_modules/graph_tool/draw/cairo_draw.py in <module>()
201
202 for k in list(_vtypes.keys()):
--> 203 _vtypes[getattr(vertex_attrs, k)] = _vtypes[k]
204
205 for k in list(_etypes.keys()):
NameError: name 'vertex_attrs' is not defined
```Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/303topology.tsp_tour : incorrect solution/erratic behaviour depending on source...2023-03-19T08:59:39Zwf-rtopology.tsp_tour : incorrect solution/erratic behaviour depending on source vertextopology.tsp_tour shows erratic behaviour (Graph-Tool 2.16, Boost 1.60, Ubuntu 14.04, Python 2.7.6), depending on source vertex given.
# How to reproduce:
```python
import graph_tool.all as gt
print(gt.tsp_tour(g, g.vertex(1)))
```
...topology.tsp_tour shows erratic behaviour (Graph-Tool 2.16, Boost 1.60, Ubuntu 14.04, Python 2.7.6), depending on source vertex given.
# How to reproduce:
```python
import graph_tool.all as gt
print(gt.tsp_tour(g, g.vertex(1)))
```
# Expected result:
```python
[ 1 2 11 12 21 22 31 32 41 42 51 52 61 62 71 72 81 82 83 73 84 74 85 75
86 76 87 77 88 78 68 58 67 57 66 56 65 55 64 54 63 53 43 33 23 13 3 4 5
6 7 8 89 79 69 59 49 39 48 38 47 37 46 36 45 35 44 34 24 14 25 15 26 16
27 17 28 18 29 19 9 91 92 93 94 95 96 97 98 99 10 20 30 40 50 60 70 80 90
0 1 ]
```
# Actual result:
```python
[ 0 10 20 30 40 50 60 70 80 90 0]
```
This is neither a TSP tour, nor does it start/end in the source node.
This is a variant of the example given in the documentation (https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.tsp_tour). If using `g.vertex(2)` instead of `g.vertex(1)`, the result is `[0 0]`.https://git.skewed.de/count0/graph-tool/-/issues/299Obtaining the triadic closure of a Graph with graph-tool2017-07-10T12:50:58ZPietro BattistonObtaining the triadic closure of a Graph with graph-toolFrom http://stackoverflow.com/questions/37029516/obtaining-the-triadic-closure-of-a-graph-with-graph-tool
``graph_tool.topology`` contains ``transitive_closure``, which is basically the "infinite-th" power of the adjacency matrix: wha...From http://stackoverflow.com/questions/37029516/obtaining-the-triadic-closure-of-a-graph-with-graph-tool
``graph_tool.topology`` contains ``transitive_closure``, which is basically the "infinite-th" power of the adjacency matrix: what it would be nice to obtain is the second, or in general the ``k``-th, power.
I think it would be nice to implement this as
graph_tool.topology.transitive_closure(g, k=np.inf)
where not passing ``k`` would result in the current behaviour while passing a (positive integer) value of ``k`` would yield what I ask (e.g. ``k=1`` would yield ``g`` itself).
However I don't think that boost provides a ready solution. Maybe it could be added? It may make sense also for finite``k`` to [go through the condensation graph](http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/transitive_closure.html), though I have no idea how much more efficient it is than just taking the ``k``-th power of the (boolean version of) the adjacency matrix.Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/259[request for feature] hierarchical contraction2017-07-10T12:50:58ZFrançois Kawala[request for feature] hierarchical contractionIn this Issue we discuss the implementation of **hierarchical contraction**.
# Motivation
As per Wikipedia "the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contr...In this Issue we discuss the implementation of **hierarchical contraction**.
# Motivation
As per Wikipedia "the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph."
# Overview
More precisely, as per Robert Geisberger "*[...] the nodes of a weighted
directed graph __G = (V, E)__ are ordered by “importance” given a total node order __<.__ Let __u < v__,
then the node __v__ is more important than __u__. We now construct a hierarchy by contracting the
nodes in this order. A node _u_ is contracted by _removing it_ from the network in such a way
that shortest paths in the remaining overlay graph are preserved. This property is achieved by
replacing paths of the form __⟨hv, u, wi⟩__ by a shortcut edge __⟨hv, wi⟩__. Note that the shortcut __⟨hv, wi⟩__ is only required if __⟨hv, u, wi⟩__ is the only shortest path from _v_ to _w_. We shall view the contraction process as a way to add all discovered shortcuts to the edge set E. We obtain a contraction hierarchy (CH).*"
# Existing implementations
(1) Graphhopper (JAVA) [https://github.com/graphhopper/graphhopper]
(2) OSMR (CPP) [https://github.com/Project-OSRM/osrm-backend]
# Bibliography (extracted from wikipedia)
(1) Robert Geisberger [http://algo2.iti.kit.edu/schultes/hwy/contract.pdf]
(2) Rice and Tsotras [http://www.vldb.org/pvldb/vol4/p69-rice.pdf]
(3) Prof. Dr. Hannah Bast's lectures https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012
Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/196Request for feature: Bipartite Graph Projection2018-04-20T07:37:00ZCarlosRequest for feature: Bipartite Graph ProjectionHi,
From our discussion:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Efficient-Bipartite-Projection-tp4025895.html;cid=1417425123974-777
I was told to open an issue for this feature here.
I a...Hi,
From our discussion:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Efficient-Bipartite-Projection-tp4025895.html;cid=1417425123974-777
I was told to open an issue for this feature here.
I am looking for a bipartite graph projection feature. Specifically I have 'g', a weighted graph and would like to have some way that the projections 'g1', and 'g2' to be also a weighted graph. I have been particularly curious on seeing both a way the projections receive on their edges the sum of the weights on graph g as well.
Thank you,
Carlos A. Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/174graph_draw draws the graph upside down if a vertex has more than three self l...2017-07-26T11:47:50ZMaxim Bermangraph_draw draws the graph upside down if a vertex has more than three self loopsUnder graph_tool 2.2.31 '(commit 245d1e2c, Thu Mar 27 11:28:39 2014 +0100)'
Using input XML file
```xml
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xsi="http://www.w...Under graph_tool 2.2.31 '(commit 245d1e2c, Thu Mar 27 11:28:39 2014 +0100)'
Using input XML file
```xml
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<key id="key0" for="node" attr.name="vtext" attr.type="string" />
<graph id="G" edgedefault="undirected" parse.nodeids="canonical" parse.edgeids="canonical" parse.order="nodesfirst">
<node id="n0">
<data key="key0">My Label</data>
</node>
<edge id="e5" source="n0" target="n0" />
<edge id="e7" source="n0" target="n0" />
<edge id="e8" source="n0" target="n0" />
</graph>
</graphml>
```
I get the following image with graph_draw, using the internal vtext property as vertex labels:
![strangefail](https://git.skewed.de/uploads/count0/graph-tool/f495480b3a/strangefail.png)
This inversion occurs both in png output and in the interactive window (and causes problems to the interactive vertex selection). I suspect it is due to the presence of 3 looping edges on the node, it doesn't occur with 1 or 2 self loops.
RegardsTiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/172Maximum cardinality matching for weighted graphs2017-07-26T11:47:50ZPedroMaximum cardinality matching for weighted graphsPlease implement a version for weighted graphs that finds the optimum result, not just a fast heuristic version.
I'm currently using igraph and R, but your library is definitely faster in all aspects. I'm currently working with hundre...Please implement a version for weighted graphs that finds the optimum result, not just a fast heuristic version.
I'm currently using igraph and R, but your library is definitely faster in all aspects. I'm currently working with hundred thousandth edges bipartite graphs, but it will probably scale up in the near future.
Thanks.
PedroTiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/140Cygwin support2017-07-26T11:47:50ZTiago PeixotoCygwin supportI have reported this issue on StackOverflow and thought you would be interested on knowing about and adding cygwin support of the platform at some point.
http://stackoverflow.com/questions/22735669/cygwin-bad-reloc-address-linking-laI have reported this issue on StackOverflow and thought you would be interested on knowing about and adding cygwin support of the platform at some point.
http://stackoverflow.com/questions/22735669/cygwin-bad-reloc-address-linking-laTiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/44Add support for the following random generators: Kleinberg and geometric2017-07-26T11:47:50ZTiago PeixotoAdd support for the following random generators: Kleinberg and geometricKleinberg:
http://www.maths.strath.ac.uk/~aap05145/contest/kleinberg.m
http://www.maths.strath.ac.uk/~aap05145/contest/geo.m
these are part of a nice matlab toolbox:
http://www.maths.strath.ac.uk/~aap05145/contest/home.html
Kleinberg:
http://www.maths.strath.ac.uk/~aap05145/contest/kleinberg.m
http://www.maths.strath.ac.uk/~aap05145/contest/geo.m
these are part of a nice matlab toolbox:
http://www.maths.strath.ac.uk/~aap05145/contest/home.html
Tiago PeixotoTiago Peixoto