CODEWITHSUNDEEP
c++algorithmgraph-algorithm
Palace Chan
Palace Chan

Reputation: 9223

How to aggregate cycles in a sequence?

I have a vector of pairs representing hops between nodes which I would like to collapse when there are cycles (as in aggregate time between the hops in a cycle to display it as just one). So, for example, The path A --> B --> C --> D --> B --> C --> D --> E traverses the subpath B--> C --> D twice, so in my structure I would have something like:

(A,B,1)(B,C,3)(C,D,2)(D,B,4)(B,C,5)(C,D,8)(D,E,6)

which I would ideally reduce to:

(A,B,1)(B,C,3+5)(C,D,2+8)(D,E,6)

storing also the 4 from D to B (loop-back edge time) to aggregate separately and be able to display B --> C --> D in a condensed way (the aggregated edge times and an aggregated loop-back time for all the D-->B instances alongside a count of how many times we looped)

How can I go about this?

Upvotes: 1

Views: 120

Answers (2)

xvatar
xvatar

Reputation: 3259

Basically you go through the path, and store each edge like this ( (A, B), 1 ) in a map, and all the discovered node in a set

  • whenever you encounter an edge that has its destination point as an already discovered node, you know it's a loop-back edge.

  • whenever you encounter a same edge, add up its value in your map

Upvotes: 1

Nicolas
Nicolas

Reputation: 960

I would go for a suffix array or suffix tree. Just produce tokens (in this case (from, to) ) and put it in the Suffix Array or Suffix Tree. Then you can get the pairs. Simple but not efficietn way:

produce tokens, produce all suffixes of this tokenstream. sort them. and then you have all common subsequences in that sorted list near each other (tokenstream length - tokenstream suffix length = position) You could do the sorting with quicksort for example, or you just looking for a suffix array implemantation. Suffix Arrays could be constructed in O(n) and with O(n) space. And finding maximal pairs/repeats (thats what you want) can be done in O(n+k) (where n = tokennumber, and k = cycles in your list)

Perhaps this helps. Then you could produce a tokenstream like: ABCDBCDE

Quick and dirty solution is here

Upvotes: 1

Related Questions