Undirected Weighted Graph

package exercises;

import java.util.*;

/**

 * Undirected Weighted Graph

 */

public class UWGraph {

private final String NA = "NA";

private final String NEIGHBOUR = "NEIGHBOUR";

private HashMap vertexMap = new HashMap<>();

private List vertices = new ArrayList<>();

public Vertex addVertex(String key) {

return this.addVertex(key, null);

}

public synchronized Vertex addVertex(String key, HashMap payload) {

if(vertexMap.containsKey(key)) return this.getVertex(key);

Vertex vertex = new Vertex(this.vertices.size() + 1, key, payload);

this.vertices.add(vertex);

this.vertexMap.put(key, vertex.getId());

return vertex;

}

public void addEdge(Edge e, Vertex start, Vertex end) {

if(this.vertexMap.containsKey(start.getKey()) && this.vertexMap.containsKey(end.getKey())) {

this.getVertex(start.getKey()).addAdjacent(end.getId(), e.getWeight());

this.getVertex(end.getKey()).addAdjacent(start.getId(), e.getWeight());

}

}

public int totalVertices() {

return this.vertices.size();

}

public int degree(String vertex) {

if(!this.hasVertex(vertex)) return 0;

return this.getVertex(vertex).degree();

}

public boolean hasVertex(String key) {

return this.vertexMap.containsKey(key);

}

public boolean hasEdge(String start, String end) {

return this.hasVertex(start) && this.hasVertex(end) && 

this.getVertex(start).hasEdgeTo(this.getVertexId(end));

}

public String getEdges(String vertex) {

return this.getVertex(vertex).toString();

}

public void dfs(String key) {

Vertex v = this.getVertex(key);

Stack<int[]> children = new Stack<>();

List visited = new ArrayList<>();

if(v == null) return;

List<int[]> adjacents = v.getAdjacents();

if(adjacents == null || adjacents.size() <= 0) return;

children.addAll(adjacents);

while(!children.isEmpty()) {

int vertex = children.pop()[0] - 1;

if(visited.contains(vertex)) continue;

visited.add(vertex); System.out.println("Visited : " + vertex);

List<int[]> childs = this.vertices.get(vertex).getAdjacents();

if(childs != null && childs.size() > 0) children.addAll(childs);

}

}

public void bfs(String key) {

Vertex v = this.getVertex(key);

Queue<int[]> children = new LinkedList<>();

List visited = new ArrayList<>();

if(v == null) return;

List<int[]> adjacents = v.getAdjacents();

if(adjacents == null || adjacents.size() <= 0) return;

children.addAll(adjacents);

while(!children.isEmpty()) {

int vertex = children.poll()[0] - 1;

if(visited.contains(vertex)) continue;

visited.add(vertex); System.out.println("Visited : " + vertex);

List<int[]> childs = this.vertices.get(vertex).getAdjacents();

if(childs != null && childs.size() > 0) children.addAll(childs);

}

}

private Vertex getVertex(String key) {

return this.vertices.get(this.vertexMap.get(key) - 1);

}

private int getVertexId(String key) {

return this.getVertex(key).getId();

}

}

class Vertex {

private int id;

private String key;

private HashMap payload;

private List<int[]> adjacents;

Vertex(int id, String key, HashMap payload) {

this.id = id;

this.key = key;

this.payload = payload;

this.adjacents = new ArrayList<int[]>();

}

List<int[]> getAdjacents() {

return this.adjacents;

}

String getKey() {

return key;

}

void setKey(String key) {

this.key = key;

}

int getId() {

return id;

}

void setId(int id) {

this.id = id;

}

HashMap getPayload() {

return payload;

}

void setPayload(HashMap payload) {

this.payload = payload;

}

void addAdjacent(int vertex, int weight) {

if(!this.hasEdgeTo(vertex)) this.adjacents.add(new int[] { vertex, weight });

}

int degree() {

if(this.adjacents == null || this.adjacents.size() <= 0) return 0;

return this.adjacents.size();

}

boolean hasEdgeTo(int vertex) {

/**

* Use Bloomfilter to check for FALSE_POSITIVE and proceed to avoid linear search

*/

if(this.adjacents == null || this.adjacents.size() <= 0) return false;

for(int[] adjacent : this.adjacents) {

if(adjacent[0] == vertex) return true;

}

return false;

}

@Override

public String toString() {

if(this.adjacents == null || this.adjacents.size() <= 0) return super.toString();

StringBuilder output = new StringBuilder();

output.append(this.getKey() + ":" + "{");

for(int[] adjacent : this.adjacents) {

output.append(adjacent[0] - 1 + " ");

}

output.append("}");

return output.toString();

}

}

class Edge {

private String key;

private int weight;

Edge(String key, int weight) {

this.key = key;

this.weight = weight;

}

int getWeight() {

return weight;

}

void setWeight(int weight) {

this.weight = weight;

}

String getKey() {

return key;

}

void setKey(String key) {

this.key = key;

}

}

