< Summary

Information
Class: Elsa.Workflows.Activities.Flowchart.Models.FlowGraph
Assembly: Elsa.Workflows.Core
File(s): /home/runner/work/elsa-core/elsa-core/src/modules/Elsa.Workflows.Core/Activities/Flowchart/Models/FlowGraph.cs
Line coverage
96%
Covered lines: 94
Uncovered lines: 3
Coverable lines: 97
Total lines: 249
Line coverage: 96.9%
Branch coverage
94%
Covered branches: 68
Total branches: 72
Branch coverage: 94.4%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%11100%
get_ForwardConnections()75%44100%
GetForwardInboundConnections(...)100%11100%
GetOutboundConnections(...)100%11100%
GetInboundConnections(...)100%11100%
IsDanglingActivity(...)100%44100%
IsBackwardConnection(...)75%4471.42%
GetAncestorActivities(...)100%11100%
ComputeAncestors(...)100%1414100%
GetForwardConnections(...)100%1818100%
HasPathToActivity(...)92.85%141493.33%
IsValidBackwardConnection(...)83.33%66100%
GetPathsToRoot(...)100%88100%

File(s)

/home/runner/work/elsa-core/elsa-core/src/modules/Elsa.Workflows.Core/Activities/Flowchart/Models/FlowGraph.cs

