Graphs

• In most of the cases of ADTs we've seen so far, the individual elements in the container bear no direct relation to each other. Sure, keys might be less than or greater than the keys of other elements, but that doesn't describe how the objects are really related.
• The one exception was Trees. These (as an ADT) did express a relationship between the elements. If we're talking about directories, the parent child relationship encodes which directories are inside which.
• Sometimes we want to encode information that is more general than a tree can provide:
  
  
  
  
  
  

  Above is the subway map for Washington DC.

  

  Above is a sketch of the proposed ARPAnet, ca. 1962

  

  Above is a sample social network, describing the "friend" relation with those grey connections.

  

  Above describes the collaboration between professors in the computer science department at the University of Massachusetts, Amherst. Red=AI, Blue=Theory, Black=Systems.

• All of these pictures above show the relationship between individual items.
  • In the subway case, its stations related by subway lines.
  • In the ARPAnet care, its computers, related by network connections.
  • In the friendster case, its people, related by who they know.
  • In the collaboration case, its professors related by who they collaborated with.
• Often we want to asks questions that relate to these structures:
  • How do I get from the Navy Yard to Bethesda?
  • How long will my email take to get my machine to Stanford?
  • Does Joe know Sara? Does he know someone who knows Sara?
  • Are there any AI professors who collaborate with no other AI professors, but do collaborate with someone else?
• These can be answered in a computer by representing the situation as a Graph.
• In Discrete Math-ese, a graph is a set of vertices V, and and collection of Edges E. Each edge is a pair (not necessarily ordered) of elements from V. Ordered pair edges (a,b) are called directed and un-ordered pair edges {a,b} are called undirected.
• Brief exercise: describe V and E for each of the pictures above.
• In all of those, the edges are undirected. The relationships go both directions. If Zilberstein collaborates with Immerman, then Immerman collaborates with Zilberstein.
• Sometimes connections between things go in a particular direction. Lets say we want to talk about the status of Big East football as of Nov 11, 2004. We want to show not only who has played whom, but what the result was. This is a job for directed links:
  Pitt beat BC, so the link goes from Pitt to BC, but not the other way.
• Some other things commonly represented by graphs:
  • City streets.
  • Plumbing or wiring.
  • Airline networks.
  • Text. Sometimes it's useful to represent text in a document based on the order of the words. Take this rendition of a 15th Century folk song, "The Riddle":
    I gave my love a cherry, that had no stone
    I gave my love a chicken, that had no bone
    I gave my love a ...(This is where John Belushi smashes the guitar)
    We might represent it as:
    
• Some definitions:
  • If all the edges in a graph are undirected, then the graph is "undirected".
  • If all the edges in a graph are directed, the the graph is "directed", or a "digraph".
  • If the edge types are mixed, then its a "mixed graph".
  • Two verticies are "adjacent" if they are connected by an edge.
  • The degree of a vertex is the number of edges connected to it.
  • The in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges. If an edge is undirected, it is both incoming and outgoing.
  • Parallel edges are two or more edges that connect the same two nodes. This often happens in the sports example when teams play each other more than once.
  • A self loop occurs when an edge connects a vertex with itself. This can happen in the text example, "To everything, turn, turn, turn..."
  • "Simple" graphs have no self-loops or parallel edges.
• Some important basic facts:
  • If there are m edges in a graph, Σ_v∊Gdeg(v) = 2m. Sinceeach edge is counted twice in the degree sum, we get twice the number of edges.
  • In a directed graph G with m edges, Σ_v∊Gindeg(v) = Σ_v∊G outdeg(v) = m
  • If G is a simple directed graph with n verticies and m edges, then m ≤ n(n-1). There are n nodes and each node can be connected to (n-1) other nodes.
  • If G is a simple undirected graph with n verticies and m edges, then m ≤ n(n-1)/2. Its the same as the directed case, but we can only have one edge between each node instead of 2.
• Some more definitions:
  • A path is a sequence of vertices and edges that starts a a vertex, ends and a vertex, and each edge is incident to its predecessor and successor in the sequence. A sample path: (Pitt,(Pitt,BC),BC,(BC,UConn),UConn,(UConn,Temple),Temple).
  • Directed path is one that follows directed edges.
  • A cycle is a path that starts and ends at the same vertex with at least one edge in it.
  • A directed cyle is a cycle along all directed edges.
  • A subgraph of G is a graph H where the vertices in H are a subset of the vertices in G, and the edges in H are a sub-collection of the edges of G. The endpoints of the edges of H must be vertices in H.
  • A spanning subgraph of G is a subgraph of G containing all the nodes of G.
  • A graph is connected if there is a path from any vertex to any other vertex.
  • A tree is an acyclic graph.
  • A spanning tree of G is a connected acyclic spanning subgraph of G.
  • and edge can have a "Label" that is information stored in the edge.
• OK, now we can formally define the graph ADT:
  • veritces() - return an iterable container of all the vertices.
  • edges() - return an iterable container of all the edges.
  • incidentEdges(v) - return an iterable container of all the edges incident on v.
  • opposite(v,e) - return the vertex opposite v across edge e.
  • endVertices(e) - return the vertices on either end of edge e.
  • connectingEdge(v,w) - return the edge between these vertices.
  • areAdjacent(v,w) - returns true if vertices v and w are connected by an edge.
  • insertVertex(x) - insert a new vertex w/ element x.
  • insertEdge(v,w,l) - insert and edge between v and w with label l.
  • removeVertex(v) - remove vertex v.
  • removeEdge(e) - remove edge e.
• Representing Graphs. There are 2 main ways to represent graphs: adjacency lists and Adjacency Matrices.
  • In an adjacency list, we actually have many lists:
    • a list of the vertices.
    • a list of the edges.
    • each vertex has a list of pointers to the edges incident on that vertex.
    • each edge has pointers two the two vertices it is incident on.
  • vertices() and edges() take O(1), but of course take O(n) and O(n) to iterate through.
  • opposite() and endVertices() take O(1).
  • incidentEdges(v) is O(1), but O(deg(v)) to iterate through.
  • areAdjacent(v,w) takes O(min(deg(v),deg(w))).
  • insertVertex(), insertEdge(), removeEdge(): O(1)
  • removeVertex(v): O(deg(v))
  • Space O(m+n).
  • In an adjacency matrix, instead of each node having a list of incident edges, all edges are represented by a big matrix. the rows and collumns are labeled by the nodes, and is there is an edge from one node to another, then that entry in the matrix is a pointer to the edge.
  • incidentEdges() is O(n)
  • areAdjacent() is O(1)
  • insert,removeVertex() is O(n²).