/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <lemon/list_graph.h>

 #include <lemon/topology.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/graph_reader.h>

 #include <lemon/dim2.h>

 #include <iostream>

 #include <cstdlib>

 #include <ctime>

 /// \ingroup demos

 /// \file

 /// \brief Demo what shows the result of some topology functions.

 ///

 ///  Demo what shows the result of some topology functions.

 ///

 /// \include topology_demo.cc

 using namespace lemon;

 using namespace lemon::dim2;

 using namespace std;

 Color color(bool val) {

   return val ? RED : BLUE;

 }

 void drawConnectedComponents() {

   typedef ListUGraph Graph;

   typedef Graph::Node Node;

   Graph graph;

   Graph::NodeMap<Point<double> > coords(graph);

   UGraphReader<Graph>("u_components.lgf", graph).

     readNodeMap("coordinates_x", xMap(coords)).

     readNodeMap("coordinates_y", yMap(coords)).

     run();

   Palette palette;

   Graph::NodeMap<int> compMap(graph);

   connectedComponents(graph, compMap);

   graphToEps(graph, "connected_components.eps").undirected().

     coords(coords).scaleToA4().enableParallel().

     nodeColors(composeMap(palette, compMap)).run();

   std::cout << "Result: connected_components.eps" << std::endl;

 }

 void drawStronglyConnectedComponents() {

   typedef ListGraph Graph;

   typedef Graph::Node Node;

   Graph graph;

   Graph::NodeMap<Point<double> > coords(graph);

   GraphReader<Graph>("dir_components.lgf", graph).

     readNodeMap("coordinates_x", xMap(coords)).

     readNodeMap("coordinates_y", yMap(coords)).

     run();

   Palette palette;

   Graph::NodeMap<int> compMap(graph);

   Graph::EdgeMap<bool> cutMap(graph);

   stronglyConnectedComponents(graph, compMap);

   stronglyConnectedCutEdges(graph, cutMap);

   graphToEps(graph, "strongly_connected_components.eps").

     coords(coords).scaleToA4().enableParallel().drawArrows().

     nodeColors(composeMap(palette, compMap)).

     edgeColors(composeMap(functorMap(&color), cutMap)).run();

   std::cout << "Result: strongly_connected_components.eps" << std::endl;

 }

 void drawNodeBiconnectedComponents() {

   typedef ListUGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::UEdge UEdge;

   Graph graph;

   Graph::NodeMap<Point<double> > coords(graph);

   UGraphReader<Graph>("u_components.lgf", graph).

     readNodeMap("coordinates_x", xMap(coords)).

     readNodeMap("coordinates_y", yMap(coords)).

     run();

   Palette palette;

   Graph::UEdgeMap<int> compMap(graph);

   Graph::NodeMap<bool> cutMap(graph);

   biNodeConnectedComponents(graph, compMap);

   biNodeConnectedCutNodes(graph, cutMap);

   graphToEps(graph, "bi_node_connected_components.eps").undirected().

     coords(coords).scaleToA4().enableParallel().

     edgeColors(composeMap(palette, compMap)).

     nodeColors(composeMap(functorMap(&color), cutMap)).

     run();

   std::cout << "Result: bi_node_connected_components.eps" << std::endl;

 }

 void drawEdgeBiconnectedComponents() {

   typedef ListUGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::UEdge UEdge;

   Graph graph;

   Graph::NodeMap<Point<double> > coords(graph);

   UGraphReader<Graph>("u_components.lgf", graph).

     readNodeMap("coordinates_x", xMap(coords)).

     readNodeMap("coordinates_y", yMap(coords)).

     run();

   Palette palette;

   Graph::NodeMap<int> compMap(graph);

   Graph::UEdgeMap<bool> cutMap(graph);

   biEdgeConnectedComponents(graph, compMap);

   biEdgeConnectedCutEdges(graph, cutMap);

   graphToEps(graph, "bi_edge_connected_components.eps").undirected().

     coords(coords).scaleToA4().enableParallel().

     nodeColors(composeMap(palette, compMap)).

     edgeColors(composeMap(functorMap(&color), cutMap)).run();

   std::cout << "Result: bi_edge_connected_components.eps" << std::endl;

 }

 void drawBipartitePartitions() {

   typedef ListUGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::UEdge UEdge;

   Graph graph;

   Graph::NodeMap<Point<double> > coords(graph);

   UGraphReader<Graph>("partitions.lgf", graph).

     readNodeMap("coordinates_x", xMap(coords)).

     readNodeMap("coordinates_y", yMap(coords)).

     run();

   Palette palette;

   Graph::NodeMap<bool> partMap(graph);

   bipartitePartitions(graph, partMap);

   graphToEps(graph, "bipartite_partitions.eps").undirected().

     coords(coords).scaleToA4().enableParallel().

     nodeColors(composeMap(functorMap(&color), partMap)).run();

   std::cout << "Result: bipartite_partitions.eps" << std::endl;

 } 

 int main() {

   drawConnectedComponents();

   drawStronglyConnectedComponents();

   drawNodeBiconnectedComponents();

   drawEdgeBiconnectedComponents();

   drawBipartitePartitions();

   return 0;

 }