graph-tool issueshttps://git.skewed.de/count0/graph-tool/-/issues2020-05-28T19:55:59Zhttps://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...2017-07-10T12:50:57Zwf-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 Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/2subgraph_isomorphism crashes when vertex indices don't start at zero2021-09-08T13:56:16ZTiago Peixotosubgraph_isomorphism crashes when vertex indices don't start at zero
```text
import graph_tool.all as gt
Bug = True
G = gt.complete_graph(10)
print "G: {}".format(", ".join(map(str,G.vertices())))
vfilt = G.new_vertex_property("bool")
for v in G.vertices(): vfilt[v] = True
if Bug:
for i...
```text
import graph_tool.all as gt
Bug = True
G = gt.complete_graph(10)
print "G: {}".format(", ".join(map(str,G.vertices())))
vfilt = G.new_vertex_property("bool")
for v in G.vertices(): vfilt[v] = True
if Bug:
for i in xrange(0,2): vfilt[G.vertex(i,use_index=False)] = False
else:
for i in xrange(8,10): vfilt[G.vertex(i,use_index=False)] = False
G1 = gt.GraphView(G,vfilt=vfilt)
print "G1: {}".format(", ".join(map(str,G1.vertices())))
vmaps, emaps = gt.subgraph_isomorphism(G1,G,max_n=1)
```Tiago PeixotoTiago Peixoto