Класс EdgeWeightedDigraph
|
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 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class EdgeWeightedDigraph { private int V; // vertices private int E; // edges private List<DirectedEdge>[] adj; private int[] Indegree; private void ValidateVertex(int v) { if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } public void AddEdge(DirectedEdge e) { int v = e.From(); int w = e.To(); ValidateVertex(v); ValidateVertex(w); adj[v].Add(e); Indegree[w]++; E++; } public IEnumerable<DirectedEdge> GetAdj(int v) { ValidateVertex(v); return adj[v]; } public int GetOutDegree(int v) { ValidateVertex(v); return adj[v].Count; } public int GetIndegree(int v) { ValidateVertex(v); return Indegree[v]; } // -- init Graph from file public EdgeWeightedDigraph(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 List<DirectedEdge>[V]; Indegree = new int[V]; for (int v = 0; v < V; v++) { adj[v] = new List<DirectedEdge>(); } 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); DirectedEdge e = new DirectedEdge(v, w, weight); AddEdge(e); } } } } catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); }; } 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 (DirectedEdge e in adj[v]) { s.Append(e.From() +" -> "+e.To()+" "); } s.Append("\n"); } return s.ToString(); } } } |
Вспомогательный класс DirectedEdge
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class DirectedEdge { private int v; private int w; private double weight; public DirectedEdge(int v, int w, double weight) { if (v < 0) throw new ArgumentException("Vertex names must be nonnegative integers"); if (w < 0) throw new ArgumentException("Vertex names must be nonnegative integers"); if (Double.IsNaN(weight)) throw new ArgumentException("Weight is NaN"); this.v = v; this.w = w; this.weight = weight; } public int From() { return v; } public int To() { return w; } public double GetWeight() { return weight; } } } |
Возьмем для примера такой взвешенный орграф
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
8 15 4 5 0,35 5 4 0,35 4 7 0,37 5 7 0,28 7 5 0,28 5 1 0,32 0 4 0,38 0 2 0,26 7 3 0,39 1 3 0,29 2 7 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |
Тестовый клиент
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class Program { static void Main(string[] args) { EdgeWeightedDigraph G = new EdgeWeightedDigraph("tinyEWD.txt"); Console.WriteLine(G.ToString()); Console.ReadLine(); } } } |
