November 2013 - graph-tool - archives.skewed.de

average path length and finding all possible paths between 2 vertices
by hux 22 Nov '13

22 Nov '13

Dear all, I am new to graph tools. I am trying to calculate the average path length (not the shortest) between any 2 given vertices. Which function should I use for that? Also, I would like to create a list of all possible paths between any 2 given vertices. Here I assume the edges are directed in both cases. So far I haven't found proper functions in the documentation for these calculations. I would appreciate any suggestions. Thanks in advance! Hu -- 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 4

./../graph_util.hh:447: error: expected '>'
by Николай Кинаш 22 Nov '13

22 Nov '13

Hi -bash-4.1$ make make all-recursive make[1]: Entering directory ` /home/peroksid/graph-tool-2.2.27 ' Making all in src make[2]: Entering directory `/home/peroksid/graph-tool-2.2.27/src' Making all in graph make[3]: Entering directory `/home/peroksid/graph-tool-2.2.27/src/graph' Making all in centrality make[4]: Entering directory `/home/peroksid/graph-tool-2.2.27/src/graph/centrality' CXX graph_betweenness.lo In file included from ./../graph_filtering.hh:54, from graph_betweenness.cc:18: ./../graph_util.hh:447: error: expected type-specifier ./../graph_util.hh:447: error: expected '>' In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/functional:70, from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/memory:70, from /opt/boost_1_54_0_icc/boost/config/no_tr1/memory.hpp:21, from /opt/boost_1_54_0_icc/boost/get_pointer.hpp:14, from /opt/boost_1_54_0_icc/boost/python/object/pointer_holder.hpp:11, from /opt/boost_1_54_0_icc/boost/python/to_python_indirect.hpp:10, from /opt/boost_1_54_0_icc/boost/python/converter/arg_to_python.hpp:10, from /opt/boost_1_54_0_icc/boost/python/call.hpp:15, from /opt/boost_1_54_0_icc/boost/python/object_core.hpp:14, from /opt/boost_1_54_0_icc/boost/python/object.hpp:9, from ./../graph.hh:23, from ./../graph_filtering.hh:21, from graph_betweenness.cc:18: /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/tr1_impl/functional: In instantiation of 'std::_Maybe_wrap_member_pointer<void>': graph_betweenness.cc:157: instantiated from here /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/tr1_impl/functional:1094: error: forming reference to void /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/tr1_impl/functional: In instantiation of 'std::_Result_of_impl<false, const volatile get_central_point_dominance(boost::adj_list<long unsigned int>&, boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<long unsigned int> >&, double&)>': /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/tr1_impl/functional:149: instantiated from 'std::result_of<const volatile get_central_point_dominance(boost::adj_list<long unsigned int>&, boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<long unsigned int> >&, double&)>' ./../graph_filtering.hh:565: instantiated from 'void graph_tool::detail::action_wrap<Action, Wrap>::operator()(T1*, T2&) const [with T1 = boost::adj_list<long unsigned int>, T2 = boost::checked_vector_property_map<unsigned char, boost::typed_identity_property_map<long unsigned int> >, Action = std::_Bind<get_central_point_dominance(std::_Placeholder<1>, std::_Placeholder<2>, std::reference_wrapper<double>)>, Wrap = mpl_::bool_<false>]' ./../mpl_nested_loop.hh:273: instantiated from 'void boost::mpl::selected_types<Action>::operator()(T1, T2) const [with T1 = boost::adj_list<long unsigned int>*, T2 = boost::checked_vector_property_map<unsigned char, boost::typed_identity_property_map<long unsigned int> >, Action = graph_tool::detail::action_wrap<std::_Bind<get_central_point_dominance(std::_Placeholder<1>, std::_Placeholder<2>, std::reference_wrapper<double>)>, mpl_::bool_<false> >]' ./../mpl_nested_loop.hh:160: instantiated from 'void boost::mpl::nested_for_each<TR1, TR2, TR3, TR4, TR5>::eval_action2<Action, T1>::operator()(T2) const [with T2 = boost::checked_vector_property_map<unsigned char, boost::typed_identity_property_map<long unsigned int> >, Action = boost::mpl::selected_types<graph_tool::detail::action_wrap<std::_Bind<get_central_point_dominance(std::_Placeholder<1>, std::_Placeholder<2>, std::reference_wrapper<double>)>, mpl_::bool_<false> > >, T1 = boost::adj_list<long unsigned int>*, TR1 = graph_tool::detail::graph_action<std::_Bind<get_central_point_dominance(std::_Placeholder<1>, std::_Placeholder<2>, std::reference_wrapper<double>)>, graph_tool::detail::never_reversed, mpl_::bool_<false>, boost::mpl::v_item<boost::typed_identity_property_map<long unsigned int>, boost::mpl::v_item<boost::checked_vector_property_map<long double, boost::typed_identity_property_map<long unsigned int> >, boost::mpl::v_item<boost::checked_vector_property_map<double, boost::typed_identity_property_map<long unsigned int> >, boost::mpl::v_item<boost::checked_vector_property_map<long int, boost::typed_identity_property_map<long unsigned int> >, boost::mpl::v_item<boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, boost::mpl::v_item<boost::checked_vector_property_map<short int, boost::typed_identity_property_map<long unsigned int> >, boost::mpl::v_item<boost::checked_vector_property_map<unsigned char, infinity strings like this: ::na>, boost::mpl::vector<mpl_::na, mpl_::na,....::na>, boost::mpl::vector<mpl_::na, mpl_::na, At the end: <unsigned char, boost::typed_identity_property_map<long unsigned int> > > > >, boost::unchecked_vector_property_map<long double, boost::adj_edge_index_property_map<long unsigned int> >, boost::unchecked_vector_property_map<long double, boost::typed_identity_property_map<long unsigned int> >, _Result = void, _Functor = get_betweenness, _Bound_args = std::_Placeholder<1>, boost::typed_identity_property_map<long unsigned int>, std::_Placeholder<2>, std::_Placeholder<3>, bool, long unsigned int] At global scope: cc1plus: warning: unrecognized command line option "-Wno-unused-local-typedefs" make[4]: *** [graph_betweenness.lo] Error 1 make[4]: Leaving directory `/home/peroksid/graph-tool-2.2.27/src/graph/centrality' make[3]: *** [all-recursive] Error 1 make[3]: Leaving directory `/home/peroksid/graph-tool-2.2.27/src/graph' make[2]: *** [all-recursive] Error 1 make[2]: Leaving directory `/home/peroksid/graph-tool-2.2.27/src' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory `/home/peroksid/graph-tool-2.2.27' make: *** [all] Error 2 Any suggeshion? The same problems for ICC comilers. In attach configure output and log.

