LJOEPG(SBQI De๏ฌnition 1. A directed graph consists of a ๏ฌnite 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 ๏ฌrst 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 ๏ฌrst 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
takanorip
watany
moznion
yuukiw00w
el_stoffel
konifar
taka_aki
jaxx2104
keio_smilab
josejuansanchez
sansan33
lycorptech_jp
eileencodes
lara
hatefulcrawdad
afnizarnur
vanstee
tammielis
danielanewman
csswizardry
chrislema
kastner
sachag
![Thanks CouchDB! $PEFQEFODJFT group_level=3 &start_key=["winston"] &end_key=["winston",{}]](https://files.speakerdeck.com/presentations/4a01bb00da3e0131c6a27202678817e0/slide_29.jpg){kind=link}
