solucion examen febrero 2012- bipartite

PARTE JAVA

package graph;

import dictionary.Dictionary;
import dictionary.HashDictionary;
import stack.Stack;
import stack.StackList;

public class BiPartite<V> {
   
    public static enum Color {Red, Blue; }

    private static Color nextColor(Color c) {
        return (c == Color.Blue) ?Color.Red:Color.Blue;
    }
   
    private Stack<Pair<V,Color>> stack; // stack with pair of vertex and color
    private Dictionary<V,Color> dict; // dictionary: Vertices -> Color
    private boolean isBiColored;

    public BiPartite(Graph<V> graph) {
        dict   = new HashDictionary<V, Color>();
        stack = new StackList<Pair<V,Color>>();
        isBiColored       = true;

        if (graph.numVertices() == 0)
            return;

        V src = graph.vertices().iterator().next(); // initial vertex     
        stack.push(new Pair<V,Color>(src,Color.Red));
       
        while (!stack.isEmpty()) {
            Pair<V,Color> vColor = stack.top();
            stack.pop();
            V val = vColor.first();
            Color col = vColor.second();
            if(dict.valueOf(vColor.fst())==null){
                 dict.insert(val,col);
                 Iterator<V> iter = graph.successors(val).iterator();
                 Color nxtC = nextColor(col);
                 while(iter.hasNext()){
                        V nxtV = iter.next();
                        stack.push(new Pair<V, Color >(nxtV,nxtC));
                 }
            }else if( dict.valueOf(vColor.fst()) !=col) {
                 isBicolored = false;
          }
          
        }
    }   
   
    public Dictionary<V,Color> biColored() {
        return dict;
    }
   
    public boolean isBicolored() {
        return isBiColored;
    }
   
}




---------------------------------
DEMO
---------------------------------

import graph.Graph;
import graph.DictionaryGraph;
import graph.BiPartite;

public class BiPartiteDemo {

    // construcción del grafo bipartito k(n,m) 
    private static Graph<Integer> k(int n, int m){
        Graph<Integer> graph = new DictionaryGraph<Integer>();
       
        for (int r = 1; r<=n; r++){
            for (int a = n+1; a<=n+m; a++){
                // addEddge añade los vértices si fuera necesario
                graph.addEdge(r, a);
            }
        }
        return graph;
    }

    private static <V> void test (Graph<V> g){
        System.out.println(g);

        BiPartite<V> testBiPartite  = new BiPartite<V>(g);
   
         if(testBiPartite.isBicolored()) {
             System.out.println("BiColoreado del anterior grafo:");
            System.out.println(testBiPartite.biColored());
         }
        else
            System.out.println("No es bipartito.");
        System.out.println("------------------");
        }

    public static void main(String[] args) {
        Graph<Integer> g = new DictionaryGraph<Integer>();
       
        g.addEdge(1,2);
        g.addEdge(2,3);
        g.addEdge(3,4);
        g.addEdge(4,5);
        g.addEdge(5,6);
//        g.addEdge(6,4); // con esta arista ya no es bipartito (tiene un ciclo impar)
        g.addEdge(6,1);

        test(g);
       

        System.out.println("Ahora probamos con el completo k(2,4)");
        Graph<Integer> gbp = k(2,4);
        test(gbp);
   
        System.out.println("Ahora añadimos la arista 4-6");
        Graph<Integer> gbp2 = (Graph<Integer>) gbp.clone();
        gbp2.addEdge(4,6);
        test(gbp2);
       
      }   
}


PARTE HASKELL

module BiPartite(
    biColored    -- :: Ord v  => Graph v -> Maybe (D.Dictionary v Color)
  , Color(..)
  )  where

import Graph
import Data.Maybe(isJust)
import qualified Dictionary as D
import qualified Stack as S


data Color = Red |  Blue deriving (Eq,Show,Ord)
nextColor Red  = Blue
nextColor Blue = Red

pushAll :: S.Stack a -> [a] -> S.Stack a
pushAll = foldr S.push  

biColored :: Ord v => Graph v -> Maybe (D.Dictionary v Color)
biColored g
 | null vs   = Just D.empty -- empty graph is bipartite
 | otherwise = aux g D.empty (S.push (src ,Red) S.empty)
 where
  vs  = vertices g
  src = head vs -- initial vertex

aux :: Ord v => Graph v -> D.Dictionary v Color -> S.Stack (v, Color) ->
                Maybe (D.Dictionary v Color)
aux g dict stack
   | S.isEmpty stack       = Just dict
--
-- ¡¡¡ completad el resto de guardas !!
--
  where
     colored  v         = D.isDefinedAt v dict
--
-- ¡¡¡ completad las variables locales necesarias !!!
--

---------------------
--- EXAMPLES --------
---------------------
data MiVertice = A|B|C|D|E|F|G deriving (Show,Eq,Enum,Ord)

{-
  A--B--D--F   
   \ |  |
     C--E--G
-}
g1  = mkGraphSuc vertices suc
  where
        vertices = [A .. G]
        suc A = [C,B]
        suc B = [A,C,D]
        suc C = [B,E]
    suc D = [B,F,E]
        suc E = [C,D,G]
        suc F = [D,D]
    suc G = [E]
-- *BiPartite> biColored g1
-- Nothing

{-
  A--B--D--F   
     |  |
     C--E
-}
g2  = mkGraphEdges vertices edges
  where
        vertices =  [A .. F]
        edges = [(A,B),(B,C),(B,D),(D,E),(D,F),(C,E)]
-- *BiPartite> biColored g2
-- Just Dictionary(A->Red,B->Blue,C->Red,D->Red,E->Blue,F->Blue)

-- construcción de los bipartitos K n m
k n m = mkGraphEdges vertices edges
  where
            vertices = [1 .. n + m]
            edges = [ (r,a) | r<-[1..n], a<-[n+1..n+m] ]

-- *BiPartite> biColored (k 2 3)
-- Just Dictionary(1->Red,2->Red,3->Blue,4->Blue,5->Blue)