Skip to content

Commit 19698c4

Browse files
justcoding121justcoding121
committed
Let undirected graph algorithms run on directed graphs
1 parent d762f8c commit 19698c4

File tree

19 files changed

+93
-49
lines changed

19 files changed

+93
-49
lines changed

‎src/Advanced.Algorithms/DataStructures/Graph/AdjacencyList/DiGraph.cs

Lines changed: 22 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ namespace Advanced.Algorithms.DataStructures.Graph.AdjacencyList
99
/// A directed graph implementation.
1010
/// IEnumerable enumerates all vertices.
1111
/// </summary>
12-
public class DiGraph<T> : IDiGraph<T>
12+
public class DiGraph<T> : IGraph<T>, IDiGraph<T>, IEnumerable<T>
1313
{
1414
public int VerticesCount => Vertices.Count;
1515
internal Dictionary<T, DiGraphVertex<T>> Vertices { get; set; }
@@ -42,7 +42,9 @@ public DiGraphVertex<T> ReferenceVertex
4242
}
4343

4444
IDiGraphVertex<T> IDiGraph<T>.ReferenceVertex => ReferenceVertex;
45-
45+
IGraphVertex<T> IGraph<T>.ReferenceVertex => ReferenceVertex;
46+
47+
4648
/// <summary>
4749
/// Add a new vertex to this graph.
4850
/// Time complexity: O(1).
@@ -218,28 +220,40 @@ public IDiGraphVertex<T> GetVertex(T value)
218220
return Vertices[value];
219221
}
220222

223+
IGraphVertex<T> IGraph<T>.GetVertex(T key)
224+
{
225+
return Vertices[key];
226+
}
227+
221228
IDiGraph<T> IDiGraph<T>.Clone()
222229
{
223230
return Clone();
224231
}
225232

226-
IEnumerator<IDiGraphVertex<T>> IEnumerable<IDiGraphVertex<T>>.GetEnumerator()
233+
IGraph<T> IGraph<T>.Clone()
227234
{
228-
return GetEnumerator() as IEnumerator<IDiGraphVertex<T>>;
235+
return Clone();
229236
}
230237

231238
public IEnumerator GetEnumerator()
232239
{
233-
return Vertices.Select(x => x.Value).GetEnumerator();
240+
return Vertices.Select(x => x.Key).GetEnumerator();
234241
}
235242

243+
IEnumerator<T> IEnumerable<T>.GetEnumerator()
244+
{
245+
return GetEnumerator() as IEnumerator<T>;
246+
}
247+
248+
public IEnumerable<IGraphVertex<T>> VerticesAsEnumberable => Vertices.Select(x => x.Value);
249+
IEnumerable<IDiGraphVertex<T>> IDiGraph<T>.VerticesAsEnumberable => Vertices.Select(x => x.Value);
236250
}
237251

