ListOfEdgesGraphReader: Handle duplicate edges and/or maintain specified/sorted order about cassovary HOT 4 CLOSED

I see two approaches possible:
a) using smart structure instead of ArrayBuffer[Int] to do dedup during adding neighbours
b) do post processing for sorting or duplicate elimination

I assume that the signature of below function should remain unchanged to makes things easier

def readEdgesBySource(): (Int2ObjectMap[ArrayBuffer[Int]], Int2IntArrayMap) = {

Solution (a) introduces additional memory overhead for keeping both set and list in case of unsorted with duplicates elimination plus some extra memory copying at the end of the processing. It should come in zero cost if neither deduplication nor sorting is applied.

Solution (b) can do the postprocessing on each value in the edgesBySource map. It will cost additional memory per neighbours list (much less than solution (a)). Memory copying will happen also in this case for some cases e.g. dedup with original order.

Time complexity ibn both cases is similar of n * O(klogk) for sorting (when n is number of nodes and k is #of neighbours). Duplicate elimination in both cases is feasible in additional O(m) cost (m = #edges).

Do you have any suggestions which approach to follow?
I have (a) implemented and tested - as it seemed to be more elegant one :-)

from cassovary.

IIUC you are saying that (a) requires at least 2x memory in your implementation as you would keep both a set and a list? If so, that is just too much. You could keep only a SortedSet in (a) and then convert to Array at the end. Alternatively, post-processing as in (b) looks good too.

from cassovary.

Yes, in solution (a) there is twice as much memory used. Unfortunately it is impossible to use only SortedSet(a) if you want to keep the order of neighbours as given in the file. It is possible if we decide that deduplication=true and sort=false is not acceptable.

from cassovary.

Makes sense -- (b) sounds more flexible then, doesn't it?

On Wed, Jul 15, 2015 at 8:23 PM, Tomek Łasica [email protected]
wrote:

Yes, in solution (a) there is twice as much memory used. Unfortunately it
is impossible to use only SortedSet(a) if you want to keep the order of
neighbours as given in the file. It is possible if we decide that
deduplication=true and sort=false is not acceptable.

—
Reply to this email directly or view it on GitHub
#185 (comment).

from cassovary.