/*******************************************************************************
+
+  LEDA 3.5
+
+  _g_misc.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <LEDA/graph.h>
#include <LEDA/ugraph.h>
#include <LEDA/graph_alg.h>

//------------------------------------------------------------------------------
// S. Naeher 
//           last modified ( April 1997)
//------------------------------------------------------------------------------

node_array<int>* num_ptr;
  
static int source_num(const edge& e) { return (*num_ptr)[source(e)]; }
static int target_num(const edge& e) { return (*num_ptr)[target(e)]; }


bool Is_Simple(const graph& G)  
{ 
  // return true iff G is simple, i.e, has no parallel edges
 
  list<edge> el= G.all_edges();

  node v;
  
  edge e;
  int n= 0;
  
  node_array<int> num(G);
  forall_nodes(v,G) num[v]= n++;
  
  num_ptr= &num;
  
  el.bucket_sort(0,n-1,&source_num);
  el.bucket_sort(0,n-1,&target_num);
  
  edge e0 = el.pop();
  
  forall(e,el)
  { if ( source(e0) == source(e) && target(e0) == target(e) )
       return false;
    else
       e0 = e;
   }

  return true;
  
}
  
  
list<node> Delete_Loops(graph& G)
{ list<edge> loops;
  list<node> L;
  edge e;
  forall_edges(e,G)
  { node v = source(e);
    node w = target(e);
    if (v == w) 
    { L.append(v);
      loops.append(e);
     }
   }
  forall(e,loops) G.del_edge(e);
  return L;
 }


list<edge> Make_Simple(graph& G)
{ 
  list<edge> L;

  //use bucket sort to find and eliminate parallel edges
  
  list<edge> el = G.all_edges();

  if (el.empty()) return L;


  node_array<int> num(G);
  int  n = 0;
  node v;
  forall_nodes(v,G) num[v] = n++;
  
  num_ptr = &num;

  el.bucket_sort(0,n-1,&source_num);
  el.bucket_sort(0,n-1,&target_num);
  
  bool deleted = false;
  edge e0 = el.pop();

  edge e;
  forall(e,el)  
    if (source(e0) == source(e) && target(e0) == target(e)) 
     { G.del_edge(e);
       if (!deleted) L.append(e0);
       deleted = true;
      }
    else 
     { deleted = false;
       e0 = e;
      }

  return L;
  
 }


static int edge_ord1(const edge& e) { return index(source(e)); }
static int edge_ord2(const edge& e) { return index(target(e)); }

bool Is_Bidirected(const graph& G, edge_array<edge>& reversal)     
{
 // computes for every edge e = (v,w) in G its reversal reversal[e] = (w,v)
 // in G ( nil if not present). Returns true if every edge has a
 // reversal and false otherwise.

  int n = G.max_node_index();
  int count = 0;

  edge e,r;

  forall_edges(e,G) reversal[e] = 0;

  list<edge> El = G.all_edges();
  El.bucket_sort(0,n,&edge_ord2);
  El.bucket_sort(0,n,&edge_ord1);
  
  list<edge> El1 = G.all_edges();
  El1.bucket_sort(0,n,&edge_ord1);
  El1.bucket_sort(0,n,&edge_ord2);


  // merge El and El1 to find corresponding edges

  while (! El.empty() && ! El1.empty())
  { e = El.head();
    r = El1.head();

    if (target(r) == source(e))
      if (source(r) == target(e))
         { reversal[e] = r;
           El1.pop();
           El.pop();
           count++;
          }
      else
         if (index(source(r)) < index(target(e)))
             El1.pop();
         else
             El.pop();

    else
      if (index(target(r)) < index(source(e)))
          El1.pop();
      else
          El.pop();

    }

  return (count == G.number_of_edges()) ? true : false;

}



void Make_Bidirected(graph& G, list<edge>& R)
{
  // make graph bi-directed by inserting reversal edges
  // appends new edges to R

  edge_array<edge> rev(G,nil);

  if (Is_Bidirected(G,rev)) return;

  // build list L of edges having no reversals

  list<edge> L;
  edge e;
  forall_edges(e,G)
   if (rev[e] == nil) L.append(e);

  // insert missing reversals
  forall(e,L)
  { edge r = G.new_edge(target(e),source(e));
    R.append(r);
   }
}


list<edge> Make_Bidirected(graph& G)
{ list<edge> R;
  Make_Bidirected(G,R);
  return R;
 }

static void dfs(node v, int& count1, int& count2, node_array<int>& dfsnum, 
                                                  node_array<int>& compnum)
{ dfsnum[v] = ++count1;
  edge e;
  forall_adj_edges(e,v)
  { node w = target(e);
    if (dfsnum[w] == 0)
      dfs(w,count1,count2,dfsnum,compnum);
   }
  compnum[v] = ++count2;
}
 

bool Is_Acyclic(const graph& G, list<edge>& back)
{ 
  //compute dfs and completeion numbers
  node_array<int> dfsnum(G,0);
  node_array<int> compnum(G,0);
  int count1 = 0;
  int count2 = 0;
  node v;
  forall_nodes(v,G)
    if (dfsnum[v] == 0)
        dfs(v,count1,count2,dfsnum,compnum);

  // compute back edges
  back.clear();
  edge e;
  forall_edges(e,G)
  { node v = source(e);
    node w = target(e);
    if (v == w || (dfsnum[v] > dfsnum[w] && compnum[v] < compnum[w]))
      back.append(e);
   }

  return back.empty();
}


bool Is_Acyclic(const graph& G)
{ list<edge> dummy;
  return Is_Acyclic(G,dummy);
}


void Make_Acyclic(graph& G)
{ list<edge> back;
  Is_Acyclic(G,back);
  edge e;
  forall(e,back) G.del_edge(e);
}




static void dfs(const graph& G, node v, node_array<bool>& reached, int& count)
{ reached[v] = true;
  count++;
  edge e;
  forall_inout_edges(e,v) 
  { node w = G.opposite(v,e);
    if ( !reached[w] ) dfs(G,w,reached,count);
   }
 } 


bool Is_Connected(const graph& G)
{
  node_array <bool>  reached(G, false);
  int  count = 0;
  node s = G.first_node();

  if (s != nil)
    dfs(G,s,reached,count);

  return count == G.number_of_nodes();
 }


void Make_Connected(graph& G, list<edge>& L)
{
  node_array <bool>  reached(G, false);
  node u = G.first_node();
  int count = 0;

  node v;
  forall_nodes(v, G) 
    if ( !reached[v] ) 
    { dfs(G,v,reached,count);  // explore connected comp with root v 
      if (u != v)                     // link v's comp to the first comp
        L.append(G.new_edge(u, v));
     }
 }



list<edge> Make_Connected(graph& G)
{ list<edge> L;
  if (G.number_of_nodes() > 0) Make_Connected(G,L);
  return L;
 }





static void make_bicon_dfs(graph& G, node v, int& dfs_count, 
                                list<edge>& L,
                                node_array<int>&  dfsnum, 
                                node_array<int>&  lowpt,
                                node_array<node>& parent)
{ node u = nil;

  dfsnum[v] = dfs_count++;
  lowpt[v]  = dfsnum[v];

  edge e;
  forall_inout_edges(e,v) 
  { 
    node w = G.opposite(v,e);

    if (u == nil) u = w; //first child

    if ( dfsnum[w] == -1) // w not reached before; e is a tree edge
      { 
        parent[w] = v;
  
        make_bicon_dfs(G, w, dfs_count, L, dfsnum, lowpt, parent);
  
        if (lowpt[w] == dfsnum[v]) 	
        { // |v| is an articulation point. We now add an edge. If |w| is the
  	  // first child and |v| has a parent then we connect |w| and
  	  // |parent[v]|, if |w| is a first child and |v| has no parent then
  	  // we do nothing. If |w| is not the first child then we connect |w|
  	  // to the first child. The net effect of all of this is to link all
  	  // children of an articulation point to the first child and the first
  	  // child to the parent (if it exists)
  
  	  if (w == u && parent[v]) 
          { L.append(G.new_edge(w, parent[v]));
  	    //L.append(G.new_edge(parent[v], w)); (if bidirected)
  	   }
  
  	  if (w != u)
  	  { L.append(G.new_edge(u, w));
  	    //L.append(G.new_edge(w, u)); (if bidirected)
  	   }
         }
  
         lowpt[v] = Min(lowpt[v], lowpt[w]);
       } 
      else // non tree edge
       lowpt[v] = Min(lowpt[v], dfsnum[w]);

  }

}



static bool is_bicon_dfs(const graph& G, node v, int& dfs_count, 
                                         node_array<int>&  dfsnum, 
                                         node_array<int>&  lowpt,
                                         node_array<node>& parent)
{ node u = nil;
  edge e;

  dfsnum[v] = dfs_count++;
  lowpt[v]  = dfsnum[v];

  forall_inout_edges(e,v) 
  { node w = G.opposite(v,e);
    if (u == nil) u = w;
    if ( dfsnum[w] == -1 )
      { parent[w] = v;
        if (!is_bicon_dfs(G, w, dfs_count, dfsnum, lowpt, parent)) return false;
        if (lowpt[w] == dfsnum[v] && (w != u || parent[v]))  return false;
        lowpt[v] = Min(lowpt[v], lowpt[w]);
       } 
    else 
        lowpt[v] = Min(lowpt[v], dfsnum[w]);
  }

  return true;
}


bool Is_Biconnected(const graph & G)
{ if (G.empty()) return true;
  if ( ! Is_Connected(G) ) return false;
  node_array<int>  lowpt(G);
  node_array<int>  dfsnum(G,-1);
  node_array<node> parent(G,nil);
  int dfs_count = 0;
  return is_bicon_dfs(G, G.first_node(), dfs_count, dfsnum, lowpt, parent);
}				




void Make_Biconnected(graph& G, list<edge>& L)
{
  if (G.number_of_nodes() == 0) return;

  Make_Connected(G,L);

  node_array<int>  lowpt(G);
  node_array<int>  dfsnum(G,-1);  // dfsnum[v] == -1  <=>  v not reached 
  node_array<node> parent(G,nil);

  int dfs_count = 0;

  make_bicon_dfs(G, G.first_node(), dfs_count, L, dfsnum, lowpt, parent);
}				


list<edge> Make_Biconnected(graph & G)
{ list<edge> L;
  Make_Biconnected(G,L);
  return L;
 }






static bool bi_bfs(const graph& G, node s, node_array<int>& side)
{ 
  list<node> Q;

  Q.append(s);
  side[s] = 0;

  while ( ! Q.empty() )
  { node v = Q.head();
    edge e;
    forall_inout_edges(e,v)
    { node w = G.opposite(v,e);
      if (side[v] == side[w]) return false;
      if (side[w] == -1)
      { Q.append(w); 
        side[w] = 1 - side[v];
       }
     }
    Q.pop();
  }

  return true;
}


bool Is_Bipartite(const graph& G, list<node>& A, list<node>& B)
{
  node_array<int> side(G,-1);
  node v;

  forall_nodes(v,G)
    if (side[v] == -1) 
       if (! bi_bfs(G,v,side)) return false;

  forall_nodes(v,G)
  { if (side[v] == 0) A.append(v);
    if (side[v] == 1) B.append(v);
   }

  return true;

 }


bool Is_Bipartite(const graph& G)
{ list<node> A,B;
  return Is_Bipartite(G,A,B);
}


int COMPONENTS(const graph&G, node_array<int>&);

int Genus(const graph& G)
{ int n = G.number_of_nodes();
  int m = G.number_of_edges()/2;  // G is bidirected

  edge_array<bool> considered(G,false);
  int f = 0;
  edge e;
  forall_edges(e,G)
  { if (G.reversal(e) == nil)
       error_handler(1,"Genus: graph must be a map.");
    if ( !considered[e] )
    { // trace the face to the left of e
      f++;
      edge x = e;
      do { considered[x] = true;
           x = G.face_cycle_succ(x);
         }
      while (x != e);
    }
  }

  node_array<int> cnum(G);
  int c = COMPONENTS(G,cnum)-1;

  return (2-n+m-f+c)/2;
}




/*
void copy_graph(const graph& G, GRAPH<node,edge>& H, 
                node_array<node>& v_in_H, edge_array<edge>& e_in_H)
{

  node v;
  forall_nodes(v,G) v_in_H[v] = H.new_node(v);

  edge e;
  forall_edges(e,G) e_in_H[e] =
      H.new_edge(v_in_H[source(e)],v_in_H[target(e)],e);
}
*/


bool Is_Map(const graph& G)
{ edge_array<edge> rev(G);
  if (!Is_Bidirected(G,rev)) return false;
  edge x;
  forall_edges(x,G)
  { edge y = G.reversal(x);
    if (x != G.reversal(y)) return false;
    if (source(x) != target(y) || source(y) != target(x)) return false; 
   }
  return true;
}


bool Is_Planar_Map(const graph& G) { return  Is_Map(G) &&Genus(G) == 0; }

bool Is_Planar(const graph& G)
{ graph G1 = G;
  return PLANAR(G1);
 }

