Examples

• 0

  breadth first search

  edit move example delete share

  0

  import java.util.Collections;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  
  /**
   * @author ahmed mazher
   */
  public class LearnBFS {
  
      public LearnBFS() {
          //creating nodes
          Node n1 = new Node("one");
          Node n2 = new Node("two");
          Node n3 = new Node("three");
          Node n4 = new Node("four");
          Node n5 = new Node("five");
          //linking node
          n1.childs.add(n2);
          n1.childs.add(n3);
          n2.childs.add(n1);
          n2.childs.add(n3);
          n2.childs.add(n4);
          n3.childs.add(n2);
          n3.childs.add(n5);
          n4.childs.add(n1);
          n4.childs.add(n3);
          n5.childs.add(n3);
          n5.childs.add(n2);
          //find path
          BFS b = new BFS();
          for (Node n : b.findPath(n1, n5)) {
              System.out.print(n.val.toString() + ",");//one,three,five,
          }
          System.out.println();
          for (Node n : b.findPath(n3, n1)) {
              System.out.print(n.val.toString() + ",");//three,two,one,
          }
      }
      
  }
  
  /**
   * node of adirected cyclic graph
   *
   */
  class Node {
  
      List<Node> childs = new LinkedList<>();//list of child nodes of this node
      Object val;//the value that node carry 
      VisitData visitData = new VisitData();//carry information of the visit to the node
  
      public Node(Object val) {
          this.val = val;
      }
  
  }
  
  class BFS {
  
      long searchId = -1;//id of search process
  
      List<Node> findPath(Node start, Node end) {
          searchId *= -1;//switch search id between 1 & -1 so that new search will
                  // not confuse with old one this will overcome the problem of 
                  //rendering the graph useless after one search process or the 
                  //need to reset the visit status of all nodes before making new 
                  //search also more efficient than using has map to keep track of 
                  //the visited node >> you can implement your own suitable technique
          //queue are the method used to perform BFS 
          //they are first in first out data structure
          //so during search we will get the start node then the first level childs
          //then the second level childs and so on
          Queue<Node> searchQueue = new LinkedList<>();
          searchQueue.add(start);//add the start node to the queue to explore its childs
          start.visitData.visitorId = searchId;//mark the node as been visited
          while (!searchQueue.isEmpty()) {//continue till no more nodes in the queue meaning all node has been explored
              Node current = searchQueue.poll();//remove node from the queue note that this is the oldest node in the queue 
              if (current.equals(end)) {//if this node equal end node will we have done
                  return constructPath(start, end);//build the path from end node to start node using visit information
              } else {//explore the children
                  for (Node child : current.childs) {
                      if (child.visitData.visitorId != searchId) {//if the child wasn't visited before visit it
                          //during the visit do the following
                          searchQueue.add(child);//add the node to the queue to test its equality to end node
                          //and explore its children later on
                          child.visitData.mother = current;//make the mother node of this child  the current node 
                          child.visitData.visitorId = searchId;//mark the node as been visited by current search id
                      }
                  }
              }
          }
          return null;
      }
  
      private List<Node> constructPath(Node start, Node end) {
          //when end node found build the pass from it to start node 
          //using the mother information in the visitData object
          Node current = end;
          List<Node> temp = new LinkedList<>();
          while (!current.equals(start)) {//loop till reaching start node
              temp.add(current);
              current = current.visitData.mother;
          }
          temp.add(start);//add the start node 
          //note that the list now starting from end node and ending by end start
          Collections.reverse(temp);//reverse the list
          return temp;
      }
  
  }
  
  class VisitData {
  
      long visitorId;//the id of the search algorithm visiting the node
      Node mother;//the node that we came from to reach this node during the search process
  
  }
  

  modification of previous technique to store search information

  import java.util.Collections;
  import java.util.HashMap;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  
  /**
   * @author ahmed mazher
   */
  public class LearnBFS {
  
      public LearnBFS() {
          //creating nodes
          Node n1 = new Node("one");
          Node n2 = new Node("two");
          Node n3 = new Node("three");
          Node n4 = new Node("four");
          Node n5 = new Node("five");
          //linking node
          n1.childs.add(n2);
          n1.childs.add(n3);
          n2.childs.add(n1);
          n2.childs.add(n3);
          n2.childs.add(n4);
          n3.childs.add(n2);
          n3.childs.add(n5);
          n4.childs.add(n1);
          n4.childs.add(n3);
          n5.childs.add(n3);
          n5.childs.add(n2);
          BFS b = new BFS();
          for (Node n : b.findPath(n1, n5)) {
              System.out.print(n.val.toString() + ",");//one,three,five,
          }
          System.out.println();
          for (Node n : b.findPath(n3, n1)) {
              System.out.print(n.val.toString() + ",");//three,two,one,
          }
      }
  
  }
  
  /**
   * node of adirected cyclic graph
   *
   */
  class Node {
  
      List<Node> childs = new LinkedList<>();//list of child nodes of this node
      Object val;//the value that node carry 
      //carry information of the visit to the node
      HashMap<Long, VisitData> visitData = new HashMap<>();//keep history of all searches
  
      public Node(Object val) {
          this.val = val;
      }
  
  }
  
  class BFS {
  
      private long searchId = 0;//id of search process
  
      List<Node> findPath(Node start, Node end) {
          searchId++;//give new id to perform new search >> or you can implement 
                  //you own suitable technique so that new search will
                  // not confuse with old one this will overcome the problem of 
                  //rendering the graph useless after one search process or the 
                  //need to reset the visit status of all nodes before making new 
                  //search also more efficient than using has map to keep track of 
                  //the visited node >> you can implement your own suitable technique
          //queue are the method used to perform BFS 
          //they are first in first out data structure
          //so during search we will get the start node then the first level childs
          //then the second level childs and so on
          Queue<Node> searchQueue = new LinkedList<>();
          searchQueue.add(start);//add the start node to the queue to explore its childs
          start.visitData.put(searchId, new VisitData(null));//mark the start node as been visited having no mother
          while (!searchQueue.isEmpty()) {//continue till no more nodes in the queue meaning all node has been explored
              Node current = searchQueue.poll();//remove node from the queue note that this is the oldest node in the queue 
              if (current.equals(end)) {//if this node equal end node will we have done
                  return constructPath(start, end, searchId);//build the path from end node to start node using visit information
              } else {//explore the children
                  for (Node child : current.childs) {
                      if (!child.visitData.containsKey(searchId)) {//if the child wasn't visited before visit it
                          //during the visit do the following
                          searchQueue.add(child);//add the node to the queue to test its equality to end node
                          //and explore its children later on
                          child.visitData.put(searchId, new VisitData(current));
                          //make the mother node of this child  the current node 
                          //mark the node as been visited by current search id by adding this 
                          //search id to the visitdata hashmap along with visitdata object carrying necessary data
                          //
                      }
                  }
              }
          }
          return null;
      }
  
      private List<Node> constructPath(Node start, Node end, long searchId) {
          //when end node found build the pass from it to start node 
          //using the mother information in the visitData object
          Node current = end;
          List<Node> temp = new LinkedList<>();
          while (!current.equals(start)) {//loop till reaching start node
              temp.add(current);//add current step to the path
              current = current.visitData.get(searchId).mother;//go up one step
          }
          temp.add(start);//add the start node 
          //note that the list now starting from end node and ending by end start
          Collections.reverse(temp);//reverse the list
          return temp;
      }
  
  }
  
  class VisitData {
  
      Node mother;//the node that we came from to reach this node during the search process
  
      
      public VisitData(Node mother) {
          this.mother = mother;
      }
  
  }
  

  created yesterday

  
