Why Graph does not recognize chains of vertexes like NetGraph

Question

Cross posted on Wolfram Community.

---

Perfect logic:

NetGraph[{1, 1, 1}, {1 -> 2 -> 3}]

But this does not make sense:

Graph[{1, 1, 1}, {1 -> 2 -> 3}]

How can Rule behave differently when called by different functions?

Answer 1

For a convenient notation, use IGraph/M

I agree that the verbosity of the notation required in Graph is slightly annoying.

Consider using the IGShorthand function from IGraph/M. It is designed precisely to deal with this.

IGShorthand["1-2-3"]

IGShorthand["1->2->3"]

IGShorthand["1->2<-3"]

There are other supported notations too within IGShorthand. For more details, and many more examples, check the IGraph/M documentation.

Why does Graph not support this concise notation?

If NetGraph supports this concise notation, why doesn't Graph? Notice that NetGraph uses only integers or strings to refer to layers. This makes it possible to extend the notation without introducing ambiguities.

But Graph supports arbitrary expressions as vertex names.

{1,2} -> 3 in NetGraph is short for 1->3, 2->3 (in IGShorthand: 1:2 -> 3). In Graph, this would mean connect the vertex named {1,2} to the vertex named 3.

If you write 1->2->3, this is equivalent to 1 -> (2->3), thus Graph would create two vertices 1 and 2->3. This is not even very unreasonable. Think of line graphs, whose vertices are the edges of another graph.

The reason why IGShorthand is able to use such a concise notation is that it imposes the same restriction as NetGraph: it only allows integer or string vertex names, avoiding ambiguities. This is a tradeoff: quick input, but little flexibility in vertex naming.

A side note

You are using Graph[{1,1,1}, ...] in your example. Do not repeat vertex names. This is wrong and invalid. One would expect Mathematica to either throw an error or to simply eliminate duplicate vertices, but what happens in reality is that you will end up with a Graph that has a broken internal representation and can cause incorrect results.

Here's a question about this:

• Why equivalent Graph objects yield different results?

This bug is still present in Mathematica 11.3.

Answer 2

The first argument to Graph is a list of vertices; you're giving it the same element three times (1). Graph expects a list of edges in various ways. You're giving it {1->2->3}, which in FullForm reads

{1 -> 2 -> 3} == List[Rule[1,Rule[2,3]]]

So you create a graph with one explicitly-given vertex 1, and one indirectly-defined vertex Rule[2,3].

Edit: a neat way to see this immediately is by entering

Graph[{1, 1, 1}, {1 -> 2 -> 3}] // FullForm

NetGraph has a different argument format, so I guess it boils down to the fact that the functions are different, hence they expect their edge list in different formats.

/ J

Answer 3

Problems With Graph Edge Operators

The situation is even worse than you describe and happens to involve a whole handful of Mathematica quirks.

The edge operators have a unique nonstandard behavior (quirk #1).

a\[DirectedEdge]b\[UndirectedEdge]c
Syntax::tsntxi: "a\[DirectedEdge]b\[UndirectedEdge]c" is incomplete; more input is needed.

The same behavior is observed with any combination of the *Edge operators. These are the only binary operators in Mathematica that exhibit this behavior. Inserting parentheses resolves the syntax error:

In[1]:=  a\[DirectedEdge](b\[UndirectedEdge]c)  //FullForm
Out[1]=  DirectedEdge[a,UndirectedEdge[b,c]]

In[2]:=  (a\[DirectedEdge]b)\[UndirectedEdge]c  //FullForm
Out[2]=  UndirectedEdge[DirectedEdge[a,b],c]

...but unfortunately, just as with your Rules notation, this will not work.

Before we move on to the next brick wall, this is a good place to mention that TwoWayRule's two different notations <-> and \[TwoWayRule] have different operator precedence. (Quirk #2.)

Problems With The Graph Function

The reason your use of Rules notation doesn't work is the same reason parenthesizing *Edge operators doesn't work: Graph isn't smart enough to understand our intended meaning of the parenthesized expression (quirk #3) and instead creates an edge with one vertex having the other edge as its name:

That the notation a\[DirectedEdge]b\[UndirectedEdge]c is a syntax error is either a bug or else someone had to work hard to make edges work differently from every other binary operator in Mathematica in order for it to behave in this unintuitive way. Likewise, not being able to use a->b->c (Rules) with Graph is either an obvious bug or a deliberate but unintuitive design decision. Since they had already allowed Rule to define edges, and since Rule is right associative (parenthesizes to the right), they had to make a choice of whether or not they would allow a vertex to make the inner rule the name of a vertex, as it would be if it were anything else, or another edge, as we would like it to be.

Note the irony that *Rule has a higher precedence than \[*Edge], and so mixing the operators specifically introduced to define graph edges with a Rule results in the rule being used as an edge and the edge being used as a name. (Quirk #4.)

A Better Graph Function

Here is a function that uses rewrite rules to transform our preferred notation into the form Graph expects:

SetAttributes[makeGraph, HoldFirst];
makeGraph[edges_,opts: OptionsPattern[]]:=
    Module[{edgelist, seq, postorderReplaceRepeated},
        postorderReplaceRepeated[expr_,rules_]:=
            FixedPoint[Replace[#,rules,{0,-1},Heads->True]&,expr];
        edgelist = If[Head[edges]===List, edges, {edges}];
        edgelist = postorderReplaceRepeated[edgelist,
        {h2_[h1_[x_, y_], h3_[z_, w_]]
                /;SubsetQ[{Rule, TwoWayRule}, {h1,h2, h3}]
                :>seq[h1[x, y],h2[y, z], h3[z, w]], 
        h1_[x_, h2_[y_, z_]]
                /;SubsetQ[{Rule, TwoWayRule}, {h1,h2}]
                :>seq[h1[x, y], h2[y, z]], 
        h2_[h1_[x_, y_], z_]
                /;SubsetQ[{Rule, TwoWayRule}, {h1,h2}]
                :>seq[h1[x, y], h2[y, z]],
        h1_[x_, seq[h2_[y_, z___], w___]]
                /;SubsetQ[{Rule, TwoWayRule}, {h1,h2}]
                :>seq[h1[x, y], h2[y, z], w],
        h2_[seq[x___, h1_[y___, z_]], w_]
                /;SubsetQ[{Rule, TwoWayRule}, {h1,h2}]
                :>seq[x, h1[y, z], h2[z, w]]}];
        edgelist=edgelist//.seq->Sequence;
        Graph[edgelist, opts]
    ]

You might notice that makeGraph uses an auxiliary function called postorderReplaceRepeated. That's because of another little quirk of Mathematica (quirk #5), described in this SE answer:

ReplaceAll and by extension ReplaceRepeated are very unusual in the context of Mathematica in that they perform a depth-first preorder traversal, whereas nearly all other functions perform a depth-first postorder traversal.

This is the first question I have seen anywhere that involves a "5 Quirk" answer.

(Answer x-posted to the Wolfram Community.)