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.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Chris Manghane 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
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
  • Zork 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
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
  • Wgd 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.
    For more options, visit https://groups.google.com/d/optout.
  • Uli Kunitz 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.
    For more options, visit https://groups.google.com/d/optout.
  • Chris Manghane 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
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
  • Uli Kunitz 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
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
  • Chris Manghane 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.
    --
    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...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
  • Charles Haynes 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.
    --
    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...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.
    --
    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.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMar 31, '15 at 4:34p
activeMar 31, '15 at 11:19p
posts9
users5
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase