FAQ
I'm trying to wrap my head around this piece of code generating graph data
structure.

package main

import (
"fmt"
"io"
"os"
"strconv"
)

type Graph struct {
Edges map[NodeId]map[NodeId]struct{}
Nodes map[NodeId]Node
lastId NodeId
}

type NodeId int

func (id NodeId) String() string {
return "n" + strconv.Itoa(int(id))
}

type Node struct {
Name string
}

func New() *Graph {
return &Graph{
Edges: make(map[NodeId]map[NodeId]struct{}),
Nodes: make(map[NodeId]Node),
lastId: 0,
}
}

func (g *Graph) Add(n Node) NodeId {
g.lastId += 1
g.Nodes[g.lastId] = n
return g.lastId
}

func (g *Graph) Link(from, to NodeId) {
list, ok := g.Edges[from]
if !ok {
list = make(map[NodeId]struct{})
g.Edges[from] = list
}
list[to] = struct{}{}
}

What is exactly the purpose of 'map[NodeId]map[NodeId]struct{}' and maybe
everything could be much more simplified...

-zork

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

## Search Discussions

•  at Mar 31, 2015 at 4:49 pm ⇧
Looks like it's implementing a the edges of a graph as a mapping between a
NodeID and a set of other NodeIDs it points to. There is no built-in "set"
type in Go, so it's common to use a map to implement a set via
map[T]struct{} or map[T]bool. It would probably be simpler to represent
edges as map[NodeID][]NodeID but then you have to be careful not to insert
duplicate NodeIDs when adding edges. That code would probably easier to
read with an extra type like `type NodeSet map[NodeID]bool` so Edges can be
`map[NodeID]NodeSet`.
On Tue, Mar 31, 2015 at 9:34 AM zork wrote:

I'm trying to wrap my head around this piece of code generating graph data
structure.

package main

import (
"fmt"
"io"
"os"
"strconv"
)

type Graph struct {
Edges map[NodeId]map[NodeId]struct{}
Nodes map[NodeId]Node
lastId NodeId
}

type NodeId int

func (id NodeId) String() string {
return "n" + strconv.Itoa(int(id))
}

type Node struct {
Name string
}

func New() *Graph {
return &Graph{
Edges: make(map[NodeId]map[NodeId]struct{}),
Nodes: make(map[NodeId]Node),
lastId: 0,
}
}

func (g *Graph) Add(n Node) NodeId {
g.lastId += 1
g.Nodes[g.lastId] = n
return g.lastId
}

func (g *Graph) Link(from, to NodeId) {
list, ok := g.Edges[from]
if !ok {
list = make(map[NodeId]struct{})
g.Edges[from] = list
}
list[to] = struct{}{}
}

What is exactly the purpose of 'map[NodeId]map[NodeId]struct{}' and maybe
everything could be much more simplified...

-zork

--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 6:22 pm ⇧

On Tuesday, March 31, 2015 at 11:48:50 AM UTC-5, Chris Manghane wrote:
Looks like it's implementing a the edges of a graph as a mapping between a
NodeID and a set of other NodeIDs it points to. There is no built-in "set"
type in Go, so it's common to use a map to implement a set via
map[T]struct{} or map[T]bool.
What are the benefits of using map[T]struct{} over map[T]bool?

It would probably be simpler to represent edges as map[NodeID][]NodeID but
then you have to be careful not to insert duplicate NodeIDs when adding
edges. That code would probably easier to read with an extra type like
`type NodeSet map[NodeID]bool` so Edges can be `map[NodeID]NodeSet`.

On Tue, Mar 31, 2015 at 9:34 AM zork <andy....@gmail.com <javascript:>>
wrote:
I'm trying to wrap my head around this piece of code generating graph
data structure.

package main

import (
"fmt"
"io"
"os"
"strconv"
)

type Graph struct {
Edges map[NodeId]map[NodeId]struct{}
Nodes map[NodeId]Node
lastId NodeId
}

type NodeId int

func (id NodeId) String() string {
return "n" + strconv.Itoa(int(id))
}

type Node struct {
Name string
}

func New() *Graph {
return &Graph{
Edges: make(map[NodeId]map[NodeId]struct{}),
Nodes: make(map[NodeId]Node),
lastId: 0,
}
}

func (g *Graph) Add(n Node) NodeId {
g.lastId += 1
g.Nodes[g.lastId] = n
return g.lastId
}

func (g *Graph) Link(from, to NodeId) {
list, ok := g.Edges[from]
if !ok {
list = make(map[NodeId]struct{})
g.Edges[from] = list
}
list[to] = struct{}{}
}

What is exactly the purpose of 'map[NodeId]map[NodeId]struct{}' and maybe
everything could be much more simplified...

-zork

--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 6:27 pm ⇧

On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:
What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 9:44 pm ⇧
Why isn't map[[2]NodeId]struct{} used here? Is definitely a better
approach, because only one map initialization (make) is required and a
simple for loop can iterate through all edges.

On Tuesday, March 31, 2015 at 8:27:45 PM UTC+2, w...@google.com wrote:
On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:

What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 9:59 pm ⇧
Hmm? What are the values the make up the [2]NodeID? I assume the first
element is the node to start from and the second is the node the edge goes
to, but how would you find that second node?
On Tue, Mar 31, 2015 at 2:44 PM Uli Kunitz wrote:

