Undirected Graphs

This is an implementation of a undirected graph. A directed graph would follow the same format except that it would incorporate a parent and child node scheme to determine the directions of an edges.

Java

Node for UDGraph

UDGraphNode.java


import java.util.ArrayList; 
 
public class UDGraphNode { 
 
    int data; 
    ArrayList<UDGraphPair> adjacent = new ArrayList<UDGraphPair>(); 
 
    public UDGraphNode(int d) { 
        data = d; 
    } 
 
    void addAdjacentToList(UDGraphNode n, int weight) { 
        adjacent.add(new UDGraphPair(n, weight)); 
    } 
 
    void printAdjacents() { 
        System.out.println("Node " + this.data + " is connected to:"); 
        for (int i = 0; i < adjacent.size(); i++) { 
            System.out.print(adjacent.get(i).getKey().data + " "); 
        } 
        System.out.println(); 
        System.out.println(); 
    } 
 
    ArrayList<UDGraphPair> getAdjacentList() { 
        return adjacent; 
    } 
 
}

UDGraph Pair between Node and List of Adjacent Nodes

UDGraphPair.java


public class UDGraphPair { 
 
    UDGraphNode key; 
    int value; 
 
    public UDGraphPair(UDGraphNode k, int v) { 
        key = k; 
        value = v; 
    } 
 
    UDGraphNode getKey() { 
        return key; 
    } 
 
    int getValue() { 
        return value; 
    } 
 
}

UDGraph

UDGraph.java


import java.util.HashMap; 
import java.util.ArrayList; 
 
public class UDGraph { 
 
    HashMap<UDGraphNode, ArrayList<UDGraphPair>> adjacencyList = new HashMap<UDGraphNode, ArrayList<UDGraphPair>>(); 
    ArrayList<UDGraphNode> nodeList = new ArrayList<UDGraphNode>(); 
 
    UDGraphNode root; 
 
    public UDGraph(int d) { 
        System.out.println("Initializing Undirected Graph Node with " + d); 
        System.out.println(); 
        root = new UDGraphNode(d); 
        nodeList.add(root); 
    } 
 
    void connectTwoNodes(UDGraphNode x, UDGraphNode y, int weight) { 
        if (!nodeList.contains(x)) { 
            nodeList.add(x); 
        } 
        if (!nodeList.contains(y)) { 
            nodeList.add(y); 
        } 
        System.out.println("Connecting " + x.data + " with " + y.data + "..."); 
        System.out.println(); 
        x.addAdjacentToList(y, weight); 
        y.addAdjacentToList(x, weight); 
        adjacencyList.put(x, x.getAdjacentList()); 
        adjacencyList.put(y, y.getAdjacentList()); 
    } 
 
    void printGraph() { 
        System.out.println("Printing Graph:"); 
        System.out.println(); 
        for (int i = 0; i < nodeList.size(); i++) { 
            if (adjacencyList.get(nodeList.get(i)) != null) { 
                System.out.println("   Node " + nodeList.get(i).data); 
                ArrayList<UDGraphPair> list = adjacencyList.get(nodeList.get(i)); 
                for (int j = 0; j < list.size(); j++) { 
                    System.out.println("      connected to " + list.get(j).getKey().data 
                            + " by weight of " + list.get(j).getValue()); 
                } 
                System.out.println(); 
            } 
        } 
    } 
 
}

Implementation of Graph

ImplementUDGraph.java


public class ImplementUDGraph { 
 
    public static void main(String[] args) { 
 
        UDGraph graph = new UDGraph(0); 
 
        UDGraphNode[] node = new UDGraphNode[11]; 
 
        for (int i = 1; i <= 10; i++) { 
            System.out.println("Creating UDGraphNode " + i); 
            node[i] = new UDGraphNode(i); 
        } 
        System.out.println(); 
 
        graph.connectTwoNodes(graph.root, node[5], 1); 
        graph.connectTwoNodes(node[2], node[5], 2); 
        graph.connectTwoNodes(node[2], node[3], 3); 
        graph.connectTwoNodes(node[7], node[10], 4); 
        graph.connectTwoNodes(node[8], node[10], 5); 
        graph.connectTwoNodes(node[10], node[7], 3); 
 
        graph.printGraph(); 
 
    } 
 
}

Console Output


Initializing Undirected Graph Node with 0

Creating UDGraphNode 1
Creating UDGraphNode 2
Creating UDGraphNode 3
Creating UDGraphNode 4
Creating UDGraphNode 5
Creating UDGraphNode 6
Creating UDGraphNode 7
Creating UDGraphNode 8
Creating UDGraphNode 9
Creating UDGraphNode 10

Connecting 0 with 5...

Connecting 2 with 5...

Connecting 2 with 3...

Connecting 7 with 10...

Connecting 8 with 10...

Connecting 10 with 7...

Printing Graph:

   Node 0
      connected to 5 by weight of 1

   Node 5
      connected to 0 by weight of 1
      connected to 2 by weight of 2

   Node 2
      connected to 5 by weight of 2
      connected to 3 by weight of 3

   Node 3
      connected to 2 by weight of 3

   Node 7
      connected to 10 by weight of 4
      connected to 10 by weight of 3

   Node 10
      connected to 7 by weight of 4
      connected to 8 by weight of 5
      connected to 7 by weight of 3

   Node 8
      connected to 10 by weight of 5