***** Graph ***** * Graphs are a special type of data structure. * They are used to solve many problems, such as the shortest path problem. * However, if the implementation is not done carefully it can be too slow to use. What is a graph? ================ * We will start by giving a definition of a graph. .. admonition:: Definition: Graph * A **graph** :math:`G = (V,E)` consists of a set of vertices :math:`V` and a set of edges :math:`E`. * Each edge is a pair :math:`(v, w)`, where :math:`v,w\in V`. * Edges are sometimes referred as **arcs** and vertices as **nodes**. Directed Graphs --------------- .. admonition:: Definition: Directed Graph * When the edges (or arcs) :math:`(v,w)` are ordered the graph is **directed**. * Vertex :math:`w` is **adjacent** to :math:`v` if and only if :math:`(v,w)\in E`. * Directed graphs are also referred as **digraphs**. * The following figure represents a digraph: .. figure:: ./img/digraph.png :align: center .. admonition:: Activity :class: activity * Write all the pairs :math:`(v,w) \in E` of the previous graph. Undirected Graphs ----------------- * If there are directed graphs, there are undirected graphs! .. admonition:: Definition: Undirected Graph * In an undirected graph with edges :math:`(v,w)\in E`, there is an edge :math:`(w,v)\in E`. * :math:`w` is adjacent to :math:`v` and :math:`v` is adjacent to :math:`w`. .. admonition:: Activity :class: activity * Take the previous graph and transform it to an undirected graph. * Draw the undirected graph that contains the following edges: * :math:`E = \{(a,b), (b,a), (a,c), (c,a), (b,c), (c,b)\}` Representing graph in memory ============================ * Obviously, we cannot represent a graph like this in memory. * We could be as close as possible to the math representation: * Storing a list of nodes * And storing the list of arcs. .. admonition:: Activity :class: activity * What do you think about this representation? * Do you have a better representation? * There are two ways to represent a graph in memory: * Adjacency matrix * Adjacency list Adjacency Matrix ---------------- * The easiest way to represent is with a 2D matrix. * This is called an adjacency matrix. The idea: * Consider a matrix :math:`M`. * For each :math:`(u,v) \in E`: * We set :math:`M[u][v]` to 1. * Otherwise to 0. .. admonition:: Example :class: example * If we take the previous graph. * We can create the following adjacency matrix. .. figure:: ./img/adjacency_matrix.png :align: center * It is very easy to use adjacency matrix and very fast. * However, the space requirement is :math:`O(|V|^2)`. * It is a lot if the graph has an important number of nodes, but few arcs. * It is appropriate if the graph is **dense** :math:`|E| = O(|V|^2)`. .. admonition:: Activity :class: activity * Why using a matrix for dense graphs is not a problem? * In most problems, graphs are not dense. .. admonition:: Example :class: example * Consider a street map of a city. * Assume a Manhattan-like orientation. * Any intersection is attached to roughly 4 streets. * So, if the graph is directed with two-way streets. * The number of edges is :math:`|E| \approx 4|V|` * If there are 3 000 intersection. * The number of vertices is 3 000. * And the number of edges is 12 000. * It requires an array of size 9 000 000. * A graph that is not dense is called **sparse**. * We need another way to represent **sparse** graph. Adjacency List -------------- * Adjacency list is a better solution when the graph is sparse. * For each vertex, we keep a list of all adjacent vertices. .. admonition:: Example :class: example * If we take the previous graph. * We can create the following adjacency list. * The space requirement is :math:`O(|E|+|V|)`. * It is linear in the size of the graph. .. figure:: ./img/adjacency_list.png :align: center .. admonition:: Activity :class: activity * Why are we not using adjacency lists for dense graphs? Weighted edges -------------- * Consider a problem in which you need to represent the streets and intersections in a city. * You would like to store the distance of each street. * A graph allows us to add **weights** on edges. * The changes to the previous representation are small: * Adjacency matrix: Instead of 0 and 1, we have the weight of the edge if it exists. If not :math:`- \infty` or :math:`+ \infty`. * Adjacency list: Add a new element in the list. .. admonition:: Activity :class: activity * Draw the directed graph that contains the following edges: * :math:`E = \{(a,b,2), (b,a,4), (a,c,3), (c,a,1), (b,c,10)\}` * Give the adjacency matrix and adjacency lists representation. Implementation ============== * Java does not provide an implementation of the Graph ADT. * We will write our own! * We want our ADT to be able to do the following: * Create a graph with the specified number of vertices. * Iterate through all the vertices in the graph. * Iterate through the vertices that are adjacent to a specified vertex. * Determine whether an edge exists between two vertices. * Determine the weight of an edge between two vertices. * Insert an edge into the graph. The Graph interface -------------------- We want to define a Graph interface that will not depend of the memory representation. It will have the following methods: * :code:`int getNumV()`: Returns the number of vertices in the graph * :code:`int isDirected()`: Return if the graph is directed * :code:`Iterator edgeIterator(int source)`: Returns an iterator to the edges that originate from a given vertex * :code:`Edge getEdge(int source, int dest)`: Gets the edge between two vertices * :code:`void insert(Edge e)`: Insert a new edge into graph * :code:`boolean isEdge(int source, int dest)`: Determines whether an edge exists from :code:`source` to :code:`dest` * :code:`default void loadEdgesFromFile(Scanner scan)`: A default method that loads the edges from a file associated with :code:`scan` .. literalinclude:: ./Graph.java :language: java :linenos: Edge Representation ------------------- The nodes will be represented by integers, but we need a class to represent the edge. The class is simple, it contains three attributes: * A source node * A destination node * A weight, :math:`1` by default. .. literalinclude:: ./Edge.java :language: java :linenos: :lines: 5-24, 28-36, 40-45, 47-51, 53-57, 59-64, 66-91 Adjacency List Representation ------------------------------ We will create a class to represent a graph using a linked list. This class :code:`ListGraph` will implement the interface :code:`Graph` and contains three attributes. .. literalinclude:: ./ListGraph.java :language: java :linenos: :lines: 3-19, 108 The constructor only takes the number of nodes and if the graph is directed as parameters. .. literalinclude:: ./ListGraph.java :language: java :linenos: :lines: 21-32 .. admonition:: Activity :class: activity Implement the following methods of the class. .. literalinclude:: ./ListGraph.java :language: java :linenos: :lines: 54-60, 65, 79-88, 96 More Definitions ================ * Graphs are used in a lot of algorithms. * To use them in these algorithms, we require some last definitions. .. admonition:: Definition: Path * In a graph, a **path** is a sequence of vertices :math:`v_1, v_2 \dots, v_N` such that :math:`(v_i, v_{i+1})\in E` for :math:`1 \leq i < N`. * The length of the path is the number of edges on the path (:math:`N-1`). .. admonition:: Definition: Cycle * In a cycle in a directed graph is a path of length at least 1 such that :math:`v_1 = v_N`. * In undirected graph the edges need to be distinct. * If a directed graph does not have a cycle, it is called a **acyclic** graph. .. admonition:: Activity :class: activity * Consider the graph given in the first example. * Give an example of a path. * Give a example of a cycle.