fofao_funk's blog

Way of Storing Edges
By fofao_funk, history, 8 years ago, In English

Hi all.

I've came across this way of storing edges in many codes:

void addEdge(int u, int v) {
    head[edges] = v;
    prev[edges] = last[u];
    last[u] = edges++;
}

How does it work? Why is it used over the 'traditional' array of vectors?

I appreciate your help!

  • Vote: I like it
  • +37
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Its basically the same. It's used because the array of vectors is slower. Personally I have never used it because I find it "ugly" and have never had problem with TL because of graph representation.

→ Reply
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Good day to you.

You basically have array of edges, where each edge has "pointer" to parent (i.e. previous edge FROM same node) {you might also want TARGET {head in your code} node + PRICE + anything else you want}. You also have to keep (last array) an array with a "pointer" to "TOP" edge from each node.

So basically when you want to iterate over all edges FROM a node, you take look to the "LAST" array and keep iterating over the "pointers" {PREV in your code}.

It might be harder to understand + to operate with. Yet, it is slightly faster + it can be used in languages with no "vector"-like structure .

The memory cost is O(N+M) with no other overhead, which is also nice.

Good Luck!

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

Well, this way of has its pros and cons... I prefer to use it only when solving flow problems. For example, you may want to find quickly the edge, which goes in the opposite direction. If you add edges in pairs, the opposite of E is E^1.

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

Could you please give a link to a full solution with this representation ?

→ Reply