[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: RE: [sarif] Another graph design issue: Do we need node.edgeIds
This is a good catch! Either nodes can describe their outgoing edges only(by describing all the nodes they link to), or we remove the edge ids from the nodes, as the edge objects define the source/targets for each edge. If we take the former case, a graph traversal could simply consist of the set of node ids in proper order. If the latter, we’d have edge ids.
The first idea is interesting because we dispense with an edge concept. The second idea is compelling because it naturally ensures no graph traversal propose a link between two nodes that isn’t mirrored in the comprehensive definition of the graph.
I see that DGML takes the nodes definitions + link defs approach.
DOT is interesting. Look at the digraph example and how it efficiently defines linkage between nodes. We could play this trick in JSON as well with an array of node id arrays to define the graph <g>. But there’d be no easy way to label the edges with this approach.
Here’s what I wrote about node.edgeIds:
A node object SHALL have a property named edgeIds whose value is an array of unique (§3.6.2) strings, each of which identifies an edge that starts at this node. Thus, each string in the array SHALL be equal to the sourcedNodeId property (§3.27.4) of one of the edge objects (§3.27) in the graph object (§3.25) in which it occurs. Likewise, the value of every such sourceNodeId SHALL occur in the edgeIds array.
That is, you don’t strictly need node.edgeIds; you could derive it by looking at every edge object and selecting those whose sourceNodeId property matched node.id. And then you wouldn’t have to worry about consistency between the node.edgeIds and the edge.sourceNodeIds.
OTOH, if the graph is large, it might be burdensome to compute node.edgeIds from the set of all edge.sourceNodeIds.