flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Greg Hogan (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-4965) AllPairsShortestPaths
Date Sun, 30 Oct 2016 12:22:58 GMT
Greg Hogan created FLINK-4965:

             Summary: AllPairsShortestPaths
                 Key: FLINK-4965
                 URL: https://issues.apache.org/jira/browse/FLINK-4965
             Project: Flink
          Issue Type: New Feature
          Components: Gelly
    Affects Versions: 1.2.0
            Reporter: Greg Hogan
            Assignee: Greg Hogan

Add a Gelly implementation of {{AllPairsShortestPaths}} to complement the existing {{SingleSourceShortestPaths}}.

Flink algorithms excel at processing big, sparse data. APSP is big, really big, but not at
all sparse. Considering only undirected graphs, each component of size {{n}} will have {{n
choose 2}} shortest paths (1,000 vertices => ~million paths, 1,000,000 vertices => ~trillion
shortest paths).

Considerations are directed vs undirected and weighted vs unweighted graphs. The actual shortest
path (not merely the distance) is required for follow-on algorithms such as betweenness centrality.

This message was sent by Atlassian JIRA

View raw message