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.