238252
/// <summary>
239253
/// DiGraph vertex for adjacency list Graph implementation.
240254
/// IEnumerable enumerates all the outgoing edge destination vertices.
241255
/// </summary>
242-
public class DiGraphVertex<T> : IDiGraphVertex<T>, IEnumerable<T>
256+
public class DiGraphVertex<T> : IDiGraphVertex<T>, IGraphVertex<T>, IEnumerable<T>
243257
{
244258
public T Key { get; set; }
245259

@@ -252,6 +266,8 @@ public class DiGraphVertex<T> : IDiGraphVertex<T>, IEnumerable<T>
252266
public int OutEdgeCount => OutEdges.Count;
253267
public int InEdgeCount => InEdges.Count;
254268

269+
IEnumerable<IEdge<T>> IGraphVertex<T>.Edges => OutEdges.Select(x => new Edge<T, int>(x, 1));
270+
255271
public DiGraphVertex(T value)
256272
{
257273
Key = value;

‎src/Advanced.Algorithms/DataStructures/Graph/AdjacencyList/Graph.cs

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ namespace Advanced.Algorithms.DataStructures.Graph.AdjacencyList
99
/// A graph implementation
1010
/// IEnumerable enumerates all vertices.
1111
/// </summary>
12-
public class Graph<T> : IGraph<T>
12+
public class Graph<T> : IGraph<T>, IEnumerable<T>
1313
{
1414
public int VerticesCount => Vertices.Count;
1515
internal Dictionary<T, GraphVertex<T>> Vertices { get; set; }
@@ -210,20 +210,22 @@ public Graph<T> Clone()
210210
return newGraph;
211211
}
212212

213-
IEnumerator<IGraphVertex<T>> IEnumerable<IGraphVertex<T>>.GetEnumerator()
213+
public IEnumerator GetEnumerator()
214214
{
215-
return GetEnumerator() as IEnumerator<IGraphVertex<T>>;
215+
return Vertices.Select(x => x.Key).GetEnumerator();
216216
}
217217

218-
public IEnumerator GetEnumerator()
218+
IEnumerator<T> IEnumerable<T>.GetEnumerator()
219219
{
220-
return Vertices.Select(x => x.Value).GetEnumerator();
220+
return GetEnumerator() as IEnumerator<T>;
221221
}
222222

223223
IGraph<T> IGraph<T>.Clone()
224224
{
225225
return Clone();
226226
}
227+
228+
public IEnumerable<IGraphVertex<T>> VerticesAsEnumberable => Vertices.Select(x => x.Value);
227229
}
228230

229231
/// <summary>

‎src/Advanced.Algorithms/DataStructures/Graph/AdjacencyList/WeightedDiGraph.cs

Lines changed: 25 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ namespace Advanced.Algorithms.DataStructures.Graph.AdjacencyList
99
/// A weighted graph implementation.
1010
/// IEnumerable enumerates all vertices.
1111
/// </summary>
12-
public class WeightedDiGraph<T, TW> : IDiGraph<T> where TW : IComparable
12+
public class WeightedDiGraph<T, TW> : IDiGraph<T>, IGraph<T>, IEnumerable<T> where TW : IComparable
1313
{
1414
public int VerticesCount => Vertices.Count;
1515
internal Dictionary<T, WeightedDiGraphVertex<T, TW>> Vertices { get; set; }
@@ -41,6 +41,7 @@ public WeightedDiGraphVertex<T, TW> ReferenceVertex
4141
}
4242

4343
IDiGraphVertex<T> IDiGraph<T>.ReferenceVertex => ReferenceVertex;
44+
IGraphVertex<T> IGraph<T>.ReferenceVertex => ReferenceVertex;
4445

4546
/// <summary>
4647
/// Add a new vertex to this graph.
@@ -197,9 +198,14 @@ public bool ContainsVertex(T value)
197198
return Vertices.ContainsKey(value);
198199
}
199200

200-
public IDiGraphVertex<T> GetVertex(T value)
201+
IGraphVertex<T> IGraph<T>.GetVertex(T key)
201202
{
202-
return Vertices[value];
203+
return Vertices[key];
204+
}
205+
206+
public IDiGraphVertex<T> GetVertex(T key)
207+
{
208+
return Vertices[key];
203209
}
204210

205211
/// <summary>
@@ -225,27 +231,35 @@ public WeightedDiGraph<T, TW> Clone()
225231
return newGraph;
226232
}
227233

228-
IEnumerator<IDiGraphVertex<T>> IEnumerable<IDiGraphVertex<T>>.GetEnumerator()
234+
IDiGraph<T> IDiGraph<T>.Clone()
229235
{
230-
return GetEnumerator() as IEnumerator<IDiGraphVertex<T>>;
236+
return Clone();
237+
}
238+
239+
IGraph<T> IGraph<T>.Clone()
240+
{
241+
return Clone();
231242
}
232243

233244
public IEnumerator GetEnumerator()
234245
{
235-
return Vertices.Select(x => x.Value).GetEnumerator();
246+
return Vertices.Select(x => x.Key).GetEnumerator();
236247
}
237248

238-
IDiGraph<T> IDiGraph<T>.Clone()
249+
IEnumerator<T> IEnumerable<T>.GetEnumerator()
239250
{
240-
return Clone();
251+
return GetEnumerator() as IEnumerator<T>;
241252
}
253+
254+
public IEnumerable<IGraphVertex<T>> VerticesAsEnumberable => Vertices.Select(x => x.Value);
255+
IEnumerable<IDiGraphVertex<T>> IDiGraph<T>.VerticesAsEnumberable => Vertices.Select(x => x.Value);
242256
}
243257

