Skip to content

Commit 20bac61

Browse files
justcoding121justcoding121
committed
Update search algorithms to accept undirected graphs
1 parent 974f3d9 commit 20bac61

File tree

11 files changed

+52
-35
lines changed

11 files changed

+52
-35
lines changed

‎src/Advanced.Algorithms/Binary/BaseConversion.cs

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,16 +27,16 @@ public static string Convert(string srcNumber,
2727
var whole = tmp[0].TrimEnd();
2828
var fraction = tmp[1].TrimStart();
2929

30-
return ConvertWhole(whole, srcBaseChars, dstBaseChars) +
30+
return convertWhole(whole, srcBaseChars, dstBaseChars) +
3131
"." + ConvertFraction(fraction, srcBaseChars, dstBaseChars, precision);
3232
}
3333

34-
return ConvertWhole(srcNumber, srcBaseChars, dstBaseChars);
34+
return convertWhole(srcNumber, srcBaseChars, dstBaseChars);
3535
}
3636
/// <summary>
3737
/// Converts the whole part of source number.
3838
/// </summary>
39-
private static string ConvertWhole(string srcNumber,
39+
private static string convertWhole(string srcNumber,
4040
string srcBaseChars,
4141
string dstBaseChars)
4242
{

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

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ public DiGraphVertex<T> ReferenceVertex
4444
IDiGraphVertex<T> IDiGraph<T>.ReferenceVertex => ReferenceVertex;
4545
IGraphVertex<T> IGraph<T>.ReferenceVertex => ReferenceVertex;
4646

47-
47+
4848
/// <summary>
4949
/// Add a new vertex to this graph.
5050
/// Time complexity: O(1).
@@ -237,7 +237,7 @@ IGraph<T> IGraph<T>.Clone()
237237

238238
public IEnumerator GetEnumerator()
239239
{
240-
return Vertices.Select(x => x.Key).GetEnumerator();
240+
return Vertices.Select(x => x.Key).GetEnumerator();
241241
}
242242

243243
IEnumerator<T> IEnumerable<T>.GetEnumerator()
@@ -275,12 +275,16 @@ public DiGraphVertex(T value)
275275
InEdges = new HashSet<DiGraphVertex<T>>();
276276
}
277277

278-
279278
public IDiEdge<T> GetOutEdge(IDiGraphVertex<T> targetVertex)
280279
{
281280
return new DiEdge<T, int>(targetVertex, 1);
282281
}
283282

283+
public IEdge<T> GetEdge(IGraphVertex<T> targetVertex)
284+
{
285+
return new Edge<T, int>(targetVertex, 1);
286+
}
287+
284288
IEnumerator IEnumerable.GetEnumerator()
285289
{
286290
return GetEnumerator();

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -246,6 +246,11 @@ public GraphVertex(T value)
246246
Edges = new HashSet<GraphVertex<T>>();
247247
}
248248

249+
public IEdge<T> GetEdge(IGraphVertex<T> targetVertex)
250+
{
251+
return new Edge<T, int>(targetVertex, 1);
252+
}
253+
249254
IEnumerator IEnumerable.GetEnumerator()
250255
{
251256
return GetEnumerator();

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

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -288,6 +288,12 @@ public IDiEdge<T> GetOutEdge(IDiGraphVertex<T> targetVertex)
288288
return new DiEdge<T, TW>(targetVertex, OutEdges[key]);
289289
}
290290

291+
public IEdge<T> GetEdge(IGraphVertex<T> targetVertex)
292+
{
293+
var key = targetVertex as WeightedDiGraphVertex<T, TW>;
294+
return new Edge<T, TW>(targetVertex, OutEdges[key]);
295+
}
296+
291297
IEnumerator IEnumerable.GetEnumerator()
292298
{
293299
return GetEnumerator();
@@ -297,7 +303,5 @@ public IEnumerator<T> GetEnumerator()
297303
{
298304
return OutEdges.Select(x => x.Key.Key).GetEnumerator();
299305
}
300-
301-
302306
}
303307
}

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

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -244,6 +244,11 @@ public WeightedGraphVertex(T value)
244244
Edges = new Dictionary<WeightedGraphVertex<T, TW>, TW>();
245245
}
246246

