OASIS Static Analysis Results Interchange Format (SARIF) TC

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.sourceNodeId s.   OTOH, if the graph is large, it might be burdensome to compute node.edgeIds from the set of all edge.sourceNodeId s.   Thoughts?   Larry

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.   http://schemas.microsoft.com/vs/2009/dgml/dgml.xsd   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.   Michael From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast) Sent: Friday, March 30, 2018 3:44 PM To: sarif@lists.oasis-open.org Subject: [sarif] Another graph design issue: Do we need node.edgeIds   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.sourceNodeId s.   OTOH, if the graph is large, it might be burdensome to compute node.edgeIds from the set of all edge.sourceNodeId s.   Thoughts?   Larry

TL;DR: Let’s take DGML’s route and get rid of node.edgeIds .   Random thoughts:   I took a few minutes to study the DGML schema and the DOT wiki page. Yes, DGML is similar to our design, with their “link” playing the role of our “edge”.   Yes, I see how you could represent a simple DOT directed graph with an array of array of node ids, and yes, that would preclude adding properties to the edges. In any case, as visually appealing and efficient as the notation “ a -> b -> c ” is, visual appeal has never been a design goal of SARIF