26 using System.Collections.Generic;
50 private class NodeAllocator : IdAllocator
53 public NodeAllocator() : base() { }
54 protected override bool IsAllocated(
long id) {
return Parent.HasNode(
new Node(
id)); }
57 private class ArcAllocator : IdAllocator
60 public ArcAllocator() : base() { }
61 protected override bool IsAllocated(
long id) {
return Parent.HasArc(
new Arc(
id)); }
64 private class ArcProperties
66 public Node U {
get;
private set; }
67 public Node V {
get;
private set; }
68 public bool IsEdge {
get;
private set; }
70 public ArcProperties(
Node u,
Node v,
bool isEdge)
80 private NodeAllocator nodeAllocator;
81 private ArcAllocator arcAllocator;
83 private HashSet<Node> nodes;
84 private HashSet<Arc> arcs;
85 private Dictionary<Arc, ArcProperties> arcProperties;
86 private HashSet<Arc> edges;
88 private Dictionary<Node, List<Arc>> nodeArcs_All;
89 private Dictionary<Node, List<Arc>> nodeArcs_Edge;
90 private Dictionary<Node, List<Arc>> nodeArcs_Forward;
91 private Dictionary<Node, List<Arc>> nodeArcs_Backward;
97 nodeAllocator =
new NodeAllocator() { Parent =
this };
98 arcAllocator =
new ArcAllocator() { Parent =
this };
100 nodes =
new HashSet<Node>();
101 arcs =
new HashSet<Arc>();
102 arcProperties =
new Dictionary<Arc, ArcProperties>();
103 edges =
new HashSet<Arc>();
105 nodeArcs_All =
new Dictionary<Node, List<Arc>>();
106 nodeArcs_Edge =
new Dictionary<Node, List<Arc>>();
107 nodeArcs_Forward =
new Dictionary<Node, List<Arc>>();
108 nodeArcs_Backward =
new Dictionary<Node, List<Arc>>();
114 nodeAllocator.Rewind();
115 arcAllocator.Rewind();
119 arcProperties.Clear();
122 nodeArcs_All.Clear();
123 nodeArcs_Edge.Clear();
124 nodeArcs_Forward.Clear();
125 nodeArcs_Backward.Clear();
130 if (
NodeCount() ==
int.MaxValue)
throw new InvalidOperationException(
"Error: too many nodes!");
131 Node node =
new Node(nodeAllocator.Allocate());
139 if (
ArcCount() ==
int.MaxValue)
throw new InvalidOperationException(
"Error: too many arcs!");
140 Arc a =
new Arc(arcAllocator.Allocate());
142 bool isEdge = (directedness ==
Directedness.Undirected);
143 arcProperties[a] =
new ArcProperties(u, v, isEdge);
145 Utils.MakeEntry(nodeArcs_All, u).Add(a);
146 Utils.MakeEntry(nodeArcs_Forward, u).Add(a);
147 Utils.MakeEntry(nodeArcs_Backward, v).Add(a);
152 Utils.MakeEntry(nodeArcs_Edge, u).Add(a);
157 Utils.MakeEntry(nodeArcs_All, v).Add(a);
160 Utils.MakeEntry(nodeArcs_Edge, v).Add(a);
161 Utils.MakeEntry(nodeArcs_Forward, v).Add(a);
162 Utils.MakeEntry(nodeArcs_Backward, u).Add(a);
171 if (!nodes.Remove(node))
return false;
173 Func<Arc, bool> arcsToRemove = (a => (
U(a) == node ||
V(a) == node));
174 Utils.RemoveAll(arcs, arcsToRemove);
175 Utils.RemoveAll(edges, arcsToRemove);
176 Utils.RemoveAll(arcProperties, arcsToRemove);
178 nodeArcs_All.Remove(node);
179 nodeArcs_Edge.Remove(node);
180 nodeArcs_Forward.Remove(node);
181 nodeArcs_Backward.Remove(node);
188 if (!arcs.Remove(arc))
return false;
190 ArcProperties p = arcProperties[arc];
191 arcProperties.Remove(arc);
193 Utils.RemoveLast(nodeArcs_All[p.U], arc);
194 Utils.RemoveLast(nodeArcs_Forward[p.U], arc);
195 Utils.RemoveLast(nodeArcs_Backward[p.V], arc);
200 Utils.RemoveLast(nodeArcs_Edge[p.U], arc);
205 Utils.RemoveLast(nodeArcs_All[p.V], arc);
208 Utils.RemoveLast(nodeArcs_Edge[p.V], arc);
209 Utils.RemoveLast(nodeArcs_Forward[p.V], arc);
210 Utils.RemoveLast(nodeArcs_Backward[p.U], arc);
220 if (arcProperties.TryGetValue(arc, out p))
return p.U;
227 if (arcProperties.TryGetValue(arc, out p))
return p.V;
234 if (arcProperties.TryGetValue(arc, out p))
return p.IsEdge;
238 private HashSet<Arc> ArcsInternal(
ArcFilter filter)
240 return filter ==
ArcFilter.All ? arcs : edges;
243 private static readonly List<Arc> EmptyArcList =
new List<Arc>();
244 private List<Arc> ArcsInternal(Node v,
ArcFilter filter)
249 case ArcFilter.All: nodeArcs_All.TryGetValue(v, out result);
break;
250 case ArcFilter.Edge: nodeArcs_Edge.TryGetValue(v, out result);
break;
251 case ArcFilter.Forward: nodeArcs_Forward.TryGetValue(v, out result);
break;
252 default: nodeArcs_Backward.TryGetValue(v, out result);
break;
254 return result ?? EmptyArcList;
259 return graph == null ? nodes : nodes.Concat(graph.
Nodes());
264 return graph == null ? ArcsInternal(filter) : ArcsInternal(filter).Concat(graph.
Arcs(filter));
269 if (graph == null || nodes.Contains(u))
return ArcsInternal(u, filter);
270 return ArcsInternal(u, filter).Concat(graph.
Arcs(u, filter));
275 foreach (var arc
in ArcsInternal(u, filter))
276 if (this.Other(arc, u) == v) yield
return arc;
277 if (!(graph == null || nodes.Contains(u) || nodes.Contains(v)))
278 foreach (var arc
in graph.
Arcs(u, v, filter))
284 return nodes.Count + (graph == null ? 0 : graph.
NodeCount());
289 return ArcsInternal(filter).Count + (graph == null ? 0 : graph.
ArcCount(filter));
294 return ArcsInternal(u, filter).Count + (graph == null || nodes.Contains(u) ? 0 : graph.
ArcCount(u, filter));
300 foreach (var arc
in ArcsInternal(u, filter))
301 if (this.Other(arc, u) == v) result++;
302 return result + (graph == null || nodes.Contains(u) || nodes.Contains(v) ? 0 : graph.ArcCount(u, v, filter));
307 return nodes.Contains(node) || (graph != null && graph.
HasNode(node));
312 return arcs.Contains(arc) || (graph != null && graph.
HasArc(arc));