Efficient graph rendering and shortest path highlighting for large undirected graphs in C# WinForms

Question

I'm currently working on a map routing project using C# and Windows Forms. The application calculates the shortest path in a graph, then renders the graph and highlights the minimum path. Right now, the renderer iterates through every node and edge to draw them. Since it's an undirected graph, I include some checks to avoid drawing duplicate edges. However, performance becomes a major issue when handling large test cases—around 200,000 nodes and 400,000 edges. Rendering in these scenarios feels like running a game at 10 FPS. If anyone wants to review the full implementation, I'm happy to share the complete file. If you want to directly check the flow and how the components are drawn start tracing from DrawGraph function.

Note: One of the core performance bottlenecks is that the graph is redrawn completely every time the panel is moved or zoomed. If there is a way to draw the graph only once and do actions on the same drawing this would probably solve the issue.

The code:

using System.Drawing.Drawing2D;
using MAP_routing.model;
namespace MAP_routing.view
{
 internal class graph_renderer
 {
 private readonly List<Node> _graph;
 private readonly Panel _panel;
 private readonly List<Edge> _edges;
 private double _scale = 1.0f;
 private PointF _offset = new PointF(0, 0);
 private bool _isPanning = false;
 private Point _lastMousePosition;
 private PointF _viewCenter = new PointF(0, 0);
 private Dictionary<int, Color> _highlightedNodes = new Dictionary<int, Color>();
 private List<Edge> _highlightedPath = new List<Edge>();
 private Dictionary<Edge, Tuple<Color, string>> _highlightedEdges = new Dictionary<Edge, Tuple<Color, string>>();
 public graph_renderer(List<Node> graph, List<Edge> edges, Panel panel)
 {
 _graph = graph;
 _panel = panel;
 _edges = edges;
 CenterGraph();
 HookEvents();
 }
 #region Public API
 public void Redraw() => _panel.Invalidate();
 public void CenterGraph()
 {
 if (_graph.Count == 0) return;
 double minX = _graph.Min(n => n.X);
 double maxX = _graph.Max(n => n.X);
 double minY = _graph.Min(n => n.Y);
 double maxY = _graph.Max(n => n.Y);
 double centerX = (minX + maxX) / 2;
 double centerY = (minY + maxY) / 2;
 double graphWidth = maxX - minX;
 double graphHeight = maxY - minY;
 if (graphWidth > 0 && graphHeight > 0)
 {
 double scaleX = (_panel.Width * 0.9f) / graphWidth;
 double scaleY = (_panel.Height * 0.9f) / graphHeight;
 _scale = Math.Min(scaleX, scaleY);
 _scale = Math.Max(0.01f, Math.Min(10f, _scale));
 }
 _viewCenter = new PointF((float)centerX, (float)centerY);
 UpdateOffsetFromViewCenter();
 }
 public void ClearHighlightedNodes()
 {
 _highlightedNodes.Clear();
 }
 public void HighlightPath(PathResult path, Color color)
 {
 if (path == null || path.Edges == null || path.Edges.Count == 0)
 return;
 _highlightedPath.Clear();
 foreach (var edge in path.Edges)
 {
 edge.IsPath = true;
 edge.Color = color;
 _highlightedPath.Add(edge);
 }
 }
 public void ClearHighlightedPath()
 {
 _highlightedPath.Clear();
 _highlightedEdges.Clear();
 }
 public void HighlightEdge(Edge edge, Color color, string label)
 {
 if (edge == null) return;
 _highlightedEdges.Clear();
 _highlightedEdges[edge] = new Tuple<Color, string>(color, label);
 }
 #endregion
 private void UpdateOffsetFromViewCenter()
 {
 _offset.X = (float)(_panel.Width / 2 - _viewCenter.X * _scale);
 _offset.Y = (float)(_panel.Height / 2 + _viewCenter.Y * _scale);
 }
 #region Event Hooks
 private void HookEvents()
 {
 _panel.Paint += OnPaint;
 _panel.MouseWheel += OnMouseWheel;
 _panel.MouseDown += OnMouseDown;
 _panel.MouseMove += OnMouseMove;
 _panel.MouseUp += OnMouseUp;
 _panel.Resize += (s, e) => _panel.Invalidate();
 }
 #endregion
 #region Paint Handler
 private void OnPaint(object sender, PaintEventArgs e)
 {
 Graphics g = e.Graphics;
 g.SmoothingMode = SmoothingMode.AntiAlias;
 g.Clear(Color.White);
 g.TranslateTransform(_offset.X, _offset.Y);
 g.ScaleTransform((float)_scale, (float)-_scale);
 DrawBoundingBox(g);
 DrawGraph(g);
 }
 #endregion
 #region Drawing Methods
 private void DrawGraph(Graphics g)
 {
 RectangleF visibleBounds = GetVisibleWorldBounds();
 foreach (var node in _graph)
 {
 foreach (var edge in node.Neighbors)
 {
 if (node.Id >= edge.To.Id)
 continue;
 if (_highlightedPath.Contains(edge)
 || _highlightedEdges.ContainsKey(edge)
 || !(visibleBounds.Contains((float)node.X, (float)node.Y)
 || visibleBounds.Contains((float)edge.To.X, (float)edge.To.Y)))
 continue;
 using var pen = new Pen(Color.Gray, 1f / (float)_scale);
 g.DrawLine(pen,
 (float)node.X, (float)node.Y,
 (float)edge.To.X, (float)edge.To.Y);
 }
 }
 PathResult currentPath = GetCurrentPathResult();
 if (currentPath != null)
 {
 DrawHighlightedPath(g, currentPath);
 DrawWalkingPaths(g, currentPath);
 DrawSingleHighlightedEdge(g);
 }
 foreach (Node node in _graph)
 {
 if (visibleBounds.Contains((float)node.X, (float)node.Y))
 DrawNode(g, node);
 }
 DrawQueryPoints(g);
 }
 private void DrawHighlightedPath(Graphics g, PathResult currentPath)
 {
 if (_highlightedPath.Count == 0) return;
 foreach (var edge in _highlightedPath)
 {
 if(edge.From.Id == -1 || edge.To.Id == -2) continue;
 if (!_highlightedEdges.ContainsKey(edge))
 {
 using var pen = new Pen(edge.Color, 3f / (float)_scale);
 g.DrawLine(pen, (float)edge.From.X, (float)edge.From.Y, (float)edge.To.X, (float)edge.To.Y);
 }
 }
 }
 private void DrawWalkingPaths(Graphics g, PathResult currentPath)
 {
 if (currentPath == null || _highlightedPath.Count == 0) return;
 using var greenPen = new Pen(Color.Green, 3f / (float)_scale) { DashStyle = DashStyle.Dash };
 using var redPen = new Pen(Color.Red, (float)(3f / _scale)) { DashStyle = DashStyle.Dash };
 if (currentPath.source != null && currentPath.source.Id == -1 && _highlightedPath.Any())
 {
 Node firstNode = _highlightedPath.First().To;
 g.DrawLine(greenPen,
 (float)currentPath.source.X, (float)currentPath.source.Y,
 (float)firstNode.X, (float)firstNode.Y);
 }
 if (currentPath.dest != null && currentPath.dest.Id == -2 && _highlightedPath.Any())
 {
 var lastEdge = _highlightedPath[_highlightedPath.Count - 2];
 g.DrawLine(redPen,
 (float)lastEdge.To.X, (float)lastEdge.To.Y,
 (float)currentPath.dest.X, (float)currentPath.dest.Y);
 }
 }
 private void DrawSingleHighlightedEdge(Graphics g)
 {
 if (_highlightedEdges.Count == 0) return;
 var entry = _highlightedEdges.First();
 Edge edge = entry.Key;
 Color color = entry.Value.Item1;
 string label = entry.Value.Item2;
 using var pen = new Pen(color, 5f / (float)_scale);
 g.DrawLine(pen,
 (float)edge.From.X, (float)edge.From.Y,
 (float)edge.To.X, (float)edge.To.Y);
 if (!string.IsNullOrEmpty(label))
 {
 PointF midpoint = new PointF(
 (float)((edge.From.X + edge.To.X) / 2),
 (float)((edge.From.Y + edge.To.Y) / 2)
 );
 float dx = (float)(edge.To.X - edge.From.X);
 float dy = (float)(edge.To.Y - edge.From.Y);
 float length = (float)Math.Sqrt(dx * dx + dy * dy);
 if (length > 0)
 {
 dx /= length;
 dy /= length;
 float perpX = -dy;
 float perpY = dx;
 float pointerLength = 160f / (float)_scale;
 PointF boxPosition = new PointF(
 midpoint.X + perpX * pointerLength,
 midpoint.Y + perpY * pointerLength
 );
 using var pointerPen = new Pen(Color.Black, 1f / (float)_scale);
 g.DrawLine(pointerPen, midpoint, boxPosition);
 Matrix originalTransform = g.Transform;
 g.ResetTransform();
 PointF screenMidpoint = new PointF(
 _offset.X + midpoint.X * (float)_scale,
 _offset.Y - midpoint.Y * (float)_scale
 );
 PointF screenBoxPos = new PointF(
 _offset.X + boxPosition.X * (float)_scale,
 _offset.Y - boxPosition.Y * (float)_scale
 );
 using var font = new Font("Arial", 10f);
 using var brush = new SolidBrush(Color.White);
 SizeF textSize = g.MeasureString(label, font);
 using var bgBrush = new SolidBrush(Color.Black);
 g.FillRectangle(bgBrush,
 screenBoxPos.X - textSize.Width / 2,
 screenBoxPos.Y - textSize.Height / 2,
 textSize.Width,
 textSize.Height);
 g.DrawRectangle(new Pen(Color.Black, 1),
 screenBoxPos.X - textSize.Width / 2,
 screenBoxPos.Y - textSize.Height / 2,
 textSize.Width,
 textSize.Height);
 StringFormat format = new StringFormat
 {
 Alignment = StringAlignment.Center,
 LineAlignment = StringAlignment.Center
 };
 g.DrawString(label, font, brush, screenBoxPos, format);
 g.Transform = originalTransform;
 }
 }
 }
 private void DrawQueryPoints(Graphics g)
 {
 PathResult path = GetCurrentPathResult();
 if (path == null || path.source == null || path.dest == null)
 return;
 if (path.source.Id == -1)
 {
 float sourceRadius = Math.Max(10f / (float)_scale, 3f);
 var sourceRect = new RectangleF(
 (float)path.source.X - sourceRadius,
 (float)path.source.Y - sourceRadius,
 sourceRadius * 2,
 sourceRadius * 2
 );
 using var sourceBrush = new SolidBrush(Color.Green);
 using var sourcePen = new Pen(Color.Black, 1.5f / (float)_scale);
 g.FillEllipse(sourceBrush, sourceRect);
 g.DrawEllipse(sourcePen, sourceRect);
 }
 if (path.dest.Id == -2)
 {
 float destRadius = Math.Max(10f / (float)_scale, 3f);
 var destRect = new RectangleF(
 (float)path.dest.X - destRadius,
 (float)path.dest.Y - destRadius,
 destRadius * 2,
 destRadius * 2
 );
 using var destBrush = new SolidBrush(Color.Red);
 using var destPen = new Pen(Color.Black, 1.5f / (float)_scale);
 g.FillEllipse(destBrush, destRect);
 g.DrawEllipse(destPen, destRect);
 }
 }
 public void DrawNode(Graphics g, Node node)
 {
 if (_highlightedNodes.ContainsKey(node.Id))
 return;
 float radius = 3f;
 var rect = new RectangleF(
 (float)node.X - radius, (float)node.Y - radius,
 radius * 2, radius * 2
 );
 using var brush = new SolidBrush(node.IsPath ? Color.Red : node.Color);
 using var pen = new Pen(Color.Black, 1);
 g.FillEllipse(brush, rect);
 g.DrawEllipse(pen, rect);
 }
 private void DrawBoundingBox(Graphics g)
 {
 if (_graph.Count == 0) return;
 double minX = _graph.Min(n => n.X);
 double maxX = _graph.Max(n => n.X);
 double minY = _graph.Min(n => n.Y);
 double maxY = _graph.Max(n => n.Y);
 var rect = new RectangleF((float)minX, (float)minY, (float)(maxX - minX), (float)(maxY - minY));
 using var pen = new Pen(Color.LightGray, (float)(5f / _scale)) { DashStyle = DashStyle.Dash };
 g.DrawRectangle(pen, rect.X, rect.Y, rect.Width, rect.Height);
 }
 private PathResult GetCurrentPathResult()
 {
 Control parent = _panel;
 while (parent != null && !(parent is map_vis))
 {
 parent = parent.Parent;
 }
 return (parent as map_vis)?.GetCurrentPathResult();
 }
 #endregion
 private RectangleF GetVisibleWorldBounds()
 {
 double left = (0 - _offset.X) / _scale;
 double top = -((0 - _offset.Y) / _scale);
 double right = (_panel.Width - _offset.X) / _scale;
 double bottom = -((_panel.Height - _offset.Y) / _scale);
 return new RectangleF(
 (float)Math.Min(left, right),
 (float)Math.Min(top, bottom),
 (float)Math.Abs(right - left),
 (float)Math.Abs(bottom - top)
 );
 }
 #region Coordinate Conversions
 private PointF ScreenToWorld(Point screenPoint)
 {
 return new PointF(
 (float)((screenPoint.X - _offset.X) / _scale),
 (float)(-((screenPoint.Y - _offset.Y) / _scale))
 );
 }
 #endregion
 #region Mouse Interaction
 private void OnMouseWheel(object sender, MouseEventArgs e)
 {
 PointF worldPoint = ScreenToWorld(e.Location);
 double oldScale = _scale;
 double zoomFactor = e.Delta > 0 ? 1.1f : 0.9f;
 _scale *= zoomFactor;
 _scale = Math.Max(0.01f, Math.Min(10f, _scale));
 double scaleRatio = _scale / oldScale;
 _viewCenter.X = (float)(worldPoint.X + (_viewCenter.X - worldPoint.X) / scaleRatio);
 _viewCenter.Y = (float)(worldPoint.Y + (_viewCenter.Y - worldPoint.Y) / scaleRatio);
 UpdateOffsetFromViewCenter();
 Redraw();
 }
 private void OnMouseDown(object sender, MouseEventArgs e)
 {
 if (e.Button == MouseButtons.Left)
 {
 _isPanning = true;
 _lastMousePosition = e.Location;
 _panel.Cursor = Cursors.Hand;
 }
 }
 private void OnMouseMove(object sender, MouseEventArgs e)
 {
 if (_isPanning)
 {
 float dx = e.X - _lastMousePosition.X;
 float dy = e.Y - _lastMousePosition.Y;
 double worldDx = dx / _scale;
 double worldDy = -dy / _scale;
 _viewCenter.X -= (float)worldDx;
 _viewCenter.Y -= (float)worldDy;
 UpdateOffsetFromViewCenter();
 _lastMousePosition = e.Location;
 Redraw();
 }
 }
 private void OnMouseUp(object sender, MouseEventArgs e)
 {
 if (_isPanning)
 {
 _isPanning = false;
 _panel.Cursor = Cursors.Default;
 }
 }
 #endregion
  }
}

