Graph updating algorithm

Question

I have a (un-directed) graph represented using adjacency lists, e.g.

a: b, c, e
b: a, d
c: a, d
d: b, c
e: a

where each node of the graph is linked to a list of other node(s)

I want to update such a graph given some new list(s) for certain node(s), e.g.

a: b, c, d

where a is no longer connected to e, and is connected to a new node d

What would be an efficient (both time and space wise) algorithm for performing such updates to the graph?

Answer 1

Maybe I'm missing something, but wouldn't it be fastest to use a dictionary (or default dict) of node-labels (strings or numbers) to sets? In this case update could look something like this:

def update(graph, node, edges, undirected=True):
    # graph: dict(str->set(str)), node: str, edges: set(str), undirected: bool
    if undirected:
        for e in graph[node]:
            graph[e].remove(node)
        for e in edges:
            graph[e].add(node)
    graph[node] = edges

Using sets and dicts, adding and removing the node to/from the edges-sets of the other nodes should be O(1), same as updating the edges-set for the node itself, so this should be only O(2n) for the two loops, with n being the average number of edges of a node.

Answer 2

Using an adjacency grid would make it O(n) to update, but would take n^2 space, regardless of how sparse the graph is. (Trivially done by updating each changed relationship by inverting the row and column.)

Using lists would put the time up to O(n^2) for updating, but for sparse graphs would not take a huge time penalty, and would save a lot of space.

Answer 3

A typical update is del edge a,e; add edge a,d, but your update looks like a new adjacency list for vertex a. So simply find the a adjacency list and replace it. That should be O(log n) time (assuming sorted array of adjacency lists, like in your description).