Класс орграфа. В качестве списков смежности вершин используется самописный Bag on Linked List
Пример применения и тест некоторых методов
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class Program { static void Main(string[] args) { Digraph d = new Digraph("tinyDG.txt"); //how much vertices? Console.WriteLine("Vertices: "+ d.GetVertices()); Console.WriteLine("Edges: " + d.GetEdges()); Console.WriteLine("InDegree for 0 vertice: " + d.GetInDegree(0)); Console.WriteLine("OutDegree for 0 vertice: " + d.GetOutDegree(0)); Console.WriteLine("ToString(): " + d.ToString()); Console.ReadLine(); } } } |
Digraph
|
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 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class Digraph { private int V; // vertices private int E; // edges private Bag<int>[] adj; // adjency list of vertex v private int[] indegree; // indegree of vertex v // Initializes an empty digraph with V vertices. public Digraph(int V) { if (V < 0) throw new ArgumentException("Number of vertices in a Digraph must be nonnegative"); this.V = 0; this.E = 0; indegree = new int[V]; adj = new Bag<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } } // --- read Graph from file public Digraph(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<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } indegree = new int[V]; 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]); ValidateVertex(v); ValidateVertex(w); AddEdge(v, w); } } } } catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); }; } // --- vertices public int GetVertices() { return V; } // --- edges public int GetEdges() { return E; } // --- Validation... private void ValidateVertex(int v) { if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); } } // --- Adds the directed edge v→w to this digraph. public void AddEdge(int v, int w) { ValidateVertex(v); ValidateVertex(w); adj[v].Push(w); indegree[w]++; E++; } // --- Adjacent public Bag<int> GetAdj(int v) { ValidateVertex(v); return adj[v]; } // --- outDegree public int GetOutDegree( int v) { ValidateVertex(v); return adj[v].Size(); } // --- inDegree public int GetInDegree(int v) { ValidateVertex(v); return indegree[v]; } // --- reverseGraph public Digraph Reverse() { Digraph reverseGraph = new Digraph(V); for (int v = 0; v < V; v++) { foreach (int w in adj[v]) { reverseGraph.AddEdge(w, v); } } return reverseGraph; } // --- to string (not tested...) public override string ToString() { StringBuilder s = new StringBuilder(); s.Append(V + " vertices," + E + " edges " +"\n"); for (int v = 0; v < V; v++) { s.Append(v.ToString()+" "); foreach (int w in adj[v]) { s.Append(w+" ");} s.Append("\n"); } return s.ToString(); } } } |
Bag on linked lists
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { public class Bag<T> : IEnumerable<T> { Node<T> first; private int N; class Node<T> { public T item; public Node<T> next; } public bool IsEmpty() { return (first == null) || (N == 0); } public int Size() { return N; } public void Push(T item) { // adding to the begining Node<T> oldfirst = first; first = new Node<T>(); first.item = item; first.next = oldfirst; N++; } /* // no pop in stack method public T pop() { T item = first.item; first = first.next; N--; return item; } */ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { var node = first; while (node != null) { yield return node.item; node = node.next; } } } } |