• Fe2O3: 400,000 edges... Do you "pre-filter" for only those nodes or edges that would appear if the initial display were 'zoomed' to best display the path being proposed? Short 'journeys' need fine grained detail; proposed long journeys are best described with only a few major waypoints. If a node is more than, say, 10% outside of any frame, it should be disregarded immediately, not "painted" into the ether... It may be good to add more info to your database to distinguish between a short grassy footpath and a long major thoroughfare...
• Ahmed3656: @Fe2O3 yes indeed I don't draw anything outside the visible bounds when zoomed in as it won't be of use. This application is mainly for long distance paths, something like google maps directions, though if a query of only a walking distance is entered it does only display the walking edges properly.
• Fe2O3: Suggestion: There's likely to be a limit to the range of minimum to maximum useful(!) zoom to be used. At the cost of storage, using 'integer' nodes vs. 'float' operations may provide some speed. (There's a number of float divisions in this code.) Again, "pre-conditioning" the raw data may yield a speed benefit. (Do you need float's 24 bits of precision for a 1000x1000 display that resolves each pixel to only ~10 bits?)

Answer 1

If there is a way to draw the graph only once [...]

Rendering it onto a bitmap would only allow panning, zooming would be a problem, and the bitmap may waste a lot of space depending on how big you make it. But there may be some options there. Anyway there are some other things that I want to highlight.

For every edge _highlightedPath.Contains is called. _highlightedPath is a list so that's a linear search. Maybe the list is always short, then it doesn't have to be bad, but it's a suspicious thing to have. Do you need this check at all (for example I would consider drawing every edge normally first, and then over-drawing the highlighted path on top, just so there's no check) and does it need to be based on a list? At least put it last, after the constant-time checks. The bounding box checks look cheapest to me so they should probably be first, but it's easier for you to try it than it is for me to guess.

