CODEWITHSUNDEEP
pythonalgorithmdata-structuresgraph
João Júlio
João Júlio

Reputation: 25

Adjacency Map - How to remove a edge from a Graph

I'm in this problem for hours, because I can't find a method that can remove the edges from a adjacency map graph in O(1) time.

If anyone has any idea, it would be very helpful.

Upvotes: 0

Views: 1123

Answers (2)

ilim
ilim

Reputation: 4547

To remove a vertex v from an adjacency map G, you would need to access all u such that there exists an edge (u, v).

Alternative to the other solution proposed by Ecto, you can keep a reverse graph G_reverse, where all the edges are reversed. So, for each edge (u, v), you can have (v, u) in this secondary adjacency map. Then, when you wish to remove all edges from G that connect v to some other node u, you can simply look into G_reverse[v], which would contain all the vertices u that have an outgoing edge to v in G.

Below is a sample implementation of the concept I described.

def remove(G, G_reverse, v):
    for u in G_reverse:
        del G[u][v] // Remove the incoming edges

    for u in G[v]:
        del G_reverse[u][v] // Delete reverses of the outgoing edges

    del G[v] // Removes the outgoing edges
    del G_reverse[v] // Remove the reverses of the incoming edges

As a final note, you may want to change the title and the description of your question to better reflect the problem. What you want seems to be the removal of all edges relevant to a particular vertex, so that each such edge is removed in O(1) time. Unfortunately the question text does not actually reflect that, and it may be misleading to people who will be searching for similar answers here.

Upvotes: 1

Ecto
Ecto

Reputation: 1147

You should have HashMap (or dict in python) with Keys some kind of Node-index and Values to be for example HashSet (or set in python) of Node-indexes, edges from given Key node reach to. For example {1: {2, 3}, 2: {1, 3}, 3: {1}} means, you have 3 nodes: 1, 2, 3 and eges are: [1, 2], [1, 3], [2, 1], [2, 3], [3, 1] - assuming it's directed graph. If you want to remove edge let's say 2, 3, obtain key (starting node of the edge) from your hashmap in O(1) time: something like graph.get(2) which will return you your value - hashSet of Nodes edges lead to, in this case {1, 3}. From this set, you can remove 3 (end node) again in O(1) time.

Repeat this process for all edges you may have.

Upvotes: 1

Related Questions