• 0

  Dijkstra's algorithm

  edit move example delete share

  0

  Dijkstra's algorithm is an algorithm for solving Single Source Shortest Path problem which is to find shortest paths from a source vertex v to all other vertices in the graph.

  Python(2.7.11) example

  Implementation:

  from heapq import heappop, heappush
  
  inf = float('inf')
  def dijkstra(G, s): # G is graph and G[u][v] is distance between u and v, and s is the source vertex
      D, Q, S = {s:0}, [(0,s)], set() # After algorithm terminated, D[u] is the shortest distance between s and u
      while Q:
          dummy, u = heappop(Q)
          if u in S:
              continue
          S.add(u)
          for v in G.get(u, {}):
              d = D.get(u, inf) + G[u][v]
              if d < D.get(v, inf):
                  D[v] = d
              heappush(Q, (D[v], v))
      return D
  

  Test:

  G = {
      'a': {'b': 1, 'c': 5},
      'b': {'c': 2, 'd': 2},
      'c': {'a': 2, 'b': 3},
      'd': {'a': 1, 'c': 3}
  }
  
  print dijkstra(G, 'a')
  

  Output:

  {'a': 0, 'c': 3, 'b': 1, 'd': 3}
  

  That means the distance from a to a is 0 and from a to b is 1 and so on.

  created Jul 22 at 12:04

  
