Message Boards Message Boards

1
|
9298 Views
|
3 Replies
|
6 Total Likes
View groups...
Share
Share this post:

Why Graph does not recognize chains of vertexes like NetGraph

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?

3 Replies

Next time, if you cross-post, please links the posts together.

https://mathematica.stackexchange.com/questions/187113/why-graph-does-not-recognize-chains-of-vertexes-like-netgraph

To sum up the answers there, your notation considers 2->3 to be a vertex, connected to vertex 1. This notation cannot be made consistent without restrictions on what expressions can be vertices. NetGraph restricts vertices to integers and strings, so it can disambiguate such notation.

POSTED BY: Szabolcs Horvát

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: enter image description here

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.

POSTED BY: Robert Jacobson

I will venture to guess that Graph design did not allow for multiple infix Rule, and so it becomes garbage in, garbage out. simply due to undefined semantics. This is just a guess though. (For what it's worth, the development teams and histories of those two functions do not, to my knowledge, intersect.)

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract