Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-3827

Reduce the time complexity of finding in-edges of a vertex in the graph

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.23.0
    • Component/s: core

      Description

      In the current graph implementation, it takes O(1) time to find the out-edges of a vertex, but O(e) time (where e is the total number of edges in the graph) to find the in-edges of a vertex.

      In some scenarios (e.g. clearing cache in hep planner), this may have severe performance penalty. To solve this problem, we add a inward edge table, in addition to the existing outward edge table, to the graph. This helps to reduce the time complexity for finding in-edges to O(1).

      Please note that, there is extra performance overhead for maintaining the in edge table, when adding/deleting vertices to the graph. However, the added overhead only takes O(1) time.

      Finally, it should be noted that, some existing operations can benefit from this improvement (e.g. topological sort).

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                julianhyde Julian Hyde
                Reporter:
                fan_li_ya Liya Fan
              • Votes:
                0 Vote for this issue
                Watchers:
                7 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 2h 50m
                  2h 50m