Figure (Graphs)

Graph (Graph)

In computer science, a graph is defined as a set of points paired with a set of edges. Edges can be weighted or directed.

There are two main strategies for describing diagrams in code; Adjacency list and adjacency matrix

The Adjacency List. In an adjacency list implementation, each point stores a list of all edges starting from that point.

The Adjacency Matrix. In an adjacency matrix implementation, a matrix with rows and columns representing vertices stores weights to indicate whether the vertices are linked and the weights.

Let V be the number of points in the graph and E be the number of edges. We have a

operation Adjacency list Adjacency matrix
The storage space O(V + E) O(V^2)
Add some O(1) O(V^2)
Add Edge O(1) O(1)
Add edge O(1) O(1)
Check the adjacency O(V) O(1) 
public struct Edge<T> :Equatable where T: Equatable.T: Hashable {
  
  public let from: Vertex<T>
  public let to: Vertex<T>
  
  public let weight: Double?
  
}
Copy the code
public struct Vertex<T> :Equatable where T: Equatable.T: Hashable {
  public var data: T
  public let index: Int
}
Copy the code

Code: adjacency list

private class EdgeList<T> where T: Equatable.T: Hashable {
	var vertex: Vertex<T>
  var edges: [Edge<T>]? = nil
  
  init(vertex: Vertex<T>) {
    self.vertex = vertex
  }
  
  func addEdge(_ edge: Edge<T>) {
    edges.append(edge)
  }
}
Copy the code
open override func createVertex(_ data: T) -> Vertex<T> {
  // check if the vertex already exists
  let matchingVertices = vertices.filter() { vertex in
  	return vertex.data = data
  }
  
  if matchingVertices.count > 0 {
    return matchingVertices.last!
  }
  
  // if the vertex doesn't exist, creat a new one
  let vertex = Vertex(data: data, index: adjacencyList.count)
  adjcencyList.append(EdgeList(vertex: vertex))
  return vertex
}
Copy the code

Code: adjacency matrix

open override func createVertex(_ data: T) -> Vertex<T> {
  // check if the vertex already exist
  let matchingVertices = vertices.filter() { vertex in
    return vertex.data = data
  }
  
  if matchingVertices.count > 0 {
    return matchingVertices.last!
  }
  
  // if the vertex doesn't exist, create a new one
  let vertex = Vertex(data: data, index: adjacencyMatrix.count)
  
  // Expand each existing row to the right one column.
  for i in 0 ..< adjacencyMatrix.count {
    adjacencyMatrix[i].append(nil)}// Add one new row at the bottom.
  let newRow = [Double? ] (repeating:nil, count: adjacencyMatrix.count + 1)
  adjacencyMatrix.append(newRow)
  
  _vertices.append(vertex)
  
  return vertex
}
Copy the code

Breadth-first search

Implementation of queues

func breadthFirstSearch(_ graph: Graph.source: Node)- > [String] {
  var queue = Queue<Node>()
  queue.enqueue(source)
  
  var nodesExplored = [source.label]
  source.visited = true
  
  while let node = queue.dequeue() {
    for edge in node.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        queue.enqueue(neighborNode)
        beighborNode.visited = true
        nodesExplored.append(neighborNode.label)
      }
    }
  }
  
  return nodesExplored
}
Copy the code

BFS can be used to solve

  • Computes the shortest path between the source node and every other node (only for unweighted graphs).
  • Compute the minimum spanning tree on an unweighted graph

Depth-first search

Simple recursive implementation

func depthFirstSearch(_ graph: Graph.source: Node)- > [String] {
  var nodesExpored = [Source.label]
  source.visited = true
  
  for edge in source.neighbors {
    if !edge.neighbor.visited {
      nodesExplored + = depthFirstSearch(graph, source: edge.neighbor)
    }
  }
  return nodesExplored
}
Copy the code

It can also be implemented using stacks

DFS can be used to solve

  • Find the connected component of the sparse graph
  • Topological ordering of nodes in a graph
  • Find the bridge of the graph
  • more

Shortest path to an unweighted graph

Goal: Find the shortest path from one node to another in the graph

Unweighted graph: breadth-first search

