graph-tool December 2020

graph-tool@skewed.de

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

get_hierarchy_control_points return values
by Davide Cittaro 20 Apr '21

20 Apr '21

Hi again, I'm writing a small package that builds on graph-tool, but not on its graphics capabilities (also because I have to represent other things rather than the graph itself). Still I could use some of the functions "under the hood" for my purposes. I have a question about gt.draw.get_hierarchy_control_points(): the function returns the Bézier spline control points for edges in a given graph, but I'm having difficulties in understanding how this information is encoded. For a single edge in graph, I have dozens of values as control points (half dozens + 2), hence I suspect all splines going from node A to the root of a hierarchy and back to node B are encoded there, and control points should be taken 6 by 6 (3x2 by 3x2 coordinates?). How (x,y) for control points are encoded then: (x, x, x, y, y, y) or (x, y, x, y, x, y)? What are the 2 additiona values I have for each vector? Also, are values absolute or relative to one node in particular (A, B or root...)? Thanks d

4 10

Find best paths sorted by length with graph tools
by Ruhm 18 Dec '20

18 Dec '20

Hello, I'm a beginner in graph algorithm, and I have trouble to find an efficient solution for my issue. My goal is to find X best paths between two vertices. Not only the shortest paths, but sub optimals path, ordered by length. My graph is relatively small (10k vertices, 20k edges) and is not directed. I don't use weight or vertices/edges attributes. My current prototype: I use first all_shortest_paths to find the best paths. Then I use all_paths with a cutoff = length of shortest_path + K . K is an arbitrary value set as an argument of my function. Finally, I sort the return of all_paths by path length and select the X shortest. It works fine when the vertices are close to each other, but when my cutoff is over 20ish, the all_paths function take forever and my CPU usage skyrockets. I can't even iterate with next() over the result. I understand that all_paths is not very effective in my case, but at the moment this is my best guess. I'm reading the documentation of graph tools, but I cant find any other function fitting my needs. I 'm considering using the function bfs_search with a custom BFSVisitor, but I'm afraid i will encounter performance issues too. Am i missing something? Anyways, thanks for this library, its impressive. Sorry for my poor English. Regards -- Sent from: https://nabble.skewed.de/

2 1

Find best paths sorted by length with graph tools
by Franco Peschiera 17 Dec '20

17 Dec '20

Good day, I can give some feedback on this since I've also used graph-tool for getting paths. In my case it was slightly different because (1) I wanted to sample paths without bias, (2) I used a weight on the arcs, (3) my arcs were directed and (4) the number of nodes and edges was really big . Sadly, (1) and (2) made it not very easy to do it via graph tool. As far as I understand, graph tool uses a DFS to obtain `all_paths`. When the number of potential paths is large for a given cutoff but the remaining number of valid paths is small, it will iterate a long time (at each `next()`) until it proves there are no more paths that have a length equal or smaller to the cutoff. You could choose to stop the iteration once it starts taking longer than certain time to find a path, but even this is no guarantee. There may be many paths still remaining to be found. You can also play with the number of paths to return... Another thing you should take into account if you want to stop `all_paths` at a limit number of paths is that since it does a DFS, two paths that are close in the returned list will be "close" in structure (i.e., similar). So "sampling" paths this way is not great. Sorry I cannot be of more help. If you find a better way to do it with graph-tool, please share it over here! Good luck! Franco On Wed, Dec 16, 2020 at 12:00 PM <graph-tool-request(a)skewed.de> wrote: > Send graph-tool mailing list submissions to > graph-tool(a)skewed.de > > To subscribe or unsubscribe via the World Wide Web, visit > https://lists.skewed.de/mailman/listinfo/graph-tool > or, via email, send a message with subject or body 'help' to > graph-tool-request(a)skewed.de > > You can reach the person managing the list at > graph-tool-owner(a)skewed.de > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of graph-tool digest..." > > > Today's Topics: > > 1. Find best paths sorted by length with graph tools (Ruhm) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 15 Dec 2020 08:22:24 -0700 (MST) > From: Ruhm <romain.da-costa-vieira(a)itsfactory.fr> > To: graph-tool(a)skewed.de > Subject: [graph-tool] Find best paths sorted by length with graph > tools > Message-ID: <1608045744698-0.post(a)n3.nabble.com> > Content-Type: text/plain; charset=us-ascii > > Hello, > > I'm a beginner in graph algorithm, and I have trouble to find an efficient > solution for my issue. > > My goal is to find X best paths between two vertices. Not only the shortest > paths, but sub optimals path, ordered by length. > My graph is relatively small (10k vertices, 20k edges) and is not directed. > I don't use weight or vertices/edges attributes. > > My current prototype: > I use first all_shortest_paths to find the best paths. > Then I use all_paths with a cutoff = length of shortest_path + K . K is an > arbitrary value set as an argument of my function. > Finally, I sort the return of all_paths by path length and select the X > shortest. > > It works fine when the vertices are close to each other, but when my cutoff > is over 20ish, the all_paths function take forever and my CPU usage > skyrockets. I can't even iterate with next() over the result. I understand > that all_paths is not very effective in my case, but at the moment this is > my best guess. > > I'm reading the documentation of graph tools, but I cant find any other > function fitting my needs. I 'm considering using the function bfs_search > with a custom BFSVisitor, but I'm afraid i will encounter performance > issues > too. > > Am i missing something? > > Anyways, thanks for this library, its impressive. > Sorry for my poor English. > > Regards > > > > -- > Sent from: https://nabble.skewed.de/ > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > graph-tool mailing list > graph-tool(a)skewed.de > https://lists.skewed.de/mailman/listinfo/graph-tool > > > ------------------------------ > > End of graph-tool Digest, Vol 155, Issue 4 > ****************************************** >

1 0

Graphs into layers
by Lietz, Haiko 15 Dec '20

15 Dec '20

Hi all, If I have two graphs g and h with internal edge property maps, how can I make these the layers of a graph i? g = Graph(directed=False) g.add_vertex(4) g_weight = g.new_ep('int') g_layer = g.new_ep('int') g.add_edge_list([[0, 1, 2, 0], [2, 3, 2, 0]], eprops=[g_weight, g_layer]) g.edge_properties['weight'] = g_weight g.edge_properties['layer'] = g_layer h = Graph(directed=False) h.add_vertex(4) h_weight = h.new_ep('int') h_layer = h.new_ep('int') h.add_edge_list([[1, 2, 1, 1]], eprops=[h_weight, h_layer]) h.edge_properties['weight'] = h_weight h.edge_properties['layer'] = h_layer This works but is not nice and gets lengthy when layers are many: i = g.copy() # make deep copy i.add_edge_list(h.edges()) # this does not add the edge properties i.ep.weight.a[-h.num_edges():] = h.ep.weight.a # manually add the edge weight i.ep.layer.a[-h.num_edges():] = h.ep.weight.a # manually add the edge layer Is there a better way? I'm using gt 2.29 from conda-ostrokach. Many thanks Haiko

2 1

Dimension of graph_tool.stats.vertex_hist
by Ben Hong 05 Dec '20

05 Dec '20

I found that the returns of counts and bins have different dimensions , it seems strange. -- Sent from: https://nabble.skewed.de/

2 1

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool December 2020