graph-tool July 2021

graph-tool@skewed.de

8 participants
11 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

Model specification and extraction of layer-specific partitions in LayeredBlockState when overlap=True
by arttu.malkamaki＠helsinki.fi 25 Jan '22

25 Jan '22

Hello, I'm studying political coalitions over time (three time slices) and across discrete types of relationships (collaboration, ideological similarity, and discursive similarity). Since graph-tool offers (the only) principled approach that does not require arbitrary user-specified parameters (such as 'resolution' or 'coupling'), I would very much like to use it for my analysis. I'm trying to fit a SBM to a graph with edges divided into distinct layers (three time slices X three types of relationships). Each edge has a discrete weight in the range of [0, 3], with weight referring to the 'strength' of the relationship. Not all nodes participate in all layers. I'm interested in how/if the block membership varies across layers that I expect to be somewhat dependent on one another (hence I would like to avoid fitting a separate SBM to each layer). In my ideal scenario, I would be using the NestedBlockState with LayeredBlockState as base and allowing for overlaps across layers: state=NestedBlockState(g, base_type=LayeredBlockState, state_args=dict(deg_corr=True, overlap=True, layers=True, ec=g.ep.layer, recs=[g.ep.weight], rec_types=["discrete-binomial"])) dS, nmoves=0, 0 for i in range(100): ret=state.multiflip_mcmc_sweep(niter=10) dS+=ret[0] nmoves+=ret[1] print("Change in description length:", dS) print("Number of accepted vertex moves:", nmoves) mcmc_equilibrate(state, wait=1000, mcmc_args=dict(niter=10), verbose=True) bs=[] def collect_partitions(s): global bs bs.append(s.get_bs()) mcmc_equilibrate(state, force_niter=10000, mcmc_args=dict(niter=10), verbose=True, callback=collect_partitions) pm=PartitionModeState(bs, nested=True, converge=True) pv=pm.get_marginal(g) bs=pm.get_max_nested() state=state.copy(bs=bs) Two questions: Q1) This is taking very long (days) on a high performance cluster and actually I haven't seen it finishing up for once. Is my model specification correct or simply too complex? If the latter, is there a better strategy to perform my analysis? All I can think of is to revert to a non-nested model and/or reduce the number of layers and/or edges: state=LayeredBlockState(g, deg_corr=True, overlap=True, layers=True, ec=g.ep.layer, recs=[g.ep.weight], rec_types=["discrete-binomial"]) dS, nattempts, nmoves=state.multiflip_mcmc_sweep(niter=1000) print("Change in description length:", dS) print("Number of accepted vertex moves:", nmoves) mcmc_equilibrate(state, wait=1000, nbreaks=2, mcmc_args=dict(niter=10), verbose=True) bs=[] def collect_partitions(s): global bs bs.append(s.b.a.copy()) mcmc_equilibrate(state, force_niter=10000, mcmc_args=dict(niter=10), verbose=True, callback=collect_partitions) pm=PartitionModeState(bs, converge=True) pv=pm.get_marginal(g) Q2) Say that the model runs and yields a neat NestedBlockState (or LayeredBlockState) object with X overlapping blocks, 9 layers, degree-corrected, with 2 edge covariates, for graph <Graph object, undirected, with 220 vertices and 11322 edges, 2 internal vertex properties, 4 internal edge properties>. Now, in previous posts there are mentions about the number of nodes multiplying by the number of layers when 'overlap=True', but in my experiments with only two layers, this does not seem to be the case and I struggle to find a way to extract the layer-specific block and respective memberships of nodes. I've tried iteration over vertices, but what I eventually need is a 2d_array [y=all nodes in g, x=all layers in g, values=most likely block membership] in order to map how/if the block membership of each node varies across those layers in which they participate (ideally somehow denoting non-participation in the layer with NaN or some unique value). Is there some way to get there? l=state.get_levels()[0] #NestedBlockState B=l.get_nonempty_B() bv=l.get_overlap_blocks()[0] z=np.zeros((g.num_vertices(), B)) #to be filled with most likely block membership with potential overlaps across ALL layers, but I need the layer-specific information for i in range(g.num_vertices()): z[int(i), :len(z[v])]=bv[i].a+1 for v in range(g.num_vertices()*max(g.ep.layer)+1): #to see if the number of vertices multiplied by layers, which it didn't print(bv[v]) Many thanks, Arttu

2 15

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

Fixed vertex size between different layouts
by Botond Molnár 03 Aug '21

03 Aug '21

Hello, I am trying to plot a few networks using two different layouts. The vertex sizes and edge width are calculated separately, then each networks is plotted using two different layouts: radial tree layout and sfdp layout. In both cases the same pre-calculated values are used to set the vertex sizes and edge width, in order to maintain the comparability of the plots. However, I end up with different vertex sizes and edge width in function of the chosen layout. I am using the cairo backend, so I can plot both layouts next to each other, but the ax sizes are the exactly the same. Can you please help me how can I sort this out? Thank you in advance, Botond

2 1

Adding property maps of custom types
by sebyakin.a 03 Aug '21

03 Aug '21

Hello, My question is: which parts of a code I should modify to add internal property maps of custom type? Is it possible without ground-breaking modifications, or should I look a way for some workaround? My usecase is to bridge python integer objects and big integer objects (from intx library) on c++ side, as a vertex property. I'm going to perform relatively heavy math operations and graph operations, so I want to write a C++ extension that does it. So I thought, is it possible to add custom property map handlers for big integers, that will convert python long objects to intx type and store it in that type later.

2 5

Best approach for calculating shortest distance tree from a location in between two vertices
by Mathias Versichele 27 Jul '21

27 Jul '21

Hi, I'm wondering what the best approach would be for calculating shortest distances from a point on an edge in between that edge's start and end vertex. The way I see it, there's two options: a) "split" the edge at the wanted location: so basically adding two new (shorter) edges; the original edge can be removed, but I guess leaving it in wouldn't change results b) - calculate Dijkstra from the start vertex and for each reachable node add the fixed cost for reaching the start vertex - same for end vertex - combine these two distance maps to get the minimum distance for each reachable node Apart from the feasibility, I can foresee problems along the road (no pun intended): a) I have a multi-threaded setup, and modifying the network from a single thread could cause all kinds of weird concurrency issues ? b) extra calculation costs: extra Dijkstra + combining the two distance maps (is there a fast approach for this ?) Any tips here, anyone who was faced with the same issue ? Thx !

1 0

Hide filtered vertices in interactive display
by anton-tot＠hotmail.fr 18 Jul '21

18 Jul '21

Hi, I want to interactively display a filtered graph whose filter is updated based on mouse events (eg when the user presses a vertex, it then display/remove its neighbors) The problem i have is that when hovering over the window with the mouse, I am still able to select or highlight a filter vertex. Is there an easy way to fully hide the filtered vertices? Thanks.

2 1

Question about recent optimizations
by Davide Cittaro 09 Jul '21

09 Jul '21

Hello, I read that since version 2.40 some optimizations have been implemented to speedup the inference. I used to run a number of concurrent minizations to find partition overlaps, this is handled by joblib which spawns n concurrent tasks (with the loki backend). I'm possibly experiencing some performance degradation (still investigating, though), possibly due to OMP "colliding" with joblib. Which optimizations were introduced in version 2.40? At what level? Thanks d

2 2

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

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool July 2021