SES Home » Science Departments » Algebraic Cryptography Center » Software Search |  People Finder

# Software

 The CRAG Software Library FAQ ``` #include "GraphType.h" #include "GraphConcept.h" #include "GraphConceptAlgorithms.h" #include "Word.h" #include "RanlibCPP.h" using namespace Graphs; //---------------------------------------------------------------------------// //----------------------------- graph_example -------------------------------// //---------------------------------------------------------------------------// void graph_example( ) { typedef GraphVertex< GraphEdge > vertex_type; typedef GraphEdge edge_type; typedef GraphConcept< vertex_type , edge_type > pres_type; GraphConcept< vertex_type , edge_type > G; // generate a random graph int N = 16; for( int i=0 ; i<16 ; ++i ) G.newVertex( vertex_type( ) ); float edge_param = 3.0/N; for( int i=0 ; i tree_in = getGeodesicTree_in( G , 0 ); map< int , pres_type::edge_type >::const_iterator t_it = tree_in.begin( ); for( ; t_it!=tree_in.end( ) ; ++t_it ) { cout << " " << (*t_it).first << " -> " << (*t_it).second << endl; } cout << "==========================================" << endl; cout << "Out tree" << endl; // Compute geodesic leaving the vertex n1 and output it map< int , pres_type::edge_type > tree_out = getGeodesicTree_out( G , 0 ); t_it = tree_out.begin( ); for( ; t_it!=tree_out.end( ) ; ++t_it ) { cout << " " << (*t_it).first << " -> " << (*t_it).second << endl; } cout << "==========================================" << endl; cout << "Distances from the vertex" << endl; map< int , int > D = getDistances_out( G , 0 ); map< int , int >::const_iterator D_it = D.begin( ); for( ; D_it!=D.end() ; ++D_it ) cout << (*D_it).first << " -> " << (*D_it).second << endl; cout << "==========================================" << endl; cout << "Distances to the vertex" << endl; D = getDistances_in( G , 0 ); D_it = D.begin( ); for( ; D_it!=D.end() ; ++D_it ) cout << (*D_it).first << " -> " << (*D_it).second << endl; cout << "==========================================" << endl; cout << "Geodesic paths from the vertex" << endl; for( int i=0 ; i > path = readoffGeodesicTree( tree_out , i ); if( !path.first ) { cout << "Distance from " << 0 << " to " << i << " is -1" << endl; } else { cout << "Distance from " << 0 << " to " << i << " is " << path.second.size( ) << ": "; for( list< pres_type::edge_type >::const_iterator p_it=path.second.end() ; p_it!=path.second.begin() ; ) cout << *--p_it << " "; cout << endl; } } cout << "==========================================" << endl; cout << "Geodesic paths to the vertex" << endl; for( int i=0 ; i > path = readoffGeodesicTree( tree_in , i ); if( !path.first ) { cout << "Distance from " << i << " to " << 0 << " is -1" << endl; } else { cout << "Distance from " << i << " to " << 0 << " is " << path.second.size( ) << ": "; for( list< pres_type::edge_type >::const_iterator p_it=path.second.begin() ; p_it!=path.second.end() ; ++p_it ) cout << *p_it << " "; cout << endl; } } } //---------------------------------------------------------------------------// //------------------------- labeled_graph_example ---------------------------// //---------------------------------------------------------------------------// void labeled_graph_example( ) { // typedef IntLabeledEdge edge_type; // typedef GraphVertex< IntLabeledEdge > vertex_type; // typedef GraphConceptRep< vertex_type , edge_type > pres_type; // GraphConcept< vertex_type , edge_type > G; typedef IntLabeledGraph Graph; typedef Graph::edge_type edge_type; typedef Graph::vertex_type vertex_type; Graph G; int N = 16; for( int i=0 ; i tree = getGeodesicTree_in( G , 0 ); map< int , edge_type >::const_iterator t_it = tree.begin( ); for( ; t_it!=tree.end( ) ; ++t_it ) { cout << " " << (*t_it).first << " -> " << (*t_it).second << endl; } cout << "==========================================" << endl; // Compute geodesic leaving the vertex n1 and output it map< int , edge_type > tree_out = getGeodesicTree_out( G , 0 ); t_it = tree_out.begin( ); for( ; t_it!=tree_out.end( ) ; ++t_it ) { cout << " " << (*t_it).first << " -> " << (*t_it).second << endl; } cout << "==========================================" << endl; cout << " Perform Folding:" << endl; set< int > candidates; for( int i=0 ; i > details; fold( G , candidates , &details ); cout << G << endl; cout << "==========================================" << endl; cout << " Perform Unfolding:" << endl; unfold( G , details.begin( ) , details.end( ) ); cout << G << endl; cout << "==========================================" << endl; } void labeled_graph_folding_example( ) { typedef IntLabeledGraph Graph; typedef Graph::edge_type edge_type; typedef Graph::vertex_type vertex_type; Graph G; G.newVertex( vertex_type( ) ); int alphabet = 2; Word u = Word::randomWord( alphabet , 5 ); cout << u << endl; addRay( G , 0 , u.begin() , u.end( ) ); for( int i=0 ; i<15 ; ++i ) { Word w = Word::randomWord( alphabet , 5 ); cout << w << endl; addLoop( G , 0 , w.begin() , w.end( ) ); } cout << G << endl; set< int > candidates; list< FoldDetails< vertex_type , edge_type > > details; candidates.insert( 0 ); fold( G , candidates , &details ); cout << G << endl; cout << " Size of details is " << details.size( ) << endl; pair< bool , list< edge_type > > path = trace_path( G , 0 , u.begin( ) , u.end( ) ); if( !path.first ) { cout << "Error! No path!" << endl; } else { list< edge_type >::const_iterator e_it = path.second.end( ); --e_it; if( (*e_it).theTarget!=0 ) { cout << "Error! Path is not a loop" << endl; } else { cout << "Loop found" << endl; liftup( G , 0 , path.second , details.begin( ) , details.end( ) ); cout << "Path length = " << path.second.size( ) << endl; list< edge_type >::const_iterator p_it = path.second.begin( ); for( ; p_it!=path.second.end( ) ; ++p_it ) cout << *p_it << " "; cout << endl; } } } //---------------------------------------------------------------------------// //--------------------------------- main ------------------------------------// //---------------------------------------------------------------------------// int main( ) { // graph_example( ); // labeled_graph_example( ); labeled_graph_folding_example( ); return 0; } ```

 Stevens Institute of Technology • Hoboken, NJ • (201) 216-5000   Sitemap