fork download
copy 
  1. import java.util.*;
  2.  
  3. class Graph {
  4.  
  5.     ArrayList<Node> nodes;
  6.  
  7.     public Graph(ArrayList<Node> nds) {
  8. 	nodes = nds;
  9.     }
  10.  
  11.     public Graph() {
  12. 	nodes = new ArrayList<Node>();
  13.     }
  14.  
  15.     public void addNode(Node nd) {
  16. 	nodes.add(nd);
  17.     }
  18.  
  19.     public Graph square() {
  20. 	ArrayList<Node> sqnodes = new ArrayList<Node>();
  21.  
  22. 	for (Node nd : this.nodes) {
  23. 	    Node newNd = new Node(nd.id); // make new node with empty adjList
  24. 	    for (Node nd2 : this.nodes) {
  25. 		if (nd != nd2 && nd.distTwoOrLess(nd2)) {
  26. 		    newNd.addNeighbour(nd2);
  27. 		}
  28. 	    }
  29. 	    sqnodes.add(newNd);
  30. 	}
  31.  
  32. 	return new Graph(sqnodes);
  33.     }
  34.  
  35.     public String toString() {
  36. 	String s = "";
  37. 	for (Node nd : this.nodes) {
  38. 	    s += nd;
  39. 	}
  40. 	return s; 
  41.     }
  42.  
  43. }
  44.  
  45. class Node {
  46.  
  47.     public String id;
  48.     public ArrayList<Node> adjList;
  49.  
  50.     public Node(String n) {
  51. 	id = n;
  52. 	adjList = new ArrayList<Node>();
  53.     }
  54.  
  55.     public boolean distTwoOrLess(Node other) {
  56. 	for (Node nd : this.adjList) {
  57. 	    if (nd==other) {
  58. 		return true; // other node found directly in adjList, distance is 1
  59. 	    }
  60. 	    for (Node nd2 : nd.adjList) {
  61. 		if (nd2==other) {
  62. 		    return true; // other node found at distance 2
  63. 		}
  64. 	    }
  65. 	}
  66. 	// reached end of adjList + adjLists of all nodes therein
  67. 	// with no link less than 2 found
  68. 	return false; 
  69.     }
  70.  
  71.     public void addNeighbour(Node nd) {
  72. 	if (!this.adjList.contains(nd)) {
  73. 	    this.adjList.add(nd);
  74. 	}
  75.     }    
  76.     public String toString() {
  77. 	String s = "\nNode: " + this.id;
  78. 	s += "\nNeighbours: ";
  79. 	for (Node nd : this.adjList) {
  80. 	    s += nd.id + ", ";
  81. 	}
  82. 	return s + "\n";
  83.     }
  84. }
  85.  
  86. class SquareTest {
  87.  
  88.     public static void main(String[] args) {
  89.  
  90. 	Node a = new Node("A");
  91. 	Node b = new Node("B");
  92. 	Node c = new Node("C");
  93. 	Node d = new Node("D");
  94. 	Node e = new Node("E");
  95.  
  96. 	a.addNeighbour(d);
  97. 	b.addNeighbour(c);
  98. 	c.addNeighbour(b);
  99. 	c.addNeighbour(d);
  100. 	d.addNeighbour(a);
  101. 	d.addNeighbour(c);
  102. 	d.addNeighbour(e);
  103. 	e.addNeighbour(d);
  104.  
  105. 	Graph test = new Graph();
  106. 	Node[] nds =  {a,b,c,d,e};
  107. 	for (Node nd : nds) {
  108. 	    test.addNode(nd);
  109. 	}
  110.  
  111. 	/* Original graph:
  112.              a------d--e
  113.                    /
  114. 	         c´----b
  115. 	 */
  116. 	System.out.println("Original graph:");
  117. 	System.out.println(test);
  118.  
  119.  
  120.  
  121. 	Graph sq = test.square();
  122.  
  123. 	/* New graph:
  124.  
  125. 	   Node: a
  126. 	   Neighbours: c, d, e, 
  127.  
  128. 	   Node: b
  129. 	   Neighbours: c, d, 
  130.  
  131. 	   Node: c
  132. 	   Neighbours: a, b, d, e, 
  133.  
  134. 	   Node: d
  135. 	   Neighbours: a, b, c, e, 
  136.  
  137. 	   Node: e
  138. 	   Neighbours: a, c, d, 
  139.  
  140. 	   + a confusing ASCII graph :--D
  141. 	      ________
  142. 	     /        \
  143. 	    a__   ____e
  144.             |  \ /   /
  145. 	    |   d-- /
  146.             c--´---´ `b
  147.              \________/
  148.  
  149. 	 */
  150.  
  151. 	System.out.println("------------------------\n");
  152. 	System.out.println("Square of the original graph:");
  153. 	System.out.println(sq);
  154.  
  155.  
  156.     }
  157.  
  158. }
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original graph:

Node: A
Neighbours: D, 

Node: B
Neighbours: C, 

Node: C
Neighbours: B, D, 

Node: D
Neighbours: A, C, E, 

Node: E
Neighbours: D, 

------------------------

Square of the original graph:

Node: A
Neighbours: C, D, E, 

Node: B
Neighbours: C, D, 

Node: C
Neighbours: A, B, D, E, 

Node: D
Neighbours: A, B, C, E, 

Node: E
Neighbours: A, C, D,
https://ideone.com/Med4AG
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!