Algorithms

Java Graph Implementation with Search Methods

import java.util.HashMap; import java.util.LinkedList;

public class Chart {

   static class Employee {
       int id;
       String firstName;
       String lastName;
       String jobTitle;
       boolean mapped;

       Employee(int id, String fn, String ln, String jt) {
           this.id = id;
           this.jobTitle = jt;
           this.firstName = fn;
           this.lastName = ln;
       }

       void map() {
           mapped = true;
       }

       void unmap() {
           mapped = false;
       }
   }

   private final HashMap<Employee, LinkedList<Employee>> assignment;

   public Chart(boolean directed) {
       assignment = new HashMap<>();
   }

   public void addEdgeHelper(Employee a, Employee b) {
       LinkedList<Employee> e = assignment.get(a);
       if (e != null) {
           assignment.remove(b);
       } else
           e = new LinkedList<>();
       e.add(b);
       assignment.put(a, e);
   }

   public void addEdge(Employee boss, Employee subordinate) {
       if (!assignment.containsKey(boss))
           assignment.put(boss, null);
       if (!assignment.containsKey(subordinate))
           assignment.put(subordinate, null);
       addEdgeHelper(boss, subordinate);
   }

   public void depthFirstSearch(Employee employee) {
       employee.map();
       System.out.println(employee.firstName + " " + employee.lastName + " is a " + employee.jobTitle);
       LinkedList<Employee> neighbors = assignment.get(employee);
       if (neighbors == null)
           return;
       for (Employee e : neighbors) {
           if (!e.mapped)
               depthFirstSearch(e);
       }
   }

   public void breadthFirstSearch(Employee employee) {
       /*Check if target item is null - if so quit*/
       if (employee == null)
           return;
       /*Declare a queue using LinkedList and add the target item*/
       LinkedList<Employee> queue = new LinkedList<>();
       queue.add(employee);
       /*As long as the queue has data get the first in item .removeFirst*/
       while (!queue.isEmpty()) {
           Employee currentFirst = queue.removeFirst();
           /*If visited move on*/
           if (currentFirst.mapped) {
               continue;
           } else {
               /*else visit it and print it*/
               currentFirst.map();

               System.out.println(currentFirst.id + ": " + currentFirst.firstName + " " + currentFirst.lastName + " - " + currentFirst.jobTitle);
           }
           /*Find neighbors of the current item*/
           LinkedList<Employee> allNeighbors = assignment.get(currentFirst);
           /*If there are none move on*/
           if (allNeighbors == null)
               continue;
           /*else if there are some and not visited, add them to the queue and the process starts over*/
           for (Employee e : allNeighbors) {
               if (!e.mapped)
                   queue.add(e);
           }
       }
   }

   public void resetMapping() {
       for (Employee e : assignment.keySet()) {
           e.unmap();
       }
   }

   public static void main(String args[]) {
       Employee a = new Employee(38, "Jimbo", "Jones", "President");
       Employee b = new Employee(39, "Mike", "McCobb", "VP");
       Employee c = new Employee(43, "Elda", "Two", "VP");
       Employee d = new Employee(48, "Simon", "Sneeth", "VP");
       Employee e = new Employee(56, "Tim", "Scott", "Manager");
       Employee f = new Employee(58, "Bob", "Tilman", "Manager");

       Employee g = new Employee(78, "Andrew", "Cole", "Analyst");
       Employee h = new Employee(83, "Matt", "Lemon", "Analyst");
       Employee i = new Employee(88, "Chris", "Lock", "Analyst");
       Employee j = new Employee(71, "Agnes", "White", "Accountant");

       Employee k = new Employee(61, "George", "Mills", "Manager");
       Employee l = new Employee(59, "Thomas", "Wells", "Manager");
       Employee m = new Employee(63, "Zip", "Two", "Manager");
       Employee n = new Employee(73, "Rasta", "Him", "Technician");

       Employee o = new Employee(89, "Claire", "Collins", "Supervisor");
       Employee p = new Employee(95, "Jim", "Four", "Receptionist");
       Employee q = new Employee(104, "Tom", "Flat", "Receptionist");

       Employee r = new Employee(64, "Grace", "Marks", "Manager");
       Employee s = new Employee(68, "Dan", "Four", "Manager");

       Employee t = new Employee(117, "Shad", "Fifty", "Security");
       Employee u = new Employee(108, "Tall", "Nephew", "Legal");
       Employee v = new Employee(109, "Short", "Nephew", "Legal");

       Chart chart = new Chart(true);
       chart.addEdge(a, b);
       chart.addEdge(a, c);
       chart.addEdge(a, d);
       chart.addEdge(b, e);
       chart.addEdge(b, f);
       chart.addEdge(e, g);
       chart.addEdge(e, h);
       chart.addEdge(e, i);
       chart.addEdge(f, j);
       chart.addEdge(c, k);
       chart.addEdge(c, l);
       chart.addEdge(c, m);
       chart.addEdge(l, n);
       chart.addEdge(k, o);
       chart.addEdge(o, p);
       chart.addEdge(o, q);
       chart.addEdge(d, r);
       chart.addEdge(d, s);
       chart.addEdge(s, t);
       chart.addEdge(r, u);
       chart.addEdge(r, v);
       //System.out.println(a.firstName + " " + a.lastName + " " + a.jobTitle + " " + a.id);
       chart.resetMapping();
       //chart.depthFirstSearch(k);

       chart.resetMapping();
       chart.breadthFirstSearch(a);
   }

}