• 0

  Floyd–Warshall algorithm

  edit move example delete share

  0

  Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge between all vertex pairs.

  Python(2.7.11) example

  Implementation:

  from copy import deepcopy
  
  inf = float('inf')
  def floyd_warshall(G): # G is graph and G[u][v] is distance between u and v, and s is the source vertex
      D = deepcopy(G)  # After algorithm terminated, D[u][v] is the shortest distance between u and v
      for v in D:
          D[v][v] = 0
      for k in D:
          for u in D:
              for v in D:
                  D[u][v] = min(D[u].get(v, inf), D[u].get(k, inf) + D[k].get(v, inf))
      return D
  

  Test:

  G = {
      'a': {'b': 1, 'c': 5},
      'b': {'c': 2, 'd': 2},
      'c': {'a': 2, 'b': 3},
      'd': {'a': 1, 'c': 3},
  }
  
  print floyd_warshall(G)
  

  Output:

  {'a': {'a': 0, 'c': 3, 'b': 1, 'd': 3}, 'c': {'a': 2, 'c': 0, 'b': 3, 'd': 5}, 'b': {'a': 3, 'c': 2, 'b': 0, 'd': 2}, 'd': {'a': 1, 'c': 3, 'b': 2, 'd': 0}}
  

  That means the distance from a to c is 3 and from c to a is 2 and so on.

  edited Jul 22 at 14:47

  
• 0

  Topological Sort

  edit move example delete share

  0

  A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right on a line and still return back to where you started from.

  Formally, in a graph G = (V, E), then a linear ordering of all its vertices is such that if G contains an edge (u, v) ∈ Efrom vertex u to vertex v then u precedes v in the ordering.

  It is important to note that each DAG has at least one topological sort.

  There are known algorithms for constructing a topological ordering of any DAG in linear time, one example is:

  1. Call depth_first_search(G) to compute finishing times v.f for each vertex v
  2. As each vertex is finished, insert it into the front of a linked list
  3. the linked list of vertices, as it is now sorted.

  A topological sort can be performed in ϴ(V + E) time, since the depth-first search algorithm takes ϴ(V + E) time and it takes Ω(1) (constant time) to insert each of |V| vertices into the front of a linked list.

  ---

  Many applications use directed acyclic graphs to indicate precedences among events. We use topological sorting so that we get an ordering to process each vertex before any of its successors.

  Vertices in a graph may represent tasks to be performed and the edges may represent constraints that one task must be performed before another; a topological ordering is a valid sequence to perform the tasks set of tasks described in V.

  Problem instance and its solution

  Let a vertice v describe a Task(hours_to_complete: int), i. e. Task(4) describes a Task that takes 4 hours to complete, and an edge e describe a Cooldown(hours: int) such that Cooldown(3) describes a duration of time to cool down after a completed task.

  Let our graph be called dag (since it is a directed acyclic graph), and let it contain 5 vertices:

  A <- dag.add_vertex(Task(4)); 
  B <- dag.add_vertex(Task(5));
  C <- dag.add_vertex(Task(3)); 
  D <- dag.add_vertex(Task(2));
  E <- dag.add_vertex(Task(7));
  

  where we connect the vertices with directed edges such that the graph is acyclic,

  // A ---> C ----+
  // |      |     |
  // v      v     v
  // B ---> D --> E
  dag.add_edge(A, B, Cooldown(2));
  dag.add_edge(A, C, Cooldown(2));
  dag.add_edge(B, D, Cooldown(1));
  dag.add_edge(C, D, Cooldown(1));
  dag.add_edge(C, E, Cooldown(1));
  dag.add_edge(D, E, Cooldown(3));
  

  then there are three possible topological orderings between A and E,

  1. A -> B -> D -> E
  2. A -> C -> D -> E
  3. A -> C -> E

  edited Jul 22 at 15:04