#LineLine coverage
 1using Elsa.Extensions;
 2using Elsa.Workflows.Activities.Flowchart.Extensions;
 3
 4namespace Elsa.Workflows.Activities.Flowchart.Models;
 5
 6/// <summary>
 7/// Represents a directed graph structure for managing workflow connections.
 8/// Caches forward and backward connections to optimize graph traversal.
 9/// </summary>
 69210public class FlowGraph(ICollection<Connection> connections, IActivity? rootActivity)
 11{
 12    private List<Connection>? _cachedForwardConnections;
 69213    private readonly Dictionary<IActivity, List<Connection>> _cachedInboundForwardConnections = new();
 69214    private readonly Dictionary<IActivity, List<Connection>> _cachedInboundConnections = new();
 69215    private readonly Dictionary<IActivity, List<Connection>> _cachedOutboundConnections = new();
 69216    private readonly Dictionary<Connection, (bool IsBackwardConnection, bool IsValid)> _cachedIsBackwardConnection = new
 69217    private readonly Dictionary<IActivity, bool> _cachedIsDanglingActivity = new();
 69218    private readonly Dictionary<IActivity, List<IActivity>> _cachedAncestors = new();
 19
 20    /// <summary>
 21    /// Gets the list of forward connections, computing them if not already cached.
 22    /// </summary>
 77523    private List<Connection> ForwardConnections => _cachedForwardConnections ??= rootActivity == null ? new() : GetForwa
 24
 25    /// <summary>
 26    /// Retrieves all inbound forward connections for a given activity.
 27    /// </summary>
 116128    public List<Connection> GetForwardInboundConnections(IActivity activity) => _cachedInboundForwardConnections.GetOrAd
 29
 30    /// <summary>
 31    /// Retrieves all outbound connections for a given activity.
 32    /// </summary>
 230633    public List<Connection> GetOutboundConnections(IActivity activity) => _cachedOutboundConnections.GetOrAdd(activity, 
 34
 35    /// <summary>
 36    /// Retrieves all inbound connections for a given activity.
 37    /// </summary>
 2038    public List<Connection> GetInboundConnections(IActivity activity) => _cachedInboundConnections.GetOrAdd(activity, ()
 39
 40    /// <summary>
 41    /// Determines if a given activity is "dangling," meaning it does not exist as a target in any forward connection.
 42    /// </summary>
 68543    public bool IsDanglingActivity(IActivity activity) => _cachedIsDanglingActivity.GetOrAdd(activity, () => activity !=
 44
 45    /// <summary>
 46    /// Determines if a given connection is a backward connection (i.e., not part of the forward traversal) and whether 
 47    /// </summary>
 48    public bool IsBackwardConnection(Connection connection, out bool isValid)
 49    {
 50        // Check if result is already cached
 12251        if (_cachedIsBackwardConnection.TryGetValue(connection, out var result))
 52        {
 053            isValid = result.IsValid;
 054            return result.IsBackwardConnection;
 55        }
 56
 57        // Compute if the connection is backward
 12258        bool isBackwardConnection = !GetForwardInboundConnections(connection.Target.Activity).Contains(connection);
 59
 60        // Compute if the backward connection is valid
 12261        isValid = isBackwardConnection && IsValidBackwardConnection(ForwardConnections, rootActivity, connection);
 62
 63        // Cache the result
 12264        _cachedIsBackwardConnection[connection] = (isBackwardConnection, isValid);
 65
 12266        return isBackwardConnection;
 67    }
 68
 69    /// <summary>
 70    /// Retrieves all ancestor activities for a given activity by traversing ForwardConnections in reverse.
 71    /// </summary>
 72    public List<IActivity> GetAncestorActivities(IActivity activity)
 73    {
 11074        return _cachedAncestors.GetOrAdd(activity, () => ComputeAncestors(activity));
 75    }
 76
 77    /// <summary>
 78    /// Computes the list of ancestors by following Source activities in ForwardConnections.
 79    /// </summary>
 80    private List<IActivity> ComputeAncestors(IActivity activity)
 81    {
 5382        HashSet<IActivity> ancestors = new();
 5383        Queue<IActivity> queue = new();
 84
 85        // Find all connections where this activity is the target
 62886        foreach (var connection in ForwardConnections.Where(c => c.Target.Activity == activity))
 87        {
 7388            if (ancestors.Add(connection.Source.Activity))
 7189                queue.Enqueue(connection.Source.Activity);
 90        }
 91
 92        // Traverse upwards through the graph
 19893        while (queue.Count > 0)
 94        {
 14595            var current = queue.Dequeue();
 96
 168397            foreach (var connection in ForwardConnections.Where(c => c.Target.Activity == current))
 98            {
 10899                if (ancestors.Add(connection.Source.Activity))
 74100                    queue.Enqueue(connection.Source.Activity);
 101            }
 102        }
 103
 53104        return ancestors.ToList();
 105    }
 106
 107    /// <summary>
 108    /// Computes the list of forward connections in the graph, excluding cyclic connections.
 109    /// </summary>
 110    private static List<Connection> GetForwardConnections(ICollection<Connection> connections, IActivity root)
 111    {
 271112        Dictionary<IActivity, List<IActivity>> adjList = new();
 113
 1608114        foreach (var conn in connections)
 115        {
 533116            if (!adjList.ContainsKey(conn.Source.Activity))
 461117                adjList[conn.Source.Activity] = new();
 118
 533119            adjList[conn.Source.Activity].Add(conn.Target.Activity);
 120        }
 121
 271122        HashSet<IActivity> visited = new();
 271123        HashSet<(IActivity, IActivity)> visitedEdges = new();
 271124        List<(IActivity Source, IActivity Target)> validEdges = new();
 271125        Queue<IActivity> queue = new();
 126
 271127        queue.Enqueue(root);
 128
 1059129        while (queue.Count > 0)
 130        {
 788131            var source = queue.Dequeue();
 788132            visited.Add(source);
 133
 788134            if (!adjList.ContainsKey(source)) continue;
 135
 2100136            foreach (var target in adjList[source])
 137            {
 564138                var edge = (source, target);
 564139                if (visitedEdges.Contains(edge))
 140                    continue;
 141
 525142                if (HasPathToActivity(validEdges, target, source))
 143                    continue;
 144
 519145                visitedEdges.Add(edge);
 519146                validEdges.Add((source, target));
 147
 519148                if (!visited.Contains(target))
 517149                    queue.Enqueue(target);
 150            }
 151        }
 152
 271153        return validEdges
 2758154            .SelectMany(e => connections.Where(c => c.Source.Activity == e.Source && c.Target.Activity == e.Target))
 271155            .Distinct()
 271156            .ToList();
 157    }
 158
 159    /// <summary>
 160    /// Determines if there is an existing path from the source activity to the target activity.
 161    /// Helps in detecting cyclic connections.
 162    /// </summary>
 163    private static bool HasPathToActivity(ICollection<(IActivity Source, IActivity Target)> edges, IActivity source, IAc
 164    {
 525165        if (source == target)
 0166            return true;
 167
 525168        HashSet<IActivity> visited = new();
 525169        Stack<IActivity> stack = new();
 525170        stack.Push(source);
 171
 1055172        while (stack.Count > 0)
 173        {
 536174            var current = stack.Pop();
 175
 536176            if (current == target)
 6177                return true;
 178
 530179            if (visited.Contains(current))
 180                continue;
 181
 530182            visited.Add(current);
 183
 1988184            foreach (var next in edges.Where(x => x.Source == current).Select(e => e.Target))
 185            {
 15186                if (!visited.Contains(next))
 15187                    stack.Push(next);
 188            }
 189        }
 190
 519191        return false;
 192    }
 193
 194    /// <summary>
 195    /// Determines whether a backward connection is valid by ensuring all paths from source to root pass through target.
 196    /// </summary>
 197    private static bool IsValidBackwardConnection(List<Connection> forwardConnections, IActivity? root, Connection conne
 198    {
 3199        if (root == null) return false;
 200
 3201        var pathsToRoot = GetPathsToRoot(forwardConnections, root, connection.Source.Activity);
 202
 12203        foreach (var path in pathsToRoot)
 204        {
 4205            if (!path.Contains(connection.Target.Activity))
 2206                return false;
 207        }
 208
 1209        return true;
 2210    }
 211
 212    /// <summary>
 213    /// Finds all paths from a given start activity to the root using BFS.
 214    /// </summary>
 215    private static List<List<IActivity>> GetPathsToRoot(List<Connection> forwardConnections, IActivity root, IActivity s
 216    {
 3217        List<List<IActivity>> paths = new();
 3218        Queue<List<IActivity>> queue = new();
 3219        queue.Enqueue(new()
 3220            { start });
 221
 28222        while (queue.Count > 0)
 223        {
 25224            var path = queue.Dequeue();
 25225            var lastNode = path.Last();
 226
 25227            if (lastNode == root)
 228            {
 8229                paths.Add([..path]);
 8230                continue;
 231            }
 232
 17233            var previousNodes = forwardConnections
 109234                .Where(c => c.Target.Activity == lastNode)
 39235                .Select(c => c.Source.Activity);
 236
 78237            foreach (var prev in previousNodes)
 238            {
 22239                if (!path.Contains(prev))
 240                {
 22241                    var newPath = new List<IActivity>(path) { prev };
 22242                    queue.Enqueue(newPath);
 243                }
 244            }
 245        }
 246
 3247        return paths;
 248    }
 249}
Generated by: ReportGenerator 5.5.0.0
11/27/2025 - 20:46:54
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Collections.Generic.ICollection`1<Elsa.Workflows.Activities.Flowchart.Models.Connection>,Elsa.Workflows.IActivity)
get_ForwardConnections()
GetForwardInboundConnections(Elsa.Workflows.IActivity)
GetOutboundConnections(Elsa.Workflows.IActivity)
GetInboundConnections(Elsa.Workflows.IActivity)
IsDanglingActivity(Elsa.Workflows.IActivity)
IsBackwardConnection(Elsa.Workflows.Activities.Flowchart.Models.Connection,System.Boolean&)
GetAncestorActivities(Elsa.Workflows.IActivity)
ComputeAncestors(Elsa.Workflows.IActivity)
GetForwardConnections(System.Collections.Generic.ICollection`1<Elsa.Workflows.Activities.Flowchart.Models.Connection>,Elsa.Workflows.IActivity)
HasPathToActivity(System.Collections.Generic.ICollection`1<System.ValueTuple`2<Elsa.Workflows.IActivity,Elsa.Workflows.IActivity>>,Elsa.Workflows.IActivity,Elsa.Workflows.IActivity)
IsValidBackwardConnection(System.Collections.Generic.List`1<Elsa.Workflows.Activities.Flowchart.Models.Connection>,Elsa.Workflows.IActivity,Elsa.Workflows.Activities.Flowchart.Models.Connection)
GetPathsToRoot(System.Collections.Generic.List`1<Elsa.Workflows.Activities.Flowchart.Models.Connection>,Elsa.Workflows.IActivity,Elsa.Workflows.IActivity)