Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Matching.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6 
7 namespace Satsuma
8 {
14  public interface IMatching : IGraph
15  {
17  IGraph Graph { get; }
22  Arc MatchedArc(Node node);
23  }
24 
29  public sealed class Matching : IMatching, IClearable
30  {
31  public IGraph Graph { get; private set; }
32 
33  private readonly Dictionary<Node, Arc> matchedArc;
34  private readonly HashSet<Arc> arcs;
35  private int edgeCount;
36 
37  public Matching(IGraph graph)
38  {
39  Graph = graph;
40 
41  matchedArc = new Dictionary<Node, Arc>();
42  arcs = new HashSet<Arc>();
43 
44  Clear();
45  }
46 
47  public void Clear()
48  {
49  matchedArc.Clear();
50  arcs.Clear();
51  edgeCount = 0;
52  }
53 
58  public void Enable(Arc arc, bool enabled)
59  {
60  if (enabled == arcs.Contains(arc)) return;
61  Node u = Graph.U(arc), v = Graph.V(arc);
62  if (enabled)
63  {
64  if (u == v)
65  throw new ArgumentException("Matchings cannot have loop arcs.");
66  if (matchedArc.ContainsKey(u))
67  throw new ArgumentException("Node is already matched: " + u);
68  if (matchedArc.ContainsKey(v))
69  throw new ArgumentException("Node is already matched: " + v);
70  matchedArc[u] = arc;
71  matchedArc[v] = arc;
72  arcs.Add(arc);
73  if (Graph.IsEdge(arc)) edgeCount++;
74  }
75  else
76  {
77  matchedArc.Remove(u);
78  matchedArc.Remove(v);
79  arcs.Remove(arc);
80  if (Graph.IsEdge(arc)) edgeCount--;
81  }
82  }
83 
84  public Arc MatchedArc(Node node)
85  {
86  Arc arc;
87  return matchedArc.TryGetValue(node, out arc) ? arc : Arc.Invalid;
88  }
89 
90  public Node U(Arc arc)
91  {
92  return Graph.U(arc);
93  }
94 
95  public Node V(Arc arc)
96  {
97  return Graph.V(arc);
98  }
99 
100  public bool IsEdge(Arc arc)
101  {
102  return Graph.IsEdge(arc);
103  }
104 
105  public IEnumerable<Node> Nodes()
106  {
107  return matchedArc.Keys;
108  }
109 
110  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
111  {
112  if (filter == ArcFilter.All) return arcs;
113  if (edgeCount == 0) return Enumerable.Empty<Arc>();
114  return arcs.Where(arc => IsEdge(arc));
115  }
116 
117  // arc must contain u
118  private bool YieldArc(Node u, ArcFilter filter, Arc arc)
119  {
120  return (filter == ArcFilter.All || IsEdge(arc) ||
121  (filter == ArcFilter.Forward && U(arc) == u) ||
122  (filter == ArcFilter.Backward && V(arc) == u));
123  }
124 
125  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
126  {
127  Arc arc = MatchedArc(u);
128  if (arc != Arc.Invalid && YieldArc(u, filter, arc)) yield return arc;
129  }
130 
131  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
132  {
133  if (u != v)
134  {
135  Arc arc = MatchedArc(u);
136  if (arc != Arc.Invalid && arc == MatchedArc(v) && YieldArc(u, filter, arc)) yield return arc;
137  }
138  }
139 
140  public int NodeCount()
141  {
142  return matchedArc.Count;
143  }
144 
145  public int ArcCount(ArcFilter filter = ArcFilter.All)
146  {
147  return filter == ArcFilter.All ? arcs.Count : edgeCount;
148  }
149 
150  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
151  {
152  Arc arc = MatchedArc(u);
153  return arc != Arc.Invalid && YieldArc(u, filter, arc) ? 1 : 0;
154  }
155 
156  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
157  {
158  if (u != v)
159  {
160  Arc arc = MatchedArc(u);
161  return arc != Arc.Invalid && arc == MatchedArc(v) && YieldArc(u, filter, arc) ? 1 : 0;
162  }
163  return 0;
164  }
165 
166  public bool HasNode(Node node)
167  {
168  return Graph.HasNode(node) && matchedArc.ContainsKey(node);
169  }
170 
171  public bool HasArc(Arc arc)
172  {
173  return Graph.HasArc(arc) && arcs.Contains(arc);
174  }
175  }
176 }