func breadthFirstSearchShortestPath(graph: Graph.source: Node) -> Graph {
  let shortestPathGraph = graph.duplicate()

  var queue = Queue<Node> ()let sourceInShortestPathsGraph = shortestPathGraph.findNodeWithLabel(label: source.label)
  queue.enqueue(element: sourceInShortestPathsGraph)
  sourceInShortestPathsGraph.distance = 0

  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.hasDistance {
        queue.enqueue(element: neighborNode)
        neighborNode.distance = current.distance! + 1}}}return shortestPathGraph
}
Copy the code

Single source shortest path

The single-source shortest path problem is the shortest path from a given source vertex to all other vertices in a directed weighted graph.

Bellman-Ford

U is the source vertex, v is the target vertex of the directed edge, e = (u, v).

U remains 0 and the other vertices start at ♾

if weights[v] > weights[u] + e.weight {
  weights[v] = weights[u] + e.weight
}
Copy the code

Minimum spanning tree tree of unweighted graphs

Depth-first search

func breadthFirstSearchMinimumSpanningTree(graph: Graph.source: Node) -> Graph {
  let minimumSpanningTree = graph.duplicate()
  
  var queue = Queue<Node> ()let sourceInMinimumSpanningTree = minimumSpanningTree.findNodeWithLabel(source.label)
  queue.enqueue(sourceInMinimumSpanningTree)
  sourceInMinimumSpanningTree.visited = true
  
  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        neighborNode.visited = true
        queue.enqueue(neighborNode)
      } else {
        current.remove(edge)
      }
    }
  }
  
  return minimumSpanningTree
}
Copy the code

Minimum spanning tree

Kruskal algorithm

Sort edges by weight. Greedily select the smallest one at a time and join MST as long as it does not form a ring.

To prepare

// Initialize the values to be returned and Union Find data structure.
var cost: Int = 0
var tree = Graph<T> ()var unionFind = UnionFind<T> ()for vertex in graph.vertices {

// Initially all vertices are disconnected.
// Each of them belongs to it's individual set.
  unionFind.addSetWith(vertex)
}
Copy the code

Edge:

let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < The $1.weight })
Copy the code

Take one edge at a time and try to insert it into the MST.

for edge in sortedEdgeListByWeight {
  let v1 = edge.vertex1
  let v2 = edge.vertex2 
  
  // Same set means the two vertices of this edge were already connected in the MST.
  // Adding this one will cause a cycle.
  if !unionFind.inSameSet(v1, and: v2) {
    // Add the edge into the MST and update the final cost.
    cost + = edge.weight
    tree.addEdge(edge)
    
    // Put the two vertices into the same set.
    unionFind.unionSetsContaining(v1, and: v2)
  }
}
Copy the code

Prim algorithm

To prepare

// Initialize the values to be returned and Priority Queue data structure.
var cost: Int = 0
var tree = Graph<T> ()var visited = Set<T> ()// In addition to the (neighbour vertex, weight) pair, parent is added for the purpose of printing out the MST later.
// parent is basically current vertex. aka. the previous vertex before neigbour vertex gets visited.
var priorityQueue = PriorityQueue<(vertex: T, weight: Int, parent: T?). >(sort: {$0.weight < The $1.weight })
Copy the code

Sort vertices:

priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))
Copy the code
// Take from the top of the priority queue ensures getting the least weight edge.
while let head = priorityQueue.dequeue() {
  let vertex = head.vertex
  if visited.contains(vertex) {
    continue
  }

  // If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.
  visited.insert(vertex)
  cost + = head.weight
  if let prev = head.parent { // The first vertex doesn't have a parent.
    tree.addEdge(vertex1: prev, vertex2: vertex, weight: head.weight)
  }

  // Add all unvisted neighbours into the priority queue.
  if let neighbours = graph.adjList[vertex] {
    for neighbour in neighbours {
      let nextVertex = neighbour.vertex
      if !visited.contains(nextVertex) {
        priorityQueue.enqueue((vertex: nextVertex, weight: neighbour.weight, parent: vertex))
      }
    }
  }
}
Copy the code

The shortest path between any two points

The shortest path between any two points simultaneously computes the shortest path from each node to other nodes in the graph.

