Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
ContractedGraph.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 ContractedGraph : IGraph
38  {
39  private IGraph graph;
40  private DisjointSet<Node> nodeGroups;
41  private int unionCount;
42 
43  public ContractedGraph(IGraph graph)
44  {
45  this.graph = graph;
46  nodeGroups = new DisjointSet<Node>();
47  Reset();
48  }
49 
51  public void Reset()
52  {
53  nodeGroups.Clear();
54  unionCount = 0;
55  }
56 
61  public Node Merge(Node u, Node v)
62  {
63  var x = nodeGroups.WhereIs(u);
64  var y = nodeGroups.WhereIs(v);
65  if (x.Equals(y)) return x.Representative;
66  unionCount++;
67  return nodeGroups.Union(x, y).Representative;
68  }
69 
73  public Node Contract(Arc arc)
74  {
75  return Merge(graph.U(arc), graph.V(arc));
76  }
77 
78  public Node U(Arc arc)
79  {
80  return nodeGroups.WhereIs(graph.U(arc)).Representative;
81  }
82 
83  public Node V(Arc arc)
84  {
85  return nodeGroups.WhereIs(graph.V(arc)).Representative;
86  }
87 
88  public bool IsEdge(Arc arc)
89  {
90  return graph.IsEdge(arc);
91  }
92 
93  public IEnumerable<Node> Nodes()
94  {
95  foreach (var node in graph.Nodes())
96  if (nodeGroups.WhereIs(node).Representative == node) yield return node;
97  }
98 
99  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
100  {
101  return graph.Arcs(filter);
102  }
103 
104  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
105  {
106  DisjointSetSet<Node> x = nodeGroups.WhereIs(u);
107  foreach (var node in nodeGroups.Elements(x))
108  {
109  foreach (var arc in graph.Arcs(node, filter))
110  {
111  bool loop = (U(arc) == V(arc));
112  // we should avoid outputting an arc twice
113  if (!loop || !(filter == ArcFilter.All || IsEdge(arc)) || graph.U(arc) == node)
114  yield return arc;
115  }
116  }
117  }
118 
119  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
120  {
121  foreach (var arc in Arcs(u, filter))
122  if (this.Other(arc, u) == v) yield return arc;
123  }
124 
125  public int NodeCount()
126  {
127  return graph.NodeCount() - unionCount;
128  }
129 
130  public int ArcCount(ArcFilter filter = ArcFilter.All)
131  {
132  return graph.ArcCount(filter);
133  }
134 
135  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
136  {
137  return Arcs(u, filter).Count();
138  }
139 
140  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
141  {
142  return Arcs(u, v, filter).Count();
143  }
144 
145  public bool HasNode(Node node)
146  {
147  return node == nodeGroups.WhereIs(node).Representative;
148  }
149 
150  public bool HasArc(Arc arc)
151  {
152  return graph.HasArc(arc);
153  }
154  }
155 }