0
$\begingroup$

Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size <= V. If I understand correctly, this is a cache oblivious algorithm since no information about the memory configuration is provided. Moreover, even if we suppose that every memory access in this algorithm produces a cache miss (the number of cache misses per line is given in comments), we would still have O(V+E) memory transfers, so I postulate this would be a worst case complexity upper bound under the CO-model. Is this correct?

def dfs(G, s):
    visited = [False for v in G] # V
    stack = [s] # 1
    nxt = [0 for v in G] # V
    degree = [len(v) for v in G] # V + E
    while stack:
        v = stack.pop(-1) # 1
        visited[v] = True # 1
        while nxt[v] < degree[v] and visited[G[v][nxt[v]]]: # 6
            nxt[v]+=1 # 1
        if nxt[v] < lens[v]: # 2
            stack.append(v) # 1
            stack.append(G[v][nxt[v]]) # 3

def main():
    #  e.g. dfs order of this graph is 0 1 2 3
    #
    #  0 -> 2
    #  | \  ^
    #  |  \ |
    #  v   v
    #  3 -> 1
    #
    G = [[1,3,2],[2],[],[1]]
    dfs(G,  0)
$\endgroup$
  • $\begingroup$ If an algorithm executes $O(f(n))$ statements each of which costs $O(1)$ (time, memory access, ... any additive cost measure works here), then the whole algorithm costs $O(f(n))$. That much is obvious just from the definition of Landau-$O$. So what't the question, really? $\endgroup$ – Raphael Nov 2 '16 at 7:57
  • $\begingroup$ Yes, "Big-Oh" is not suitable for analyses of this kind. You'll have to look more closely. $\endgroup$ – Raphael Nov 2 '16 at 7:58
  • $\begingroup$ @Rapahel Thanks. Actually, Arge et al [1] proposed cache oblivious graph traversal algorithms (DFS/BFS) based of buffered repository trees that match the I/O model bound of O((V+E/B)*lg V + sort(E)) memory transfers (B=block size). What I fail to understand is how this is better than the straightforward O(v+E) bound. [1] Arge et al. An optimal cache-oblivious priority queue and its applications to graph algorithms. SIAM J. Comput, 2005. $\endgroup$ – Paulo Nov 2 '16 at 13:41
  • $\begingroup$ I don't, either. I don't even understand what that O-term is supposed to mean. Is B constant? If not, what's it's limiting process? Imho, there's too much abuse of notation and no useful statement at all. $\endgroup$ – Raphael Nov 3 '16 at 23:15
  • $\begingroup$ In the external memory I/O model, B is the "block size" (like in B-trees). In the cache-oblivious model, this is equivalent to the length of a cache line, a fixed parameter (the other is M, the # of cache lines) that is however unknown to the algorithm. The general goal is to devise algorithms that perform just as well w.r.t #memory accesses, without issuing explicit I/O operations (being thus oblivious to the memory), but rather accessing data directly from the cache and relying on an "ideal" cache replacement mechanism. $\endgroup$ – Paulo Nov 4 '16 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.