Floyd – Warshall algorithm


d i j ( k ) = { w i j . k = 0 m i n ( d i j ( k – 1 ) . d i k ( k – 1 ) + d k j ( k – 1 ) ) . k p 1 d_{ij}^{(k)} = \left\{ \begin{aligned} & w_{ij} & ,k=0\\ & min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}) & ,k\ge1\\ \end{aligned} \right.

Informally, an adjacency matrix records the direct distance between any two points. In turn, let’s go through the first vertex and update the adjacency matrix; Allow to update the adjacency matrix through the first and second points…

Dijkstra shortest path algorithm

This is used when you have a source vertex and want to find the shortest path to all the other vertices in the graph.

First, create a class to describe any vertices in the graph

open class Vertex {
  
  //Every vertex should be unique that's why we set up identifier
  open var identifier: String
  
  //For Dijkstra every vertex in the graph should be connect with at least one other vertex.But there can be some usecases
  //when you firstly initialize all vertices without neighbours. And then on next iteration you set up their neighbours. So, initially neighbours is an empty array.
  //Array contains tuples (Vertex, Double). Vertex is a neighbour and and Double is as edge weight to that neighbour.
  open var neighbours: [(Vertex.Double)] = []
  
  //As it was mentioned in the algorithm description, default path length from start for all vertices should be as much as possible.
  //It is var because we will update it during the algorith execution.
  open var pathLengthFromStart = Double.infinity
  
  //This array contains vertices which we need to go through to reach this vertex from starting one
  //As with path length from start, we will change this array during the algorithm execution.
  open var pathVerticesFromStart: [Vertex] = []
  
  public init(identifier: String) {
    self.identifier = identifier
  }
  
  //This function let us use the same array of vertices again and again to calculate paths with different starting vertex.
  //When we will need to set new starting vertex and recalculate paths then we will simply clear graph vertices' cashes.
  open func clearCache(a) {
    pathLengthFromStart = Double.infinity
    pathVerticesFromStart =[]}}Copy the code

Since each vertex should be unique, it is useful to set them to Hashable and according to Equatable.

extension Vertex: Hashable {
  open var hashValue: Int {
    return identifier.hashValue
  }
}

extension Vertex: Equatable {
  public static func = =(lhs: Vertex.res: Vertex) -> Bool {
    return lhs.hashValue = = rhs.hashValue
  }
}
Copy the code
public class Dijkstra {
    //This is a storage for vertices in the graph.
    //Assuming that our vertices are unique we can use Set instead of array. This approach will bring some benefits later.
    private var totalVertices: Set<Vertex>

    public init(vertices: Set<Vertex>) {
        totalVertices = vertices
    }

    //Remember clearCache function in the Vertex class implementation?
    //This is just a wrapper that cleans cache for all stored vertices.
    private func clearCache(a) {
        totalVertices.forEach { $0.clearCache() }
    }

