Рассмотрим такой граф
Представление в текстовом файле будет таким
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
8 16 4 5 0,35 4 7 0,37 5 7 0,28 0 7 0,16 1 5 0,32 0 4 0,38 2 3 0,17 1 7 0,19 0 2 0,26 1 2 0,36 1 3 0,29 2 7 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |
Напишем вспомогательный класс Edge
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WGraph { class Edge :IComparable<Edge> { private int v; private int w; private double weight; /** * Initializes an edge between vertices {@code v} and {@code w} of * the given {@code weight}. * * @param v one vertex * @param w the other vertex * @param weight the weight of this edge * @throws IllegalArgumentException if either {@code v} or {@code w} * is a negative integer * @throws IllegalArgumentException if {@code weight} is {@code NaN} */ public Edge(int v, int w, double weight) { if ((v < 0) || (w < 0)) throw new ArgumentException("vertex index must be a nonnegative integer"); if (Double.IsNaN(weight)) throw new ArgumentException("Weight is NaN"); this.v = v; this.w = w; this.weight = weight; } /** * Returns the weight of this edge. * * @return the weight of this edge */ public double GetWeight() { return weight; } /** * Returns either endpoint of this edge. * * @return either endpoint of this edge */ public int Either() { return v; } /** * Returns the endpoint of this edge that is different from the given vertex. * * @param vertex one endpoint of this edge * @return the other endpoint of this edge * @throws IllegalArgumentException if the vertex is not one of the * endpoints of this edge */ public int Other(int vertex) { if (vertex == v) return w; if (vertex == w) return v; else throw new ArgumentException("Illegal endpoint"); } /** * Compares two edges by weight. * Note that {@code compareTo()} is not consistent with {@code equals()}, * which uses the reference equality implementation inherited from {@code Object}. * * @param that the other edge * @return a negative integer, zero, or positive integer depending on whether * the weight of this is less than, equal to, or greater than the * argument edge */ public int CompareTo(Edge that) { if (this.GetWeight() < that.GetWeight()) return -1; if (this.GetWeight() > that.GetWeight()) return 1; else return 0; } // to string public override string ToString() { return String.Format("{0}-{1},weight {2}",v,w,weight); } } } |
Теперь напишем класс, здесь вместо смежных вершин в списках смежности будем использовать ребра.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WGraph { class EdgeWeightedGraph { private int V; private int E; private Bag<Edge>[] adj; // -- init empty Graph public EdgeWeightedGraph(int V) { if (V < 0) throw new ArgumentException("Number of vertices must be nonnegative"); this.V = V; this.E = 0; adj = new Bag<Edge>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Edge>(); } } // -- init Random Graph public EdgeWeightedGraph(int V, int E) { if ((V < 0) || (E < 0)) throw new ArgumentException("must be non-negative"); Random r = new Random(); for (int i = 0; i < E; i++) { int v = r.Next(0, V); int w = r.Next(0, V); double weight = r.NextDouble(); Edge e = new Edge(v, w, weight); AddEdge(e); } } // -- init Graph from file public EdgeWeightedGraph(string filepath) { try { if (!File.Exists(filepath)) { throw new Exception("no file with such filepath"); } using (StreamReader sr = new StreamReader(filepath)) { int i = 0; while (sr.Peek() >= 0) { // reading number of verticles if (i == 0) { V = Convert.ToInt32(sr.ReadLine()); adj = new Bag<Edge>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Edge>(); } i++; } // reading number of edges else if (i == 1) { E = Convert.ToInt32(sr.ReadLine()); if (E < 0) throw new ArgumentException("number of edges in a Graph must be nonnegative"); i++; } else { string s = sr.ReadLine(); Char delimiter = ' '; String[] substrings = s.Split(delimiter); int v = Convert.ToInt32(substrings[0]); int w = Convert.ToInt32(substrings[1]); double weight = Convert.ToDouble(substrings[2]); ValidateVertex(v); ValidateVertex(w); Edge e = new Edge(v, w, weight); AddEdge(e); } } } } catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); }; } // -- add edge public void AddEdge(Edge e) { int v = e.Either(); int w = e.Other(v); ValidateVertex(v); ValidateVertex(w); adj[v].Push(e); adj[w].Push(e); E++; } //-- validate Vertex private void ValidateVertex(int v) { if ((v < 0) || (v >= V)) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } // public int GetVertices() { return V; } public int GetEdges() { return E; } /** * Returns the edges incident on vertex {@code v}. * * @param v the vertex * @return the edges incident on vertex {@code v} as an Iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public IEnumerable<Edge> GetAdj(int v) { ValidateVertex(v); return adj[v]; } public int GetDegree(int v) { ValidateVertex(v); return adj[v].Size(); } /** * Returns all edges in this edge-weighted graph. * To iterate over the edges in this edge-weighted graph, use foreach notation: * {@code for (Edge e : G.edges())}. * * @return all edges in this edge-weighted graph, as an iterable */ public IEnumerable<Edge> GetAllEdges() { Bag<Edge> list = new Bag<Edge>(); for (int v = 0; v < V; v++) { int selfLoops = 0; foreach (Edge e in GetAdj(v)) { if (e.Other(v) > v) { list.Push(e); } // add only one copy of each self loop (self loops will be consecutive) else if (e.Other(v) == v) { if (selfLoops % 2 == 0) list.Push(e); selfLoops++; } } } return list; } /** * Returns a string representation of the edge-weighted graph. * This method takes time proportional to <em>E</em> + <em>V</em>. * * @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>, * followed by the <em>V</em> adjacency lists of edges */ public override string ToString() { StringBuilder s = new StringBuilder(); s.Append("Verticles: "+ V + " " + "Edges: "+ E/2 + "\n"); // E%2 because each edge twice in verticle for (int v = 0; v < V; v++) { s.Append(v + ": "); foreach (Edge e in adj[v]) { s.Append(e + " "); } s.Append("\n"); } return s.ToString(); } } } |
Протестируем API вышенаписанного класса в консоли
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WGraph { class Program { static void Main(string[] args) { EdgeWeightedGraph G = new EdgeWeightedGraph("tinyEWG.txt"); Console.WriteLine("Test Api"); Console.WriteLine("Number of Vertices: "+G.GetVertices()); Console.WriteLine("Number of Edges: " + G.GetVertices()); Console.WriteLine("Edges " + G.GetVertices()); Console.WriteLine("Adjacaent edges to 0"); Stack<Edge> adjEdges = new Stack<Edge>(G.GetAdj(0)); foreach(Edge e in adjEdges) { int v = e.Either(); int w = e.Other(v); Console.WriteLine(v+"-"+w); } Console.WriteLine("All edges"); Stack<Edge> allEdges = new Stack<Edge>(G.GetAllEdges()); foreach (Edge e in allEdges) { int v = e.Either(); int w = e.Other(v); Console.WriteLine(v + "-" + w); } Console.WriteLine("Comparing Edges by weight"); Stack<Edge> edges = new Stack<Edge>(G.GetAdj(0)); Edge e1 = edges.Pop(); Edge e2 = edges.Pop(); if (e1.CompareTo(e2) == -1) Console.WriteLine("e1<e2"); else Console.WriteLine("e1>e2"); Console.WriteLine("Weight of e1 == "+e1.GetWeight()); Console.WriteLine("Weight of e2 == " + e2.GetWeight()); Console.WriteLine(" "); Console.WriteLine("String Representation of Graph"); Console.WriteLine(G.ToString()); Console.ReadLine(); } } } |
Вот результат тестирования в консоли…