2 2

Parallel Processing
by Derek Ditch 21 Nov '13

21 Nov '13

I want to use graph-tool using the multiprocessing library in Python 2.6. I keep running into issues though with trying to share a full graph object. I can store the graph in a multiprocessing.Namespace, but it doesn't keep the dicts of properties. Example: def initNS( ns ): _g = Graph( directed = False) ns.graph = _g ns.edge_properties = { 'genres': _g.new_edge_property("vector<string>"), 'movieid': _g.new_edge_property("int"), } ns.vertex_properties = { 'personid': _g.new_vertex_property("int32_t") } """ Build property maps for edges and vertices to hold our data The graph vertices represent actors whereas movies represent edges """ # Edges _g.edge_properties["genres"] = ns.edge_properties['genres'] _g.edge_properties["movieid"] = ns.edge_properties['movieid'] # Vertices _g.vertex_properties["personid"] = ns.vertex_properties['personid'] ns.graph = _g ########## This initializes 'ns', which is a multiprocessing.Namespace. The problem is that for example, ns.edge_properties[ * ] tells me that the type isn't pickle-able. I tried to just skip that and use the _g.edge_properties to access it, but those dicts aren't carried over to the different process in the pool. Presumably b/c they aren't pickle-able. Any thoughts about how to fix this? (For those interested, I'm attempting to use the IMDbPy library to do some graph analysis on the relationships among actors and movies. Each process has it's own db connection and trying to populate the graph with actor and movie information in parallel since it's a pretty large and dense graph. Somewhere in the neighborhood of 250,000+ vertices for just a depth of three relationships) Thanks, -- Derek

3 7

Multiline text
by John Reid 21 Nov '13

21 Nov '13

Hi, Is there any functionality for multiline vertex or edge text? Thanks for a great package, John.

2 1

Citation
by Anatol Wegner 18 Nov '13

18 Nov '13

Hi, Is there a prefered way to cite /acknowledge the use of grpah-tool in a research paper? Regards, A.W.

2 1

About extract communities from a graph
by vcongz 14 Nov '13

14 Nov '13

After using community_structure(), each vertex in the graph has a community property. However, how to extract some certain communities from this graph ? Such as, the graph G contains communities {1,2,3,4,5}, now, I hope to get and save a sub-graph which contains the vertices and their edge in communities {2,4,5} of G ? Is there any continent and fast function or algorithm in graph_tool to solve this problem ? -- 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.

2 8

Incorrect path for cairommconfig.h in RHEL 6.4
by nhusted＠gmail.com 08 Nov '13

08 Nov '13

The cairommconfig.h include path in graph_cairo_draw.cc is incorrect for RHEL 6.4's cairomm-1.0 package. I've included a simple fix at the bottom of the post if the developers choose to use it. I've also included the package versions for gcc and cairomm for developer reference. Packages: cairomm-1.8.0-2.1.el6.x86_64 cairomm-devel-1.8.0-2.1.el6.x86_64 gcc-4.4.7-3.el6.x86_64 gcc-c++-4.4.7-3.el6.x86_64 --- --- graph-tool-2.2.26-ORIGINAL/src/graph/draw/graph_cairo_draw.cc 2013-10-20 05:15:51.000000000 -0700 +++ graph-tool-2.2.26/src/graph/draw/graph_cairo_draw.cc 2013-11-08 08:27:55.379892995 -0800 @@ -32,7 +32,7 @@ #include "tr1_include.hh" #include TR1_HEADER(unordered_map) -#include <cairommconfig.h> +#include <cairomm/cairommconfig.h> #include <cairomm/context.h> #include <cairomm/surface.h> #include <pycairo/pycairo.h>

2 1

problem with using a loaded graph (graphml)
by Tasos 08 Nov '13

08 Nov '13

Hello, I have a problems using a loaded graphml graph. my graphml look like this: /////// <?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="ref" attr.type="long" /> <key id="key1" for="edge" attr.name="weight" attr.type="double" /> <graph id="G" edgedefault="undirected" parse.nodeids="canonical" parse.edgeids="canonical" parse.order="nodesfirst"> <node id="n0"> <data key="key0">0</data> </node> <node id="n1"> <data key="key0">1</data> </node> //////// <edge id="e0" source="n0" target="n1"> <data key="key1">0.1</data> </edge> <edge id="e1" source="n0" target="n16"> <data key="key1">1.08661</data> </edge> <edge id="e2" source="n0" target="n205"> <data key="key1">1.17957</data> </edge> //////// // What I do g_uDirG = Graph(directed=False) eprop_ang_weight = g_uDirG.new_edge_property("float") g_uDirG = load_graph(xml_filename) // Prints about the loaded graph Num of Nodes 7269 Num of Edges 16526 ref (vertex) (type: int64_t) weight (edge) (type: long double) //// // copy the edge weights eprop_ang_weight = g_uDirG.edge_properties["weight"] // run betweenness graph_tool.centrality.betweenness(g_uDirG, vprop=vprop_betweenness, weight=eprop_ang_weight , norm=False) /////////// The problem is that I get '0' in the distances of shortest paths and I get betweeness 'nan' for all vertices. What am I missing? Thanks T -- 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.

2 3

Katz centrality calculation
by xenil 08 Nov '13

08 Nov '13

Hi, I'm testing the Katz centrality function in order to use in a project. In order to calculate the Katz centrality and following the graph_tool documentation I supposed that you use: (I - \alpha A) x = \beta x = \beta / (I - \alpha A) = (I + \alpha A + \alpha^2 A^2 + ... ) \beta where I is the identity matrix and there was appllied the geometric series expansion. My first test was to take a simple circular directed graph with 4 nodes. I used the attached test program with the attached graph file. The adjacency matrix for this graph, A, is: 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 I used distinct values of the max_iter parameter and I set \alpha=1. I use 4 unitary vectors as beta parameter in order to obtain the contents of the calculation matrix (I + \alpha A + \alpha^2 A^2 + ... ), I'll call the F matrix. The test results are for \alpha=1: a) max_iter=1, F matrix is: 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 expected matrix, F = I b) max_iter=2, F matrix is: 0.7 0.0 0.5 0.5 0.5 0.7 0.0 0.5 0.5 0.5 0.7 0.0 0.0 0.5 0.5 0.7 when the expected matrix, F = I + A, is: 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 c) max_iter=3, F matrix is: 0.7 0.0 0.5 0.5 0.5 0.7 0.0 0.5 0.5 0.5 0.7 0.0 0.0 0.5 0.5 0.7 the same as for case max_iter=2 when the expected matrix, F = I + A + A^2, is: 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 d) max_iter=4, F matrix is: 0.52 0.30 0.63 0.48 0.48 0.52 0.30 0.63 0.63 0.48 0.52 0.30 0.30 0.63 0.48 0.52 when the expected matrix, F = I + A + A^2 + A^3, is: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 The first finding was that a normalization is done during the intermediate steps of the calculation because the diagonal elements are changing of value. I look at the graph_katz.hh file and i havesome questions: a) Line 72: c_temp[v] += alpha * get(w, *e) * c[s]; when w is not specified, What w value is used? The normalized adjacency matrix value? b) Line 87: c_temp[v] /= norm; after the swap of the line 90. Could be this the intermediate step nomralization? Is this correct? Thanks in advance, David. katz.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> test4.xml <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> -- 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.

2 7

Compilation problem (boost related)
by bminano 08 Nov '13

08 Nov '13

Hi, I am compiling the library in my Ubuntu 11.10. Not possible to upgrade by now. I have boost 1.46. Compiling with gcc 4.6.1. The compilation thows the following error: /usr/include/boost/range/join.hpp:63:60: error: 'template<class SinglePassRange1, class SinglePassRange2> boost::joined_range<const SinglePassRange1, const SinglePassRange2> boost::join(const SinglePassRange1&, const SinglePassRange2&)' conflicts with previous using declaration 'template<class SequenceSequenceT, class Range1T> typename boost::range_value<SequenceSequenceT>::type boost::algorithm::join(const SequenceSequenceT&, const Range1T&)' Please, could any help me to find the problem? -- 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 2