graph_from_literal() does not preserve edge order

[szhorvat]

Describe the bug

graph_from_literal() does not preserve the edge order, which makes it inconvenient (and confusing) to set edge attributes on a graph right after creation. There is an instance of this going wrong here: https://stackoverflow.com/q/76345800/695132

graph <- graph.formula(
  A -+ B,
  B -+ C,
  C -+ D,
  D -+ E,
  A -+ D,
  B -+ D,
  B -+ E
)

E(graph)$weight <- c(3, 2, 4, 5, 5, 1, 4)

The user assumed that A -> B will have weight 3, B->C weight 2, and so on. But this is not the case.

To reproduce

Notice that the edge order of the graph does not correspond to the edge order used in the creation formula.

> g <- graph_from_literal(A -+ B, B -+ C, C -+ D, D -+ E, A -+ D, B -+ D, B -+ E)
> E(g)
+ 7/7 edges from e733585 (vertex names):
[1] A->B A->D B->C B->D B->E C->D D->E

Both the Python and Mathematica interfaces preserve the edge order. It was surprising to me to discover that the R interface does not.

Version information

1.4.3 and igraph_1.4.99.9014

[krlmlr]

Thanks, confirmed with 5008105:

options(conflicts.policy = list(warn = FALSE))
library(igraph)

g1 <- graph_from_literal(
  A -+ B,
  B -+ C,
  C -+ D,
  D -+ E,
  A -+ D,
  B -+ D,
  B -+ E
)
E(g1)
#> + 7/7 edges from 5064704 (vertex names):
#> [1] A->B A->D B->C B->D B->E C->D D->E

g2 <- graph.formula(
  A -+ B,
  B -+ C,
  C -+ D,
  D -+ E,
  A -+ D,
  B -+ D,
  B -+ E
)
E(g2)
#> + 7/7 edges from 74c7499 (vertex names):
#> [1] A->B A->D B->C B->D B->E C->D D->E

waldo::compare(g1, g2)
#> `old[[10]]$igraph` is <pointer: 0x600003a20140>
#> `new[[10]]$igraph` is <pointer: 0x600003a20280>
#> 
#> `old[[10]]$myid`: "50647049-a0c5-4e6f-a587-2c76b9a386d1"
#> `new[[10]]$myid`: "74c74995-48a2-449f-ae8d-8ad6c222ec61"

^{Created on 2023-05-28 with reprex v2.0.2}

[krlmlr]

Same with igraph 1.4.2, it's not a recent regression.

Can we even fix the edge order in the C core or in the R interface? Should we?

[szhorvat]

Same with igraph 1.4.2, it's not a recent regression.

No, this is a not a regression, it's just an unfortunate behaviour that would be good to fix.

Can we even fix the edge order in the C core or in the R interface? Should we?

I don't understand this question, can you clarify? Edges are referred to by ID, so the order is important.

This issue is specific to the graph_from_literal() function and not related at all to the C core, or to other parts of the R interface.

[krlmlr]

This is from simplify() :

options(conflicts.policy = list(warn = FALSE))
library(igraph)

g <- make_graph(c(1L, 2L, 2L, 3L, 3L, 1L), directed = FALSE)
g
#> IGRAPH f02a017 U--- 3 3 -- 
#> + edges from f02a017:
#> [1] 1--2 2--3 1--3
simplify(g)
#> IGRAPH 29cc670 U--- 3 3 -- 
#> + edges from 29cc670:
#> [1] 1--2 1--3 2--3

graph_from_literal(A - B - C - A)
#> IGRAPH 21f4c43 UN-- 3 3 -- 
#> + attr: name (v/c)
#> + edges from 21f4c43 (vertex names):
#> [1] A--B A--C B--C
graph_from_literal(A - B - C - A, simplify = FALSE)
#> IGRAPH 8706407 UN-- 3 3 -- 
#> + attr: name (v/c)
#> + edges from 8706407 (vertex names):
#> [1] A--B B--C A--C

^{Created on 2023-05-28 with reprex v2.0.2}

[szhorvat]

It seems I was wrong, and the Python interface suffers from this as well, as it also calls simplify() directly. Nevertheless, it would be better to avoid this behaviour, especially considering that simplify=TRUE is the default.

Perhaps the easiest solution is to check if the graph is simple, and if yes, do not call simplify(). This bring a performance hit, but that's irrelevant for a function like this. graph_from_literal() is meant to create graphs from a notation typed in manually. It works only with small graphs.

@ntamas, any opinions on this?

[krlmlr]

If simplify() didn't drop edge attributes, we could use that to restore the original order:

options(conflicts.policy = list(warn = FALSE))
library(igraph)

g <- make_graph(c(1L, 2L, 2L, 3L, 3L, 1L), directed = FALSE)
g
#> IGRAPH 99bd454 U--- 3 3 -- 
#> + edges from 99bd454:
#> [1] 1--2 2--3 1--3
E(g)$idx <- 1:3
g <- simplify(g)
E(g)$idx
#> NULL

^{Created on 2023-05-28 with reprex v2.0.2}

Of course, simplify() could also preserve the order of the edges.

[szhorvat]

Of course, simplify() could also preserve the order of the edges.

