Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Supergraph.cs
Go to the documentation of this file.
1 #region License
2 /*This file is part of Satsuma Graph Library
3 Copyright © 2013 Balázs Szalkai
4 
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any damages
7 arising from the use of this software.
8 
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it
11 freely, subject to the following restrictions:
12 
13  1. The origin of this software must not be misrepresented; you must not
14  claim that you wrote the original software. If you use this software
15  in a product, an acknowledgment in the product documentation would be
16  appreciated but is not required.
17 
18  2. Altered source versions must be plainly marked as such, and must not be
19  misrepresented as being the original software.
20 
21  3. This notice may not be removed or altered from any source
22  distribution.*/
23 #endregion
24 
25 using System;
26 using System.Collections.Generic;
27 using System.Linq;
28 
29 namespace Satsuma
30 {
49  {
50  private class NodeAllocator : IdAllocator
51  {
52  public Supergraph Parent;
53  public NodeAllocator() : base() { }
54  protected override bool IsAllocated(long id) { return Parent.HasNode(new Node(id)); }
55  }
56 
57  private class ArcAllocator : IdAllocator
58  {
59  public Supergraph Parent;
60  public ArcAllocator() : base() { }
61  protected override bool IsAllocated(long id) { return Parent.HasArc(new Arc(id)); }
62  }
63 
64  private class ArcProperties
65  {
66  public Node U { get; private set; }
67  public Node V { get; private set; }
68  public bool IsEdge { get; private set; }
69 
70  public ArcProperties(Node u, Node v, bool isEdge)
71  {
72  U = u;
73  V = v;
74  IsEdge = isEdge;
75  }
76  }
77 
78  private IGraph graph;
79 
80  private NodeAllocator nodeAllocator;
81  private ArcAllocator arcAllocator;
82 
83  private HashSet<Node> nodes;
84  private HashSet<Arc> arcs;
85  private Dictionary<Arc, ArcProperties> arcProperties;
86  private HashSet<Arc> edges;
87 
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;
92 
93  public Supergraph(IGraph graph)
94  {
95  this.graph = graph;
96 
97  nodeAllocator = new NodeAllocator() { Parent = this };
98  arcAllocator = new ArcAllocator() { Parent = this };
99 
100  nodes = new HashSet<Node>();
101  arcs = new HashSet<Arc>();
102  arcProperties = new Dictionary<Arc, ArcProperties>();
103  edges = new HashSet<Arc>();
104 
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>>();
109  }
110 
112  public void Clear()
113  {
114  nodeAllocator.Rewind();
115  arcAllocator.Rewind();
116 
117  nodes.Clear();
118  arcs.Clear();
119  arcProperties.Clear();
120  edges.Clear();
121 
122  nodeArcs_All.Clear();
123  nodeArcs_Edge.Clear();
124  nodeArcs_Forward.Clear();
125  nodeArcs_Backward.Clear();
126  }
127 
128  public Node AddNode()
129  {
130  if (NodeCount() == int.MaxValue) throw new InvalidOperationException("Error: too many nodes!");
131  Node node = new Node(nodeAllocator.Allocate());
132  nodes.Add(node);
133 
134  return node;
135  }
136 
137  public Arc AddArc(Node u, Node v, Directedness directedness)
138  {
139  if (ArcCount() == int.MaxValue) throw new InvalidOperationException("Error: too many arcs!");
140  Arc a = new Arc(arcAllocator.Allocate());
141  arcs.Add(a);
142  bool isEdge = (directedness == Directedness.Undirected);
143  arcProperties[a] = new ArcProperties(u, v, isEdge);
144 
145  Utils.MakeEntry(nodeArcs_All, u).Add(a);
146  Utils.MakeEntry(nodeArcs_Forward, u).Add(a);
147  Utils.MakeEntry(nodeArcs_Backward, v).Add(a);
148 
149  if (isEdge)
150  {
151  edges.Add(a);
152  Utils.MakeEntry(nodeArcs_Edge, u).Add(a);
153  }
154 
155  if (v != u)
156  {
157  Utils.MakeEntry(nodeArcs_All, v).Add(a);
158  if (isEdge)
159  {
160  Utils.MakeEntry(nodeArcs_Edge, v).Add(a);
161  Utils.MakeEntry(nodeArcs_Forward, v).Add(a);
162  Utils.MakeEntry(nodeArcs_Backward, u).Add(a);
163  }
164  }
165 
166  return a;
167  }
168 
169  public bool DeleteNode(Node node)
170  {
171  if (!nodes.Remove(node)) return false;
172 
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);
177 
178  nodeArcs_All.Remove(node);
179  nodeArcs_Edge.Remove(node);
180  nodeArcs_Forward.Remove(node);
181  nodeArcs_Backward.Remove(node);
182 
183  return true;
184  }
185 
186  public bool DeleteArc(Arc arc)
187  {
188  if (!arcs.Remove(arc)) return false;
189 
190  ArcProperties p = arcProperties[arc];
191  arcProperties.Remove(arc);
192 
193  Utils.RemoveLast(nodeArcs_All[p.U], arc);
194  Utils.RemoveLast(nodeArcs_Forward[p.U], arc);
195  Utils.RemoveLast(nodeArcs_Backward[p.V], arc);
196 
197  if (p.IsEdge)
198  {
199  edges.Remove(arc);
200  Utils.RemoveLast(nodeArcs_Edge[p.U], arc);
201  }
202 
203  if (p.V != p.U)
204  {
205  Utils.RemoveLast(nodeArcs_All[p.V], arc);
206  if (p.IsEdge)
207  {
208  Utils.RemoveLast(nodeArcs_Edge[p.V], arc);
209  Utils.RemoveLast(nodeArcs_Forward[p.V], arc);
210  Utils.RemoveLast(nodeArcs_Backward[p.U], arc);
211  }
212  }
213 
214  return true;
215  }
216 
217  public Node U(Arc arc)
218  {
219  ArcProperties p;
220  if (arcProperties.TryGetValue(arc, out p)) return p.U;
221  return graph.U(arc);
222  }
223 
224  public Node V(Arc arc)
225  {
226  ArcProperties p;
227  if (arcProperties.TryGetValue(arc, out p)) return p.V;
228  return graph.V(arc);
229  }
230 
231  public bool IsEdge(Arc arc)
232  {
233  ArcProperties p;
234  if (arcProperties.TryGetValue(arc, out p)) return p.IsEdge;
235  return graph.IsEdge(arc);
236  }
237 
238  private HashSet<Arc> ArcsInternal(ArcFilter filter)
239  {
240  return filter == ArcFilter.All ? arcs : edges;
241  }
242 
243  private static readonly List<Arc> EmptyArcList = new List<Arc>();
244  private List<Arc> ArcsInternal(Node v, ArcFilter filter)
245  {
246  List<Arc> result;
247  switch (filter)
248  {
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;
253  }
254  return result ?? EmptyArcList;
255  }
256 
257  public IEnumerable<Node> Nodes()
258  {
259  return graph == null ? nodes : nodes.Concat(graph.Nodes());
260  }
261 
262  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
263  {
264  return graph == null ? ArcsInternal(filter) : ArcsInternal(filter).Concat(graph.Arcs(filter));
265  }
266 
267  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
268  {
269  if (graph == null || nodes.Contains(u)) return ArcsInternal(u, filter);
270  return ArcsInternal(u, filter).Concat(graph.Arcs(u, filter));
271  }
272 
273  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
274  {
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))
279  yield return arc;
280  }
281 
282  public int NodeCount()
283  {
284  return nodes.Count + (graph == null ? 0 : graph.NodeCount());
285  }
286 
287  public int ArcCount(ArcFilter filter = ArcFilter.All)
288  {
289  return ArcsInternal(filter).Count + (graph == null ? 0 : graph.ArcCount(filter));
290  }
291 
292  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
293  {
294  return ArcsInternal(u, filter).Count + (graph == null || nodes.Contains(u) ? 0 : graph.ArcCount(u, filter));
295  }
296 
297  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
298  {
299  int result = 0;
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));
303  }
304 
305  public bool HasNode(Node node)
306  {
307  return nodes.Contains(node) || (graph != null && graph.HasNode(node));
308  }
309 
310  public bool HasArc(Arc arc)
311  {
312  return arcs.Contains(arc) || (graph != null && graph.HasArc(arc));
313  }
314  }
315 }