/**

* [ [1, 6, 8],

[0, 4, 6, 9],

  [4, 6],

  [4, 5, 8],

  [1, 2, 3, 5, 9],

  [3, 4],

  [0, 1, 2],

  [8, 9],

  [0, 3, 7],

  [1, 4, 7] 

]

*/

public static void demoGraph() {

UWGraph graph = new UWGraph();

Vertex v0 = graph.addVertex("0"); Vertex v1 = graph.addVertex("1"); Vertex v2 = graph.addVertex("2");

Vertex v3 = graph.addVertex("3"); Vertex v4 = graph.addVertex("4"); Vertex v5 = graph.addVertex("5");

Vertex v6 = graph.addVertex("6"); Vertex v7 = graph.addVertex("7"); Vertex v8 = graph.addVertex("8");

Vertex v9 = graph.addVertex("9");

graph.addEdge(new Edge("01", 1), v0, v1); graph.addEdge(new Edge("06", 6), v0, v6); graph.addEdge(new Edge("08", 8), v0, v8);

graph.addEdge(new Edge("10", 10), v1, v0); graph.addEdge(new Edge("14", 14), v1, v4); graph.addEdge(new Edge("16", 16), v1, v6);

graph.addEdge(new Edge("19", 19), v1, v9);

graph.addEdge(new Edge("24", 24), v2, v4); graph.addEdge(new Edge("26", 26), v2, v6);

graph.addEdge(new Edge("34", 34), v3, v4); graph.addEdge(new Edge("35", 35), v3, v5); graph.addEdge(new Edge("38", 38), v3, v8);

graph.addEdge(new Edge("41", 41), v4, v1); graph.addEdge(new Edge("42", 42), v4, v2); graph.addEdge(new Edge("43", 43), v4, v3);

graph.addEdge(new Edge("45", 45), v4, v5); graph.addEdge(new Edge("49", 49), v4, v9);

graph.addEdge(new Edge("53", 53), v5, v3); graph.addEdge(new Edge("54", 54), v5, v4);

graph.addEdge(new Edge("60", 60), v6, v0); graph.addEdge(new Edge("61", 61), v6, v1); graph.addEdge(new Edge("62", 62), v6, v2);

graph.addEdge(new Edge("78", 78), v7, v8); graph.addEdge(new Edge("79", 79), v7, v9); 

graph.addEdge(new Edge("80", 80), v8, v0); graph.addEdge(new Edge("83", 83), v8, v3); graph.addEdge(new Edge("87", 87), v8, v7);

graph.addEdge(new Edge("91", 91), v9, v1); graph.addEdge(new Edge("94", 94), v9, v4); graph.addEdge(new Edge("97", 97), v9, v7);

System.out.println("Vertex 0,  Degree :" + graph.degree(v0.getKey()) + ", Edges : " + graph.getEdges(v0.getKey()));

System.out.println("Vertex 1,  Degree :" + graph.degree(v1.getKey()) + ", Edges : " + graph.getEdges(v1.getKey()));

System.out.println("Vertex 2,  Degree :" + graph.degree(v2.getKey()) + ", Edges : " + graph.getEdges(v2.getKey()));

System.out.println("Vertex 3,  Degree :" + graph.degree(v3.getKey()) + ", Edges : " + graph.getEdges(v3.getKey()));

System.out.println("Vertex 4,  Degree :" + graph.degree(v4.getKey()) + ", Edges : " + graph.getEdges(v4.getKey()));

System.out.println("Vertex 5,  Degree :" + graph.degree(v5.getKey()) + ", Edges : " + graph.getEdges(v5.getKey()));

System.out.println("Vertex 6,  Degree :" + graph.degree(v6.getKey()) + ", Edges : " + graph.getEdges(v6.getKey()));

System.out.println("Vertex 7,  Degree :" + graph.degree(v7.getKey()) + ", Edges : " + graph.getEdges(v7.getKey()));

System.out.println("Vertex 8,  Degree :" + graph.degree(v8.getKey()) + ", Edges : " + graph.getEdges(v8.getKey()));

System.out.println("Vertex 9,  Degree :" + graph.degree(v9.getKey()) + ", Edges : " + graph.getEdges(v9.getKey()));

//graph.dfs("0");

graph.bfs("0");

}

DFS