At this scale (hundreds of thousands of nodes/edges) it may pay to have some space-partitioning data structure (coarse grid or quad tree, that sort of thing) to in the first place limit the number of nodes/edges that need to be tested against the bounds, but that only helps when many of them are not in view.

A lot of pens and brushes are created, used once, and then immediately destroyed. Unfortunately these are not simple data-only objects that only represent a color (plus a couple of other parameters), they're GDI+ resources wrapped in an object. Creating and deleting them both involve a PInvoke call to native code. It's not that big of a deal to create dozens or even hundreds of them, but you probably don't want to create and delete hundreds of thousands of them for one frame.

This all seems a bit much for the good old GDI+based rendering to handle, it would be more complicated but you could move to GPU-based rendering. Drawing a hundred thousand nodes and a hundred thousand edges on the GPU doesn't sound too bad, as long as they're batched and not drawn individually. Scenes with millions of triangles in them are routinely rendered at good frame rates, you could have smooth panning and zooming.

• Olivier Jacot-Descombes: SkiaSharp is a library which allows you to use GPU rendering easily in winforms.
• Ahmed3656: Thanks, really useful points. I’ll try out your suggestions and see how it goes especially the part about the highlighted path and the brushes. Didn’t realize GDI+ was that heavy on those. I’ll follow up once I’ve tested a few things.