### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 661 Class Note for PHYS 597A with Professor Albert at PSU

### View Full Document

## 28

## 0

## Popular in Course

## Popular in Department

This 39 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 28 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 661 Class Note for PHYS 597A with Professor Albert at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Graph Processing Istv n Albert Bioinformatics Consulting Center Huck Institute for Life Sciences Part 1 Representations and Algorithms Graph Processing Compute some static value of the graph degree distribution clustering coef cient Identify some subset of edges or vertices shortest path spanning tree connected components Not easy to write The Challenge of Binary Search it took more than 10 years to publish the rst correct binary search Graph algorithms are dif cult to test for correctness The Big Oh Represents the complexity of a worst case analysis Common complexities Ol Olog N ON NOlog N ONA2 It is about growth not ef ciency Graph algorithms can be hard Some are NP Hard proved to have no ef cient solutions more than ONk k constant Traveling salesman ON 15510 billion Many others are unknown Luckily the problems can often be greatly simpli ed a bridge is an edge that if removed an articulation point is a vertex that if removed would separate a connected graph into at least two disjoint subgraphs no bridges edge connected biconnected gt no articulation points Representations V number of vertices nodes E number of edges Edge array size E Adj aeeney matrix Size V V Adjaceney lists size V E Real representations are often more complicated Adj acency matrix 91 9h Adj acency List 9 5 elngeuagc becacab ab Cd er I gun Representation properties V number of vertices E number of edges matrix list edge array space V2 VE E nd edge 1 V E insert edge 1 1 1 path v to w V2 VE E lgV Important details Directional or undirectional Cyclic or acyclic Self loops Parallel edges Node or edge removal hiding Optimize the data structure for the task Graph Processing Problems Traversal shortest paths longest paths Simple and strong connectivity Subgraphs cliques Planarity no edge crossing Isomorphism Graph drawing 007621435 Post 123456700 Pre adeefgh m n e V Properties of DFS trees for a link going from v to w edges corresponding to recursive calls tree edges tree link ifw has not been visited parent link if during the traversal we went from v to w edges connecting a vertex with an ancestor that is not a parent back link if prew lt pre V down link if prew gt pre 007654321 Post 123456700 Pre abegChdf m n e V Properties of BFS traversal Corresponds to shortest path hops if the edges have equal weight DFS wends it way through the graph BFS sweeps through the graph but the only difference between them is in the data structure that holds the nodes Stack vs Queue Application Example Strong components nd the largest group of mutually reachable nodes brute force check every pair VA2 clever methods linear time V Kosaraju algorithm Run the depth first search on its reverse and compute the postorder numbering Then run the search again but this time visit the highest post ordered verticesfirst Shortest Paths Weight for every edge cost distance time nonnegative and negative weights single source allpairs shortest paths Concept relaxation at each step check Whether the path is shorter than the paths seen so far Dijikstra s algorithm OElgV or OVlgV Los Angeles 1500 In class exercise 1 List the nodes in a bfs order starting from Dallas node hop distance 2 Find the cheapest route from Dallas to Chicago Other graph concepts Biconnectivity every pair of edges is connected by two disjoint paths Spanning trees the tree that can reach all vertices Topological sorting DAG relabel vertices so that every edge points from a lower number to a higher one Strong components each pair of nodes is reachable from both ends Books Graph Algorithms by Robert Sedgevick many code examples C C Java LEDA A Platform for Combinatorial and Geometric Computing by Kurt Mehlhorn and Stefan Naher Algorithms I N A Free Resource Data Structures and Algorithms with ObjectOriented Design Patterns Python Java C and C I by Bruno R Preiss webbook with source code httpwwwbrpreisscombooksopus7 Part 2 Software Tools Classi cation GUI programs Paj ek SpectraNET yED 0 Command line programs graphviz R Libraries LEDA boost pygraphlib Input Ouput Input mouseclicks or certain le formats Output image les or les in certain formats Focus Visualization display or graph algorithms Most le formats are should be text GraphML Pajek DOT LEDA Potential standard The GraphML File Format About Download Specl ca on What is GraphML GraphML is a comprehensive and easyrtoruse le format for graphs it consists of a language core to describe the structural properties of a graph and a exible extension mechanism to add app ca nnrsped c data lts main features include suppon of GXL r anmbased graph exchange tonnat developed for sottware reengineer39mg Mra delyused graph exehange torrnat 110mm directed undirected and mixed graphs hypergraphs hierarchical graphs graphical representations references to external data app ca ourspem c attribute data and lightweight parsers Unlike many other le faunas for graphs GraphML does not use a custom syntax instead it is based on m and hence ideally suited as a common denominator for all kinds of services generating archiving or processing graphs Getting Started Aneasy introduction to GraphML is the Graphlul Pn39mer GraphML primer is a nonrnnrma ve document intended to XGMZML a an mbased le funnat fur graphs based on GNEL SVGV mmbased grapbi es tormat Graph Bran 5 W home orgraph dranrng GDzuusrxgth lntl Symp Graph Drawing i244 Sep 2005 Limerick lreland o3 August 100 LEDA extension package for GraphML release candidate nonoload GraphML Primer released is March 2003 mL Sehenia speci cation and documentation available for GraphML Lure release randidate GraphML presentation at the annual meeting ufDFG Research Priority ms v ies extension GraphML example ltxml versionquot10quot encodingquotUTF8quotgt ltgraphmlgt ltgraph idquotGquot edgedefautquotundirectedquotgt ltnode idquotnOquotgt ltnode idquotn1quotgt ltnode idquotn2quotgt ltnode idquotn3quotgt ltedge sourcequotn0quot targetquotn2quotgt ltedge sourcequotn1quot targetquotn2quotgt ltedge sourcequotn2quot targetquotn3quotgt ltgraphgt ltgraphmlgt GraphViz command line graph Visualizer the language that it understands is called dot quot3 1 Graphviz Graph Visualization Software ha Graph Visualization Mammal isr L me Graph usuallzan39en is away ufrepresen ng structural information as diagams pr abskact graphs and networks Anlnmann graph drawing Ramses has many important apph39eanens n software enaaneenng database and web nesrgn nemprlnng and lnwsual mtafncesfor many other 7 domams Credits Graphnz is open snarne graphn39snahzannn so ware It has several mam graph layout pmng See the aallerv for same sample layouts It also has web and intnacdwe grapheal rnlerfanes and almllary tools hhranes and language bindings The Mac os x edlhon of Cyragl39mz by Glen Law won two 2004 Apple Daily Awards Pajek windows program httpvladofmfum sipubnetworkspaj ek Aglzl W M NH 5mm leunn mm Permumiun Fernum uns mm Hmmrmw Vemr anrs mans Draw Mm m Tank New 5mm vaurk r m Equot M WWW J 7 Bmkevage Wes Mm E E a Newm d 7 Transan gt lemyamezwuyk b MW gt E H a CnuntNengbnurCo n39s r Summ nngEghhcurs gt v W n mum r wn nFnghbuurs r 7 7 7 7 7 We mp HEquot M Emma W lv 7 WW M M E gquot Funmnawcumpusmun r mm r v 7 Ewand Pamaun b Venn Evand nemmm F mm Rr nePamun b yED yFIIeS yED editor is free but yFiles costs 553555 the best graph layout you ll ever see Q About yFIles Hume s arseoes gt Anuuk vFllaS What Is yFiles mm quotmquot 39 YFlles ls an extenslve JavaTM class llorarv tnat Dmvldes algorltnms and components fur analyzlrlg vlewmg and drawlrlg graons dlagrams and networks The current lFlles verslon ls 23 Refer to the release notes to learn more abouttecnnlcal reuulrements and feature enllancements Benefits Home VPTOdU S vFlles orolIldes essentlal odlldlng blocks for Java aoollcatlons tnat need to analyze Demos Ilsuallze edlt or autumatlcallv draw graons dlagrams or networks Anvune wno needs Dacumenrsnm such components as part uf nlsner own aoollcatlon shuuld unslder uslrlg yFlles Gallery Versatlllty ls one of tne maln features of YFlles Our custamers came frum dlverse V YFlles aoollaatlon areas such as svslostlan Fade olocnemlcal network analvsls and Ilsuallzatlun buslness Drucess modellng news was data mlrllrlg eg log le analvsls database management and modellng Fn network management uraenng suclal networks software englneerlng eg UML dlagrammlng wurk uw management www Ilsuallzatlun lgt yFllesExtel lslul ls lgt yFllesNEl LEDA Libray of efficient data types written in C 150 for the academic license You can buy the Leda Guide from Amazon also available free on the web High performance professional product covers much more than just graphs So abstract that it feels like a high level programming language LEDA example include ltLEDAIgraphhgt include ltLEDAIbasicgraphaghgt using namespace leda int main graph G istltnodegt dfsres node n0 Gnewnode Gnewedge n0n1 dfsres DFS G n0 n5 forall node dfsres Gprintnodenode NetworkX Python graph library httpsnetw0rkx1anlg0v from networkx import Graph G GraphC Gaddedge12 Gaddedge23 print Gnodes 1 2 3 4 5 6 for v in Gnodes print v Gdegreev base 1ae dame for graph and atgraph centrality Centraztty rneaure on ones CIzqmz e Find and rnantpuzate ehoue ofgraph cluster Cornpute cItutermg eoemetent and trawxmvlty ofgraph mat and rnontpuzate the k arex afa graph oreutnq a layout Layout pomtonltg a1gortthrnfor graph drawmg o nx pydot Import and exportnetwarla network to aot format utngpyozot o nx Vt Draw netwth In ad wzrh vtk generators A paolmgefor generattng vurmm graph In networot o atlas Generator for the may graph min oteeete Generator for orne 51mm graph oeor sq Generate graph wtth a given degree equenoe oeomeerte Generator for geornetrto graph random graphs Generator for random graph small Ianou rna11anaz narnea graph together wzth orne oornpaet generator hybr o Hybrm end and wrtte graph and network Eonorpa Fast ahechrng to ee fgraphx are not tornorphtc Ue mway tnterfaae to Judy a mm zrlymg 11am Irring operator Operatton on graph tnozuatng wmm oornpzernent uograph om Shortetpath atarneter ranqu eccenmczty and related rnethoa queue Helper queuEJbr ue m graph xenrchw release39 Releae dutufar NerwarkX Search Search algorzrhmx hortetpath panntng tree eta Search class Graph earah c1ae spectrum Laplaotan udncency mnmz um peoman ofgraph judybas

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.