public class Node
    {
        public int Id { get; set; }

        public String Name { get; set; }

        public String Parent { get; set; }

        [JsonIgnore]
        public bool Visited { get; set; }

        [JsonIgnore]
        public List Children { get; set; }
    }

   public static class TreeManager
    {
        static Node tree = null;

        static TreeManager()
        {
            tree = new Node();
        }

        public static Node Get()
        {
            return tree;
        }
    }

    public static class TestData
    {
        static int id = 1;

        public static Node Initialise()
        {
            var root = TreeManager.Get();

            root.Id = Identifier;
            root.Name = "Root";

            root.Children = CreateDepartment();

            CreateChildren(root.Children, "aisle");
            CreateChildren(root.Children.SelectMany(c => c.Children).ToList(), "shelve");
            //CreateChildren(root.Children.SelectMany(c => c.Children).SelectMany(c => c.Children).ToList(), "sub_shelve");

            return root;
        }

        private static int Identifier
        {
            get
            {
                return id++;
            }
        }

        private static List CreateDepartment()
        {
            string[] departments = new string[]
                        {
                            "Fresh Food", "Level 1 Mos Test", "Food cupboard test",
                            "Frozen food", "Drinks", "Drugstore", "Baby", "Pets", "Home and entertainment"
                        };

            return Create(departments);
        }

        private static void CreateChildren(List nodes, string childName)
        {
            Random seeder = new Random(1);

            foreach (var node in nodes)
            {
                int looper = seeder.Next(1, 10);
                List names = new List();

                while ((looper--) > 0)
                {
                    names.Add(node.Name + "-" + childName + looper.ToString());
                }

                node.Children = new List();

                node.Children.AddRange(Create(names.ToArray()));
            }
        }

        private static List Create(string[] names)
        {
            List nodes = new List();

            foreach (var name in names)
            {
                nodes.Add(new Node { Id = Identifier, Name = name });
            }

            return nodes;
        }
    }

    //http://www.codeproject.com/Articles/32212/Introduction-to-Graph-with-Breadth-First-Search-BF
    //http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first

    public static class DFSTraverse
    {
        static List orderedNodes = new List();

        public static void Traverse(Node tree)
        {
            orderedNodes.Clear();

            Stack stack = new Stack();

            tree.Visited = true;
            Push(stack, tree);
            Print(stack.Peek());

            while (!stack.IsEmpty())
            {
                Node node = GetChildNode(stack.Peek());

                if (node == null) stack.Pop();
                else
                {
                    node.Visited = true;
                    Push(stack, node, stack.Peek().Name);
                    Print(stack.Peek());
                }
            }
        }

        public static string OrderedList()
        {
            return JsonConvert.SerializeObject(orderedNodes);
        }

        public static Node RebuildHierarchy(Stack stack)
        {
            Node root = stack.Peek();

            BuildHierarchy(stack, stack.Pop());

            return root;
        }
       
        private static void BuildHierarchy(Stack stack, Node parent)
        {
            if (parent == null) return;

            Node addedNode = null;

            while (!stack.IsEmpty())
            {
                if (stack.Peek().Parent.Equals(parent.Name))
                {
                    if (parent.Children == null) parent.Children = new List();

                    addedNode = stack.Pop();
                    parent.Children.Add(addedNode);
                }
                else if (stack.Peek().Parent.Equals(addedNode.Name)) BuildHierarchy(stack, addedNode);
                else return;
            }
        }

        private static void AddToOrderedList(Node node)
        {
            orderedNodes.Add(node);
        }

        private static void Push(Stack stack, Node node, string parent = null)
        {
            stack.Push(node);

            node.Parent = parent;
            AddToOrderedList(node);
        }

        private static Node GetChildNode(Node node)
        {
            if (!node.Visited) return node;
            if (node.Children == null) return null;

            return node.Children.FirstOrDefault(n => n.Visited == false);
        }

        private static void Print(Node node)
        {
            Console.WriteLine(node.Id + ":" + node.Name);
        }

        private static bool IsEmpty(this Stack stack)
        {
            return stack.Count <= 0;
        }
    }

   class Program
    {
        const string file = "Naviagtion.txt";

        static void DemoDFSTraverse(Node root)
        {
            DFSTraverse.Traverse(root);

            if (File.Exists(file)) File.Delete(file);
           
            File.WriteAllText(file, DFSTraverse.OrderedList());
        }

        static Node RebuildHierarchy()
        {
            var result = JsonConvert.DeserializeObject(File.ReadAllText(file));

            Stack node = new Stack(result.Reverse());

            return DFSTraverse.RebuildHierarchy(node);
        }

        static bool AreEquals(Node node1, Node node2)
        {
            if (node1.Id == node2.Id && node1.Name.Equals(node2.Name))
            {
                int item = 0;

                if (node1.Children == null && node2.Children == null) return true;

                foreach (var node in node1.Children)
                {
                    var otherNode1 = node1.Children[item];
                    var otherNode2 = node2.Children[item];

                    item++;

                    return AreEquals(otherNode1, otherNode2);
                }
            }

            return false;
        }

        static void Main(string[] args)
        {
            Node originalNode = TestData.Initialise();

            DemoDFSTraverse(originalNode);
            Node rebuilededNode = RebuildHierarchy();

            Console.WriteLine(AreEquals(originalNode, rebuilededNode));
           
            Console.Clear();
            DemoDFSTraverse(rebuilededNode);

            Console.ReadLine();
        }