This does not look feasible to me, or at least it looks difference.

Any objection to my suggestion, i.e. replacing

if (simplify) 
        res <- simplify(res)

with

if (simplify && !is_simple(res))
    res <- simplify(res)

?

[szhorvat]

For context, the main reason for the simplify parameter (and its default of TRUE) is the :-notation. Colons are used to define groups, then one can create edges between all pairs across two groups. If the two groups share some vertices, this will create self-loops and multi-edges, something that's not typically desired. Example:

graph_from_literal(1:2:3 -- 1:2:3, simplify = F)

However, when : is used, the edge order is not clear from the formula anyway, so IMO it's fine to change it arbitrarily.

[ntamas]

Any objection to my suggestion

Hmmm, one case that can potentially still be problematic is:

# no simplification will be done here
> graph_from_literal(1--2, 2--3, 3--4)

# then the user adds an innocent-looking loop edge and suddenly the simplification kicks in
> graph_from_literal(1--2, 2--3, 3--4, 1--1)

So I'm not really in favour of deciding whether to call simplify() or not based on whether the graph is already simple. We should either provide explicit guarantees that the order of edges will be respected, or document that we provide no guarantees.

[krlmlr]

For 1:2:3 -- 2:3:4, I would expect edges in the following, lexicographic, ordering: 12, 13, 14, 22, 23, 24, 32, 33, 34. This is perhaps consistent with what igraph gives today?

I believe the typical workflow can be:

• Construct a graph
• Look at the resulting edges
• Construct an attribute based on that order

So, stability seems important. We can teach users to use simplify = FALSE if they care about that.

I'm in favor of solving this via documentation, and (if possible) keeping the edge order stable in simplify() .

[szhorvat]

So I'm not really in favour of deciding whether to call simplify() or not based on whether the graph is already simple. We should either provide explicit guarantees that the order of edges will be respected, or document that we provide no guarantees.

Makes senses from the developer's technical perspective, but there's still the issue that a function specifically meant to provide convenience fails at its job when we need to add edge weights. Can we come up with a compact and convenient way to create a graph from a simple notation, with vertex names, and still add edge weights to it?

I'd still say that the current behaviour is an "UX bug". The workflow @krlmlr proposes in the above comment defeats the function's purpose. At the same time I do see the disadvantages of my proposal. Any other ideas for improving convenience here?

---

Nevertheless, let me try to examine the situation a bit more closely.

# no simplification will be done here
> graph_from_literal(1--2, 2--3, 3--4)

# then the user adds an innocent-looking loop edge and suddenly the simplification kicks in
> graph_from_literal(1--2, 2--3, 3--4, 1--1)

If there were a way to add edge attributes directly within graph_from_literal(), then a weight could be specified for 1 -- 1 as well. If 1 -- 1 is removed, the corresponding weight is also removed. In fact, we do have a notation to specify a weight, but I'm not sure that the implementation is easily extensible to deal with the situation we're talking about. Consider this:

g <- make_(from_literal(1--2, 2--3, 1--1, 3--4), simplify=F, with_edge_(weight=c(1,2,3,4)))

Now I had to add simplify=F. It seems it can go either in make_() or from_literal(). What I envisioned is that with the default simplify=T, the graph would be constructed with weights first, and the simplification would be done afterwards. I know that this probably doesn't fit in the current framework though.

Let's do look at what happens with simplify=T though:

g<-make_(from_literal(1--2, 2--3, 1--1, 3--4), simplify=T, with_edge_(weight=c(1,2,3,4)))
Error in i_set_edge_attr(graph = graph, name = name, value = value, check = FALSE) : 
  Length of new attribute value must be 1 or 3, the number of target edges, not 4

Well, this behaviour is actually pretty good. The user was protected from making a mistake: they are alerted to the fact that the graph that's actually created is not what they thought it was. This is thanks to @krlmlr's change that checks that attribute vectors are of the correct length!

---

In conclusion, let me put it this way:

If simplification kicks in, then not only the edge order changes, but also the edge count. So the user's attempt to add weights will simply fail. What's important is that they won't get a graph that differs from what they believe they are getting. Note that does this does happen at this moment, as demonstrated by the SO thread I linked!!

Right now we have:

• With simplify=F, the edge order and count are unchanged
• With simplify=T, the edge order changes, but the edge count may stay the same, which exposes users to mistakes

I think we should have a function which does not ever change the edge order unless it also changes the edge count. This will protect users from mistakes.

Does this reasoning makes sense to you @ntamas @krlmlr ?

The solution I propose not ideal, but it's improved compared to what we have now.

[szhorvat]

Here's another thought:

We have a conflict between convenience (compact notation) and predictability (either always preserve order or give zero guarantees). This is a very common scenario. I see it very often in Mathematica, which typically errs in favour of convenience, but harms predictability—that's the source of most of my complaints about the Wolfram Language!

But consider the use of this function: it's specifically for convenience! It's something that's typically used interactively. IMO it's okay to sacrifice a little bit of predictability for convenience here.

Add this to the observation I made above about my proposal actually reducing the chance of mistakes by users. Do I have a case?

[krlmlr]

I agree, there are other battles to fight. We can surely do "simplify only if it's not simple" without a change to the C core.