Some clarifications regarding directness
Hi, Consider the following GraphML file (attached). According to the GraphML file, it represents an undirected graph. Therefore, I would expect that as I set it to directed graph: gtGraph=gt.load_graph("yeast.graphml") gtGraph.set_directed(1) I would obtain two directed edges for every undirected edge. In particular, the in degree of every node should be equal to the out degree. However, this is not the case, for example: v=gtGraph.vertex(1834) v.in_degree() Out[3]: 5 v.out_degree() Out[4]: 2 I'm a bit puzzled. A) Is the source file corrupted? B) When I set the directedness flag to 1, am I guaranteed that every undirected edge would be converted to two directed edges? If not, how can I perform this operation (A = A + A', assuming the adjacency matrix is triangular) or validate it? yeast.graphml <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4026916/yeast.graphml> -- 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.
On 07.12.2016 23:08, bloodymeli wrote:
B) When I set the directedness flag to 1, am I guaranteed that every undirected edge would be converted to two directed edges?
Not at all. The set_directed() function does nothing more than to set a flag indicating the directness, it does not modify the graph in any other way. It is supposed to be an efficient O(1) operation. In particular, the number of edges is exactly the same after the function is called.
If not, how can I perform this operation (A = A + A', assuming the adjacency matrix is triangular) or validate it?
If you want to make the graph bidirectional, you have to iterate through all the edges and add an opposing one for each: edges = list(g.edges()) for e in edges: g.add_edge(e.target(), e.source()) -- Tiago de Paula Peixoto <tiago@skewed.de>
Should not set_directed() redefine the definition of out_neighbours() and in_neighbours()? When I created a simple Erdős–Rényi graph, then change it to a directed graph, out_neighbours() and in_neighbours() do not return the expected edges: import graph_tool.all as gt, numpy as np, numpy.random as rand N = 12 p = 1.5 * np.log(N)/N g = gt.random_graph(N, deg_sampler=lambda: rand.poisson((N-1)*p), directed=False, model='erdos') vroot = g.vertex(0) g.set_directed(False) print([g.edge(vroot,v) for v in vroot.out_neighbours()]) print([g.edge(v,vroot) for v in vroot.in_neighbours()]) g.set_directed(True) print([g.edge(vroot,v) for v in vroot.out_neighbours()]) print([g.edge(v,vroot) for v in vroot.in_neighbours()]) Result: [<Edge object with source '0' and target '3' at 0x1245b9050>, <Edge object with source '0' and target '10' at 0x1245bbf28>, <Edge object with source '0' and target '6' at 0x1245b90e8>] [] [None, None, <Edge object with source '0' and target '6' at 0x1245bf050>] [] You can see that out_neighbours() returns *all* edges, even ones that are inward-pointing, and in_neighbours() fails to return any edges. -- 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.
On 23.02.2017 03:35, Steve wrote:
Should not set_directed() redefine the definition of out_neighbours() and in_neighbours()?
It does.
When I created a simple Erdős–Rényi graph, then change it to a directed graph, out_neighbours() and in_neighbours() do not return the expected edges:
import graph_tool.all as gt, numpy as np, numpy.random as rand N = 12 p = 1.5 * np.log(N)/N g = gt.random_graph(N, deg_sampler=lambda: rand.poisson((N-1)*p), directed=False, model='erdos') vroot = g.vertex(0)
g.set_directed(False) print([g.edge(vroot,v) for v in vroot.out_neighbours()]) print([g.edge(v,vroot) for v in vroot.in_neighbours()]) g.set_directed(True) print([g.edge(vroot,v) for v in vroot.out_neighbours()]) print([g.edge(v,vroot) for v in vroot.in_neighbours()])
Result:
[<Edge object with source '0' and target '3' at 0x1245b9050>, <Edge object with source '0' and target '10' at 0x1245bbf28>, <Edge object with source '0' and target '6' at 0x1245b90e8>] [] [None, None, <Edge object with source '0' and target '6' at 0x1245bf050>] []
You can see that out_neighbours() returns *all* edges, even ones that are inward-pointing, and in_neighbours() fails to return any edges.
What is happening here is that the vertex descriptor is still referring to the original graph. When you do g.set_directed(True), the vroot vertex descriptor still refers to the old graph. To get the result you were expecting you have to do: vroot = g.vertex(0) after you do g.set_directed(). This is done for efficiency reasons, but is somewhat counter-intuitive. I'll add a clear note in the documentation. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
bloodymeli -
Steve -
Tiago de Paula Peixoto