247+
public IEdge<T> GetEdge(IGraphVertex<T> targetVertex)
248+
{
249+
return new Edge<T, TW>(targetVertex, Edges[targetVertex as WeightedGraphVertex<T, TW>]);
250+
}
251+
247252
IEnumerator IEnumerable.GetEnumerator()
248253
{
249254
return GetEnumerator();
@@ -253,6 +258,5 @@ public IEnumerator<T> GetEnumerator()
253258
{
254259
return Edges.Select(x => x.Key.Value).GetEnumerator();
255260
}
256-
257261
}
258262
}

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
namespace Advanced.Algorithms.DataStructures.Graph
88
{
99
/// <summary>
10-
/// UnDirected graph.
10+
/// UnDirected graph. (When implemented on a directed graphs only outgoing edges are considered as Edges).
1111
/// </summary>
1212
/// <typeparam name="T"></typeparam>
1313
public interface IGraph<T>
@@ -29,6 +29,8 @@ public interface IGraphVertex<T>
2929
{
3030
T Key { get; }
3131
IEnumerable<IEdge<T>> Edges { get; }
32+
33+
IEdge<T> GetEdge(IGraphVertex<T> targetVertex);
3234
}
3335

3436
public interface IEdge<T>

‎src/Advanced.Algorithms/Graph/Cut/MinimumCut.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.Graph
88

99
/// <summary>
1010
/// Compute minimum cut edges of given graph
11-
/// using Edmond Karps improved Ford-Fulkerson Max Flow Algorithm.
11+
/// using Edmond-Karps improved Ford-Fulkerson Max Flow Algorithm.
1212
/// </summary>
1313
public class MinCut<T, W> where W : IComparable
1414
{

‎src/Advanced.Algorithms/Graph/Search/BiDirectional.cs

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ public class BiDirectional<T>
1313
/// <summary>
1414
/// Returns true if Path exists from source to destination.
1515
/// </summary>
16-
public bool PathExists(IDiGraph<T> graph, T source, T destination)
16+
public bool PathExists(IGraph<T> graph, T source, T destination)
1717
{
1818
return bfs(graph, source, destination);
1919
}
@@ -22,13 +22,13 @@ public bool PathExists(IDiGraph<T> graph, T source, T destination)
2222
/// Use breadth First Search from Source and Target until they meet.
2323
/// If they could'nt find the element before they meet return false.
2424
/// </summary>
25-
private bool bfs(IDiGraph<T> graph, T source, T destination)
25+
private bool bfs(IGraph<T> graph, T source, T destination)
2626
{
2727
var visitedA = new HashSet<T>();
2828
var visitedB = new HashSet<T>();
2929

30-
var bfsQueueA = new Queue<IDiGraphVertex<T>>();
31-
var bfsQueueB = new Queue<IDiGraphVertex<T>>();
30+
var bfsQueueA = new Queue<IGraphVertex<T>>();
31+
var bfsQueueB = new Queue<IGraphVertex<T>>();
3232

3333
bfsQueueA.Enqueue(graph.GetVertex(source));
3434
bfsQueueB.Enqueue(graph.GetVertex(destination));
@@ -49,7 +49,7 @@ private bool bfs(IDiGraph<T> graph, T source, T destination)
4949
return true;
5050
}
5151

52-
foreach (var edge in current.OutEdges)
52+
foreach (var edge in current.Edges)
5353
{
5454
if (visitedA.Contains(edge.TargetVertexKey))
5555
{
@@ -71,7 +71,7 @@ private bool bfs(IDiGraph<T> graph, T source, T destination)
7171
return true;
7272
}
7373

74-
foreach (var edge in current.InEdges)
74+
foreach (var edge in current.Edges)
7575
{
7676
if (visitedB.Contains(edge.TargetVertexKey))
7777
{

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

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ public AStarShortestPath(IShortestPathOperators<W> @operator, IAStarHeuristic<T,
2424
/// <summary>
2525
/// Search path to target using the heuristic.
2626
/// </summary>
27-
public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T destination)
27+
public ShortestPathResult<T, W> FindShortestPath(IGraph<T> graph, T source, T destination)
2828
{
2929
if (this.@operator == null)
3030
{
@@ -97,11 +97,11 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
9797
}
9898

9999
//visit neighbours of current
100-
foreach (var neighbour in graph.GetVertex(current.Vertex).OutEdges.Where(x => !x.TargetVertexKey.Equals(source)))
100+
foreach (var neighbour in graph.GetVertex(current.Vertex).Edges.Where(x => !x.TargetVertexKey.Equals(source)))
101101
{
102102
//new distance to neighbour
103103
var newDistance = @operator.Sum(current.Distance,
104-
graph.GetVertex(current.Vertex).GetOutEdge(neighbour.TargetVertex).Weight<W>());
104+
graph.GetVertex(current.Vertex).GetEdge(neighbour.TargetVertex).Weight<W>());
105105

106106
//current distance to neighbour
107107
var existingDistance = progress[neighbour.TargetVertexKey];
@@ -149,7 +149,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
149149
/// <summary>
150150
/// Trace back path from destination to source using parent map.
151151
/// </summary>
152-
private ShortestPathResult<T, W> tracePath(IDiGraph<T> graph, Dictionary<T, T> parentMap, T source, T destination)
152+
private ShortestPathResult<T, W> tracePath(IGraph<T> graph, Dictionary<T, T> parentMap, T source, T destination)
153153
{
154154
//trace the path
155155
var pathStack = new Stack<T>();
@@ -174,7 +174,7 @@ private ShortestPathResult<T, W> tracePath(IDiGraph<T> graph, Dictionary<T, T> p
174174
for (int i = 0; i < resultPath.Count - 1; i++)
175175
{
176176
resultLength = @operator.Sum(resultLength,
177-
graph.GetVertex(resultPath[i]).GetOutEdge(graph.GetVertex(resultPath[i + 1])).Weight<W>());
177+
graph.GetVertex(resultPath[i]).GetEdge(graph.GetVertex(resultPath[i + 1])).Weight<W>());
178178
}
179179

180180
return new ShortestPathResult<T, W>(resultPath, resultLength);

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

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
using Advanced.Algorithms.DataStructures;
22
using Advanced.Algorithms.DataStructures.Graph;
3-
using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;
43
using System;
54
using System.Collections.Generic;
65
using System.Linq;
@@ -21,7 +20,7 @@ public DijikstraShortestPath(IShortestPathOperators<W> @operator)
2120
/// <summary>
2221
/// Get shortest distance to target.
2322
/// </summary>
24-
public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T destination)
23+
public ShortestPathResult<T, W> FindShortestPath(IGraph<T> graph, T source, T destination)
2524
{
2625
//regular argument checks
2726
if (graph?.GetVertex(source) == null || graph.GetVertex(destination) == null)
@@ -93,11 +92,11 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
9392
}
9493

9594
//visit neighbours of current
96-
foreach (var neighbour in graph.GetVertex(current.Vertex).OutEdges.Where(x => !x.TargetVertexKey.Equals(source)))
95+
foreach (var neighbour in graph.GetVertex(current.Vertex).Edges.Where(x => !x.TargetVertexKey.Equals(source)))
9796
{
9897
//new distance to neighbour
9998
var newDistance = @operator.Sum(current.Distance,
100-
graph.GetVertex(current.Vertex).GetOutEdge(neighbour.TargetVertex).Weight<W>());
99+
graph.GetVertex(current.Vertex).GetEdge(neighbour.TargetVertex).Weight<W>());
101100

102101
//current distance to neighbour
103102
var existingDistance = progress[neighbour.TargetVertexKey];
@@ -135,7 +134,7 @@ public ShortestPathResult<T, W> FindShortestPath(IDiGraph<T> graph, T source, T
135134
/// <summary>
136135
/// Trace back path from destination to source using parent map.
137136
/// </summary>
138-
private ShortestPathResult<T, W> tracePath(IDiGraph<T> graph, Dictionary<T, T> parentMap, T source, T destination)
137+
private ShortestPathResult<T, W> tracePath(IGraph<T> graph, Dictionary<T, T> parentMap, T source, T destination)
139138
{
140139
//trace the path
141140
var pathStack = new Stack<T>();
@@ -160,7 +159,7 @@ private ShortestPathResult<T, W> tracePath(IDiGraph<T> graph, Dictionary<T, T> p
160159
for (int i = 0; i < resultPath.Count - 1; i++)
161160
{
162161
resultLength = @operator.Sum(resultLength,
163-
graph.GetVertex(resultPath[i]).GetOutEdge(graph.GetVertex(resultPath[i + 1])).Weight<W>());
162+
graph.GetVertex(resultPath[i]).GetEdge(graph.GetVertex(resultPath[i + 1])).Weight<W>());
164163
}
165164

166165
return new ShortestPathResult<T, W>(resultPath, resultLength);

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

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11

22
using Advanced.Algorithms.DataStructures.Graph;
3-
using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;
43
using System;
54
using System.Collections.Generic;
65
using System.Linq;
@@ -15,7 +14,7 @@ public class TravellingSalesman<T, W> where W : IComparable
1514
{
1615
IShortestPathOperators<W> @operator;
1716

18-
public W FindMinWeight(IDiGraph<T> graph, IShortestPathOperators<W> @operator)
17+
public W FindMinWeight(IGraph<T> graph, IShortestPathOperators<W> @operator)
1918
{
2019
this.@operator = @operator;
2120
if (this.@operator == null)
@@ -34,14 +33,14 @@ public W FindMinWeight(IDiGraph<T> graph, IShortestPathOperators<W> @operator)
3433

3534
return findMinWeight(graph.ReferenceVertex, graph.ReferenceVertex,
3635
graph.VerticesCount,
37-
new HashSet<IDiGraphVertex<T>>(),
36+
new HashSet<IGraphVertex<T>>(),
3837
new Dictionary<string, W>());
3938
}
4039

41-
private W findMinWeight(IDiGraphVertex<T> sourceVertex,
42-
IDiGraphVertex<T> tgtVertex,
40+
private W findMinWeight(IGraphVertex<T> sourceVertex,
41+
IGraphVertex<T> tgtVertex,
4342
int remainingVertexCount,
44-
HashSet<IDiGraphVertex<T>> visited,
43+
HashSet<IGraphVertex<T>> visited,
4544
Dictionary<string, W> cache)
4645
{
4746
var cacheKey = $"{sourceVertex.Key}-{remainingVertexCount}";
@@ -55,7 +54,7 @@ private W findMinWeight(IDiGraphVertex<T> sourceVertex,
5554

5655
var results = new List<W>();
5756

58-
foreach (var edge in sourceVertex.OutEdges)
57+
foreach (var edge in sourceVertex.Edges)
5958
{
6059
//base case
6160
if (edge.TargetVertex.Equals(tgtVertex)

0 commit comments

Comments
 (0)