json - 用 JSON 表示图形

Question

灵感来自 this问题，我正在尝试用 JSON 表示 DAG。我的案例包括包含一些数据的边和节点(而不仅仅是本示例中的字符串)。我在想这样的规范:

{
    "graph": {
        "a": ["b", "c"],
        "b": ["c"]
        "c"
    },

    "nodes": {
        "a": {
            "name": "Adam"
        },
        "b": {
            "name": "Bob"
        },
        "c": {
            "name": "Caillou"
        }
    },

    "edges": {
        // how to do the same for edges?
        // ie: how to query edges ?
    }
}

我的一个想法是让边的键成为它连接的两个顶点 id 的串联。例如， ab , ac , 和 bc是该图中的三个边。我想知道是否有更标准的方法来做到这一点。

编辑:这就是我现在在想的

{
    "graph": {
        "a": {
            "data": {
                // a's vertex data
            },
            "neighbors": {
                "b": {
                    "data": {
                        // data in edge ab
                    }
                },
                "c": {
                    "data": {
                        // data in edge ac
                    }
                }
            }
        },
        "b": {
            "data": {
                // b's vertex data
            },
            "neighbors": {
                "c": {
                    "data": {
                        // data in edge bc
                    }
                }
            }
        },
        "c": {
            "data": {
                // c's vertex data
            }
        }
    }
}

Answer 1

由于 DAG 的边保存数据，因此它们最好有自己的标识符，就像节点一样。也就是说，json 表示应该由三个组件组成:

节点记录:将每个节点标识符映射到节点的数据。

边缘记录:将每个边标识符映射到边的数据。

邻接表:将每个节点标识符映射到一个边标识符数组，每个标识符对应一条离开节点的边。

DAG = {
  "adjacency": {
    "a": ["1", "2"],
    "b": ["3"]
  },
  "nodes": {
    "a": {
      // data
    },
    "b": {
      // data
    },
    "c": {
      // data
    }
  },
  "edges": {
    "1": {
      "from": "a", "to": "b",
      "data": {
        // data
      }
    },
    "2": {
      "from": "a", "to": "b",
      "data": {
        // data
      }
    },
    "3": {
      "from": "b", "to": "c",
      "data": {
        // data
      }
    }
  }
}