Keep track of order of graph edges when iterating over them

Specific Domains Graphs
1

I have a piece of code where I might want to convert Graphs to DiGraphs. 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)
add_edge!(g0, 1, 2)
add_edge!(g0, 2, 3)
add_edge!(g0, 3, 4)
add_edge!(g0, 4, 1)
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)
add_edge!(g0, 3, 2)
add_edge!(g0, 4, 3)
add_edge!(g0, 1, 4)
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)

2

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

3

Sorry, confussed, do you mean creating both

g0_1 = DiGraph(4)
add_edge!(g0, 1, 2)
add_edge!(g0, 2, 3)
add_edge!(g0, 3, 4)
add_edge!(g0, 4, 1)

and

g0_2 = DiGraph(4)
add_edge!(g0, 2, 1)
add_edge!(g0, 3, 2)
add_edge!(g0, 4, 3)
add_edge!(g0, 1, 4)

or both

g0_1 = DiGraph(4)
add_edge!(g0, 1, 2)
add_edge!(g0, 2, 3)
add_edge!(g0, 3, 4)
add_edge!(g0, 4, 1)

and

g0_1 = DiGraph(4)
add_edge!(g0, 1, 2)
add_edge!(g0, 2, 3)
add_edge!(g0, 3, 4)
add_edge!(g0, 4, 1)
add_edge!(g0, 2, 1)
add_edge!(g0, 3, 2)
add_edge!(g0, 4, 3)
add_edge!(g0, 1, 4)

?

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?

5

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, ...]
6

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?
7

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?

8

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

9

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

10

That is a solid point

11

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

12

done