Multidimensional Arrays & Graphs CMSC 420: Lecture 3Mini-Review•Abstract Data Types:•List•Stack•Queue•Deque•Dictionary•Set•Implementations:•Linked Lists•Circularly linked lists•Doubly linked lists•XOR Doubly linked lists•Ring buffers•Double stacks•Bit vectorsTechniques: Sentinels, Zig-zag scan, link inversion, bit twiddling, self-organizing lists, constant-time initializationConstant-Time Initialization•Design problem:-Suppose you have a long array, most values are 0.-Want constant time access and update-Have as much space as you need.•Create a big array:-a = new int[LARGE_N];-Too slow: for(i=0; i < LARGE_N; i++) a[i] = 0•Want to somehow implicitly initialize all values to 0 in constant time...Constant-Time Initialization•Access(i): if (0≤ When[i] < count and Where[When[i]] == i) return Data[] = means unchangedWhere[] = 3Count =6 12 131 26 1213Count holds # of elements changedWhere holds indices of the changed elements.When[] = 1 3 2When maps from index i to the time step when item i was first changed.Access(i): if 0 ≤"When[i] < Count and Where[When[i]] == i: return Data[i] else: return DEFAULTMultidimensional Arrays•Often it’s more natural to index data items by keys that have several dimensions. E.g.:•(longitude, latitude)•(row, column) of a matrix•(x,y,z) point in 3d space•Aside: why is a plane “2-dimensional”?Row-major vs. Column-major order•2-dimensional arrays can be mapped to linear memory in two ways:12345678910111213141516171819201591317261014183711151948121620Row-major orderColumn-major order12341 2 3 4 512341 2 3 4 5Addr(i,j) = Base + 5(i-1) + (j-1) Addr(i,j) = Base + (i-1) + 4(j-1)Row-major vs. Column-major order•Generalizes to more than 2 dimensions•Think of indices <i1, i2, i3, i4, i5,...,id> as an odometer.-Row-major order: last index varies fastest-Column-major order: first index varies fastestSparse Matrices•Sometimes many matrix elements are either uninteresting or all equal to the same value.•Would like to implicitly store these items, rather than using memory for them.Linked 2-d Array AllocationA1C1M4F4A2Q2P5Z3E5Array with random access to linked list representing rowsRow represented by linked list; items contain column numbersLinked 2-d Array AllocationA21C31M34F14A42Q12P25Z23E45ThreadingA21C31M34F14A42Q12P25Z23E45•Column pointers allow iteration through items with same column index.•Example of threading: adding additional pointers to make iteration faster.•Threading usefulwhen the definition of“next” depends oncontext.•We’ll see additionalexamples of threadingwith trees.Hierarchical Tables•Combination of sequential and linked allocation.•Particularly useful when filled elements cluster together, or when all entries in one dimension are always known.•Natural to implement by combining Perl arrays, C++ vectors, etc. 4 x 5 x 5 x 3 arrayUpper Triangular Matrices•Sometimes “empty” elements are arranged in a pattern.•Example: symmetric distance matrix.•Want to store in contiguous memory.•How do you access item i, j?n + (n-1) + (n-2) + ... + (n - i + 1) plus j-i come before the jth element in the ith row # elements taken up by the first (i-1) rows:Graphs – Examples•Computer Networks•Street map connecting cities•Airline routes.•Dependencies between jobs (must finish A before starting B)•Protein interactionsUsed to represent relationships between pairs of objects.Image Graphs•Black & white image, 0/1 pixels (crossword puzzle, e.g.)•G = (V,E), a set of vertices V and edges E-V = {set of pixels}-{u,v} in E if pixels u and v are next to each other.•Separate connected parts of the graph = disjoint regions of the image (space fill, e.g.)•Graph defined this way is planar (can be drawn without edge crossings).Graphs – Terminology•Graph G = (E, V)-V = set of vertices-E = set of pairs of vertices, represents edges•Degree of vertex = # of edges adjacent to it•If there is an edge {u,v} then u is adjacent to v.•Edge is incident to its endpoints.•Directed graph = edges are arrows•out-degree, in-degree•The set of vertices adjacent to a node u is called its neighbors. vertex or nodeedgeGraphs – Example•V = {u,v,w,x,y,z}•E = { {u,v}, {v,w}, {u,x}, {w,x}, {z,y}, {x,y}}uvwxyzGraphs – More Terminology•A path is a sequence of vertices u1, u2, u3, ... such that each edge (ui, ui+1) is present.•A path is simple if each of the ui is distinct.•A subgraph of G = (V, E) is a graph H = (V’, E’) such that V’ is a subset of V and an edge (u,v) is in E’ iff (u,v) is in E and u and v are in V’.•A graph is connected if there is a path connecting every pair of vertices.•A connected component of G is a maximally sized, connected subgraph of G.Graphs – Still More Terminology•A cycle is a path u1, u2, u3, ..., uk such that u1 = uk.•A graph without any cycles is called acyclic.•An undirected acyclic graph is called a free tree (or usually just a tree)•A directed acyclic graph is called a DAG (for “Directed Acyclic Graph”)•Weighted graph means that either vertices or edges (or both) have weights associated with them.•Labeled graph = nodes are labeled.Graphs – Basic properties•Undirected graphs:•What’s the maximum number of edges?(A graph that contains all possible edges is called complete)•What’s the sum of the all the degrees?•Directed graphs:•What’s the maximum number of edges?•What’s the sum of all the degrees?Graphs –!Isomorphism•Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there’s a 1-to-1 and onto mapping f(v) between V1 and V2 such that:{u,v} in E1 iff {f(u), f(v)} in E2.•In other words, G1 and G2 represent the same topology.Does checking whether two graphs are isomorphic seem like an easy problem or a hard problem?Graphs –!ADT•S = vertices()•S = edges()•neighbors(G, v)•insert_edge(G, u,v)•insert_vertex(G, u)•remove_edge(G, u,v)•remove_vertex(G, u)Return sets - set ADT we talked about last time may be usefulTime to perform these tasks will depend on implementation.What are ways to implement graphs?Graphs – Implementations1. List of edges2. Adjacency matrix3. Adjacency listEdge List Representation•Simple: store edges (aka vertex pairs) in a list.•Good if: the “structure” of the graph is not needed, and iterating through all the edges is the common operation.•Bad because: •testing whether an edge is present may take