Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Subgraph.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 {
37  public sealed class Subgraph : IGraph
38  {
39  private IGraph graph;
40 
41  private bool defaultNodeEnabled;
42  private HashSet<Node> nodeExceptions = new HashSet<Node>();
43  private bool defaultArcEnabled;
44  private HashSet<Arc> arcExceptions = new HashSet<Arc>();
45 
46  public Subgraph(IGraph graph)
47  {
48  this.graph = graph;
49 
50  EnableAllNodes(true);
51  EnableAllArcs(true);
52  }
53 
56  public void EnableAllNodes(bool enabled)
57  {
58  defaultNodeEnabled = enabled;
59  nodeExceptions.Clear();
60  }
61 
64  public void EnableAllArcs(bool enabled)
65  {
66  defaultArcEnabled = enabled;
67  arcExceptions.Clear();
68  }
69 
72  public void Enable(Node node, bool enabled)
73  {
74  bool exception = (defaultNodeEnabled != enabled);
75  if (exception)
76  nodeExceptions.Add(node);
77  else nodeExceptions.Remove(node);
78  }
79 
82  public void Enable(Arc arc, bool enabled)
83  {
84  bool exception = (defaultArcEnabled != enabled);
85  if (exception)
86  arcExceptions.Add(arc);
87  else arcExceptions.Remove(arc);
88  }
89 
91  public bool IsEnabled(Node node)
92  {
93  return defaultNodeEnabled ^ nodeExceptions.Contains(node);
94  }
95 
97  public bool IsEnabled(Arc arc)
98  {
99  return defaultArcEnabled ^ arcExceptions.Contains(arc);
100  }
101 
102  public Node U(Arc arc)
103  {
104  return graph.U(arc);
105  }
106 
107  public Node V(Arc arc)
108  {
109  return graph.V(arc);
110  }
111 
112  public bool IsEdge(Arc arc)
113  {
114  return graph.IsEdge(arc);
115  }
116 
117  private IEnumerable<Node> NodesInternal()
118  {
119  foreach (var node in graph.Nodes())
120  if (IsEnabled(node)) yield return node;
121  }
122 
123  public IEnumerable<Node> Nodes()
124  {
125  if (nodeExceptions.Count == 0)
126  {
127  if (defaultNodeEnabled) return graph.Nodes();
128  return Enumerable.Empty<Node>();
129  }
130  return NodesInternal();
131  }
132 
133  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
134  {
135  foreach (var arc in graph.Arcs(filter))
136  if (IsEnabled(arc) && IsEnabled(graph.U(arc)) && IsEnabled(graph.V(arc))) yield return arc;
137  }
138 
139  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
140  {
141  if (!IsEnabled(u)) yield break;
142  foreach (var arc in graph.Arcs(u, filter))
143  if (IsEnabled(arc) && IsEnabled(graph.Other(arc, u))) yield return arc;
144  }
145 
146  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
147  {
148  if (!IsEnabled(u) || !IsEnabled(v)) yield break;
149  foreach (var arc in graph.Arcs(u, v, filter))
150  if (IsEnabled(arc)) yield return arc;
151  }
152 
153  public int NodeCount()
154  {
155  return defaultNodeEnabled ? graph.NodeCount() - nodeExceptions.Count : nodeExceptions.Count;
156  }
157 
158  public int ArcCount(ArcFilter filter = ArcFilter.All)
159  {
160  if (nodeExceptions.Count == 0 && filter == ArcFilter.All)
161  return defaultNodeEnabled ?
162  (defaultArcEnabled ? graph.ArcCount() - arcExceptions.Count : arcExceptions.Count)
163  : 0;
164 
165  return Arcs(filter).Count();
166  }
167 
168  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
169  {
170  return Arcs(u, filter).Count();
171  }
172 
173  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
174  {
175  return Arcs(u, v, filter).Count();
176  }
177 
178  public bool HasNode(Node node)
179  {
180  return graph.HasNode(node) && IsEnabled(node);
181  }
182 
183  public bool HasArc(Arc arc)
184  {
185  return graph.HasArc(arc) && IsEnabled(arc);
186  }
187  }
188 }