Bipartite.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 |
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BipartiteGraphExample { public class Bipartite { public bool isBipartite { get; set; } // is the graph bipartite? private bool[] color; // color[v] gives vertices on one side of bipartition private bool[] marked; // marked[v] = true if v has been visited in DFS private int[] edgeTo; // edgeTo[v] = last edge on path to v public Stack<int> cycle; // odd-length cycle /** * Determines whether an undirected graph is bipartite and finds either a * bipartition or an odd-length cycle. * * @param G the graph */ public Bipartite(Graph G) { isBipartite = true; color = new bool [G.V]; marked = new bool [G.V]; edgeTo = new int[G.V]; for (int v = 0; v < G.V; v++) { if (!marked[v]) { dfs(G, v); } } Trace.Assert(check(G)); } private void dfs(Graph G, int v) { marked[v] = true; foreach (int w in G.adjVerticles(v)) { // short circuit if odd-length cycle found if (cycle != null) return; // found uncolored vertex, so recur if (!marked[w]) { edgeTo[w] = v; color[w] = !color[v]; dfs(G, w); } // if v-w create an odd-length cycle, find it else if (color[w] == color[v]) { isBipartite = false; cycle = new Stack<int>(); cycle.Push(w); // don't need this unless you want to include start vertex twice for (int x = v; x != w; x = edgeTo[x]) { cycle.Push(x); } cycle.Push(w); } } } public bool getColor(int v) { validateVertex(v); if (!isBipartite) throw new ArgumentException("graph is not bipartite"); return color[v]; } /** * Returns an odd-length cycle if the graph is not bipartite, and * {@code null} otherwise. * * @return an odd-length cycle if the graph is not bipartite * (and hence has an odd-length cycle), and {@code null} * otherwise */ public IEnumerable<int> oddCycle() { return cycle; } private bool check(Graph G) { // graph is bipartite if (isBipartite) { for (int v = 0; v < G.V; v++) { foreach (int w in G.adjVerticles(v)) { if (color[v] == color[w]) { Console.WriteLine("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w); return false; } } } } // graph has an odd-length cycle else { // verify cycle int first = -1, last = -1; foreach (int v in oddCycle()) { if (first == -1) first = v; last = v; } if (first != last) { Console.WriteLine("cycle begins with %d and ends with %d\n", first, last); return false; } } return true; } // 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)); } public void showCycle() { foreach (var c in cycle) Console.WriteLine(c); } } } |
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 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BipartiteGraphExample { 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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BipartiteGraphExample { 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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BipartiteGraphExample { class Program { static void Main(string[] args) { Graph g = new Graph("tinyG.txt"); Console.WriteLine(g.toString()); Bipartite b = new Bipartite(g); if (b.isBipartite) Console.WriteLine("Yes! Bipartite!"); else Console.WriteLine("Not Bipartite"); b.showCycle(); Console.ReadLine(); } } } |