Balancing directed graph
I have a set of edges looking like this:
public class Edge<T>
{
public T From { get; set; }
public T To { get; set; }
}
Now I would like to check if my schedule is balanced. By "balanced" I mean that any vertex has an equal number of incoming and outgoing edges. My current code:
public static bool IsGraphBalanced<T>(List<Edge<T>> edges)
{
var from = new Dictionary<T, int>);
var to = new Dictionary<T, int>);
foreach (var edge in edges)
{
if (!from.ContainsKey(edge.From))
from.Add(edge.From, 0);
if (!to.ContainsKey(edge.To))
to.Add(edge.To, 0);
from[edge.From] += 1;
to[edge.To] += 1;
}
foreach (var kv in from)
{
if (!to.ContainsKey(kv.Key))
return false;
if (to[kv.Key] != kv.Value)
return false;
}
// mirrored check with foreach on "to" dictionary
return true;
}
Can Linq replace it?
PS The size edges
is less than 100-150 elements, so I need readability, not performance
source to share
Here is a brief implementation using Enumerable
the class ToLookup
, All
, Count
and Any
extension methods (I'll let you decide whether it is more readable or not):
public static bool IsGraphBalanced<T>(List<Edge<T>> edges)
{
var from = edges.ToLookup(e => e.From);
var to = edges.ToLookup(e => e.To);
return from.All(g => g.Count() == to[g.Key].Count())
&& to.All(g => from[g.Key].Any());
}
The method ToLookup
is similar GroupBy
but creates a reusable data structure (because we need 2 passes).
Then from.All(g => g.Count() == to[g.Key].Count())
checks if each From
matching To
and their counters match . Note that in case the key does not exist, the indexer ILookup<TKey, TElement>
does not throw an exception or return null
, but returns empty IEnumerable<TElement>
, which allows us to combine checks.
Finally, to.All(g => from[g.Key].Any())
checks if each has a To
matching one From
. There is no need to check the counters here because they were checked in the previous step.
source to share