_Muhammad's blog

How to erase edge from adjacency list of an undirected graph in O(1) for eular tour?
By _Muhammad, history, 5 years ago, In English

Assalamualikum!

For finding eular cycle we need to erase edges from graph. But I don't know how to erase edges in O(1) for undirected graph. I can only erase edges in O(log(n)) using C++ set for adjacency list instead of vector.

But I need to erase edges in O(1) so that my eular cycle finding algorithm will run in O(N) instead of O(Nlog(N)). Please tell me how to do it.

Thanks In Advance.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All the times that I had to so something like that I always used vectors, and they always performed better than sets, you can try yourself in local.

g[i].erase(find(g[i].begin(),g[i].end(),val));
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    But time complexity of find() is up to linear in the distance between first and last compares elements until a match is found. So time complexity will be up to O(n^2) in worst case.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Using set is unnecessary. vector can be thought of as a stack (and you can pop stuff off the stack in amortized O(1)). Just iterate through your adjacency list from back to front.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    But how it will work for undirected graph? Here we have to delete both u -> v and v -> u edge.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Give every edge an id so u -> v and v -> u have same id. Then if you encounter an edge id you have already encountered, you can pop it without processing it.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        Praise be to Allah! Got it. I thank both of you. :)

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just use linked lists or std::list so you can remove edges in $$$O(1)$$$ time. I implemented this kind of adjacency list in my solution to Tanya and Password which requires you to find Eulerian path in a directed graph.

For undirected graphs, there are ways to setup edges so that each edge contains a pointer to the reverse edge, meaning that when you delete one edge, you can also delete the node containing the reverse edge as well.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Well, you actually don't :)), at least right away. I erase the node (or edge) in a lazy manner. Firstly, in the adjacency list, I also store the edge's ID beside the node. Secondly, I declare a global array removed to mark removed edges. When you remove an edge, just mark it as removed. And then when you try to get the next edge to go to, you just continue to iterate the adjacency list of the current node until you find the unremoved one.

→ Reply