    public func findShortestPaths(from startVertex: Vertex) {
	//Before we start searching the shortest path from startVertex,
	//we need to clear vertices cache just to be sure that out graph is clean.
	//Remember that every Vertex is a class and classes are passed by reference.
	//So whenever you change vertex outside of this class it will affect this vertex inside totalVertices Set
        clearCache()
	//Now all our vertices have Double.infinity pathLengthFromStart and an empty pathVerticesFromStart array.

	//The next step in the algorithm is to set startVertex pathLengthFromStart and pathVerticesFromStart
        startVertex.pathLengthFromStart = 0
        startVertex.pathVerticesFromStart.append(startVertex)

	//Here starts the main part. We will use while loop to iterate through all vertices in the graph.
	//For this purpose we define currentVertex variable which we will change in the end of each while cycle.
        var currentVertex: Vertex? = startVertex

        while let vertex = currentVertex {

    	    //Next line of code is an implementation of setting vertex as visited.
    	    //As it has been said, we should check only unvisited vertices in the graph,
	    //So why don't just delete it from the set? This approach let us skip checking for *"if ! vertex.visited then"*
            totalVertices.remove(vertex)

	    //filteredNeighbours is an array that contains current vertex neighbours which aren't yet visited
            let filteredNeighbours = vertex.neighbours.filter { totalVertices.contains($0.0)}//Let's iterate through them
            for neighbour in filteredNeighbours {
		//These variable are more representative, than neighbour.0 or neighbour.1
                let neighbourVertex = neighbour.0
                let weight = neighbour.1

		//Here we calculate new weight, that we can offer to neighbour.
                let theoreticNewWeight = vertex.pathLengthFromStart + weight

		//If it is smaller than neighbour's current pathLengthFromStart
		//Then we perform this code
                if theoreticNewWeight < neighbourVertex.pathLengthFromStart {

		    //set new pathLengthFromStart
                    neighbourVertex.pathLengthFromStart = theoreticNewWeight

		    //set new pathVerticesFromStart
                    neighbourVertex.pathVerticesFromStart = vertex.pathVerticesFromStart

		    //append current vertex to neighbour's pathVerticesFromStart
                    neighbourVertex.pathVerticesFromStart.append(neighbourVertex)
                }
            }

	    //If totalVertices is empty, i.e. all vertices are visited
	    //Than break the loop
            if totalVertices.isEmpty {
                currentVertex = nil
                break
            }

	    //If loop is not broken, than pick next vertex for checkin from not visited.
	    //Next vertex pathLengthFromStart should be the smallest one.
            currentVertex = totalVertices.min { $0.pathLengthFromStart < The $1.pathLengthFromStart }
        }
    }
}
Copy the code

Dijkstra’s algorithm is based on [breadth first] [greedy] [dynamic programming].

Bellman-ford’s advantage is that it can be used to determine the presence of negative rings.

A * algorithm

Wall cracks recommend www.redblobgames.com/pathfinding…

The A* algorithm calculates the priority of each node by using the following function


f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n)

Among them:

  • F (n) is the comprehensive priority of node N. When we choose the next node to traverse, we always select the node with the highest overall priority (lowest value).
  • G (n) is the cost of the distance between node n and the starting point.
  • H (n) is the estimated cost of node N from the end point, which is also the heuristic function of A* algorithm.

This formula follows the following properties:

  • ifg(n)Is 0, then the algorithm is transformed into the best-first search using greedy strategy, which has the fastest speed, but may not get the optimal solution
  • ifh(n)Is not greater than the actual distance between vertex N and the target vertex, then the optimal solution can be obtained, andh(n)The smaller the size is, the more nodes need to be calculated and the lower the efficiency of the algorithm. Common evaluation functions include Euclid distance, Manhattan distance and Chebyshev distance
  • ifh(n)Is 0, then it is converted to single-source shortest path problem (SSSP), that is, Dijkstra algorithm, in which the most vertices need to be calculated.
/ / the Matlab languagefunction A*(start,goal)Openset := set containing the initial node // Start came_from := empty map g_score[start] :=0//g(n) h_score[start] := heuristic_estimate_of_distance(start, Goal) / / by estimating function h (start) f_score [start] : = h_score [start] / / f (n) = h (n) + g (n), g (n) =0, so omitwhileOpenset is not empty // When the node to be estimated exists, X := the node in openSet having the lowest f_score[] value // Find the node with the lowest f(x) in the set to be estimatedifX = goal // If x is the end, executereturnReconstruct_path (came_from,goal) // Best path to return to x remove x from openSet add X to closedset insert X into the already estimated nodeforEach y in neighbor_nodes(x) // Loops over adjacent nodes with XifY in closedset // If y is already valued, skipcontinueTentative_g_score := g_score[x] + dist_between(x,y) // The distance from the starting point to node YifY not in openset // If y is not the node to be estimated tentative_is_better :=true// For now it is betterelseifTentative_g_score < g_score[y] // If the distance from the starting point to Y is smaller than the actual distance from y, tentative_is_Better :=true// For now it is betterelse
                 tentative_is_better := false// Otherwise, it is judged as worseif tentative_is_better = trueCame_from [y] := x // set y to g_score[y] := tentative_g_score // update y to 0 h_score[y] := heuristic_estimate_of_distance(y, F_score [y] := g_score[y] + h_score[y] add y to openSet // Insert y into nodes to be estimatedreturn failure
 
 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return current_node
Copy the code

Rapid-exploring Random Trees (RRT)