testGraph – which verticles are closable? We have 3 groups! 7 and 8 closable ! 0 and 7 not !
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SearchInGraphExample { public class CC // ClosableComponents { public bool[] marked; // marked[v] = has vertex v been marked? public int[] id; // id[v] = id of connected component containing v public int[] size; // size[id] = number of vertices in given component public int count; // number of connected components /** * Computes the connected components of the undirected graph {@code G}. * * @param G the undirected graph */ public CC(Graph G) { marked = new bool[G.V]; id = new int[G.V]; size = new int[G.V]; for (int v = 0; v < G.V; v++) { if (!marked[v]) { dfs(G, v); count++; } } } // depth-first search for a Graph private void dfs(Graph G, int v) { marked[v] = true; id[v] = count; size[count]++; foreach (int w in G.adjVerticles(v)) { if (!marked[w]) { dfs(G, w); } } } /** * Returns the component id of the connected component containing vertex {@code v}. * * @param v the vertex * @return the component id of the connected component containing vertex {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int idGroup(int v) { validateVertex(v); return id[v]; } /** * Returns the number of vertices in the connected component containing vertex {@code v}. * * @param v the vertex * @return the number of vertices in the connected component containing vertex {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int sizeGroup(int v) { validateVertex(v); return size[id[v]]; } /** * Returns the number of connected components in the graph {@code G}. * * @return the number of connected components in the graph {@code G} */ public int countGroup() { return count; } /** * Returns true if vertices {@code v} and {@code w} are in the same * connected component. * * @param v one vertex * @param w the other vertex * @return {@code true} if vertices {@code v} and {@code w} are in the same * connected component; {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} * @throws IllegalArgumentException unless {@code 0 <= w < V} */ public bool connected(int v, int w) { validateVertex(v); validateVertex(w); return idGroup(v) == idGroup(w); } // 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)); } } } |
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.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 |
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); CCTest(g); Console.ReadLine(); } static void CCTest(Graph g) // Closable components test { CC cc = new CC(g); Console.WriteLine(); if (cc.connected(7, 8)) Console.WriteLine("Yes! 7 and 8 in one part of Graph, connected"); if (!cc.connected(7, 0)) Console.WriteLine("N0! 7 and 0 in diff parts of Graph, not connected"); } static void testBFS(Graph g) { BreadthFirstSearch bfp = new BreadthFirstSearch(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(); } } } |