Matthias Ekman | 2 Mar 09:02 2012

paths output from search algorithms?

Hi,


is there a way to get the actual paths itself - instead of the distance - from the search algorithms like e.g. dijkstra_search?

As a related question, in a weighted adjacency matrix, how are the weights interpreted for dijkstra and centrality functions (pagerank, betweenness centrality) that rely on it. Is it low weight = easier to "travel", or is it the other way around?

Thanks in advance!
 Matthias
_______________________________________________
graph-tool mailing list
graph-tool <at> skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool
Tiago de Paula Peixoto | 2 Mar 09:20 2012
Picon

Re: paths output from search algorithms?

On 03/02/2012 09:02 AM, Matthias Ekman wrote:
> Hi,
>
> is there a way to get the actual paths itself - instead of the
> distance - from the search algorithms like e.g. dijkstra_search?

You can use the shortest_path() function.

    http://projects.skewed.de/graph-tool/doc/topology.html#graph_tool.topology.shortest_path

Otherwise you can write your own search visitor which records the path
for you.

> As a related question, in a weighted adjacency matrix, how are the
> weights interpreted for dijkstra and centrality functions (pagerank,
> betweenness centrality) that rely on it. Is it low weight = easier to
> "travel", or is it the other way around?

The weights are always _minimized_, unless otherwise stated. Note that
in Pagerank the weights are used differently, since there is no shortest
path computation in this case (see its documentation for more details).

Cheers,
Tiago

--

-- 
Tiago de Paula Peixoto <tiago <at> skewed.de>

_______________________________________________
graph-tool mailing list
graph-tool <at> skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool
Matthias Ekman | 2 Mar 11:21 2012

Re: paths output from search algorithms?

Thank you Tiago!

On Friday, March 2, 2012 9:20:27 AM UTC+1, Tiago de Paula Peixoto wrote:

On 03/02/2012 09:02 AM, Matthias Ekman wrote:
> Hi,
>
> is there a way to get the actual paths itself - instead of the
> distance - from the search algorithms like e.g. dijkstra_search?

You can use the shortest_path() function.

    http://projects.skewed.de/graph-tool/doc/topology.html#graph_tool.topology.shortest_path

Otherwise you can write your own search visitor which records the path
for you.

> As a related question, in a weighted adjacency matrix, how are the
> weights interpreted for dijkstra and centrality functions (pagerank,
> betweenness centrality) that rely on it. Is it low weight = easier to
> "travel", or is it the other way around?

The weights are always _minimized_, unless otherwise stated. Note that
in Pagerank the weights are used differently, since there is no shortest
path computation in this case (see its documentation for more details).

Cheers,
Tiago

--
Tiago de Paula Peixoto <tiago <at> skewed.de>

_______________________________________________
graph-tool mailing list
graph-tool <at> skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool

_______________________________________________
graph-tool mailing list
graph-tool <at> skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool

Gmane