244258
/// <summary>
245259
/// A weighted graph vertex for adjacency list Graph implementation.
246260
/// IEnumerable enumerates all the outgoing edge destination vertices.
247261
/// </summary>
248-
public class WeightedDiGraphVertex<T, TW> : IDiGraphVertex<T>, IEnumerable<T> where TW : IComparable
262+
public class WeightedDiGraphVertex<T, TW> : IDiGraphVertex<T>, IGraphVertex<T>, IEnumerable<T> where TW : IComparable
249263
{
250264
public T Key { get; private set; }
251265

@@ -258,6 +272,8 @@ public class WeightedDiGraphVertex<T, TW> : IDiGraphVertex<T>, IEnumerable<T> wh
258272
public int OutEdgeCount => OutEdges.Count;
259273
public int InEdgeCount => InEdges.Count;
260274

275+
IEnumerable<IEdge<T>> IGraphVertex<T>.Edges => OutEdges.Select(x => new Edge<T, TW>(x.Key, x.Value));
276+
261277
public WeightedDiGraphVertex(T value)
262278
{
263279
Key = value;

‎src/Advanced.Algorithms/DataStructures/Graph/AdjacencyList/WeightedGraph.cs

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ namespace Advanced.Algorithms.DataStructures.Graph.AdjacencyList
99
/// A weighted graph implementation.
1010
/// IEnumerable enumerates all vertices.
1111
/// </summary>
12-
public class WeightedGraph<T, TW> : IGraph<T> where TW : IComparable
12+
public class WeightedGraph<T, TW> : IGraph<T>, IEnumerable<T> where TW : IComparable
1313
{
1414
public int VerticesCount => Vertices.Count;
1515
internal Dictionary<T, WeightedGraphVertex<T, TW>> Vertices { get; set; }
@@ -207,20 +207,22 @@ public WeightedGraph<T, TW> Clone()
207207
return newGraph;
208208
}
209209

210-
IEnumerator<IGraphVertex<T>> IEnumerable<IGraphVertex<T>>.GetEnumerator()
210+
public IEnumerator GetEnumerator()
211211
{
212-
return GetEnumerator() as IEnumerator<IGraphVertex<T>>;
212+
return Vertices.Select(x => x.Key).GetEnumerator();
213213
}
214214

215-
public IEnumerator GetEnumerator()
215+
IEnumerator<T> IEnumerable<T>.GetEnumerator()
216216
{
217-
return Vertices.Select(x => x.Value).GetEnumerator();
217+
return GetEnumerator() as IEnumerator<T>;
218218
}
219219

220220
IGraph<T> IGraph<T>.Clone()
221221
{
222222
return Clone();
223223
}
224+
225+
public IEnumerable<IGraphVertex<T>> VerticesAsEnumberable => Vertices.Select(x => x.Value);
224226
}
225227

226228
/// <summary>

‎src/Advanced.Algorithms/DataStructures/Graph/IDiGraph.cs

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,14 +3,18 @@
33

44
namespace Advanced.Algorithms.DataStructures.Graph
55
{
6-
public interface IDiGraph<T> : IEnumerable<IDiGraphVertex<T>>
6+
/// <summary>
7+
/// Directed graph.
8+
/// </summary>
9+
/// <typeparam name="T"></typeparam>
10+
public interface IDiGraph<T>
711
{
812
bool IsWeightedGraph { get; }
913

1014
bool ContainsVertex(T value);
1115
IDiGraphVertex<T> GetVertex(T key);
1216
IDiGraphVertex<T> ReferenceVertex { get; }
13-
17+
IEnumerable<IDiGraphVertex<T>> VerticesAsEnumberable { get; }
1418
int VerticesCount { get; }
1519

1620
bool HasEdge(T source, T destination);

‎src/Advanced.Algorithms/DataStructures/Graph/IGraph.cs

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,15 +6,19 @@
66

77
namespace Advanced.Algorithms.DataStructures.Graph
88
{
9-
public interface IGraph<T> : IEnumerable<IGraphVertex<T>>
9+
/// <summary>
10+
/// UnDirected graph.
11+
/// </summary>
12+
/// <typeparam name="T"></typeparam>
13+
public interface IGraph<T>
1014
{
1115
bool IsWeightedGraph { get; }
1216

1317
int VerticesCount { get; }
14-
1518
IGraphVertex<T> ReferenceVertex { get; }
1619
bool ContainsVertex(T key);
1720
IGraphVertex<T> GetVertex(T key);
21+
IEnumerable<IGraphVertex<T>> VerticesAsEnumberable { get; }
1822

1923
bool HasEdge(T source, T destination);
2024

‎src/Advanced.Algorithms/Graph/Connectivity/KosarajuStronglyConnected.cs

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ public List<List<T>>
1919
var finishStack = new Stack<T>();
2020

2121
//step one - create DFS finish visit stack
22-
foreach (var vertex in graph)
22+
foreach (var vertex in graph.VerticesAsEnumberable)
2323
{
2424
if(!visited.Contains(vertex.Key))
2525
{
@@ -98,12 +98,12 @@ private IDiGraph<T> reverseEdges(IDiGraph<T> graph)
9898
{
9999
var newGraph = new DiGraph<T>();
100100

101-
foreach (var vertex in graph)
101+
foreach (var vertex in graph.VerticesAsEnumberable)
102102
{
103103
newGraph.AddVertex(vertex.Key);
104104
}
105105

106-
foreach (var vertex in graph)
106+
foreach (var vertex in graph.VerticesAsEnumberable)
107107
{
108108
foreach (var edge in vertex.OutEdges)
109109
{

‎src/Advanced.Algorithms/Graph/Connectivity/TarjansStronglyConnected.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ public List<List<T>> FindStronglyConnectedComponents(IDiGraph<T> graph)
2222
var pathStack = new Stack<T>();
2323
var pathStackMap = new HashSet<T>();
2424
var discoveryTime = 0;
25-
foreach (var vertex in graph)
25+
foreach (var vertex in graph.VerticesAsEnumberable)
2626
{
2727
if (!discoveryTimeMap.ContainsKey(vertex.Key))
2828
{

‎src/Advanced.Algorithms/Graph/Flow/EdmondsKarp.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -228,13 +228,13 @@ private WeightedDiGraph<T, W> createResidualGraph(IDiGraph<T> graph)
228228
var newGraph = new WeightedDiGraph<T, W>();
229229

230230
//clone graph vertices
231-
foreach (var vertex in graph)
231+
foreach (var vertex in graph.VerticesAsEnumberable)
232232
{
233233
newGraph.AddVertex(vertex.Key);
234234
}
235235

236236
//clone edges
237-
foreach (var vertex in graph)
237+
foreach (var vertex in graph.VerticesAsEnumberable)
238238
{
239239
//Use either OutEdges or InEdges for cloning
240240
//here we use OutEdges

‎src/Advanced.Algorithms/Graph/Flow/FordFulkerson.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -207,13 +207,13 @@ private WeightedDiGraph<T, W> createResidualGraph(IDiGraph<T> graph)
207207
var newGraph = new WeightedDiGraph<T, W>();
208208

209209
//clone graph vertices
210-
foreach (var vertex in graph)
210+
foreach (var vertex in graph.VerticesAsEnumberable)
211211
{
212212
newGraph.AddVertex(vertex.Key);
213213
}
214214

215215
//clone edges
216-
foreach (var vertex in graph)
216+
foreach (var vertex in graph.VerticesAsEnumberable)
217217
{
218218
//Use either OutEdges or InEdges for cloning
219219
//here we use OutEdges

‎src/Advanced.Algorithms/Graph/Flow/PushRelabel.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -189,13 +189,13 @@ private WeightedDiGraph<T, W> createResidualGraph(IDiGraph<T> graph)
189189
var newGraph = new WeightedDiGraph<T, W>();
190190

191191
//clone graph vertices
192-
foreach (var vertex in graph)
192+
foreach (var vertex in graph.VerticesAsEnumberable)
193193
{
194194
newGraph.AddVertex(vertex.Key);
195195
}
196196

197197
//clone edges
198-
foreach (var vertex in graph)
198+
foreach (var vertex in graph.VerticesAsEnumberable)
199199
{
200200
//Use either OutEdges or InEdges for cloning
201201
//here we use OutEdges

‎src/Advanced.Algorithms/Graph/MinimumSpanningTree/Kruskals.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ public List<MSTEdge<T, W>>
4040
var disJointSet = new DisJointSet<T>();
4141

4242
//create set
43-
foreach (var vertex in graph)
43+
foreach (var vertex in graph.VerticesAsEnumberable)
4444
{
4545
disJointSet.MakeSet(vertex.Key);
4646
}

‎src/Advanced.Algorithms/Graph/ShortestPath/AStar.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
5858
var heapMapping = new Dictionary<T, AStarWrap<T, W>>();
5959

6060
//add vertices to min heap and progress map
61-
foreach (var vertex in graph)
61+
foreach (var vertex in graph.VerticesAsEnumberable)
6262
{
6363
//init parent
6464
parentMap.Add(vertex.Key, default(T));

‎src/Advanced.Algorithms/Graph/ShortestPath/Bellman-Ford.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph,
4646
var progress = new Dictionary<T, W>();
4747
var parentMap = new Dictionary<T, T>();
4848

49-
foreach (var vertex in graph)
49+
foreach (var vertex in graph.VerticesAsEnumberable)
5050
{
5151
parentMap.Add(vertex.Key, default(T));
5252
progress.Add(vertex.Key, @operator.MaxValue);
@@ -61,7 +61,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph,
6161
{
6262
updated = false;
6363

64-
foreach (var vertex in graph)
64+
foreach (var vertex in graph.VerticesAsEnumberable)
6565
{
6666
//skip not discovered nodes
6767
if (progress[vertex.Key].Equals(@operator.MaxValue))

‎src/Advanced.Algorithms/Graph/ShortestPath/Dijikstra.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
5555
var heapMapping = new Dictionary<T, MinHeapWrap<T, W>>();
5656

5757
//add vertices to min heap and progress map
58-
foreach (var vertex in graph)
58+
foreach (var vertex in graph.VerticesAsEnumberable)
5959
{
6060
//init parent
6161
parentMap.Add(vertex.Key, default(T));

0 commit comments

Comments
 (0)