# Keep track of order of graph edges when iterating over them

I have a piece of code where I might want to convert `Graph`s to `DiGraph`s. However, I need to keep track of where the edges are (so that for the edge connecting vertices 1 and 2 in the original graph, I know where `1 => 2` and `2 => 1` are for the created digraph. However, it seems that whenever you iterate over a graph’s list o edges, they always do so in order of the index of the source followed by the destination, which makes it an utter mess to keep track of this order.

E.g, if I have:

``````using Graphs
g0 = DiGraph(4)
foreach(e -> println(e), edges(g0))
``````

I get:

``````Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Edge 4 => 1
``````

And then if I add the reverse edges and print:

``````add_edge!(g0, 2, 1)
foreach(e -> println(e), edges(g0))
``````

I get:

``````Edge 1 => 2
Edge 1 => 4
Edge 2 => 1
Edge 2 => 3
Edge 3 => 2
Edge 3 => 4
Edge 4 => 1
Edge 4 => 3
``````

While I ideally would have liked:

``````Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Edge 4 => 1
Edge 2 => 1
Edge 3 => 2
Edge 4 => 3
Edge 1 => 4
``````

(where edge i maps to i and i+4)
or maybe

``````Edge 1 => 2
Edge 2 => 1
Edge 2 => 3
Edge 3 => 2
Edge 3 => 4
Edge 4 => 3
Edge 4 => 1
Edge 1 => 4
``````

(where edge i maps to 2*(i-1)+1 and 2*(i-1)+2)

Can you just create both graphs and then a dictionary mapping edge indices in one to edge indices in the other?

Sorry, confussed, do you mean creating both

``````g0_1 = DiGraph(4)
``````

and

``````g0_2 = DiGraph(4)
``````

or both

``````g0_1 = DiGraph(4)
``````

and

``````g0_1 = DiGraph(4)
``````

?

No I meant creating the Graph on one side and the DiGraph on the other side then iterating to link the two, but it has quadratic complexity. Perhaps you can tell me a bit more about why you need to keep track of edge indices?

1 Like

Sorry, yeah, the request is probably a bit confusing.

Basically, I am building a spatial simulator for biological ODEs (also SDE and Gillespie stuff). Basically, I provide a non-spatial ODE and a graph, and the simulator simulates the ODE in every vertex of the graph. There is also a transportation rule for some variables, so that these can “move” between vertexes, along edges.

The rate at which this movement occurs is provided as a parameter (`d`) to the simulator.

• Often, `d` is constant along all edges (in which a single value is provided, e.g. `d=0.1`).
• It is also possible that `d` vary from edge to edge. Here, `d` would be a vector (e.g. `d=[0.10, 0.11, 0.12, 0.09, 0.11, ...]`) where `d[i]` correspond to the rate along the i’th edge.
• Internally, the spatial geometry is represented as a `DiGraph`. In most cases, the system is symmetric along each edge, so the user can provide a `Graph`, which is internally converted to a `DiGraph`.
• If a `Graph` with `ne=N` is provided, for the internal digraph, we will have `ne=2N`. Here, I want the user to be able to provide a `d` vector of length `N`, and it is implicitly assumed that the value `d[i]` will be used for the two edges generated by the i’th edge in the input `Graph`.

It is internally recorded if a `Graph` (rather than a `DiGraph`) was used as input, and if then `d` is a vector of length `N` (rather than `2N`) I want to engage this routine. My idea was that if I had a custom-made way to generate the `DiGraph` from the `Graph, where I used one of these schemes to generate the former from the latter, creating the new `d` vector is trivial, e.g. by running

``````(2length(d) == ne(g)) && (d = [d_val for d_val in d for _ in 1:2])
# Sets d = [d1,d1,d2,d2,d3,d3,d4,d4, ...]
``````

No matter how you generate the `DiGraph`, its iteration order will stay the same.

• An inelegant solution would be changing the internal mechanics handling `d` so that it adapts to the current order of iteration in `Graph` and `DiGraph`, but since this order is not part of the API, I don’t like it.
• An elegant solution would be rolling out your own graph format with custom edge order.
• A middle ground would be using a sparse matrix, which can then be made symmetric? Or a weighted graph?
1 Like

So basically you want to keep track of the order of the edges to associate some metadata with every edge? I think there is MetaGraphs.jl that allows you to assign metadata directly to the edges (@gdalle knows a lot more about that package ^^). With that you could for example assign an index to each edge that indexes into your parameter vector. Does that solve your problem?

1 Like

Don’t use MetaGraphs.jl, use MetaGraphsNext.jl, it’s way more efficient But yes, that is the fourth solution

1 Like

Ah interesting, didn’t know about MetaGraphsNext May I suggest putting this info/warning at the top the Readme.md of MetaGraphs?

2 Likes

That is a solid point

3 Likes

Thanks a lot, that makes it very clear what is (and is not) possible. I should be able to sort thing out from here

done