Bipartite Graph

BipartiteGraph

// http://www.geeksforgeeks.org/bipartite-graph/

using System;
using System.Collections.Generic;

namespace BipartiteGraph
{
    public enum Color {
        NoColor,
        Green,
        Red
    };
    
    public class Program
    {
        public static void Main(string[] args)
        {
            Vertex v1 = new Vertex(1);
            Vertex v2 = new Vertex(2);
            Vertex v3 = new Vertex(3);
            Vertex v4 = new Vertex(4);
            
            v1.Neighbors.Add(v2);
            v2.Neighbors.Add(v1);
            
            v2.Neighbors.Add(v3);
            v3.Neighbors.Add(v2);
            
            v3.Neighbors.Add(v4);
            v4.Neighbors.Add(v3);
                        
            Graph g1 = new Graph(v1);
            Console.WriteLine("Is Graph 1 bipartite: {0}", g1.IsBipartite());
            
            Vertex v5 = new Vertex(5);
            Vertex v6 = new Vertex(6);
            Vertex v7 = new Vertex(7);
            
            v5.Neighbors.Add(v6);
            v5.Neighbors.Add(v7);
            
            v6.Neighbors.Add(v5);
            v6.Neighbors.Add(v7);
            
            v7.Neighbors.Add(v5);
            v7.Neighbors.Add(v6);
            
            Graph g2 = new Graph(v5);
            Console.WriteLine("Is Graph 2 bipartite: {0}", g2.IsBipartite());
        }
    }
    
    public class Vertex {
               
        public Vertex(int data) {
            Data = data;
            Neighbors = new List<Vertex>();
        }     
        
        public int Data { get; private set;}
        
        public List<Vertex> Neighbors;
        
        public bool IsVisited { get; set; }
        
        public Color Color { get; set; }
    }
        
    class Graph {
        private Vertex source;
    
        public Graph(Vertex source) {
            this.source = source;
        }
        
        public bool IsBipartite() {
            if (source == null) {
                return false;
            }
            
            Color currentColor = Color.Green;
            
            Queue<Vertex> vertices = new Queue<Vertex>();
            vertices.Enqueue(source);
            source.IsVisited = true;
            source.Color = currentColor;
            
            while (vertices.Count > 0) {
                Vertex vertex = vertices.Dequeue();
                currentColor = currentColor == Color.Green ? Color.Red : Color.Green;

                foreach(var neighbor in vertex.Neighbors) {
                    if (neighbor.Color == vertex.Color) {
                        return false;
                    } else if (!neighbor.IsVisited) {
                        neighbor.IsVisited = true;
                        neighbor.Color = currentColor;
                        vertices.Enqueue(neighbor);
                    }
                }
            }
            
            return true;
        }
    }
}