Graph

Graphs: Collection of distinct vertices and distinct edges.

• Real-World Example: Road map
• Subgraph: Portion of a graph that is itself a graph.

Directed Graph: Graph where the edges are arrows.

• Real-World Example: Map of course pre-requisites

Example: On Adjacency B \to A

• A is adjacent to B, but B is not adjacent to A

Three Types of Graphs:

1. Connected Graph: Has a path between every pair of distinct vertices (You can pick any two vertices and find a path between them)
2. Complete: There is a path from every vertex to every other vertex.
3. Disconnected: There is at least one pair of vertices with no edge connecting them.

Paths

Path: A path between two vertices is a sequence of edges.

• Length: Number of edges in the path
• Cycle: A path that begins and ends at the same vertex.

Note: Directed Path

• In a directed graph, the edge’s direction must also be considered! (Directed Path)

Note: Weighted Edges

• If the edges have weights, the length is equal to the sum of their weights.

Traversals

1. Breadth-First (Level Order)
   • You need a queue to do this.

Example: Breadth-First Algorithm

Algorithm getBreadthFirstTraversal(originVertex) {
  traversalOrderQueue; // Holds result
  vertexQueue; // Holds vertices as they're visited
  while(!vertexQeuue.isEmpty()) {
      frontVertex = vertexQueue.dequeue();
      while (frontVertex has a neighbor) {
          nextNeighbor = next neighbor of frontVertex;
          if (nextNeighbor is not visited) {
              Mark nextNeighor as visited;
              traversalOrder.enqeue(nextNeighbor);
              vertexQeue.enqueue(nextNeighbor);
          }
      }
  }
  return traversalOrderQueue;
}

• Note: Neighbors are the same thing as adjacent vertices.

2. Depth-First (Pre-order)
   • Done by traversing until you reach a vertex with no outsync nodes.

Example: Depth-First Algorithm

Algorithm 

• Note: Neighbors are the same thing as adjacent vertices.

Note: Finding Neighbors

• To find neighbors, you need to use iterator (hasNext())

Topological Order

Directed Acyclic Graph (DAC): Directed graph without cycles

• In topological order of the vertices in DAC, vertex a precedes vertex b whenever a directed edge exists from a to b.

Example: Topological Sort Algorithm

Algorithm getTopologicalOrder() {
  vertexStack = stack to hold verticies as they're visited;
  numberOfVertices = number of vertices on the stack;
  for (counter = 1 to numberOfVertices) {
      nextVertex = anunvisited vertex whose neighbors, if any, are all visited
      Mark nextVertex as visited
      vertexStack.push(nextVertex)
  }
  return vertexStack;
}

• Note How this returns a stack (pop items off to get the right order)

Real-World Example: Project Management

Shortest Path

Note: Unweighted Graph

• In an unweighted graph, we can find all traversals and pick the one with the smallest length.

Data Structure for Vertices:

1. Vertex Label
2. Path Length
3. Predecessor

Data Structure for Paths:

• We store paths as stacks.

Example: Algorithm to get shortest path of unweighted graph

Algorithm getShortestPath(originVertex, endVertex, path) {
  done = false;
  vertexQueue;
  Mark originVertex as visited
  // Traverse (kinda like breadth-first_
  while (!done && frontVettex has a neighbor) {
      nextNeighbor = next neighbor of frontVertex;
      if (nextNeighbor is not visited) {
          Mark nextNeighbor as visited
          Set the length of the path to nextNeighbor to 1 + ength of path to frontVertex
          Set the predecessor of nextNeighbor to frontVertex
          vertexQueue.enqueue(nextNeighbor);
      }
      if (nextNeighbor equals endVertex) {
          done = true;
      }
  }
  // Construct shortest path
  pathLength = length of path to endVertex
  path.push(endVertex);
  vertex = endVertex;
  while (vertex has a predecessor) {
      vertex = predecessor of vertex;
      path.push(vertex)
  }
  return pathLength;
}

• If queue is empty, there is no path (disconnected or not there).
• This is basically a simplified version of Dijkstra’s algorithm.
  • To handle weights, we need to use a priority queue.

Graph Interfaces

public interface BasicGraphInterface<T> {
    boolean addVertex(T vertexLabel);
    boolean addEdge(T begin, T end, double edgeWeight);
    boolean addEdge(T begin, T end);
    boolean hasEdge(T begin, T end);
    boolean isEmpty();
    int getNumberOfVertices();
    int getNumberOfEdges();
    void clear();
}

public interface GraphAlgorithmsInterface<T> {
    QueueInterface<T> getBreadthFirstTraversal(T origin);
    QueueInterface<T> getDepthFirstTraversal(T origin);
    StackInterface<T> getTopologicalOrder();
    int getShortestPath(T begin, T end, StackInterface<T> path);
    double getCheaprestPath(T begin, T end, StackInterface<T> path);
}

Implementation

Two ways to implement graph:

1. Array: A two-dimensional square array.
   • Adjacency matrix.
   • Rows and columns represent nodes, and values are set to true and false to indicate adjacency.
2. List.
   • Adjacency list.
   • Basically just give each label a list of adjacent nodes.

Vertices and Edges

What the Vertex class needs:

• Identify vertices
• Visit vertices
• Adjacency list
• Path operations

Vertex interface:

public interface VertexInterface<T> {
    T getLabel();
    void visit();
    void unvisit();
    boolean isVisited();
    boolean connect(VertexInterface<T> endVertex, double edgeWeight);
    boolean connect(VertexInterface<T> endVertex);
    Iterator<VertexInterface<T>> getNeighborIterator();
    Iterator<Double> getWeightIterator();
    boolean hasNeighbor();
    VertexInterface<T> getUnvisitedNeighbor();
    void setPredecessor(VertexInterfac<T> predecessor);
    VertexInterface<T> getPredecessor();
    boolean hasPredecessor();
    void setCost(double newCost);
    double getCost();
}

Edge inner-class:

protected class Edge {
    private VertexInterface<T> vertex; // Vertex at end of edge
    private double weight;
    protected Edge(VertexInterface<T> endVertex, double edgeWeight) {
        vertex = endVertex;
        weight = edgeWeight;
    }
    protected Edge(VertexInterface<T> endVertex) {
        vertex = endVertex;
        weight = 0;
    }
    protected VertexInterface<T> getEndVertex() {
        return vertex;
    }
    protected double getWeight() {
        return weight;
    }
}

Directed graph:

public class DirectedGraph<T> implements GraphInterface<T> {
    private DictionaryInterface<T> VertexInterface<T>> vertices;
    private int edgeCount;
    public DirectedGraph() {
        vertices = new LinkeDictionary<>();
        edgeCount = 0;
    }
}

Important: Remember to check if getCost() returned no path every time you use it.

Digraph: A set of distinct vertices and distinct edges.

• Dictionary of vertices

• Only Java class we’re allowed to use is the list, every other thing needs to be implemented by us.