LJOEPG(SBQI Definition 1. A directed graph consists of a finite set of vertices V and a set of directed edges E. An edge is an ordered pair of vertices (u,v). Vertex Vertex Edges Edges
& LJOEPG(SBQI • A path is a sequence of vertices (x1 , x2 , . . . , xn ) such that consecutive vertices are adjacent (edge (xi , xi + 1) ∈ E for all 1 ≤ i ≤ n − 1). • A path is simple when all vertices are distinct. • A cycle is a simple path that ends where it starts, that is, xn = x1 . • The distance between between u and v is the length of the shortest path from u to v. • An undirected graph is connected when there is a path between every pair of vertices.
& LJOEPG(SBQI • The connected component of a node u in an undirected graph is the set of all nodes in the graph reachable by a path from u. • A directed graph is strongly connected when, for every pair of vertices u, v, there is a path from u to v and a path from v to u. • The strongly connected component of a node u in a directed graph is the set of nodes v such that there is a path from u to v and a path from v to u.
with edges |E| = m can be represented as a list of m adjacency pairs. • Adjacency matrix: A graph of size |V| = n can be represented as an n x n matrix. Question: How do we represent the edges?
the first edge out of s, towards some node v. 2. Continue from v until you reach a “dead end”, that is, a node whose neighbors have all been explored. 3. Backtrack to the first node with an unexplored neighbor and repeat 2.
"HSBQIJTBUSFF 1. Forward edges: go from an ancestor to a descendant other than a child. 2. Back edges: go from a descendant to an ancestor, other than the parent. 3. Cross edges: go from right to left, that is, • from tree to tree; e.g., (v5 ,v4 ) in Figure 2(b). • between nodes in the same tree but in different branches. e.g., (u, v) on the right of Figure 3(b).
The Question. what are all of the shortest paths in G from s? i.e. What is the shortest path from a single source, s, and to all other verticies in G? By knowing an answer to this, we also know: • Single-pair shortest-path: What is the shortest s-t path in G? • Single-destination shortest-path: what are all of the shortest paths in G to a single sink, t? • All-pairs shortest-paths: What is the shortest path between all (u,v) vertex pairs in G?
collective form of computer scientists is ...? a dijkstra! Seriously tho. Dijkstra was a boss. He created an algorithm to solve this for us. Here is how it works.
s And a set of shortest paths from s for vertices, Q Initially, Q only contains s, with distance(s) = 0 In every iteration, examine V - Q and select vertex v: 1. has an incoming edge from some vertex ∈ Q 2. minimizes the quantity among all v ∈ V − Q d(v) = min distance(u) + weight(u, v) u ∈ Q
graph representation is not extremely helpful for visualizing package relationships. • But it does provide a basic structure for a graph search problem.
then add a colored edge from any node nA to nB if package A depends on package B. • Edges are colored by dependency type: dependencies or devDependencies • To build our graph, G, we add a node (or vertex) for every package. na nb nc
all well and good, but what the heck are you doing?!?! For module NAME generate a matrix by: - Rank codependencies based on number of times they appear - For each codependency C in the SET of the top N: Rank SET - {C} by number of times they appear to create ROW[C]
The size of the arc represents the degree of the codependency relationship with the parent module. • The size of the chord represents the degree of the codependency relationship between each pair. • The color of the chord represents the “dominant” module between the pair. winston
indexzero
imamura_ko_0314
neonankiti
akiroom
lmi
oracle4engineer
naveed92
masatoshi0205
shigashiyama
mineo_matsuya
jscseminar
kenta_hi
linyows
tammyeverts
jnunemaker
cassininazir
honnibal
panda_program
lemiorhan
jrom
kneath
aarron
irinanazarova
tanoku
maltzj
![Thanks CouchDB! $PEFQEFODJFT group_level=3 &start_key=["winston"] &end_key=["winston",{}]](https://files.speakerdeck.com/presentations/4a01bb00da3e0131c6a27202678817e0/slide_29.jpg){kind=link}
