### Create a StudySoup account

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

Already have a StudySoup account? Login here

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

### View Full Document

## 43

## 0

## Popular in Course

## Popular in Department

This 48 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 43 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 654 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 ISTVAN ALBERT BIOINFORMATICS CENTER HUCK INSTITUTES FOR THE LIFE SCIENCES SPRING 2009 Covering introductory concepts 0 Graph Representations Graph Algorithms Software Tools for Visualization From the Graph Atlas Tables 0 graph numbers smmnwmmn1zzs n mm 1 2 z 3 s a s m 7 ma m y 2 mu m m mac n m w n m sum 71592 1 m m m u 29 asus m w is mm mm vow um 15 m was ms w m 7 u m mm m um mm a mm m 5m W M m w m mm mm W mm 7qu mm m mwlnmwwssmwmmm 1 am m nu ma 19m 153755113mm m a m m m m m 5171 m m m m z 5599 14939 599 ms 9515 Wu um mu m use mm 2 m mm W m m m m m m m m m 3 mm m ms ma 15154 as m was 92m mm m m mu Typical Graph Processing Problems Ra 0 Compute some static value of the graph degree distribution clustering coefficient 0 Identify some subset of edges or vertices shortest path spanning tree connected components Implementation more difficult than it seems 0 The Challenge of Binary Search it took more than 10 years to publish the first correct binary search 0 Graph algorithms are notoriously difficult to test for correctness The Big Oh Represents the complexity of a worst case analysis Common complexities N number of elements 01 Olog N ON ONlog N ONA2 It is about growth not efficiency Travelling alesman m y Q lg Given a list of cities and their pair Wise distances find a shortest possible tour that Visits each city exactly once Clearly a network problem One of the most intensively studied problems in optimization Graph algoriths can be hard Some are NP Hard proven to have no efficient solutions better than ONk k constant Traveling salesman ON 15 5 10 billion Many others are unknown Luckily problems can often be greatly simplified a bridge is an edge that if removed would separate a connected graph into at least two disjoint subgraphs I 5 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 no articulation points Representations V number of vertices nodes E number of edges Edge array size E Adjacency matrix size V V Adjacency lists size V E pure representations O Adj acency matrix g1 Adjacency List g I Eh geua 9C 0 Cb C a C 30 ab Cd erT 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 0 Cyclic or acyclic 0 Self loops 0 Parallel edges 0 Node or edge removal hiding Surprising number of tools do not fully support all these features Optimize the data structure for the task Graph Processing Problems 0 Traversal shortest paths longest paths Simple and strong connectivity Subgraphs cliques Planarity no edge crossing Isomorphism Graph drawing We often need more than what the pure implementation offers Which two graphs are identical Graph traversal exploring a maze Q R00mvertices edgescor1id0rs O For substantialli more details see SediwickGraih Alion39chms Following one particular traversal O Vertex Pre Post a 1 8 b 2 c 3 5 rd 4 2 e 5 1 f 6 4 g 7 3 h 8 6 Glossary for DFS trees 6 edges corresponding to recursive calls tree edges 0 tree link if w has not been visited 0 parent link if during the traversal we went from v to w o edges connecting a vertex with an ancestor that is not a parent 0 back link if pre w lt prev 0 down link if prew gt prev Back to our maze make different choices An alternative type of traversal O Vertex Pre Post a 1 8 b 2 7 e 3 6 g 4 5 c 5 3 h 6 4 d 7 2 f 8 1 Properties ofVBFS traversal kg 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 LIFO Queue FIFO Algorithm Example Strong components find 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 post order numbering Then run the search again but this time visit the highest post ordered vertices first Shortest Paths Ricst Weight for every edge cost distance time non negative and negative weights single source all pairs shortest paths Relaxation at each step check whether the path is shorter than the paths seen so far Optimal substructure sub paths are also shortest paths dynamic programming Dijkstra s algorithm OElgV or OVlgV Other type traversals 0 Various heuristics to choose from the seen nodes 0 Random traversal o A star A search algorithm path finding in games Earth Mass Med1ab In class exercise WW 0 mmmmmmmmmmmmmmm m 1 List the nodes in a bfs order starting from Dallas node hop distance 1500 2 Find the cheapest route from Dallas to Chicago Same task Wlth the python networkx 11brary m saga Lu Angela L50 rhirngn Ban rranriltrn 700 Dallas Mlan1 100 Danaa chum 350 V quotquot Darrow Chlcagcl 50 39 39 39 quotquotquot quotquot quotquotquotquot 39 m Angcm untrult L50 L05 Angee Dallas 150 New Vnrk sm Datum so chlc aa zoo mum 100 San rrancisco Lu Angeles so v import netwurkx aa nx def read datafname39 ea grape Erma ar egelia graph nxVDiEzaphO fer line in EfnamE head tail cast 1inasplit39 graphaddiedge head tail flea return graph 1 grap A graph e readidata 39cit adar print nx shortestjath graph 39pauaa39 argelee39 print udijkstzaathgraph Eallas39 aa ngeles39 quot 39Dallas39 39Chicago39 Los Angeles39 Dallaa Detrn r39 39Ch Gaga Documentation httpnetworkxlanlg0v O NetworkX mmrkxnume Search Dwnluld un4uper5m Bummenmrim R femne prtvlnus nut mmnes mde Algorithms naumm nemrkxubelmmcmpmewrs may Cllgge mg a we Algrmmm mm a m nenu 7 M n usanzz 0m 0 Search Nemrkx New surm Downlnau Dlvekversmz Documenmnm Miekmnm prtvmus next masuks Index upmghrzul s AH H gbyg Lasnmdali an MN m was reate usmgsumm us Another networkx example O we cf randcm grapns unpnrt netwcrkx ee nx e few a a gene at nxerdnairenyiigraph1 100 01 nxwatta atrngatz graph 1 mo 10 02 17xbazabas 731hertigraph1 mo 2 nem m a 115 er Ha be 1 a grln Varlnua netwcrk measuris fur graph m allgen avg nxclusteraverage cluaterlng1 graph diam nxdi3tancedlamet3r1 graph eem 11xcentralltybetweenness centrality1graph print g 4 ECenra 39 s 1an diam cent e 2 Dlameex Betweeness Centrality ac on ofnumber o f shortest pa ms am pass mmugh each not 5 vFOJlD nieueeeeca ECentralO 0015015371533121305 1 00035172733050537005 cogs D111eteF BCentra c 0037242545115432597 00233045333351741 vFOJLS DianeteF ECentra 0 01753592133217217 1 00 2 02535557752701 Other graph concepts Q BiconnectiVity every pair of edges is connected by two dISJOlIlt paths 0 Spanning trees the tree that can reach all vertices Topological sorting DAG relabel vertices so that every edge p01nts from a lower number to a higher one 0 Strong components each pair of nodes is reachable from both ends Graph processing software tools Homework Use a software tool to draw analyze a graph Submit your results and some commentary Categories 56 lt 0 GUI programs Pajek yED iSee 0 Command line programs graphViz R 0 Software Libraries LEDA boost networkx Input Ouput Input user input mouse clicks or files Output images or data files Focus Visualization display or graph algorithms Most file formats are text graph formats Standardized GML GraphML Home grown DOT LEDA Pajek Potential standard The GraphML File Format Download SpeLL ca on About What is GraphML GXLranmbased gt 39 V V LEDA extension i GraphML is a comprehelJSJVe and 535 atoause le format for PP hangmma graphs It consists of a language eore to describe the structural WWWquot Wm developed for software relwecandldate properties of a graph and a exible extension meehanism to reengineerrng Download add apphcaunnaspem c data Its mam features inelude am a a ider used PM of graph exehange format tummy directed undirected and mixed graphs ff m hypergraphs we XGmnsaz hierarchical graphs Kimbashei eeffmaf graphical representations Eadie d Era 5 as on reterenees to external data 5 can 5 Gm E m b d d documenta un app campuaspe 9 arm ute ata an ame for Gmth SVGranXMIrbased ghtquotth Parsers Lurc ek ase graphics umlat tandidate Unhke many other le faunas for graphs GraphML does not Gap D 5 nse a eastern syntax lnstead it is hased on XllnT and henee my Newman ideally sulted as a common denominator for all lands of le mm mm E SE 3 Es g semees generating arehmng or proeessing graphs an Reggae home ufglaph dranrng Priority ms GEM mg m Gettl ng Sta rted Symp Graph Dram39ng 2166p 20051 Aneasy introduction to GraphML is the GraphML Primer Wench Ireland GraphML Primer is a nonanorma ve document intended to vFiIes extension GraphML example 0 lt7me versmnquot1n encudmgsmpsquot gt 7 ltgraphn gt 7 ltgraph edgedefau t undirecledB modem Delroil gt ltnude d ChicagD gt made d New York gt ltnude d Miamiquot gt ltedgesuurc quot elroil targe Chicagoquotgt ltedge suurc elmilquot targe amiquotgt ltedge suurc iamiquot target New Yorkquot gt ltgraphgt dgraphmb GraphML an XML is a markup language smudardizationat the cost ofmaking life a whole lot more complicated Q GraphViz command line graph Visualizer a the language itself is called dot About Download 551 Documentation M g a m ist License Graph Visualization Resources xedns damams Graph summon rs away ufrepresen ng saurmrai infumadun as diagams of abskact graphs and networks Automanc graph drawing has many important applicath m software enameemg database and web deser networking and mvisual mtafncesfm many other Graphnz is open smrre graphn39suamapprr so ware It has several mam graph layaut pmng See me gallerv far same sample laymuts It also has web and interac we gaphmal rmafares and armimry tomls hbmnes and language brndmgs The Mac as x edth pr Cyraghviz by Glen Law Von two 2004 Apple Desrpr Awards digraph warld 123quot77quot raniFsamE raniFsamE IanFsalne IanFsalne IanFsalne IanFsalne IanFsalne IanFsalne IanFsalue 2 7gt 43 m 7gt 4 n 31 7gt n 31 7gt 32 5 TE 43 2s a 35 4a 23 2a 42 22 3 33 4 31 34 22 42 27 s 22 32 2a 524 s 35 T24 Tl 1 35 623 7gt 151721 a 1421 3 12 37 35 m 2 Graphviz example 530 ram gt 27 2 m 19 39 4 15 2s 2m 25 ng windows program google the name F M NH smug PIrWnn Pardtun Pemumiun Femumdnni mum Hmva Vemr Mars mans rm Mam In Yank Newk 5mm NlMurk y m Equot M avan umNEMurk gt j 7 Bmk vage Ru es pmmm mmmuamy p E Equot g Newark39vzmr j 7 Transfum gt lemv Imelwmk gt P mmuquot Rennie gt Hamnmmm gt m Equot a CnuntNengnan n39s r summ nngeghbcws r v AAAA 7 mm r WnnFNelyhbuurs r OWE Blhnn gt mm m Equot M B ndamdehng gt mums amt v 7 smemsmm Putmnrdnam gt A 7 H EWW Parmuh un r um n mum m E gquot Funmnnmtumpnsmnn r mm r v 7 auandpamaun gt Venn Evandkamdim 1 1mm Fun gt Mnevamun gt yED yFiles yED editor is free ut yFile s costs httpwwwyworksc0m j WbI kS About yFI es Name gt Dreams a Abnuk VFHE Evaluate Now 31 What is yFiles YFHes rs an extenswe JavaTM ctass horarv that provrdes a qunthms and components for ana yzmg viewrng and drawmg graphs dradrams and networks The current YF es versmn rs 23 Refer to the refease notes to earn more abouttechnrca redutrements and feature enhancements Benefits YFnes medes essenna buhdmg mocks for Java apphcatmns that need to ana vzer wsuahze edrt or automatrcawy draw graphs dradrams or networks Anvune who needs unaumantanan such components as Dan ofhrsher own apphcatmn shumd consrder usmg vFHes Canary Versatmty rs one of the marn features of yFHes our customers come from drverse V YF eg auuhca un areas such as soaroaaan gnaw orochemrdar network anarysrs and vfsoahzatron busmess process mudehng mm was data mWHg ed ug me ana vsws database management and mudehnq network management suma networks 397 YFHe5 Extensmns software engrneennd e th diagrammrnd lgt yFHes wurk uw management Drdenng yED Excellent Layout 00000000000000 We de2 View Laynut Tao Gmupmg Wmduw He p a Hemehea 5 i DWHLN WW Q QIEHROH W Enema gt a 55555555 555st 55555555 E M ngana thanne Emsml 1 mm Amsmmt a 0 SW Pre edmg equot 1 Tvee NUSWIN DbeyNudeSues 1 Fam yTvee 555 M55555 an m M mma Nudersmn R d 5555 N55eE55e a Labehng CWPWESS ampanents 355mm 5e55e55555e5 55ee55e5 v epeeeehzumen H 5555m 2105555 5 5 5 5 5 5555 e 5 1 i 15 n 5 13 rw Sha e v a General Text 13 x 239 71553535 v 2m a Math so a Hem so a nu 55 I mamas nu 55 z Erma me 55 I mummy uneTWe 7 Transparent D a me me Eafkgmund Burder war I mummy P amment Intema Center Sue mcmenc Cnn guraoun 5555555 Ahgnment Cent r may new meme 13 5555555 Ang e a n a um um Desmvoan a Shall Shave Redang e DraD 555555 c 555mm 515555555 Sha a Vemm 55555 a Cytoscape biology oriented Cytoscape onnne Tulmiak Get smmed wmn the expanded Lvmseepe nnhne tutunals E ght tutunals esmbe Mosque ham base operatmn m de ed vmgn Ovemnun DDwnload qmsmpe ann oad Vavsmn 251 H439 e a e Hum e Dnum rn Reqmres Java SE 5 Dr Java SE 5 mm gtn winallzlnaun my ann Inter317W 1 rm We n e man mvk 39 2 1 mass Notes Download cytoscape u 16R 1Juse meter Manual HTML fumal or PDF furmat exDTams 2H basw featmes of Gltosmve Get Aenmat veader Cytoscape 261 me e a mnomugenx reJeaee that snumd work wen an 26u p ugms There ave rm AP enangee however we have added a new entrahzed oggng fauvty See Helv39gtError Comlemsee LYtosmpe ssmrtup mesrageszmi any warmngs m enursthatozcurdunng upeyenun seme Bugs me have been xed ndude Tupmwgy kerverfarmnze XGMMUnamng unsmeniy Mae usahnmy ssues Updated 4112008 New features mdude Web Service chem Manager a Semessaeeeesm Pathway Commons 1mm and NCBI Getting Help Need he v gem semen mm Cvms ve7Emad bur neweek nenng hst qmeepenewweek Suhsmbe IBmwse Avmwes wtoscape Annoulmemems Cymap pmgrammmg mm Navzmber 19 2mm mavervune We ve auhng reren alv lenuad Java anvammer m wmk m we cymmpe amen ate ucsu 1r ynu le meveecedp1eeee ewyneye mk manksMkE mm mas 10 M Dumam raph mm vazmber171m8 DamavaEW demnpeeee Wmem nmman nemns mm memnaenymg uenenmceremne Gmenetwmks anhehaded m wsuahze meeneeaed Dmtemsand mew dumam mnpoemens Addmuna w Dumaanva Wm Mathematica arsssrs mummy Each new gt Esmr Each rh r Mimsmiu gt Mimsmiua m map Mllhsmurm m rrshsren gt humazwsgt aea usr menu rhuhrrura Canmtmcvsgt E rm gt woman mrhm az7 Mimimm Cnnmculms gt Lanamle gt Pij kstra39s Algorith m merwnwam Wen names w mmth Ah argurnhm rurhhmrrg a graph geodesrc r e Ihe shunes Dam belween MU graph vemces m a graph u mndmns by cunstmdmg ashunes rnalh tree rmrmhe rhmar venexm every mhervenex m we graph The argurrmm rs rmprememea as mm Lu m we Mathemahca package camemacmeaw The Wursrrease Whgrrme farms Duksua argurrhm an a graph wrm nodes andquot edges rs 0 quot1 because rtaHuwsVurmrecledcyde5 teven ndsmeshunss pamslmmasuurcenudenuaHmher nudes mme graph Tms rs DasrcaHyO rlherme seem andapnylurms ance urinates whhe 0 rs the bes pussrpre sumprexrcyrnr dense graphs the sumprexrcy can pe rmpruveasrghrheahuymr sparse graphs Wrm sham mudmca mns nuksuas argerhhm can pe used as a reverse argumhm that marmarhs mrhrmum spanmng rees39 rmesmknude Wrmmnhermudmcauun Moan beenendemu peeume prmremruhar ThebnmeneckmDukstra39sa gunmmrsnudese edmn HuweVEI usmgDraVsmp ementa mm hrscan pe srghmeamry rmpruvearursparse graphs rrr me Seasun 3 eprsune 39Mphey Fur Nummg39 2mm unhe erewsruh errme drama NUMBSRS mamemaucs pruressur charhe Eppes uses Duksua s argumhm m hhmhe musurkery eseape rumes um quusAngeresVurahuackedtmckma rs earryrhg mrurohs ufduHars m cash and memear supphes and arsumxrahapprhgmrms smuso rwarrs Shunes Pam BeHmzanurdA gamhm meWavsth Mganmm Graph Gendes c Reacmng Ngunmm Shunest Pam Prnmem Python NetworkX NetworkX NE WNK H IM 323v l VWHICVRK DEVEIUUP Suel DAKHHVF HMIGquot gt9 modules Ild nus dotomemaoon IX currenty llelrlg updated for release 099 afNelwakx ms update mtludes slgm tam fungal to he HildeMug Clapl and 171mm nbjenx to refen ourmlllmo use ease ofwelghmdgla hx and m Improve llen orma ce see the AP hands for denslea lrlformanorl CH Newarkx from 1 mmquot current version 099 Patkage mdzx or Install lt High productivity software for complex networks wn NetworkX IS a Python package for me treauon easyiinstal netmrkx manlpulatlon and Study ofthe sttueture dynamus and funlIlans ofmmplex networks lolnthe coogle 9mm Quick Example youiemall gtgtgt impon nemarkx as nx xoraphl gtgtgt addiedge12 gtgtgt o addinadev39spamquot gtgtgt pm Gmudeso 1 2 39span39 gtgtgt print oeugeso You Can also open an ISSUE at the on the developer s slte 1 2 Documentation Tutallal Contents Start here 3 rampere ovemew Refel ente Seal ll Page guide m all runeoans and 3559 search the datummtzrlarl Examples Geneva lndex 11le the IIIme all runeoons 175595 term Galley Module llldex network dromngs quirk mess to all dotumemed modules LEDA Q Libray of efficient data types written in C free versions 150 for the academic license 1K Hehlh 39 You can buy the Leda Guide from Amazon Mama 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 A Free Resource 6 Data Structures and Algorithms with ObjectOriented Design Patterns Python Java C and C by Bruno R Preiss web book with source code http wwwbrpreisscombooksopus7 More Books Algorithms INC quot1 h Graph Algorithms by Robert SedgeVick many code examples C C Java LEDA A Platform for Combinatorial and Geo I Computing by Kurt Mehlhorn and Stefan Naher Tu h ur

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "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!"

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

#### "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.