Chapter 9. Graph Algorithms
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart WeissGraph Algorithms1 Preliminary De nitionsThere is a lot of terminology associated with graphs and graph algorithms, and so we start byde ning the terms we will use for the remainder of this chapter.De nition 1.is a pairA(v, w)graphwhereG (V, E) is a set of vertices V and av V and w V . Formally,E V V ,itself. Edges are also calledset ofarcs .edgesE.Each edgethe Cartesian product ofVe Ewithdirected graph (a digraph , for short) if E is a set ofordered pairs, in which case the edges are called directed edges . A graph that is not directed iscalled an undirected graph .De nition 2.A graphG (V, E)is aEvery graph is therefore either directed or undirected. If it is not speci ed, i.e., if you see the wordgraphwithout any modi er, it is usually in a context in which it does not matter whether it isgraph withoutany graph.directed or undirected. Sometimes, sources might use the wordan undirected graph. In these notes, the word(v, w) is an edge then w isgraph, if (v, w) is an edge then vIn a digraph, ifundirected(v, w) is saidboth v and w .edgeto beincidentgraphwill meansaid to beadjacentis adjacent toon the vertexw,wandtowv,a modi er to meanbut not vice versa.In anv . The directed(v, w) is incident onis adjacent toand the undirected edgeDe nition 3. A weighted graph is a graph (directed or undirected), in which edges have weights ,also called costs . A weight is a numeric value assigned to an edge.You can think of a weighted graph as having a weight, or cost, function that assigns an integer toeach edge. Weighted graphs are very common because they model many real world relationships.For the remainder of this chapter, I will assume that if a graph is weighted, then there is a functionc : E Zthat assigns an integer, positive, negative, or zero, to each edge.Example 4.G (V, E) be the graph in which V is the set of all American cities with airports,and E is the set of all edges (v, w) such that there is a scheduled ight from city v to city w bysome commercial airline. The weight c(v, w) assigned to the edge (v, w) might beLet1. the air distance betweenvandw,2. the air time between them, or3. the price of a minimum price ticket.Online reservation systems often let the user choose from among many criteria for weighting ights.This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.1
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsExample 5.computers.LetEG (V, E)Prof. Stewart WeissVbe a computer network and letbe the set of routers and endpointis the set of connections between routers and routers and between routers andcomputers. Weights might be the latency of a transmission across an edge, or the bandwidth of anedge. It might even be the length of the physical wire.De nition 6.Apathin a graph is a sequence of vertices,1 i N , (vi , vi 1 ) E . The length of a path iswhich is N 1 if there are N vertices in the path.A path of lengthcontrast,called a(v, v)such that for eachi,is a path from a vertex to itself with no edges, so it is just a single vertex. Inis a path of lengthloop .De nition 7.0v1 , v2 , v3 , . . . , vNthe number of edges (not vertices) in the path,1,which is di erent from a path of length0.A path(v, v)isAsimple pathAcycle in a directed graph is a path of length at least 1 such that the rst and lastis a path such that all vertices are distinct except possible the rstand the last.De nition 8.vertices are the same. A cycle is simple if it is a simple path.De nition 9.Acycle in an undirected graph is a path in which the rst and last vertices are thesame and the edges are distinct (to avoid the problem that a path likeu, v, uis called a cycle eventhough the second edge is the same as the rst edge.)De nition 10.A graph isacyclicif it has no cycles. A directed acyclic graph is called aDAGfor short.De nition 11.An undirected graph is calledconnectedif there is a path from every vertex toevery other vertex. A directed graph with this property is calledstrongly connected .2 Graph RepresentationsThere are two common representations.2.1Adjacency MatrixA boolean or numeric-valued square matrixis an edge fromu to v.IfAA is numeric valued,with a row for every vertex.thenA[u][v]is true if thereA[u][v] would be the weight of the edge (u,v).The following asymmetric boolean matrix represents the directed graph in Figure This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.2
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart Weiss024135Figure 1: A directed graph.AdvantagesAn adjacency matrix has a very simple implementation. That is about its only advantage.Disadvantages Graphs are usually sparse, meaning that they have lots of zeros. There arematrix of Nvertices, but the number of edges may only be a multiple ofentries in aN.Many problems that have e cient solutions cannot be solved e ciently when this representation is used, because they will all tend to be2.2N2O(N 2 ).Adjacency ListsAn adjacency list is a linear array with an entry for each vertex, such that each entry is a pointerto a list of vertices adjacent to that vertex. This is the more common representation because it isthe most e cient for most purposes. Formally,De nition 12.Anadjacency listfor a graphvi V , A[i] is a pointerE for each j 1, 2, . . . , k.for each vertexis an edge inG (V,E)A of size n V such that,(v1 , v2 , . . . , vk ) such that (A[i],vj )is an arrayto a linked list of nodesIf the graph is a weighted graph, then the node for each edge in the list would have a membervariable that stores the weight.Vertices often have labels or names, such as the name of the cities they represent. In this case theproperties are stored in the array entry along with the pointer to the list. The graph in Figure 1would have the following adjacency list:This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.3
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart WeissFigure 2: Prerequisites for CS Major in Hunter College031220434540513 Graph Algorithms: Warming UpWe will examine a few of the simplest algorithms for solving problems related to graphs. We startwith topological sorting.3.1Topological Sort of a Directed Acyclic GraphFigure 2 is a snapshot of what the prerequisites for computer science courses were in Hunter Collegesome years back.Most students will immediately realize that the set of courses required for theThis work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.4
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart Weisscomputer science major together with the prerequisite relation is a directed, and hopefully acyclic,c2 are nodes in a graph that represent two di erence courses, and there isc1 to c2 , then it means that c1 is a prerequisite for c2 , and that therefore onecannot take c2 until one has successfully completed c1 . So for example, according to Figure 2, theregraph. That is, ifc1anda directed edge fromis a directed path from CS127 to CS415 of length 4, which means that after completing CS127, oneneeds at least 4 semesters to complete CS415.Suppose that you are a very busy person and that you can take just one course in each semester.You seek to assign the numbers1, 2, . . . , Nto theNcourses you need to take to graduate with amajor in Computer Science with the meaning that the course labeledk.kis to be taken in semesterThis is an example of a topological sort of the graph of courses. It is alinear,of the nodes of the graph such that, if there is a directed path from a nodegraph, thenvhas a lower number thanwvortotal,to a nodeorderingwin thein the ordering.It should be pretty obvious that there are many possible topological sorts of the graph in Figure2. When two or more nodes in the graph are not related, meaning that there is no directed pathfrom one to the other, then their relative order in the topological sort does not matter and multipletopological sorts of the graph are possible. Any valid topological sort is a solution to the problem.partial ordering relation on the vertices; it is notA topological sort imposes a total ordering that is consistent with the underlying partialIn general, the edge settotal.Ein a graph de nes aordering that the edges de ne.G (V, E) with vertices{v1 , v2 , v3 , . . . , vN } is an ordering of the vertices such that if there is a path from vi to vj in the graph,then vi must precede vj in the ordering. The output of a topological sort of a graph G (V, E) isan assignment of the numbers 1, 2, . . . , N to the vertices.To make the problem precise now, a topological sort of a graphA topological sort is not possible for graphs with cycles. If a graph has cycles, then for any twoverticesvbecause ifandvwin a cycle,v precedesprecedesw,thenwwandwprecedescannot be beforev,v.There is no way to create a sequenceand vice versa.The AlgorithmDe ne thein-degree of a node to be the number of edges incident upon the node.For example, inFigure 2, M121 has in-degree 0 and CS235 has in-degree 3. We now proveLemma 13. If a graph has no cycles, then there is at least one node with in-degree 0.Proof.Suppose to the contrary that every node has in-degree greater than zero.arbitrarily.Pick any nodePick an edge incident on that node and visit the node at its source.Repeat thisprocedure of following the edge incident on the node in the reverse direction of the edge. If multipleedges are incident on a node, pick any one arbitrarily.Since every node has at least one suchincoming edge, the path so followed is of in nite length, as there is always an edge to follow. Butthere are nitely many nodes in the graph, so some node must appear twice on this path, whichimplies that the path contains a cycle.Letvbe any one of the nodes whose in-degree is zero. We assignin-degree of all vertices adjacent toremoving the edge fromvvvthe number 1 and reduce theby 1. Reducing the in-degree of an adjacent node by 1 is liketo the node, so if you were simulating this algorithm on paper with apicture of the graph, it would be best to do so using a pencil with an eraser! Next, we try to ndThis work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.5
CSci 335 Software Design and Analysis 3Chapter 9 Graph Algorithmsanother node whose in-degree isProf. Stewart Weiss0 and if we do, we repeat this procedure.If we cannot nd a vertexwith in-degree 0 but we have not visited every vertex, then there must be a cycle, because it meansthat every node in the remaining non-empty graph has at least one incoming edge, which meansthat the remaining graph has a cycle, by Lemma 13 above. The following listing is a pseudocodedescription of the resulting algorithm.initialize the in - degrees of all vertices by scanning theadjacency lists1234567891011121314counter 1;while there are vertices in V yet to be processed{let v be any vertex with in - degree 0;if no such vertex exists ,return CycleFoundelse {v . topologicalNumber counter ;for each w that is adjacent to v ,decrement its in - degree by 1}}CorrectnessWe want to prove that if there is a path froma smaller number thanwvtowin the graph, thenvis assignedby the algorithm.v to w. If the path has length 1, thenw cannot be visited before v because the edge (v, w) will not beremoved until v is visited, so in-degree(w) will not be 0 until after v is visited. This implies thatthe number assigned to w is greater than the number assigned to v.We can argue by induction on the length of a path from(v, w)is an edge in the graph andSuppose that we have proved the claim for all paths of length less thansuch that the length of the path fromv, . . . , uis a path of lengthandvtow(u, w)isnv, w be nodesvertex u such thatand let 1. By assumption there is ais an edge. By the hypothesis, the topological numberu, and by the previous argument, thenumber assigned to u is less than that assigned to w, proving the claim for paths of length n.assigned tovn 1nis less than the topological number assigned toImplementation and Performance AnalysisThe simplest way to implement this algorithmis to use a queue for storing the vertices whose in-degrees are zero. The in-degree of each vertexis computed by reading every adjacency list and incrementing the in-degree of vertexthatvappears in the adjacency list of some other vertex. This isO(E)vevery timesince it looks at each edgeonce.Having computed all in-degrees, all vertices with in-degree 0 are enqueued and a loop is entered.In the loop, the front of the queue is removed, it is given a topological number, its successors'in-degrees decremented, and if 0, they are enqueued. The resulting pseudocode follows.1234// Find all nodes with in - degree 0q . makeEmpty () ;for each vertex v in Vif ( v . indegree 0 )This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.6
CSci 335 Software Design and Analysis 3Chapter 9 Graph Algorithms5678910111213141516171819202122Prof. Stewart Weissq . enqueue ( v ) ;// Start processing with a count of 1counter 1;while ( ! q . empty () ){v q . dequeue () ;// v has in - degree 0v . topologicalNumber counter ;for each w that is adjacent to v {// (v , w ) is an edge in the graphw . indegree - -;if ( w . indegree 0 )q . enqueue ( w ) ;}}if ( counter ! V )return CycleFound ; // or throw an exceptionThis algorithm requiresO( E V ) time.This is because, in the while-loop, each edge is examinedat most once and each vertex is processed at most once. Whichever is larger is what dominates therunning time.Example1324657Figure 3: Digraph to be topologically sorted.Consider the graph in Figure 3. Two topological orderings of it are 1, 2, 5, 4, 7, 3, 6 and 1, 2, 5, 4,3, 7, 6. Let us apply the algorithm to it. The in-degrees of all nodes are computed and we see thatnode 1 has in-degree 0.We assign a 1 to node 1, and remove edges (1,2), (1,3), and (1,4). Node 2 now has in-degree 0, sowe assign 2 to it and remove the edges (2,4) and (2,5). The resulting graph isThis work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.7
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart Weiss1324567Node 5 now has in-degree 0 so it is assigned 3, and the edges (5,4) and (5,7) are removed. Thisresults in node 4 having in-degree 0, so it is given number 4 and edges (4,3), (4,6), and (4,7) areremoved. The graph is now1324567The last few steps assign 3 the number 5, deleting edge (3,6), then assigning number 6 to node 7,deleting (7,6), and assigning 7 to node 6.3.2Minimum Spanning TreesDe nition 14.such thatG'Aspanning tree1for an undirected graphG (V, E)is a graphG' (V, E ')is a tree.In other words,G'has the same set of vertices asG,but edges have been removed fromthe resulting graph is a tree. This amounts to saying thatG'Eso thatis acyclic. It is called a spanning treebecause every node is connected to every other node, so the tree spans all of the nodes. Removalof any single edge from a spanning tree causes the graph to be unconnected. A spanning tree isminimumif there is no other spanning tree with smaller cost. If the graph is unweighted, thenthe cost is just the number of edges. If it has weighted edges, then the cost is the sum of the edgeweights of the edges in the spanning tree. See Figure 4 for an example.An example of an application of spanning trees is for nding the least length of wiring that can beused to wire the electrical connections in a building.1For directed graphs the problem is still de ned but we will not consider them.This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.8
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart Weiss214213235107484561672121234546167Figure 4: An undirected graph and a minimum spanning tree for it.The problem of nding a minimum spanning tree amounts to nding the set of edges of which thistree is composed.After all, the spanning tree is the same vertex set as the graph, but a subsetof the edges. So the idea is to design an algorithm that selects which edges belong in the tree. Arelatively simple algorithm for nding a minimum spanning tree isKruskal's Algorithm .a greedy algorithm in that it always tries to nd the best solution at each step.approaches work. Here it does. It uses theUnion-FindIt isNot all greedyalgorithm from Chapter 8. Its greediness is in always choosing an edge with least weight among the possible choices of edge.Kruskal's AlgorithmThe algorithm starts out with a forest in which each vertex is a tree by itself. Then it looks for theedge with least weight and connects its two vertices into a tree with two vertices. If there is morethan one such edge, any of them can be chosen. It then looks for another edge that is least weightamong those that remain and connects the two vertices together if they are not already part of thesame tree. If they are in the same tree, then adding this edge would form a cycle, so the edge is notadded. The algorithm continues this procedure until there is just one tree, i.e., every vertex is ina single tree. This tree will be minimum cost because the edges were added in order of ascendingcost.The algorithm represents the trees as sets of vertices. To form a new tree from two existing trees,aunionoperation is applied to the two sets that represent these trees. When given an edgein the graph, the algorithm uses thendoperation to nd in which setsvandwThis work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.(v,w)each belong.9
CSci 335 Software Design and Analysis 3Chapter 9 Graph AlgorithmsProf. Stewart WeissTherefore, a disjoint set ADT is used to represent the sets of vertices. A heap is used for pickingthe minimum weight edge at each step. The algorithm is presented in pseudocode in the followinglisting.1234567891011void kruskal (){Vertex u , v ;// Vertex is the type of vertex labelsEdge e ;// Edge is a struct containing (source vertex , target vertex , weight )DisjointSet s ( NUM VERTICES ) ; // the set of treesPriorityQueue Edge h ( NUM EDGES ) ; // the edges , with smallestweight having highest prioritySetType uset , vset ;// SetType is the range of indices 0.NUM VERTICESlist Edge edgelist ;// list of edges in the minimumspanning treereadGraphIntoHeapArray ( h ) ;that gets heapifiedh . buildHeap () ;121314151617181920212223242526}// read the edge set into the array// now heapify based on edge weightsint edgesAccepted 0;while ( edgesAccepted NUM VERTICES -1 ) {e h . deleteMin ( ) ;// assume e (u , v )uset s . find ( u ) ;vset s . find ( v ) ;if ( uset ! vset ) {// add the edge to the list of edges in the tree and incrementcountedgelist . pushback ( e ) ;edgesAccepted ;s . union ( uset , vset ) ;}}Performance AnalysisThe algorithm takesO( E )steps to build the heap in lines 11 and 12.Since the while-loop iterates in the worst case once for each edge in the graph, it can takeO( E )deleteMin, nd, and union operations to build the minimum spanning tree. Each deleteMin takeslog E steps, so this isO( E log E )steps.The nd and union operations take less time thanthe deleteMin, so they do not increase the amortized running time.log( V 2 ) O(log V ),this isSince E O( V 2 )andO( E log V ).4 Shortest Path AlgorithmsWe assume that the graphs in question are directed graphs.general statement of the problem is theThere are a few di erent types ofsingle-source shortest pathshortest weighted path problem.shortest path problems. The simplest one is theproblem. The mostThis is one of thehardest versions of the problem. A weighted path is a path
de ning the terms we will use for the remainder of this chapter. De nition 1. A graph G (V;E) is a set of vertices V and a set of dgese E. Each edge e 2E is a pair (v;w) where v 2V and w 2V. ormallyF, E V V, the Cartesian product of V with itself. Edges are also called arcs . De nition 2.
Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .
The totality of these behaviors is the graph schema. Drawing a graph schema . The best way to represent a graph schema is, of course, a graph. This is how the graph schema looks for the classic Tinkerpop graph. Figure 2: Example graph schema shown as a property graph . The graph schema is pretty much a property-graph.
Oracle Database Spatial and Graph In-memory parallel graph analytics server (PGX) Load graph into memory for analysis . Command-line submission of graph queries Graph visualization tool APIs to update graph store : Graph Store In-Memory Graph Graph Analytics : Oracle Database Application : Shell, Zeppelin : Viz .
TO KILL A MOCKINGBIRD. Contents Dedication Epigraph Part One Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Part Two Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18. Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26
DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .
a graph database framework. The proposed approach targets two kinds of graph models: - IFC Meta Graph (IMG) based on the IFC EXPRESS schema - IFC Objects Graph (IOG) based on STEP Physical File (SPF) format. Beside the automatic conversation of IFC models into graph database this paper aims to demonstrate the potential of using graph databases .
1.14 About Oracle Graph Server and Client Accessibility 1-57. 2 . Quick Starts for Using Oracle Property Graph. 2.1 Using Sample Data for Graph Analysis 2-1 2.1.1 Importing Data from CSV Files 2-1 2.2 Quick Start: Interactively Analyze Graph Data 2-3 2.2.1 Quick Start: Create and Query a Graph in the Database, Load into Graph Server (PGX) for .
1.14 About Oracle Graph Server and Client Accessibility 1-46. 2 . Quick Starts for Using Oracle Property Graph. 2.1 Using Sample Data for Graph Analysis 2-1 2.1.1 Importing Data from CSV Files 2-1 2.2 Quick Start: Interactively Analyze Graph Data 2-3 2.2.1 Quick Start: Create and Query a Graph in the Database, Load into Graph Server (PGX) for .
