/*******************************************************************************
+
+  LEDA 7.2.3  
+
+
+  gw_shortest_path.c
+
+
+  Copyright (c) 1995-2026
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/



#include <LEDA/graph/graph_alg.h>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/core/map.h>

using namespace leda;


GRAPH<int,int> G;

const int min_cost = -9;
const int max_cost = +9;

const color dark_blue = 0x0000a0;

void display_shortest_path(GraphWin& gw)
{
  gw.message("");

  node_array<int> dist(G);
  node_array<edge> pred(G);

  node s = G.first_node();

  SHORTEST_PATH(G,s,G.edge_data(),dist,pred);
  node_array<int> type = CHECK_SP(G,G.first_node(),G.edge_data(),dist,pred);

  gw.set_flush(false);

  //gw.set_shape(s,square_node);

  // reset edge attributes
  edge e; 
  forall_edges(e,G) {
    gw.set_color(e,grey3);
    gw.set_width(e,2);
    //gw.set_user_label(e,string("%d",G[e]));
  }


  node v;
  forall_nodes(v,G) 
  { if (type[v] > 0 )
    { gw.set_color(v,grey3);
      gw.set_user_label(v,"+oo");
    }
    if (type[v] == 0 )
    { gw.set_color(v,(v == s)? green2 : blue2);
      gw.set_user_label(v,string("%d",dist[v]));
    }
    if (type[v] < 0 )
    { gw.set_color(v,yellow);
      gw.set_user_label(v,"-oo");
    }
    
  }

  forall_edges(e,G) 
  { node v = G.target(e);
    if ( e == pred[v] )
    { gw.set_width(e,3); 
      if (type[v] == 0  ) gw.set_color(e,dark_blue);
      if (type[v] == -1 ) gw.set_color(e,violet);
      if (type[v] == -2 ) gw.set_color(e,red);
    }
  }

  gw.redraw();

}

void init_handler(GraphWin& gw)
{ edge e;
  forall_edges(e,G) 
  { G[e] = rand_int(min_cost+2,max_cost-2);
    gw.set_slider_value(e,(G[e] - min_cost)/((double) (max_cost - min_cost)));
  }
  display_shortest_path(gw);
}


void new_edge_handler(GraphWin& gw, edge e)  
{ G[e] = rand_int(min_cost+2,max_cost-2);
  gw.set_slider_value(e,(G[e] - min_cost)/((double) (max_cost - min_cost)));
  display_shortest_path(gw); 
}


void undo_graph_handler(GraphWin& gw)      { display_shortest_path(gw); }
void del_edge_handler(GraphWin& gw)        { display_shortest_path(gw); }
void new_node_handler(GraphWin& gw,node)   { display_shortest_path(gw); }
void del_node_handler(GraphWin& gw)        { display_shortest_path(gw); }


void start_edge_slider_handler(GraphWin& gw, edge e, double f)
{ 
  // when changing the cost of edge e = (u,v) reset dist labels 
  // of all nodes reachable from v and colors of all incident edges 

  node u = G.source(e);

  // u is not reachable from s (changing cost(e) has no effect)
  if (gw.get_label(u) == "+oo") return;

  gw.set_color(e,grey1);
  gw.set_width(e,2);

  node_array<bool> visited(G,false);
  list<node> L = DFS(G,G.target(e),visited);

  node v;
  forall(v,L) {
     gw.set_user_label(v,"--");
     gw.set_color(v,grey1);
     edge x;
     forall_out_edges(x,v) {
       gw.set_color(x,grey1);
       gw.set_width(x,2);
     }
  }

  gw.redraw();
}
  

void edge_slider_handler(GraphWin& gw, edge e, double f)
{ // moving slider: update G[e] (cost of e)
  G[e] = int(min_cost + (max_cost - min_cost) * f);
}

void end_edge_slider_handler(GraphWin& gw, edge e, double f)
{ // display result
  G[e] = int(min_cost + (max_cost - min_cost) * f);
  display_shortest_path(gw); 
}


void about_shortpath(GraphWin& gw) 
{ window& W = gw.get_window();
 
  panel P(3*W.width()/4,-1);

P.text_item("\\bf Shortest Paths\\rm");
P.text_item("");
P.text_item("This demo illustrates the output convention of shortest-paths ");
P.text_item("algorithms.");
P.text_item("");
P.text_item("You can construct and edit a graph in the graphics window.");
P.text_item("The first node entered is the source node of the shortest-path ");
P.text_item("problem. Every edge has a slider that can be used to adjust ");
P.text_item("the cost value of the edge. The solution of the shortest path ");
P.text_item("computation is updated after each edit operation.");
P.text_item("");
P.text_item("Unreachable nodes are labeled by +infinity.");
P.text_item("Reachable nodes with finite distance are labeled with their distance.");
P.text_item("Reachable nodes for which there are paths with");
P.text_item("arbitrary negative length are labeled with -infinity.");
P.text_item("");
P.text_item("For each reachable node one of the incoming edges is highlighted.");
P.text_item("For each node with finite distance this is the");
P.text_item("last edge on a shortest path to the node.");
P.text_item("For the nodes with distance minus infinity these edges form");
P.text_item("negative cycles or paths emanating from these cycles."); 

P.button("continue");

  gw.open_panel(P);
}

int main()
{ 
  GraphWin gw(G,"Shortest Paths");

  gw.display();

  int h_menu = gw.get_menu("Help");

  if (h_menu != -1)
    gw_add_simple_call(gw,about_shortpath, "About Shortest Paths",h_menu);

  about_shortpath(gw);

  gw.set_action(A_LEFT|A_IMMEDIATE|A_EDGE,0);
  gw.set_action(A_LEFT|A_DRAG|A_EDGE,0); // prevent adding edge bends
  gw.set_action(A_LEFT|A_EDGE,0);


  gw.set_init_graph_handler(init_handler);
  gw.set_new_edge_handler(new_edge_handler);
  gw.set_del_edge_handler(del_edge_handler);
  gw.set_new_node_handler(new_node_handler);
  gw.set_del_node_handler(del_node_handler);
  gw.set_undo_graph_handler(undo_graph_handler);

  gw.set_directed(true);

  gw.set_node_shape(circle_node);
  gw.set_node_label_type(user_label);

  // show graph edge data G[e] as label 
  gw.set_edge_label_type(data_label);

  gw.set_start_edge_slider_handler(start_edge_slider_handler);
  gw.set_edge_slider_handler(edge_slider_handler);
  gw.set_end_edge_slider_handler(end_edge_slider_handler);

  gw.message("Please construct a graph.");

  gw.edit();

  return 0;
}

