testGraph
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SearchInGraphExample { class BreadthFirstPaths { private static int INFINITY = int.MaxValue; private bool[] marked; // marked[v] = is there an s-v path private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path private int[] distTo; // distTo[v] = number of edges shortest s-v path /** * Computes the shortest path between the source vertex {@code s} * and every other vertex in the graph {@code G}. * @param G the graph * @param s the source vertex * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public BreadthFirstPaths(Graph G, int s) { marked = new bool[G.V]; distTo = new int[G.V]; edgeTo = new int[G.V]; G.validateVertex(s); bfs(G, s); //assert check(G, s); } public BreadthFirstPaths(Graph G) { marked = new bool[G.V]; distTo = new int[G.V]; edgeTo = new int[G.V]; } // breadth-first search from a single source public void bfs(Graph G, int s) { Queue<int> q = new Queue<int>(); for (int v = 0; v < G.V; v++) distTo[v] = INFINITY; distTo[s] = 0; marked[s] = true; Console.Write(s + " "); q.Enqueue(s); while (q.Count!=0) { int v = q.Dequeue(); foreach (int w in G.adjVerticles(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; Console.Write(w+" "); q.Enqueue(w); } } } } /** * Is there a path between the source vertex {@code s} (or sources) and vertex {@code v}? * @param v the vertex * @return {@code true} if there is a path, and {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public bool hasPathTo(int v) { validateVertex(v); return marked[v]; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = marked.Length; if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } /** * Returns the number of edges in a shortest path between the source vertex {@code s} * (or sources) and vertex {@code v}? * @param v the vertex * @return the number of edges in a shortest path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int distanceTo(int v) { validateVertex(v); return distTo[v]; } /** * Returns a shortest path between the source vertex {@code s} (or sources) * and {@code v}, or {@code null} if no such path. * @param v the vertex * @return the sequence of vertices on a shortest path, as an Iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public IEnumerable<int> pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack<int> path = new Stack<int>(); int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.Push(x); path.Push(x); // adding start verticle here return path; } public IEnumerable<int> pathTo2(int v,int startVertex) { validateVertex(v); validateVertex(startVertex); if (!hasPathTo(v)) return null; Stack<int> path = new Stack<int>(); int x; for (x = v; x!=startVertex; x = edgeTo[x]) path.Push(x); path.Push(startVertex); return path; } } } |
Graph.cs
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SearchInGraphExample { using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; using System.IO; public class Graph { // private static final String NEWLINE = System.getProperty("line.separator"); public int V { get; set; } public int E { get; set; } public Bag<int>[] adj { get; set; } /** * Initializes an empty graph with {@code V} vertices and 0 edges. * param V the number of vertices * * @param V number of vertices * @throws IllegalArgumentException if {@code V < 0} */ public Graph(int V) { if (V < 0) throw new ArgumentException("Number of vertices must be nonnegative"); this.V = V; this.E = 0; adj = new Bag<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } } /** * Initializes a graph from the specified input stream. * The format is the number of vertices <em>V</em>, * followed by the number of edges <em>E</em>, * followed by <em>E</em> pairs of vertices, with each entry separated by whitespace. * * @param in the input stream * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range * @throws IllegalArgumentException if the number of vertices or edges is negative * @throws IllegalArgumentException if the input stream is in the wrong format */ public Graph(string filepath) { try { 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>(); } 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 { // for (int j = 0; j < E; j++) // { 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()); }; } // throw an IllegalArgumentException unless {@code 0 <= v < V} public void validateVertex(int v) { if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } /** * Adds the undirected edge v-w to this graph. * * @param v one vertex in the edge * @param w the other vertex in the edge * @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V} */ public void addEdge(int v, int w) { validateVertex(v); validateVertex(w); E++; adj[v].push(w); adj[w].push(v); } /** * Returns the vertices adjacent to vertex {@code v}. * * @param v the vertex * @return the vertices adjacent to vertex {@code v}, as an iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public IEnumerable<int> adjVerticles(int v) { validateVertex(v); return adj[v]; } /** * Returns the degree of vertex {@code v}. * * @param v the vertex * @return the degree of vertex {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int degree(int v) { validateVertex(v); return adj[v].size(); } /** * Returns a string representation of this graph. * * @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 */ public String toString() { StringBuilder s = new StringBuilder(); s.Append(V + " vertices, " + E + " edges " + "\n"); for (int v = 0; v < V; v++) { s.Append(v + ": "); foreach (int w in adj[v]) { s.Append(w + " "); } s.Append("\n"); } return s.ToString(); } } } |
Bag.cs
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SearchInGraphExample { 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; } } } } |
Test
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SearchInGraphExample { class Program { static void Main(string[] args) { Graph g = new Graph("tinyG.txt"); Console.WriteLine(g.toString()); //testDFS(g); testBFS(g); Console.ReadLine(); } static void testBFS(Graph g) { BreadthFirstPaths bfp = new BreadthFirstPaths(g); // graph consists of 3 parts so we start search since 3 start elements bfp.bfs(g, 0); Console.WriteLine(); bfp.bfs(g, 7); Console.WriteLine(); bfp.bfs(g, 9); } static void testDFS(Graph g) { Console.WriteLine("Which verticles are marked?"); DepthFirstSearch dfs = new DepthFirstSearch(g); // graph consists of 3 parts so we start search since 3 start elements dfs.dfs(g, 0); Console.WriteLine(); dfs.dfs(g, 7); // will write to console if verticle marked Console.WriteLine(); dfs.dfs(g, 9); // will write to console if verticle marked Console.WriteLine(); dfs.unmarkAll(); Console.WriteLine("Is verticle 12 in graph?"); if (dfs.isVertex(g, 9, 12)) Console.WriteLine("Yes"); else Console.WriteLine("No"); Console.Read(); } } } |