Why isn't map[[2]NodeId]struct{} used here? Is definitely a better
approach, because only one map initialization (make) is required and a
simple for loop can iterate through all edges.

On Tuesday, March 31, 2015 at 8:27:45 PM UTC+2, w...@google.com wrote:
On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:

What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 10:24 pm ⇧
You are right. A Graph consists of a set V of vertices, aka nodes, and a
set E of edges. An edge connects two nodes and is represented by a pair of
nodes. [2]NodeId stores the pair. The map represents then the set E of
edges.

Note that in an undirected graph the pairs (a,b) and (b,a) represent the
same edge. The edge has no direction.
On Tuesday, March 31, 2015 at 11:59:30 PM UTC+2, Chris Manghane wrote:

Hmm? What are the values the make up the [2]NodeID? I assume the first
element is the node to start from and the second is the node the edge goes
to, but how would you find that second node?

On Tue, Mar 31, 2015 at 2:44 PM Uli Kunitz <uli.k...@gmail.com
<javascript:>> wrote:
Why isn't map[[2]NodeId]struct{} used here? Is definitely a better
approach, because only one map initialization (make) is required and a
simple for loop can iterate through all edges.

On Tuesday, March 31, 2015 at 8:27:45 PM UTC+2, w...@google.com wrote:
On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:

What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 10:50 pm ⇧
I understand [2]NodeID is supposed to represent a pair of nodes, but if you
just store a list of edges what's the point of the mapping you proposed? It
seems you might as well simplify it to [][2]NodeID which is just a list of
edges. The advantage of the other representation is being able to quickly
discover the set of neighboring edges of a particular node as opposed to
creating all possible pairs and seeing if they exist. Not like it matters.
On Tue, Mar 31, 2015 at 3:24 PM Uli Kunitz wrote:

You are right. A Graph consists of a set V of vertices, aka nodes, and a
set E of edges. An edge connects two nodes and is represented by a pair of
nodes. [2]NodeId stores the pair. The map represents then the set E of
edges.

Note that in an undirected graph the pairs (a,b) and (b,a) represent the
same edge. The edge has no direction.
On Tuesday, March 31, 2015 at 11:59:30 PM UTC+2, Chris Manghane wrote:

Hmm? What are the values the make up the [2]NodeID? I assume the first
element is the node to start from and the second is the node the edge goes
to, but how would you find that second node?

On Tue, Mar 31, 2015 at 2:44 PM Uli Kunitz wrote:
Why isn't map[[2]NodeId]struct{} used here? Is definitely a better
approach, because only one map initialization (make) is required and a
simple for loop can iterate through all edges.

On Tuesday, March 31, 2015 at 8:27:45 PM UTC+2, w...@google.com wrote:
On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:

What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.
--
Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
•  at Mar 31, 2015 at 11:19 pm ⇧
There are a bunch of different ways one could represent a graph, the best
one will depend a lot on the way that graph is going to be used. The edge
set representation for directed graphs has advantages in size when you have
a lot nodes with high fan out, or when it's important to be able to
efficiently manipulate all the neighbors of a single node. It has a
limitation that you can't have multiple edges between two nodes.

Shrug.
On Wed, Apr 1, 2015 at 9:50 AM, 'Chris Manghane' via golang-nuts wrote:

I understand [2]NodeID is supposed to represent a pair of nodes, but if
you just store a list of edges what's the point of the mapping you
proposed? It seems you might as well simplify it to [][2]NodeID which is
just a list of edges. The advantage of the other representation is being
able to quickly discover the set of neighboring edges of a particular node
as opposed to creating all possible pairs and seeing if they exist. Not
like it matters.
On Tue, Mar 31, 2015 at 3:24 PM Uli Kunitz wrote:

You are right. A Graph consists of a set V of vertices, aka nodes, and a
set E of edges. An edge connects two nodes and is represented by a pair of
nodes. [2]NodeId stores the pair. The map represents then the set E of
edges.

Note that in an undirected graph the pairs (a,b) and (b,a) represent the
same edge. The edge has no direction.
On Tuesday, March 31, 2015 at 11:59:30 PM UTC+2, Chris Manghane wrote:

Hmm? What are the values the make up the [2]NodeID? I assume the first
element is the node to start from and the second is the node the edge goes
to, but how would you find that second node?

On Tue, Mar 31, 2015 at 2:44 PM Uli Kunitz wrote:
Why isn't map[[2]NodeId]struct{} used here? Is definitely a better
approach, because only one map initialization (make) is required and a
simple for loop can iterate through all edges.

On Tuesday, March 31, 2015 at 8:27:45 PM UTC+2, w...@google.com wrote:
On Tuesday, March 31, 2015 at 11:22:11 AM UTC-7, zork wrote:

What are the benefits of using map[T]struct{} over map[T]bool?
A value of type struct{} takes up zero space, so you get a slight size
advantage. Also the ternary logic of "No such map entry", "Maps to false",
and "Maps to true" adds additional complexity that you don't really need to
deal with, no matter how you choose to map that to a boolean "is/isn't
present" state.
--
Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

## Related Discussions

Discussion Overview
 group golang-nuts categories go posted Mar 31, '15 at 4:34p active Mar 31, '15 at 11:19p posts 9 users 5 website golang.org

### 5 users in discussion

Content

People

Support

Translate

site design / logo © 2021 Grokbase