PDF Publication Title:
Text from PDF Page: 142
122 6 ⋅ software 6.3.1 The Boost graph library (BGL) The Boost graph library or BGL [Siek et al., 2001] is a large set of C++ codes that implement generic graph algorithms. The advantage of these generic graph algorithms is that they specify the algorithm independently of the data structure. This independence is not accomplished using interfaces or ab- stract classes, which are common in standard object oriented programming. Instead, the Boost graph library uses C++ templates and techniques from generic programming [Alexandrescu, 2001] to write their data-structure-free algorithms. These techniques, in theory, allows the compiler to view the algo- rithm and data structure simultaneously and optimize the entire package. In particular, the compiler can generate in-line optimizations between function calls. In the Boost graph library, each algorithm places certain requirements on the C++ graph type. Concepts codify these requirements. In the BGL, the concepts largely express mutability (support for changing the graph during the algorithm) and access (support for querying the existing graph structure in various ways). Most of the algorithms wrapped in MatlabBGL do not change the graph; thus we focus on the access concepts. For example, the strong_components BGL function requires a graph type that supports the VertexListGraph and IncidenceGraph concepts. These con- cepts allow the algorithm to iterate over all vertices in the graph and access the out-edges for an arbitrary vertex. This access to the graph suffices to implement Tarjan’s algorithm for strongly connected components [Tarjan, 1972]. The other access concepts are EdgeListGraph BidirectionalGraph AdjacencyGraph iterate over the edges of the graph access in-edges to an arbitrary vertex, and access adjacent (out-edge connected) ver- tices to an arbitrary vertex. Most algorithms are like strong_components and require only the VertexList- Graph and IncidenceGraph concepts. Two notable exceptions are maximum flow (push_relabel_max_flow, kolmogorov_max_flow), and planar graph triangulation (make_maximal_planar). In this document, we focus on the common cases and leave the exceptions to the source code documentation and help files of MatlabBGL. 6.3.2 Matlab and Boost graph library interface Before describing the interface, we reiterate one main point of MatlabBGL. To integrate cleanly with Matlab, MatlabBGL uses the Matlab sparse matrix type as the graph type. Thus, the goal of the interface between Matlab and the Boost graph library is to take a Matlab sparse matrix data structure and view it as a C++ type that implements the VertexListGraph and IncidenceGraph concepts. (Our actual implementation also supports the EdgeListGraph and AdjacencyGraph concepts.) With such an interface, we can access the majority of graph analysis algorithms in the Boost graph library. What is lost from thePDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)