# HG changeset patch
# User jacint
# Date 1078846360 0
# Node ID 0defa5aa1229e4028399d2d0f4086beadd6d8dec
# Parent  4f54d89fa9d256865ad215007cb7ce0599cd938f
*** empty log message ***

diff -r 4f54d89fa9d2 -r 0defa5aa1229 src/work/jacint/dijkstra.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/dijkstra.cc	Tue Mar 09 15:32:40 2004 +0000
@@ -0,0 +1,242 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+#include <list_graph.hh>
+#include <dijkstra.h>
+
+using namespace hugo;
+
+int main (int, char*[])
+{
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  
+  ListGraph flow_test;
+ 
+  /*    //Ahuja könyv példája, maxflowvalue=13
+  NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt v3=flow_test.addNode();
+  NodeIt v4=flow_test.addNode();
+  NodeIt v5=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
+  
+  ListGraph::NodeMap<std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(v5, "v5");
+  Node_name.set(t, "t");
+
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt s_v2=flow_test.addEdge(s, v2);
+  EdgeIt s_v3=flow_test.addEdge(s, v3);
+  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
+  EdgeIt v2_v5=flow_test.addEdge(v2, v5);
+  EdgeIt v3_v5=flow_test.addEdge(v3, v5);
+  EdgeIt v4_t=flow_test.addEdge(v4, t);
+  EdgeIt v5_t=flow_test.addEdge(v5, t);
+  EdgeIt v2_s=flow_test.addEdge(v2, s);
+  
+   ListGraph::EdgeMap<int> cap(flow_test);  
+  cap.set(s_v1, 0);
+  cap.set(s_v2, 10);
+  cap.set(s_v3, 10);
+  cap.set(v2_v4, 5);
+  cap.set(v2_v5, 8);
+  cap.set(v3_v5, 5);
+  cap.set(v4_t, 8);
+  cap.set(v5_t, 8);
+  cap.set(v2_s, 0);
+  */
+
+  
+  //Marci példája, maxflowvalue=23
+    NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt v3=flow_test.addNode();
+  NodeIt v4=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
+  NodeIt z=flow_test.addNode();
+
+  
+   ListGraph::NodeMap<std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(t, "t");
+  Node_name.set(z, "z");
+
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt s_v2=flow_test.addEdge(s, v2);
+  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
+  EdgeIt v2_v1=flow_test.addEdge(v2, v1);
+  EdgeIt v1_v3=flow_test.addEdge(v1, v3);
+  EdgeIt v3_v2=flow_test.addEdge(v3, v2);
+  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
+  EdgeIt v4_v3=flow_test.addEdge(v4, v3);
+  EdgeIt v3_t=flow_test.addEdge(v3, t);
+  EdgeIt v4_t=flow_test.addEdge(v4, t);
+  EdgeIt v3_v3=flow_test.addEdge(v3, v3);
+  EdgeIt s_z=flow_test.addEdge(s, z);
+  //  EdgeIt v2_s=flow_test.addEdge(v2, s);
+  
+
+
+   ListGraph::EdgeMap<int> cap(flow_test);  
+  cap.set(s_v1, 16);
+  cap.set(s_v2, 13);
+  cap.set(v1_v2, 10);
+  cap.set(v2_v1, 4);
+  cap.set(v1_v3, 12);
+  cap.set(v3_v2, 9);
+  cap.set(v2_v4, 14);
+  cap.set(v4_v3, 7);
+  cap.set(v3_t, 20);
+  cap.set(v4_t, 4);
+  cap.set(v3_v3, 4);
+  cap.set(s_z, 4);
+  //  cap.set(v2_s, 0);
+
+
+
+  //pelda 3, maxflowvalue=4
+  /*      NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
+  NodeIt w=flow_test.addNode();
+  
+  NodeMap<ListGraph, std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(t, "t");
+  Node_name.set(w, "w");
+
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
+  EdgeIt v2_t=flow_test.addEdge(v2, t);
+  EdgeIt v1_v1=flow_test.addEdge(v1, v1);
+  EdgeIt s_w=flow_test.addEdge(s, w);
+
+
+  EdgeMap<ListGraph, int> cap(flow_test); 
+    
+  cap.set(s_v1, 16);
+  cap.set(v1_v2, 10);
+  cap.set(v2_t, 4);
+  cap.set(v1_v1, 3);
+  cap.set(s_w, 5);
+  */
+  
+
+
+  /*
+  std::cout << "Testing reverse_bfs..." << std::endl;
+  
+  reverse_bfs<ListGraph> bfs_test(flow_test, t);
+
+  bfs_test.run();
+
+  for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
+    std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
+    }
+
+  */
+
+
+  /*
+  std::cout << "Testing preflow_push_hl..." << std::endl;
+  
+  preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
+
+  preflow_push_test.run();
+
+  std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
+
+  std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
+
+   ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();  
+  for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
+    std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
+    }
+
+  std::cout << "A minimum cut: " <<std::endl;  
+   ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
+
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+      if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
+    }
+  
+  std::cout<<"\n\n"<<std::endl;
+
+
+
+
+  std::cout << "Testing preflow_push_max_flow..." << std::endl;
+ 
+  preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
+
+  max_flow_test.run();
+
+  std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
+
+  std::cout << "A minimum cut: " <<std::endl;  
+   ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
+
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+    if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
+  }
+  
+  std::cout << std::endl <<std::endl;
+  */
+
+  
+    std::cout << "Testing dijkstra..." << std::endl;
+  
+    NodeIt root=s;
+
+    Dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
+
+    dijkstra_test.run();
+
+    EachNodeIt w;
+
+    for ( flow_test.getFirst(w); flow_test.valid(w) ; flow_test.next(w) ) {
+      if (dijkstra_test.reach(w)) {
+      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
+      if (dijkstra_test.pred(w).valid()) {
+      std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl; 
+      } else {
+       std::cout <<", this is the root."<<std::endl; }
+      
+      } else {
+	std::cout << w << " is not reachable from " << root <<std::endl;
+      }
+    }
+
+
+
+  return 0;
+}
+
+
+
+
+
+
+
+
+
diff -r 4f54d89fa9d2 -r 0defa5aa1229 src/work/jacint/dijkstra.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/dijkstra.h	Tue Mar 09 15:32:40 2004 +0000
@@ -0,0 +1,124 @@
+// -*- C++ -*-
+/* 
+ *template <Graph, T, Heap=FibHeap>
+ *
+ *
+ *Constructor: 
+ *
+ *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
+ *
+ *
+ *
+ *Member functions:
+ *
+ *void run()
+ *
+ *  The following function should be used after run() was already run.
+ *
+ *
+ *T dist(NodeIt v) : returns the distance from s to v. 
+ *   It is 0 if v is not reachable from s.
+ *
+ *
+ *EdgeIt pred(NodeIt v) : returns the last edge 
+ *   of a shortest s-v path. Returns an invalid iterator 
+ *   if v=s or v is not reachable from s.
+ *
+ *
+ *bool reach(NodeIt v) : true iff v is reachable from s
+ *
+ */
+
+#ifndef DIJKSTRA_HH
+#define DIJKSTRA_HH
+
+#include <fib_heap.h>
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename Heap=FibHeap<typename Graph::NodeIt, T, 
+    typename Graph::NodeMap<int> > >
+    class Dijkstra{
+      typedef typename Graph::NodeIt NodeIt;
+      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::OutEdgeIt OutEdgeIt;
+      
+      Graph& G;
+      NodeIt s;
+      typename Graph::NodeMap<EdgeIt> predecessor;
+      typename Graph::NodeMap<T> distance;
+      typename Graph::EdgeMap<T>& length;
+      typename Graph::NodeMap<bool> reached;
+          
+  public :
+
+    /*
+      The distance of the nodes is 0.
+    */
+    Dijkstra(Graph& _G, NodeIt const _s, 
+	     typename Graph::EdgeMap<T>& _length) : 
+      G(_G), s(_s), predecessor(G), distance(G), 
+      length(_length), reached(G, false) { }
+    
+      
+      void run() {
+	
+	typename Graph::NodeMap<bool> scanned(G, false);
+	typename Graph::NodeMap<int> heap_map(G,-1);
+
+	Heap heap(heap_map);
+
+	heap.push(s,0); 
+	reached.set(s, true);
+
+	while ( !heap.empty() ) {
+
+	  NodeIt v=heap.top(); 
+	  T oldvalue=heap.get(v);
+	  distance.set(v, oldvalue);
+	  heap.pop();
+	  
+	  OutEdgeIt e;
+	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
+	    NodeIt w=G.head(e); 
+	    
+	    if ( !scanned.get(w) ) {
+	      if ( !reached.get(w) ) {
+		reached.set(w,true);
+		heap.push(w,oldvalue+length.get(e)); 
+		predecessor.set(w,e);
+
+	      } else if ( oldvalue+length.get(e) < heap.get(w) ) {
+		predecessor.set(w,e);
+		heap.decrease(w, oldvalue+length.get(e)); 
+	      }
+	    }
+	  }
+	  scanned.set(v,true);
+	}
+      } 
+      
+
+      T dist(NodeIt v) {
+	return distance.get(v);
+      }
+
+
+      EdgeIt pred(NodeIt v) {
+	if ( v!=s ) return predecessor.get(v);
+	else return EdgeIt();
+      }
+     
+
+      bool reach(NodeIt v) {
+	return reached.get(v);
+      }
+
+    };
+
+}
+
+#endif
+
+
diff -r 4f54d89fa9d2 -r 0defa5aa1229 src/work/jacint/fib_heap.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/fib_heap.h	Tue Mar 09 15:32:40 2004 +0000
@@ -0,0 +1,399 @@
+// -*- C++ -*-
+/*
+ *template <typename Item, 
+ *          typename Prio, 
+ *          typename ItemIntMap, 
+ *          typename Compare = std::less<Prio> >
+ * 
+ *constructors:
+ *
+ *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
+ *
+ *Member functions:
+ *
+ *int size() : returns the number of elements in the heap
+ *
+ *bool empty() : true iff size()=0
+ *
+ *void push(Item, Prio) : pushes Item to the heap with priority Prio. If
+ *     Item was already in the heap, it calls decrease(Item, Prio) 
+ *
+ *Item top() : returns the Item with least Prio
+ *
+ *Prio prio() : returns the least Prio
+ *  
+ *Prio get(Item) : returns Prio of Item
+ *
+ *void pop() : deletes the Item with least Prio
+ *
+ *void erase(Item) : deletes Item from the heap if it was already there
+ *
+ *void decrease(Item, P) : If Item was not in the heap, then it calls 
+ *     push(Item, P). If item is in the heap with Prio more than P
+ *     then sets its Prio to P.
+ *
+ *void increase(Item, P) : If Item was not in the heap, then it calls 
+ *     push(Item, P). If item is in the heap with Prio less than P
+ *     then sets its Prio to P.
+ *
+ *
+ *In Fibonacci heaps, increase and erase are not efficient, in case of
+ *many calls to these operations, it is better to use bin_heap.
+ */
+
+#ifndef FIB_HEAP_H
+#define FIB_HEAP_H
+
+#include <vector>
+#include <functional>
+#include <math.h>
+
+namespace hugo {
+  
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare = std::less<Prio> >
+ 
+  class FibHeap {
+  
+    typedef Prio PrioType;
+    
+    class store;
+    
+    std::vector<store> container;
+    int minimum;
+    bool blank;
+    ItemIntMap &iimap;
+    Compare comp;
+    
+  public :
+    
+    FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} 
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
+      blank(true), iimap(_iimap), comp(_comp) {}
+    
+    
+    int size() const {
+      int s=0;
+      for ( unsigned int i=0; i!=container.size(); ++i )
+	if ( container[i].in ) ++s;
+      return s; 
+    }
+
+
+   bool empty() const { return blank; }
+    
+    
+   void push (Item const it, PrioType const value) 
+   {
+   
+     int i=iimap.get(it);
+      
+     if ( i >= 0 && container[i].in ) decrease(it, value); 
+     else {
+       if ( i < 0 ) {
+	 int s=container.size();
+	 iimap.set( it, s );	
+	 store st;
+	 st.name=it;
+	 container.push_back(st);
+	 i=s;
+       }
+       
+       if ( !blank ) {
+	 container[container[minimum].right_neighbor].left_neighbor=i;
+	 container[i].right_neighbor=container[minimum].right_neighbor;
+	 container[minimum].right_neighbor=i;
+	 container[i].left_neighbor=minimum;
+	 if ( !comp( container[minimum].prio, value) ) minimum=i; 
+
+
+
+       } else {
+	 container[i].right_neighbor=container[i].left_neighbor=i;
+	 minimum=i;	
+	 blank=false;
+       }
+       container[i].prio=value;
+     }
+   }
+
+
+    Item top() const {
+      if ( !blank ) { 
+	return container[minimum].name;
+      } else {
+	return Item();
+      }
+    }
+    
+    
+    PrioType prio() const {
+      if ( !blank ) { 
+	return container[minimum].prio;
+      } else {
+	return PrioType();
+      }
+    }
+    
+
+    const PrioType get(const Item& it) const
+    {
+      int i=iimap.get(it);
+      
+      if ( i >= 0 && container[i].in ) { 
+	return container[i].prio;
+      } else {
+	return PrioType();
+      }
+    }
+
+
+    void pop() {
+      if ( !blank ) {
+	
+	/*The first case is that there are only one root.*/
+	if ( container[minimum].left_neighbor==minimum ) {
+	  container[minimum].in=false;
+	  if ( container[minimum].degree==0 ) blank=true; 
+	  else { 
+	    makeroot(container[minimum].child);
+	    minimum=container[minimum].child;
+	    balance();
+	  } 
+       } else {
+	 int right=container[minimum].right_neighbor;
+	 unlace(minimum);
+	 container[minimum].in=false;
+	 if ( container[minimum].degree > 0 ) {
+	   int left=container[minimum].left_neighbor;
+	   int child=container[minimum].child;
+	   int last_child=container[child].left_neighbor;
+	   
+	   container[left].right_neighbor=child;
+	   container[child].left_neighbor=left;
+	   container[right].left_neighbor=last_child;
+	   container[last_child].right_neighbor=right;
+	   
+	   makeroot(child);
+	 }
+	 minimum=right;
+	 balance();
+       } // the case where there are more roots
+     } 
+   }
+
+    
+   void erase (const Item& it) {
+     int i=iimap.get(it);
+     
+     if ( i >= 0 && container[i].in ) { 
+	
+       if ( container[i].parent!=-1 ) {
+	 int p=container[i].parent;
+	 cut(i,p);	    
+	 cascade(p);
+	 minimum=i;     //As if its prio would be -infinity
+       }
+       pop();
+     }
+   }
+    
+
+   void decrease (Item it, PrioType const value) {
+     int i=iimap.get(it);
+     if ( i >= 0 && container[i].in ) { 
+       
+       if ( comp(value, container[i].prio) ) {
+	 container[i].prio=value;
+	 
+	 if ( container[i].parent!=-1 ) {
+	   int p=container[i].parent;
+	    
+	   if ( !comp(container[p].prio, value) ) { 
+	     cut(i,p);	    
+	     cascade(p);
+	     if ( comp(value, container[minimum].prio) ) minimum=i; 
+	   }
+	 } 
+       }
+     } else push(it, value);
+   }
+   
+
+    void increase (Item it, PrioType const value) {
+      int i=iimap.get(it);
+      
+      if ( i >= 0 && container[i].in ) { 
+	if ( comp(container[i].prio, value) ) { 
+	  erase(it);
+	  push(it, value);
+	}
+      } else push(it, value);
+    }
+
+
+  private:
+    
+    void balance() {      
+    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
+  
+    std::vector<int> A(maxdeg,-1); 
+    
+    /*
+     *Recall that now minimum does not point to the minimum prio element.
+     *We set minimum to this during balance().
+     */
+    int anchor=container[minimum].left_neighbor; 
+    int next=minimum; 
+    bool end=false; 
+    	
+       do {
+	int active=next;
+	int d=container[active].degree;
+	if ( anchor==active ) end=true;
+	next = container[active].right_neighbor;
+	if ( !comp(container[minimum].prio, container[active].prio) )
+	  minimum=active;
+
+	while (A[d]!=-1) {
+	  
+	  if( comp(container[active].prio, container[A[d]].prio) ) {
+	    fuse(active,A[d]); 
+	  } else { 
+	    fuse(A[d],active);
+	    active=A[d];
+	  } 
+	  A[d]=-1;
+	  ++d;
+	}
+	
+	A[d]=active;
+       } while ( !end );
+  }
+
+
+
+
+    /*
+     *All the siblings of a are made roots.
+     */
+    void makeroot (int c)  
+    {
+      int s=c;
+      do {  
+	container[s].parent=-1;
+	s=container[s].right_neighbor;
+      } while ( s != c );
+    }
+    
+
+    void cut (int a, int b) 
+    {    
+
+      /*
+       *Replacing a from the children of b.
+       */
+      --container[b].degree;
+
+      if ( container[b].degree !=0 ) {
+      int child=container[b].child;
+      if ( child==a ) 
+	container[b].child=container[child].right_neighbor;
+      
+      unlace(a);
+	
+      }
+    
+
+      /*Lacing i to the roots.*/
+      int right=container[minimum].right_neighbor;
+      container[minimum].right_neighbor=a;
+      container[a].left_neighbor=minimum;
+      container[a].right_neighbor=right;
+      container[right].left_neighbor=a;
+
+      container[a].parent=-1;
+      container[a].marked=false;
+    }
+
+
+    void cascade (int a) 
+    {
+      if ( container[a].parent!=-1 ) {
+	int p=container[a].parent;
+	
+	if ( container[a].marked==false ) container[a].marked=true;
+	else {
+	  cut(a,p);
+	  cascade(p);
+	}
+      }
+    }
+
+
+    void fuse (int a, int b) 
+    {
+      
+      unlace(b);
+
+      
+      /*Lacing b under a.*/
+      container[b].parent=a;
+
+      if (container[a].degree==0) {
+	container[b].left_neighbor=b;
+	container[b].right_neighbor=b;
+	container[a].child=b;	
+      } else {
+	int child=container[a].child;
+	int last_child=container[child].left_neighbor;
+	container[child].left_neighbor=b;
+	container[b].right_neighbor=child;
+	container[last_child].right_neighbor=b;
+	container[b].left_neighbor=last_child;
+      }
+
+      ++container[a].degree;
+      
+      container[b].marked=false;
+    }
+
+
+    /*
+     *It is invoked only if a has siblings.
+     */
+
+    void unlace (int a) {      
+      int leftn=container[a].left_neighbor;
+      int rightn=container[a].right_neighbor;
+      container[leftn].right_neighbor=rightn;
+      container[rightn].left_neighbor=leftn;
+    }
+
+
+    class store {
+      friend class FibHeap;
+      
+      Item name;
+      int parent;
+      int left_neighbor;
+      int right_neighbor;
+      int child;
+      int degree;  
+      bool marked;
+      bool in;
+      PrioType prio;
+
+      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
+    };
+    
+  };
+  
+} //namespace hugo
+#endif 
+
+
+
+
+
+
diff -r 4f54d89fa9d2 -r 0defa5aa1229 src/work/jacint/makefile
--- a/src/work/jacint/makefile	Mon Mar 08 12:29:07 2004 +0000
+++ b/src/work/jacint/makefile	Tue Mar 09 15:32:40 2004 +0000
@@ -3,7 +3,7 @@
 CXXFLAGS = -W -Wall -ansi -pedantic
 LEDAROOT = /ledasrc/LEDA-4.1
 
-BINARIES = preflow
+BINARIES = preflow dijkstra
 
 all: $(BINARIES)
 
@@ -13,6 +13,9 @@
 preflow: 
 	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
 
+dijkstra: 
+	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
+
 clean:
 	$(RM) *.o $(BINARIES) .depend