Skip to content

Instantly share code, notes, and snippets.

@amir734jj
Created April 9, 2022 07:27
Show Gist options
  • Save amir734jj/f5b072f41cf38eb32062106a6128c815 to your computer and use it in GitHub Desktop.
Save amir734jj/f5b072f41cf38eb32062106a6128c815 to your computer and use it in GitHub Desktop.
public record Cfg<T>(T Root, HashSet<T> Vertices, HashSet<(T, T)> Edges) where T : IEquatable<T>
{
private Dictionary<(T, T), bool> reach => Reach();
private readonly Dictionary<T, HashSet<T>> dom = new();
private readonly Dictionary<T, HashSet<T>> pred = new();
/// <summary>
/// <see href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms"/>
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public HashSet<T> Dom(T n)
{
if (dom.TryGetValue(n, out var result))
{
return result;
}
result = Root.Equals(n)
? new HashSet<T> { n }
: new HashSet<T> { n }
.Concat(Pred(n)
.SelectMany(Dom)
.ToHashSet())
.ToHashSet();
dom[n] = result;
return result;
}
/// <summary>
/// If v is reachable from u, then u is a predecessor of v and v is a successor of u. If there is an arc
/// from u to v, then u is a direct predecessor of v, and v is a direct successor of u.
/// </summary>
/// <param name="v"></param>
/// <returns></returns>
private HashSet<T> Pred(T v)
{
if (pred.TryGetValue(v, out var result))
{
return result;
}
result = Vertices.Where(u => reach[(u, v)]).ToHashSet();
pred[v] = result;
return result;
}
public Dictionary<(T, T), bool> Reach()
{
var result = new Dictionary<(T, T), bool>();
foreach (var vertex1 in Vertices)
{
foreach (var vertex2 in Vertices)
{
result[(vertex1, vertex2)] = Edges.Contains((vertex1, vertex2));
}
}
foreach (var vertex1 in Vertices)
{
foreach (var vertex2 in Vertices)
{
foreach (var vertex3 in Vertices)
{
result[(vertex2, vertex3)] |= result[(vertex2, vertex1)] &&
result[(vertex1, vertex3)];
}
}
}
return result;
}
}
@amir734jj
Copy link
Author

var root = 1;
var vertices = new HashSet<int>
{
    root,
    2,
    3
};
var edges = new HashSet<(int, int)>
{
    (1, 2),
    (2, 3)
};

var result = new Cfg<int>(root, vertices, edges);

Console.WriteLine(string.Join(", ", result.Dom(2)));

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment