diff options
-rw-r--r-- | Edge.cs | 9 | ||||
-rw-r--r-- | Graph.cs | 26 | ||||
-rw-r--r-- | IO/GraphFile.cs | 12 | ||||
-rw-r--r-- | Vertex.cs | 27 |
4 files changed, 45 insertions, 29 deletions
@@ -1,12 +1,13 @@ using System; +using Interfaces; namespace Graph { - public struct Edge<T> where T : IComparable<T> + public struct Edge<T> : IEdge<T> where T : IComparable<T> { - public int U { get; } - public int V { get; } - public T Weight { get; } + public int U { get; set; } + public int V { get; set; } + public T Weight { get; set; } public Edge(int u, int v, T weight) { @@ -1,35 +1,41 @@ using System; using System.Collections.Generic; +using Interfaces; namespace Graph { - public class Graph<T> where T : IComparable<T> + public class Graph<T, U, V> + where T : IVertex<U, V>, new() + where U : IEdge<V>, new() + where V : IComparable<V> { - public List<Vertex<T>> Vertices { get; set; } = new List<Vertex<T>>(); + public List<T> Vertices { get; set; } = new List<T>(); public Graph() { } - public Graph(List<Vertex<T>> vertices) + public Graph(List<T> vertices) { Vertices = vertices; } // indexer for accessing vertex with id of index - public Vertex<T> this[int index] { get => Vertices.Find(vertex => vertex.Id == index); } + public T this[int index] { get => Vertices.Find(vertex => vertex.Id == index); } // create virtex if needed, then add the edge to it's edges list - public void AddEdge(Edge<T> edge) + public void AddEdge(U edge) { // look for existing vertex, and use it if found - Vertex<T> vertex = Vertices.Find(u => u.Id == edge.U); + T vertex = Vertices.Find(u => u.Id == edge.U); + // if not found, create a new vertex if (vertex == null) { - // if not found, create a new vertex - Vertices.Add(vertex = new Vertex<T>(edge.U)); - vertex = Vertices[Vertices.Count - 1]; + // weird constructor call to avoid using more generics + vertex = new T(); + vertex.Id = edge.U; + Vertices.Add(vertex); } - + // add the edge to the new/found vertex vertex.Edges.Add(edge); } diff --git a/IO/GraphFile.cs b/IO/GraphFile.cs index 42a1b2b..2e00eef 100644 --- a/IO/GraphFile.cs +++ b/IO/GraphFile.cs @@ -3,13 +3,15 @@ using Interfaces; namespace Graph.IO { + using Graph = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; + public static class GraphFile { // read a graph from file using IFileReader (i.e. Dependancy injection for unit testing) - public static Graph<double> Read(IFileReader reader) + public static Graph Read(IFileReader reader) { string[] lines = reader.Lines; - Graph<double> graph = new Graph<double>(); + Graph graph = new Graph(); foreach (string line in reader.Lines) { @@ -42,11 +44,11 @@ namespace Graph.IO } // write a graph to file using IFileWriter (i.e. Dependancy injection for unit testing) - public static void Print(Graph<double> graph, IFileWriter writer) + public static void Print(Graph graph, IFileWriter writer) { // create array of strings with a size equal to vertices string[] lines = new string[graph.Vertices.Count]; - + // add each vertex to it's parents output line graph.Vertices.ForEach(vertex => { @@ -57,7 +59,7 @@ namespace Graph.IO // for vertex & parent, create string if not already lines[vertex.Id] ??= $"{vertex.Id}"; lines[vertex.Parent] ??= $"{vertex.Parent}"; - + // add vertex + weight to parent's string & visa versa lines[vertex.Parent] += $" {vertex.Id} {vertex.Key.ToString("F1")}"; lines[vertex.Id] += $" {vertex.Parent} {vertex.Key.ToString("F1")}"; @@ -5,37 +5,44 @@ using Interfaces; namespace Graph { - public class Vertex<T> : INode<T>, IComparable<INode<T>> where T : IComparable<T> + public class Vertex<T, U> : IVertex<T, U>, INode<U>, IComparable<INode<U>> + where T : IEdge<U>, new() + where U : IComparable<U> { public int Id { get; set; } - public T Key { get; set; } + public U Key { get; set; } public int Parent { get; set; } = -1; - public List<Edge<T>> Edges { get; set; } = new List<Edge<T>>(); + public List<T> Edges { get; set; } = new List<T>(); // indexer for accessing edge with v of index - public Edge<T> this[int index] { get => Edges.Find(edge => edge.V == index); } + public T this[int index] { get => Edges.Find(edge => edge.V == index); } + public Vertex() { } public Vertex(int id) => Id = id; - public Vertex(int id, List<Edge<T>> edges) : this(id) => + public Vertex(int id, List<T> edges) : this(id) => Edges = edges; - public Vertex(Vertex<T> vertex) + public Vertex(Vertex<T, U> vertex) { Id = vertex.Id; Parent = vertex.Parent; Key = vertex.Key; - foreach (Edge<T> edge in vertex.Edges) + foreach (T edge in vertex.Edges) { - Edge<T> newEdge = new Edge<T>(edge.U, edge.V, edge.Weight); + T newEdge = new T(); + newEdge.U = edge.U; + newEdge.V = edge.V; + newEdge.Weight = edge.Weight; + Edges.Add(newEdge); } } - public int CompareTo(INode<T> node) => - Key.CompareTo(node.Key); + public int CompareTo(INode<U> vertex) => + Key.CompareTo(vertex.Key); public override string ToString() => $"{Id} {String.Join(" ", Edges.Select(e => (e.V, e.Weight)))}"; } |