# HG changeset patch # User deba # Date 1132132541 0 # Node ID fdfa3aa18607dee6ecf6b54baea37d51d94b5732 # Parent 049f42e44dee481bd5ba357008546cdd0f2e025a Demo for topology diff -r 049f42e44dee -r fdfa3aa18607 demo/Makefile.am --- a/demo/Makefile.am Wed Nov 16 09:11:44 2005 +0000 +++ b/demo/Makefile.am Wed Nov 16 09:15:41 2005 +0000 @@ -15,7 +15,8 @@ sub_graph_adaptor_demo \ descriptor_map_demo \ coloring \ - grid_graph_demo + grid_graph_demo \ + topology_demo if HAVE_GLPK noinst_PROGRAMS += lp_demo lp_maxflow_demo @@ -56,4 +57,6 @@ lp_maxflow_demo_SOURCES = lp_maxflow_demo.cc lp_maxflow_demo_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) -descriptor_map_demo_SOURCES = descriptor_map_demo.cc \ No newline at end of file +descriptor_map_demo_SOURCES = descriptor_map_demo.cc + +topology_demo_SOURCES = topology_demo.cc \ No newline at end of file diff -r 049f42e44dee -r fdfa3aa18607 demo/dir_components.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/dir_components.lgf Wed Nov 16 09:15:41 2005 +0000 @@ -0,0 +1,52 @@ +@nodeset +coordinates_x coordinates_y id +218.178 27.2723 19 +157.79 -130.517 18 +44.8044 15.5841 17 +-465.576 -42.8564 16 +-675.963 -3.89604 15 +-574.666 -153.893 14 +-490.901 120.777 13 +-368.176 331.163 12 +-266.879 114.933 11 +-251.294 -335.059 10 +-173.374 377.916 9 +169.478 311.683 8 +5.84406 175.322 7 +342.851 111.037 6 +670.118 -118.829 5 +364.28 -222.074 4 +-105.193 -261.035 3 +-227.918 -40.9084 2 +-389.604 -136.361 1 +@edgeset + id +17 19 23 +19 18 24 +18 17 25 +3 17 21 +14 16 18 +13 16 17 +16 15 19 +15 14 20 +11 13 15 +13 12 16 +12 11 14 +1 10 1 +11 9 13 +7 9 12 +6 8 10 +8 7 11 +7 6 9 +4 6 6 +6 5 7 +19 4 22 +5 4 8 +3 4 5 +10 3 2 +3 2 3 +2 1 4 +@nodes +@edges +@attributes +@end diff -r 049f42e44dee -r fdfa3aa18607 demo/graph_to_eps_demo.cc --- a/demo/graph_to_eps_demo.cc Wed Nov 16 09:11:44 2005 +0000 +++ b/demo/graph_to_eps_demo.cc Wed Nov 16 09:15:41 2005 +0000 @@ -32,6 +32,7 @@ #include #include +#include using namespace std; using namespace lemon; diff -r 049f42e44dee -r fdfa3aa18607 demo/partitions.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/partitions.lgf Wed Nov 16 09:15:41 2005 +0000 @@ -0,0 +1,58 @@ +@nodeset +coordinates_x coordinates_y id +513.857 -446.322 23 +393.468 566.711 22 +869.153 52.8539 21 +596.074 302.442 20 +-82.2171 593.138 19 +-663.61 546.157 18 +-1077.63 161.498 17 +-1177.47 -234.906 16 +-880.898 -528.539 15 +-499.175 -499.175 14 +79.2808 -528.539 13 +637.183 -184.989 12 +205.543 -322.996 11 +399.34 88.0898 10 +-842.726 243.715 9 +-860.344 -29.3633 8 +-211.415 -452.194 7 +-99.8351 99.8351 6 +120.389 -129.198 5 +108.644 334.741 4 +-484.494 328.869 3 +-607.82 -246.651 2 +-274 -131 1 +@undiredgeset + id +12 23 15 +13 23 14 +4 22 23 +20 21 20 +12 21 19 +22 20 22 +22 19 25 +6 19 24 +9 18 28 +16 15 1 +2 14 8 +7 13 13 +11 12 16 +5 10 18 +17 9 5 +17 8 3 +16 8 2 +14 7 10 +3 6 30 +9 6 27 +11 5 17 +7 5 12 +6 4 26 +10 4 21 +18 3 29 +15 2 7 +8 2 6 +5 1 11 +14 1 9 +9 1 4 +@end diff -r 049f42e44dee -r fdfa3aa18607 demo/topology_demo.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/topology_demo.cc Wed Nov 16 09:15:41 2005 +0000 @@ -0,0 +1,192 @@ +/* -*- C++ -*- + * demo/min_route.cc - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 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 +#include +#include +#include +#include + +#include + +#include +#include + +/// \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 std; + + +Color color(bool val) { + return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0); +} + + +void drawConnectedComponents() { + typedef UndirListGraph Graph; + typedef Graph::Node Node; + + Graph graph; + Graph::NodeMap > coords(graph); + + UndirGraphReader("undir_components.lgf", graph). + readNodeMap("coordinates_x", xMap(coords)). + readNodeMap("coordinates_y", yMap(coords)). + run(); + + ColorSet colorSet; + + Graph::NodeMap compMap(graph); + connectedComponents(graph, compMap); + + graphToEps(graph, "connected_components.eps").undir(). + coords(coords).scaleToA4().enableParallel(). + parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). + nodeColors(composeMap(colorSet, compMap)).run(); + + std::cout << "Result: connected_components.eps" << std::endl; +} + +void drawStronglyConnectedComponents() { + typedef ListGraph Graph; + typedef Graph::Node Node; + + Graph graph; + Graph::NodeMap > coords(graph); + + GraphReader("dir_components.lgf", graph). + readNodeMap("coordinates_x", xMap(coords)). + readNodeMap("coordinates_y", yMap(coords)). + run(); + + ColorSet colorSet; + + Graph::NodeMap compMap(graph); + Graph::EdgeMap cutMap(graph); + stronglyConnectedComponents(graph, compMap); + stronglyConnectedCutEdges(graph, cutMap); + + graphToEps(graph, "strongly_connected_components.eps"). + coords(coords).scaleToA4().enableParallel(). + drawArrows().arrowWidth(10.0).arrowLength(10.0). + parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). + nodeColors(composeMap(colorSet, compMap)). + edgeColors(composeMap(functorMap(&color), cutMap)).run(); + + std::cout << "Result: strongly_connected_components.eps" << std::endl; +} + +void drawNodeBiconnectedComponents() { + typedef UndirListGraph Graph; + typedef Graph::Node Node; + typedef Graph::UndirEdge UndirEdge; + + Graph graph; + Graph::NodeMap > coords(graph); + + UndirGraphReader("undir_components.lgf", graph). + readNodeMap("coordinates_x", xMap(coords)). + readNodeMap("coordinates_y", yMap(coords)). + run(); + + ColorSet colorSet; + + Graph::UndirEdgeMap compMap(graph); + Graph::NodeMap cutMap(graph); + biNodeConnectedComponents(graph, compMap); + biNodeConnectedCutNodes(graph, cutMap); + graphToEps(graph, "bi_node_connected_components.eps").undir(). + coords(coords).scaleToA4().enableParallel(). + parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0). + edgeColors(composeMap(colorSet, compMap)). + nodeColors(composeMap(functorMap(&color), cutMap)). + run(); + + std::cout << "Result: bi_node_connected_components.eps" << std::endl; +} + +void drawEdgeBiconnectedComponents() { + typedef UndirListGraph Graph; + typedef Graph::Node Node; + typedef Graph::UndirEdge UndirEdge; + + Graph graph; + Graph::NodeMap > coords(graph); + + UndirGraphReader("undir_components.lgf", graph). + readNodeMap("coordinates_x", xMap(coords)). + readNodeMap("coordinates_y", yMap(coords)). + run(); + + ColorSet colorSet; + + Graph::NodeMap compMap(graph); + Graph::UndirEdgeMap cutMap(graph); + biEdgeConnectedComponents(graph, compMap); + biEdgeConnectedCutEdges(graph, cutMap); + + graphToEps(graph, "bi_edge_connected_components.eps").undir(). + coords(coords).scaleToA4().enableParallel(). + parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). + nodeColors(composeMap(colorSet, compMap)). + edgeColors(composeMap(functorMap(&color), cutMap)).run(); + + std::cout << "Result: bi_edge_connected_components.eps" << std::endl; +} + +void drawBipartitePartitions() { + typedef UndirListGraph Graph; + typedef Graph::Node Node; + typedef Graph::UndirEdge UndirEdge; + + Graph graph; + Graph::NodeMap > coords(graph); + + UndirGraphReader("partitions.lgf", graph). + readNodeMap("coordinates_x", xMap(coords)). + readNodeMap("coordinates_y", yMap(coords)). + run(); + + ColorSet colorSet; + + Graph::NodeMap partMap(graph); + bipartitePartitions(graph, partMap); + + graphToEps(graph, "bipartite_partitions.eps").undir(). + coords(coords).scaleToA4().enableParallel(). + parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). + nodeColors(composeMap(functorMap(&color), partMap)).run(); + + std::cout << "Result: bipartite_partitions.eps" << std::endl; +} + +int main() { + srand(time(0)); + + drawConnectedComponents(); + drawStronglyConnectedComponents(); + drawNodeBiconnectedComponents(); + drawEdgeBiconnectedComponents(); + drawBipartitePartitions(); + return 0; +} diff -r 049f42e44dee -r fdfa3aa18607 demo/undir_components.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/undir_components.lgf Wed Nov 16 09:15:41 2005 +0000 @@ -0,0 +1,103 @@ +@nodeset +coordinates_x coordinates_y id +574.035 177.301 44 +694.579 115.483 43 +280.402 10.3938 42 +212.403 -23.6057 41 +286.584 -48.3327 40 +438.037 -88.514 39 +397.855 -196.694 38 +366.947 -110.15 37 +271.13 -175.058 36 +277.311 -252.33 35 +206.221 -205.967 34 +-840.856 -246.718 18 +-579.033 445.603 17 +-767.847 113.289 16 +906.312 201.403 15 +986.873 -115.807 14 +-470.779 158.605 13 +422.945 521.129 12 +-5.03507 561.41 11 +329.797 314.692 10 +-67.9734 319.727 9 +762.812 -17.6227 8 +526.164 32.7279 7 +730.084 -307.139 6 +415.393 -289.516 5 +-67.9734 -347.42 4 +-309.657 -57.9033 3 +-323.543 -433.964 2 +-539.894 -262.64 1 +-26.6953 -19.9585 19 +116.407 -173.66 20 +201.208 38.3422 21 +-262.548 107.243 22 +-13.4452 133.743 23 +-180.397 245.045 24 +-416.25 345.746 26 +-132.697 451.748 27 +-371.2 568.349 28 +670.264 274.195 29 +588.113 544.499 30 +924.667 409.347 31 +-689.204 -237.261 32 +-567.302 43.6423 33 +@undiredgeset + id +41 42 44 +40 42 43 +37 40 49 +36 40 47 +41 40 42 +38 39 46 +38 37 53 +36 37 48 +39 37 45 +35 36 51 +34 36 50 +34 35 52 +16 17 1 +18 16 2 +14 15 3 +8 15 4 +8 14 5 +17 13 6 +16 13 7 +3 13 8 +11 12 9 +10 12 10 +9 11 11 +9 10 12 +6 8 13 +7 8 14 +5 7 15 +9 7 16 +12 7 17 +5 6 18 +4 5 19 +2 4 20 +1 3 21 +4 3 22 +1 2 23 +22 19 24 +19 20 25 +21 20 26 +19 21 27 +22 23 28 +19 23 29 +22 24 30 +23 24 31 +26 27 32 +24 27 33 +24 27 34 +27 28 35 +26 28 36 +44 29 55 +43 29 54 +29 30 37 +29 31 38 +30 31 39 +32 33 40 +32 33 41 +@end