Int pairs

5k3105 commented

2016-06-27 22:27:09 +00:00

(Migrated from github.com)

Hi,

I use pairs of ints which are id's for my data. These are 'maps' - relations between two data. What data structure do you suggest I use? Treemap.Map would seem slow for lookup because I can only Get by Key and I'd like to Get by Key or Value.

If I use 2 lists or 2 sets the int pairs will not align.

Should I just use a 2 dimensional int slice? [][]int{}

Thanks.

Hi, I use pairs of ints which are id's for my data. These are 'maps' - relations between two data. What data structure do you suggest I use? Treemap.Map would seem slow for lookup because I can only Get by Key and I'd like to Get by Key or Value. If I use 2 lists or 2 sets the int pairs will not align. Should I just use a 2 dimensional int slice? [][]int{} Thanks.

👍 1

emirpasic commented

2016-06-27 23:52:16 +00:00

(Migrated from github.com)

@5k3105

It seems to me that you are in need of a bidirectional map, if I understood correctly.

I have all intention of implementing that data structure, since it had helped me a few times in the past (albeit Java implementation). It won't take long, give me a few days to find some free time and implement it.

For now, you can use two maps (HashMap if you don't care about keys ordering). First map is for mapping first value to second, and the second map the second value to the first. This is somewhat ugly, since you have to care of consistency of those two maps (if you delete in one, you have to delete in the other, same goes with adding). This is ugly, but it will work.

I'll notify you when the bidirectional map is done in GoDS.

Cheers

@5k3105 It seems to me that you are in need of a [bidirectional map](https://en.wikipedia.org/wiki/Bidirectional_map), if I understood correctly. I have all intention of implementing that data structure, since it had helped me a few times in the past (albeit Java implementation). It won't take long, give me a few days to find some free time and implement it. For now, you can use two maps (HashMap if you don't care about keys ordering). First map is for mapping first value to second, and the second map the second value to the first. This is somewhat ugly, since you have to care of consistency of those two maps (if you delete in one, you have to delete in the other, same goes with adding). This is ugly, but it will work. I'll notify you when the bidirectional map is done in GoDS. Cheers

👍 1

5k3105 commented

2016-06-28 16:02:07 +00:00

(Migrated from github.com)

Yes. This looks great!

nkev commented

2016-07-01 02:15:03 +00:00

(Migrated from github.com)

What about if there are more than 2, where each can lookup any other? Is there a such a thing as n-directional map?

emirpasic commented

2016-07-01 02:45:19 +00:00

(Migrated from github.com)

@nkev

To my best knowledge, I haven't heard of that. At least not in that terminology, but the structure that can support that is simply a graph.

Specifically speaking, the closest type of graph I can think of is a tripartite graph or some variation of it.

Initially, I had the intention of covering graphs before trees, since trees are acyclic specializations of graphs. However, I didn't want to get into graph theory madness that would consume me. The challenge is intriguing, so I hope to do it one day, hopefully with somebody's help that has a better understanding of graphs than me.

@nkev To my best knowledge, I haven't heard of that. At least not in that terminology, but the structure that can support that is simply a graph. Specifically speaking, the closest type of graph I can think of is a tripartite graph or some variation of it. ![image002](https://cloud.githubusercontent.com/assets/3115942/16510353/80404984-3f45-11e6-9aba-4259768fa9fc.jpg) Initially, I had the intention of covering graphs before trees, since trees are acyclic specializations of graphs. However, I didn't want to get into graph theory madness that would consume me. The challenge is intriguing, so I hope to do it one day, hopefully with somebody's help that has a better understanding of graphs than me.

emirpasic commented

2016-07-01 06:07:02 +00:00

(Migrated from github.com)

@5k3105

You can now use the bidirectional map in GoDS, e.g:

package main

import "github.com/emirpasic/gods/maps/hashbidimap"

func main() {
    m := hashbidimap.New() // empty
    m.Put(1, "x")          // 1->x
    m.Put(3, "b")          // 1->x, 3->b (random order)
    m.Put(1, "a")          // 1->a, 3->b (random order)
    m.Put(2, "b")          // 1->a, 2->b (random order)
    _, _ = m.GetKey("a")   // 1, true
    _, _ = m.Get(2)        // b, true
}

Over the course of the few next day I will implement also another bidirectional map implementation using the red-black tree that will be more memory efficient.

Let me know if this works for you.

Cheers

@5k3105 You can now use the bidirectional map in GoDS, e.g: ``` go package main import "github.com/emirpasic/gods/maps/hashbidimap" func main() { m := hashbidimap.New() // empty m.Put(1, "x") // 1->x m.Put(3, "b") // 1->x, 3->b (random order) m.Put(1, "a") // 1->a, 3->b (random order) m.Put(2, "b") // 1->a, 2->b (random order) _, _ = m.GetKey("a") // 1, true _, _ = m.Get(2) // b, true } ``` Over the course of the few next day I will implement also another bidirectional map implementation using the red-black tree that will be more memory efficient. Let me know if this works for you. Cheers

5k3105 commented

2016-07-01 15:32:15 +00:00

(Migrated from github.com)

What about if there are more than 2, where each can lookup any other? Is there a such a thing as n-directional map?

Maybe he was talking about Multi-index Container (http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/index.html)?

Let me know if this works for you.

Yes! This looks like it will work. Thank you!

> What about if there are more than 2, where each can lookup any other? Is there a such a thing as n-directional map? Maybe he was talking about Multi-index Container (http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/index.html)? > Let me know if this works for you. Yes! This looks like it will work. Thank you!

emirpasic commented

2016-07-02 08:20:41 +00:00

(Migrated from github.com)

Maybe he was talking about Multi-index Container

It could be, but I am not 100% sure. One could make something similar with multi-index container, but it more looks like a graph to me, at least in my head.

On another note, I'll keep this issue open until the TreeBidiMap is implemented as an alternative to HashBidiMap.

> Maybe he was talking about Multi-index Container It could be, but I am not 100% sure. One could make something similar with multi-index container, but it more looks like a graph to me, at least in my head. On another note, I'll keep this issue open until the TreeBidiMap is implemented as an alternative to HashBidiMap.

Rows
Columns

Int pairs #22