Math/test/testGraph.cpp

0001 #include "DataFormats/Math/interface/Graph.h"
0002 #include "DataFormats/Math/interface/GraphWalker.h"
0003 #include "DataFormats/Math/interface/GraphUtil.h"
0004
0005 #include <iostream>
0006 #include <string>
0007
0008 using namespace std;
0009
0010 using graph_type = math::Graph<string, string>;
0011 using walker_type = math::GraphWalker<string, string>;
0012
0013 void build_graph(graph_type& g) {
0014   /*
0015
0016        A     B
0017       //\    |
0018       C  D   E
0019       \ /
0020        G F
0021        |/
0022        H
0023  edge direction is from top to down, e.g. from D to G
0024  edge-names e.g.:  B-E: e1
0025                    F-H: h1
0026
0027  The graph has 3 possible roots: A, B, F
0028 */
0029
0030   g.addEdge("B", "E", "e1");
0031   g.addEdge("G", "H", "h1");
0032   g.addEdge("A", "C", "c1");
0033   g.addEdge("D", "G", "g1");
0034   g.addEdge("A", "C", "c2");
0035   g.addEdge("C", "G", "g1");
0036   g.addEdge("F", "H", "f1");
0037   g.addEdge("A", "D", "d1");
0038 }
0039
0040 void build_graph2(graph_type& g) {
0041   /*
0042        AA
0043       /  \     EE
0044      BB  CC   / \
0045      \\  /   FF GG
0046        DD
0047   */
0048
0049   g.addEdge("AA", "BB", "bb1");
0050   g.addEdge("AA", "CC", "cc1");
0051   g.addEdge("BB", "DD", "dd1");
0052   g.addEdge("BB", "DD", "dd2");
0053   g.addEdge("CC", "DD", "dd3");
0054   g.addEdge("EE", "FF", "ff1");
0055   g.addEdge("EE", "GG", "gg2");
0056 }
0057
0058 /* invert the graph of build_graph2():
0059
0060       DD
0061     //  \     FF  GG
0062     BB  CC     \ /
0063      \ /        EE
0064       A
0065 */
0066 void build_graph3(const graph_type& input, graph_type& output) { input.invert(output); }
0067
0068 void list_roots(const graph_type& g, ostream& os) {
0069   graph_type::edge_list roots;
0070   g.findRoots(roots);
0071   while (roots.size()) {
0072     os << g.nodeData(roots.back().first) << ' ';
0073     roots.pop_back();
0074   }
0075 }
0076
0077 void serialize(const graph_type& g, const string& root, ostream& os) {
0078   walker_type w(g, root);
0079   bool go = true;
0080   while (go) {
0081     os << w.current().first << ' ';
0082     go = w.next();
0083   }
0084 }
0085 void serialize(const graph_type& g, ostream& os) {
0086   walker_type w(g);
0087   bool go = true;
0088   while (go) {
0089     os << w.current().first << ' ';
0090     go = w.next();
0091   }
0092 }
0093
0094 void dfs_bfs(const graph_type& g, const string& root, ostream& os) {
0095   walker_type w1(g, root);
0096   walker_type w2(g, root);
0097
0098   bool doit = true;
0099   os << "bfs iteration:" << endl;
0100   while (doit) {
0101     os << w2.current_bfs().first << ' ';
0102     doit = w2.next_bfs();
0103   }
0104   os << endl;
0105   doit = true;
0106   os << "dfs iteration:" << endl;
0107   while (doit) {
0108     os << w2.current().first << ' ';
0109     doit = w2.next();
0110   }
0111   os << endl;
0112 }
0113
0114 int main() {
0115   ostream& os = cout;
0116
0117   graph_type g1;
0118   build_graph(g1);
0119   dfs_bfs(g1, "A", os);
0120
0121   os << "roots of the graph are: ";
0122   list_roots(g1, os);
0123   os << endl;
0124
0125   os << "tree serialization: ";
0126   serialize(g1, "A", os);
0127   os << "tree hierarchy: " << endl;
0128   graph_tree_output(g1, string("A"), os);
0129
0130   os << "exchanging node C through node Y." << endl;
0131   unsigned int idx = g1.replace("C", "Y");
0132   os << idx << endl;
0133   graph_tree_output(g1, string("A"), os);
0134
0135   os << "replacing edge h1 with exchanged_h1 " << endl;
0136   g1.replaceEdge("h1", "exchanged_h1");
0137   graph_tree_output(g1, string("A"), os);
0138
0139   graph_type g2;
0140   build_graph2(g2);
0141   os << "second graph:" << endl;
0142   serialize(g2, "AA", os);
0143
0144   os << endl << "combining g1 and g2:" << endl;
0145   os << "g1: ";
0146   serialize(g1, "A", os);
0147   os << endl;
0148   os << "g2: ";
0149   serialize(g2, "AA", os);
0150   os << endl;
0151   graph_type g3;
0152   graph_combine<string, string>(g1, g2, "A", "AA", "NewRoot", g3);
0153   os << "g3: ";
0154   serialize(g3, "NewRoot", os);
0155   os << endl;
0156   graph_tree_output(g3, string("NewRoot"), os);
0157
0158   os << endl << "inverting g2:" << endl;
0159   graph_type g4;
0160   g2.invert(g4);
0161   graph_tree_output(g4, string("DD"), os);
0162   graph_tree_output(g4, string("FF"), os);
0163   graph_tree_output(g4, string("GG"), os);
0164
0165   os << endl << "graph-iterator test: loop over g1" << endl;
0166   graph_type gg1;
0167   build_graph(gg1);
0168   graph_type::const_iterator it(gg1.begin_iter());
0169   graph_type::const_iterator ed(gg1.end_iter());
0170   for (; it != ed; ++it) {
0171     cout << "looping! from=" << (*it).from() << " to=" << flush;
0172     cout << (*it).to() << " edge=" << flush;
0173     cout << it->edge() << endl;
0174   }
0175
0176   return 0;
0177 }