Клиент тестирования будет выглядеть так…
|
1 2 3 4 5 6 7 8 9 10 |
//--- Cycles bool isCycle = G.IsCycle(G); Console.WriteLine("Is Cycle? " + isCycle); if (isCycle) { Stack<int> cycle = new Stack<int>(); cycle = G.GetCycle(G); foreach (int v in cycle) Console.WriteLine(v); } |
Клиент тестирования полностью
|
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 |
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 G = new Digraph("tinyDG.txt"); //how much vertices? Console.WriteLine("Vertices: " + G.GetVertices()); //how much edges? Console.WriteLine("Edges: " + G.GetEdges()); // indegree Console.WriteLine("InDegree for 0 vertice: " + G.GetInDegree(0)); // outdegree Console.WriteLine("OutDegree for 0 vertice: " + G.GetOutDegree(0)); // is v reachible from s ? Console.WriteLine("is 1 reachible from 0: " + G.IsReachible(G, 0, 1)); // True Console.WriteLine("is 6 reachible from 0: " + G.IsReachible(G, 0, 1)); // False int s = 0; // start vertex int f = 2; // finish vertex // --- DFS Console.WriteLine(" --- DFS..."); // Has path to ? Console.WriteLine("Has path from " + s + " to " + f + " vertex, DFS? " + G.IsPathToDFS(G, s, f)); // This is the path, DFS Console.WriteLine("This is the path, DFS?"); Stack<int> path = new Stack<int>(); G.GetPathToDFS(G, s, f, ref path); if (path.Count != 0) { foreach (int i in path) Console.WriteLine(" > " + i.ToString()); } else Console.WriteLine("no path..."); // --- BFS Console.WriteLine("--- BFS..."); // Haspath to Console.WriteLine("Has path from " + s + " to " + f + " vertex, DFS? " + G.IsPathToBFS(G, s, f)); // --- shortest distance path.Clear(); if (G.IsPathToBFS(G, s, f)) Console.WriteLine("Shortest distance: " + G.GetShortestDistToBFS(G, s, f)); // --- Console.WriteLine("This is the path, DFS?"); G.GetShortestPathToBFS(G, s, f, ref path); if (path.Count != 0) { foreach (int i in path) Console.WriteLine(" > " + i.ToString()); } else Console.WriteLine("no path..."); //--- Cycles bool isCycle = G.IsCycle(G); Console.WriteLine("Is Cycle? " + isCycle); if (isCycle) { Stack<int> cycle = new Stack<int>(); cycle = G.GetCycle(G); foreach (int v in cycle) Console.WriteLine(v); } // --- just describing the orGraph... toString() Console.WriteLine("ToString(): " + G.ToString()); Console.ReadLine(); } } } |
Класс для поиска цикла
|
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 |
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class DirectedCycle { private bool[] marked; private int[] edgeTo; private bool[] onStack; private Stack<int> cycle; /** * Determines whether the digraph {@code G} has a directed cycle and, if so, * finds such a cycle. * @param G the digraph */ public DirectedCycle(Digraph G) { marked = new bool[G.GetVertices()]; onStack = new bool[G.GetVertices()]; edgeTo = new int[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) if (!marked[v] && cycle == null) Dfs(G, v); } // check that algorithm computes either the topological order or finds a directed cycle private void Dfs(Digraph G, int v) // v is start vertex here { onStack[v] = true; marked[v] = true; foreach (int w in G.GetAdj(v)) { // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; Dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<int>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.Push(x); } cycle.Push(w); cycle.Push(v); Debug.Assert(Check()); } } onStack[v] = false; } // --- does the digraph have a directed cycle? public bool IsCycle() { return cycle != null; } // --getCycle public Stack<int> GetCycle() { return cycle; } // --- certify that digraph has a directed cycle if it reports one private bool Check() { if (IsCycle()) { // verify cycle int first = -1, last = -1; foreach (int v in cycle) { if (first == -1) first = v; last = v; } if (first != last) { // System.err.printf("cycle begins with %d and ends with %d\n", first, last); return false; } } return true; } } } |
Оберточные методы в классе Digraph
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// --- Cycles public bool IsCycle(Digraph G) { DirectedCycle o = new DirectedCycle(G); return o.IsCycle(); } // --- GetCycle public Stack<int> GetCycle(Digraph G) { DirectedCycle o = new DirectedCycle(G); return o.GetCycle(); } |
Класс 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 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 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
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(); } // --- public Boolean IsReachible(Digraph G, int s, int v) { DirectedDFS dfs = new DirectedDFS(G, s); return dfs.IsMarked(v); } // --- HasPathToDFS public Boolean IsPathToDFS(Digraph G, int s, int v) { DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); return d.IsPathTo(v); } // --- GetPathToDFS public void GetPathToDFS(Digraph G, int s, int v, ref Stack<int> path) { if (!IsPathToDFS(G,s,v)) return; DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); d.GetPathTo(v, ref path); } // --- HasPathToBFS public Boolean IsPathToBFS(Digraph G, int s, int v) { BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); return d.IsPathTo(v); } // --- GetShortestDistTo public int GetShortestDistToBFS(Digraph G, int s, int v) { if (!IsPathToBFS(G, s, v)) return -1; BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); return d.GetShortestDistTo(v); } // --- GetShortestPathTo public void GetShortestPathToBFS(Digraph G, int s, int v, ref Stack<int> path) { if (!IsPathToBFS(G, s, v)) return; BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); d.GetShortestPathTo(v, ref path); } // --- Cycles public bool IsCycle(Digraph G) { DirectedCycle o = new DirectedCycle(G); return o.IsCycle(); } // --- GetCycle public Stack<int> GetCycle(Digraph G) { DirectedCycle o = new DirectedCycle(G); return o.GetCycle(); } } } |
Класс Bag
|
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; } } } } |