Uploaded image for project: 'Flink'
  1. Flink
  2. FLINK-4965

AllPairsShortestPaths

    XMLWordPrintableJSON

Details

    Description

      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.

      Attachments

        Issue Links

          depends upon

          New Feature - A new feature of the product, which has yet to be developed. FLINK-3695 ValueArray types

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed
          is depended upon by

          New Feature - A new feature of the product, which has yet to be developed. FLINK-4966 BetweennessCentrality

          • Not a Priority -
          • Closed

          Activity

            People

              Unassigned Unassigned
              greghogan Greg Hogan
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: