Feature suggestion: extensions to igraph_path_length_hist() for weighted and vertex-subset case #919

Open
szhorvat opened this Issue Feb 8, 2016 · 1 comment

Projects

None yet

2 participants

@szhorvat
Contributor
szhorvat commented Feb 8, 2016

This is a feature request to provide some extensions of the igraph_path_length_hist() functionality (possibly implemented as a separate function):

  1. Allow weighted path lengths. This would be a very different function as one would need to specify a bin size for histogramming when path lengths are not guaranteed to be integers.
  2. Allow computing the histogram only for a subset of the start and end vertices (just like igraph_shortest_paths()).

Why is this useful if we already have functions to compute the distance matrices (igraph_shortest_paths(), igraph_shortest_paths_dijkstra(), etc.)? Because igraph_path_length_hist() works even when the distance matrix is too large to keep in memory. On my computer I can run the histogramming function for a 40000-vertex graph, but I cannot run the distance matrix computation without running out of memory.

@ntamas ntamas added Wishlist C labels Feb 8, 2016
@ntamas
Member
ntamas commented Feb 8, 2016

igraph_shortest_paths_dijkstra() could probably be used as a workaround until this is implemented properly - just run it with a single source vertex, for each of the vertices in your graph. This way you only have to keep a single row of the distance matrix in memory.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment