douweicheng5532
2019-08-16 22:13 浏览 150

将节点列表转换为图形

I am trying to convert a list of nodes in Go to a graph representation. This example is a 1<- 2 <-3 structure but I always get a 1 <- 2 as the result and the 2<-3 is not included as it is not a parent node in the final list.How do I ensure that the reference is updated correctly for the child node's reference.

A node is defined like the struct below:

type Node struct {
    Name       string `json:"name"`
    UUID       string `json:"uuid"`
    ParentUUID string `json:"parentUuid"`
    ParentName string `json:"parentName"`
    Node       []Node
}

This is my implementation so far

func BuildTree(nodeList []models.Node) []models.Node {
    //build hashmap with reference to all nodes in the list
    nodeHashMap := make(map[string]NodeHash)
    for index, node := range nodeList {
        nodeHash := NodeHash{}
        nodeHash.NodeRef = &nodeList[index]
        nodeHash.Uid = node.UUID
        if len(node.ParentUUID) == 0 {
            nodeHash.IsParent = true
        }

        nodeHashMap[node.UUID] = nodeHash
    }

    //link all the nodes with parent nodes
    for _, node := range nodeList {
        if len(node.ParentUUID) != 0 {
            if parentHashNode, ok := nodeHashMap[node.ParentUUID]; ok {
                parentNodeRef := parentHashNode.NodeRef
                parentNodeRef.Node = append(parentNodeRef.Node, node)
            }
        }
    }

    //build a new list with only the parent nodes which is like the "root" level for the graph
    newNodeList := []models.Node{}
    for _, v := range nodeHashMap {
        if v.IsParent {
            newNodeList = append(newNodeList, *v.NodeRef)
        }
    }
    return newNodeList
}

I am trying to call this method like this:

node1 := models.Node{UUID:"1",Name: "parent"}
node2 := models.Node{UUID:"2",Name: "child",ParentUUID:"1"}
node3 := models.Node{UUID:"3",Name: "grandchild",ParentUUID:"2"}

nodeList := []models.Node{}
nodeList = append(nodeList,node1)
nodeList = append(nodeList,node2)
nodeList = append(nodeList,node3)
nodeTreeList := BuildTree(nodeList)
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答 默认 最新

  • 已采纳
    dongsha1544 dongsha1544 2019-08-16 22:40

    You have child nodes ([]Node) as value, not reference. So you add node 2 to node 1:

    node1 -> node2

    Then you add node3 to node2:

    node2 -> node3

    But since you have nodes by value, you never added node3 to the copy of node2 attached to node1, only to the node2 that is in the original array.

    Change the declaration to:

    Node []*Node
    
    点赞 评论 复制链接分享

相关推荐