graph-tool June 2021

graph-tool@skewed.de

8 participants
10 discussions

How to control the orientation of the graph topology
by Xun Xiao 26 Feb '22

26 Feb '22

Hi Tiago, sometimes, when delete the graph and create a new one, then plot it, the plotted graph is shown upside down (in terms of the node text). So how could we control the orientation of the graph? Or which parameter we should use to always make node text shown in a correct orientation. Thanks a lot. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

3 5

Upside down labels
by charlie 26 Feb '22

26 Feb '22

Hi, I'm suffering from the same issue mentioned in this post: https://git.skewed.de/count0/graph-tool/issues/174 Namely, I'm trying to draw a graph that includes a lot of self-looping edges, and my labels are being printed upside down. If I remove the self-loops the labels are shown the right way up. Is there a fix for it? Thanks, Charlie -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

3 3

random graph
by JM 01 Sep '21

01 Sep '21

Dear Tiago, I have a directed graph of about half a million nodes and approximately a million edges following scale free behaviour and a power law degree distribution. To test some of my hypothesis, I would like to generate random smaller graphs (about 50 up to 200 nodes) representative of the big one. When I used a sample function that samples straight away from the real distribution of the big network, I have following problems: - I generate unconnected nodes with both 0 in AND out degree. - I generate small sub parts of a few nodes that are not connected to the main graph. - If only sampling from nodes with at least 1 degree, the generated graph is coherent, but not representative anymore as I need a big portion of nodes with either only one in or one out degree. Here is the part of my script I used for that, where samples are drawn from dictionaries of the degrees: def sample_in(): a=np.random.randint(num) k_in = in_degrees[a] return k_in def sample_out(): if sample_in()==0: b=np.random.randint(num_out) k_out=out_zero_zeros.values()[b] return k_out else: b=np.random.randint(num) k_out=out_degrees[b] return k_out N=200 g=gt.random_graph(N, lambda:(sample_in(), sample_out()), model="constrained-configuration", directed=True) I also tried sampling from a list of tuples as you have mentioned before in the forum, but I didn't receive any results, as the tuples randomly drawn from my list might not be combinable. degs=[(7,1),(4,3),(5,6),(2,4),(6,8),(2,0),(3,5),(0,3),(2,7),(2,1)] g = gt.random_graph(4, lambda i: degs[i], directed=True) - Is there any option I could active that would help me in those cases I described above? - Is there a better way how to create representative small networks? Any help on that issue will be much appreciated. Best wishes, Jana -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

3 5

Expected memory usage for large-scale road networks
by Mathias Versichele 05 Jul '21

05 Jul '21

Hi, I've been using graph-tool for the last year or so for calculating shortest-path trees on large-scale road networks. We used to do this in a postgres database with the pgrouting extension, but were continually confronted with unacceptable startup costs. The switch to a python module using graph-tool has considerably sped up our routing queries, but we are suffering from this service using too much memory. I have the feeling I might be using graph-tool in a wrong way, but before I dive into that, it would be good to know what is the expected memory footprint for my use case. Take for example a road network with 30Mio edges and 31 Mio nodes (the combined road network of Belgium, Netherland, France and Germany in OSM). For this road network, I need to calculate shortest paths using different edge weights (edge property map). What would be a very rough estimate how much memory this would use ? For the network only + per edge-property-map. In our setup, there would be one edge-property-map with edge weights per country. We're currently seeing usage of over 50Gb easily, spiking even higher when we're loading extra cost structures or networks. Is that expected ? Or am I experiencing memory leaks somewhere ? How I'm using graph-tool right now: *1) loading network* *nw = dataframe with edges info in the structure: startnode-id, endnode-id, edge-id, country* G = gt.Graph(directed=True) G.ep["edge_id"] = G.new_edge_property("int") G.ep["country_id"] = G.new_edge_property("int16_t") eprops = [G.ep["edge_id"], G.ep["country_id"]] n = G.add_edge_list(nw.to_numpy(), hashed=True, eprops=eprops) G.vertex_properties["n"] = n *2) loading edge costs: I'm using GraphViews* *countries = list of country-codes* edge_filter = np.in1d(G.ep["country_id"].a, [get_country_id(c) for c in countries]) GV = gt.GraphView(G, efilt=edge_filter) edges = GV.get_edges([GV.edge_index]) sources = G.vertex_properties["n"].a[edges[:,0]] targets = G.vertex_properties["n"].a[edges[:,1]] idxs = edges[:,2] *db_costs = pandas dataframe with structure: source, target, cost* sti = np.vstack((idxs,sources,targets)).T sti_df = pd.DataFrame({'idx': sti[:, 0], 'source': sti[:, 1], 'target': sti[:, 2]}) m = pd.merge(sti_df, db_costs, on=['source', 'target'], how='left', sort=False)[['idx', 'c']] wgts_list = m.sort_values(by=['idx']).T.iloc[1].to_numpy() wgts_list = np.where(wgts_list==np.nan, np.iinfo(np.int32).max, wgts_list) wgts = GV.new_edge_property("int32_t") wgts.fa = wgts_list wgts.fa = np.where(wgts.fa==-2147483648, np.iinfo(np.int32).max, wgts.fa) GV.edge_properties[cs_ids_str] = wgts GV2 = gt.GraphView(GV, efilt=wgts.fa != np.inf) *3) I then use GV2 for calculating Dijkstra and such...* I could of course work on an MWE of some sorts. But would be very nice to get an estimate on mem footprint, and to see if I'm doing sth really silly in the code above. Thx!

2 4

property map values are not loaded for .graphml graph
by bnikparv＠gmail.com 28 Jun '21

28 Jun '21

Hi, I have saved a graph in Networkx with .graphml format. I can successfully load the graph in graph-tool and I can see the edge property attached to graph. However, when I try to access the values I get an error that the property does not exist. G = gt.load_graph('gdrive/MyDrive/ColabNotebooks/Thesis/sources/k4p3-2-test.graphml') G.properties {('e', '_graphml_edge_id'): <EdgePropertyMap object with value type 'string', for Graph 0x7f0347bd2950, at 0x7f0347d2a4d0>, ('e', 'etype'): <EdgePropertyMap object with value type 'int32_t', for Graph 0x7f0347bd2950, at 0x7f0347d2af50>, ('v', '_graphml_vertex_id'): <VertexPropertyMap object with value type 'string', for Graph 0x7f0347bd2950, at 0x7f0347d2aa50>} e = G.edges().next() etype[e] NameError: name 'etype' is not defined

2 1

Problem on bipartite-networks with label
by filippo.valle＠edu.unito.it 28 Jun '21

28 Jun '21

I am using [SBMtopicmodeling](https://github.com/martingerlach/hSBM_Topicmodel) to inference partition on bipartite networks After a recent graph-tool update I noticed there is a problem with **state_args** in minimize_nested_blockmodel_dl step to reproduce: given a trivial bi-partite network, with VertexProperty **kind** that imposes the bi-partition clabel = g.vp['kind'] state_args = {} state = gt.minimize_nested_blockmodel_dl(g, state_args=state_args) finds partitions but when I impose bi-partition clabel = model.g.vp['kind'] state_args = {'clabel': clabel, 'pclabel': clabel} state = gt.minimize_nested_blockmodel_dl(g, state_args=state_args) it fails to find any partition. What could be the problem?

2 1

Graph tool Maximum cardinality Matching error
by Chaitanya Agarwal 16 Jun '21

16 Jun '21

Hi This email is in reference to the thread: https://archives.skewed.de/hyperkitty/list/graph-tool@skewed.de/thread/VVDN… As I had said earlier, I cannot share my code with you. I have instead saved and attached the graph with this email. I am not able to run the optimal maximum matching algorithm on this graph. However, I am able to run the heuristic algorithm. I would like to run the optimal algorithm as well. Please let me know if there is some error with this graph format or if there is some error with the library itself. Code to reproduce: from graph_tool.all import Graph, load_graph graph = load_graph("temp.xml.gz") max_cardinality_matching(graph, weight=graph.edge_properties["weight"], bipartite=False, heuristic=False, edges=True) I'm sorry I couldn't reply to the thread itself as I wasn't able to figure out a way to attach a file to the existing thread. Thanks and Regards Chaitanya Agarwal

1 0

Fail to build on macOS with boost 1.76
by da.sumin＠gmail.com 15 Jun '21

15 Jun '21

Using various options to build graph-tool on macOS (brew and generic build), I'm getting the following error: ``` In file included from ./graph_avg_correlations.hh:21: ./graph_correlations.hh:113:22: error: no template named 'greater' in namespace 'boost::mpl'; did you mean simply 'greater'? typename mpl::greater<typename mpl::sizeof_<Type1>::type, ^~~~~~~~~~~~ greater ``` Is it some update in boost (I'm using the latest 1.76) or another issue? Thanks for the help!

2 1

Maximum-Matching using graph-tool
by chaitanyaagarwal291＠gmail.com 06 Jun '21

06 Jun '21

Hi I am working on a project where I need to use the maximum cardinality matching algorithm. My graphs are complete and weighted. However, even for moderately large graph instances, I am facing a segmentation fault error. I have complete graphs with 400-5000 vertices (I would like to run the algorithm on much bigger graphs too). The algorithm works fine for smaller instances. It seems that this is a memory issue. My machine has more than enough memory to run such instances (16 GB). Further, earlier I wasn't even able to run graphs with 100-200 nodes. I was able to run them after changing the edge weight property type from "double" to "int_16". Please let me know if there is something else I can do to run this code. It's a pretty large and distributed codebase, so it would be difficult for me to post my code for reference over here. On the other hand, if you feel that this is an issue with the library itself, please fix it. Thanks and Regards Chaitanya Agarwal

2 3

Generate SBM with edge weights
by Davide Cittaro 01 Jun '21

01 Jun '21

Hello, I need some hints about generating graphs using gt.generate_sbm. I had myself used it to generate a random graph given a predefined modular structure passing blocks and their connectivities. I have now a more complicated problem: I'm inferring communities from a complete weighted graph and I want to generate random graphs using the inferred structure. Is it possible to generate the graph with edge weights modeled after the types used to define the original BlockState? Best, d

2 3

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool June 2021