topology_demo.cc File Reference

---

Detailed Description

Demo what shows the result of some topology functions.

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * 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>


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;
}

#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>