Performance of Large-ish graphs with weighted edges

Questions
1

Hi, I’d been trying to solve the Advent of Code 2024 problems using WL and in particular using graphs where it made sense. One of the solutions I came up with involved creating a 141x141 grid graph, deleting some vertices (leaving ~7000), then adding about 5000 edges.

I got a version of this working so that it made one call to VertexDelete and one call to EdgeAdd and then 5000 calls to AnnotationValue[]= to set the edge weights. This took about 15 hours to run on my PC, which is just unbelievably slow.

After a lot of experimentation with different ways to making this more efficient and adding Print functions everywhere to see exactly what is taking the time, virtually all the time is taken in setting the edge weights.

I even tried building a new graph, concatenating the edges from the first graph with the new edges in the form Annotation[edge, EdgeWeight->1002] and that still takes just as long even though it is one call. If I remove the edgeweight annotation from the new edges, it completes almost immediately.

So what’s the deal with graphs with edgeweights being many orders of magnitude slower to build? Note that none of this time includes doing any pathfinding or other graph algorithm. This is 15 hours just to build a graph. Not great.

2

Which problem are you specifically referring to? What code do you have now?

I was able to solve all of them in Wolfram language except for 24 part 2, which was only semi-automated…

3

I’m not that interested in the problems, it was probably a mistake to mention the application. I’m more interested in discovering why WL has pathological performance issues with adding weighted edges to only moderately large graphs.

But since you ask the problem is Day 16. I’m aware this is far from a great way to solve it, but I build a grid-graph from the input. I then delete all the vertices representing # (walls). Then in order to account for the cost of turning I identify all the vertices where a turn might take place, delete those and reconnect their neighbours with weighted edges at account for the costs appropriately. It does produce the correct answer since I did run it long enough to complete one time. Sadly I didn’t realise part 2 of Day 16 would require me to regenerate the graph in order to answer another question about it.

I can upload a notebook with a test case but it’ll take a little time prepare a minimal test case so that’ll have to wait until tomorrow now.

4

Nik from the Wolfram Institute did a full series for AoC on our YouTube channel! You can watch it here: https://www.youtube.com/playlist?list=PLM_MgbAF1uYJ3ewejaW9XQHi4ZJmi8mWV

5

I built the graph myself in something like:

Graph[edges, EdgeWeight -> weights]

which runs in < a second. The annotation route has never been my favorite as it is slow. Here is my code so you can see how I built up the graph:

str="###############\n#.......#....E#\n#.#.###.#.###.#\n#.....#.#...#.#\n#.###.#####.#.#\n#.#.#.......#.#\n#.#.#####.###.#\n#...........#.#\n###.#.#####.#.#\n#...#.....#.#.#\n#.#.#.###.#.#.#\n#.....#...#.#.#\n#.###.#.#.#.#.#\n#S..#.....#...#\n###############";
str=Characters/@StringSplit[str,"\n"];
posses=Position[str,"."|"E"|"S",{2}];
start={1,-1}FirstPosition[str,"S",Missing[],{2}];
stop={1,-1}FirstPosition[str,"E",Missing[],{2}];
posses[[All,2]]*=-1;
dirs={{0,1},{1,0},{0,-1},{-1,0}};
rotations=Catenate@Table[
    ss={p,#}&/@dirs;
    Join[Append[#,1000]&/@Partition[ss,2,1,1],Append[#,1000]&/@Partition[Reverse[ss],2,1,1]]
    ,
    {p,posses}
];
hs=CreateDataStructure["HashSet",posses];
moves=Catenate@Table[
    conns=Select[{{p,#},{p+#,#},1}&/@dirs,hs["MemberQ",#[[2,1]]]&]
    ,
    {p,posses}
];
gr=Graph[Join[DirectedEdge@@@rotations[[All,;;2]],DirectedEdge@@@moves[[All,;;2]]],EdgeWeight->Join[rotations[[All,3]],moves[[All,3]]]];
Min[GraphDistance[gr,{start,{0,-1}},{stop,#}]&/@dirs]

Not the neatest code, but hopefully understandable. It basically makes vertices with {x,y,direction} and then does the pathfinding. 10 milliseconds on the example, and less than 1 second on my input.

I think your way of adding and deleting edges works fine, but not fast if you do it 5000 times sequentially.

6

Thank you for providing your code. I ran it with my data and it finds the correct answer and completes almost instantaneously. Bravo!

I mentioned before that in attempting to find a solution that ran in a sensible amount of time I had changed my code so that rather than adding the new edges and then setting their edge weights one by one I instead: Extract the existing edges into a list, and add my new edges specified thus Annotation[UndirectedEdge[v1,v2],EdgeWeight->1002] and then build a new graph using the combined set of edges. So I have something like:-

newGraph = Graph[Join[EdgeList[oldGraph], newEdges /. {e_,w_}->Annotation[e,EdgeWeight->w] ]

That was still taking a super-long time even though it was then only 1 function call.

So I compared my program with yours. The only thing I changed was that I supplied the edge weights for my added edges using the other way of doing it:

ew = newEdges /. {e_,w_}-> e->w;
newGraph = Graph[Join[EdgeList[oldGraph], newEdges[[All,1]] ], EdgeWeight → ew];

And do you know what… This runs almost as fast as your solution.

Why should two different ways of creating a graph with weighted edges take vastly different times to run? The documentation indicates that both approaches to specifying edge weights are equally valid and doesn’t mention anything about runtime costs. I should probably report this as a bug, but I only have a Home Edition licence so I don’t have support access.

7

hmm strange, but I don’t know why it runs much slower to be honest. Despite having a Home Edition license I think you can submit a bug here: Contact Wolfram Support by Email or Phone

8

There is no restriction as to who can report a problematic behavior. There likely are limitations on services e.g. for receiving workarounds from Technical Services (obviously there is no such restriction on Wolfram Community though).