Created
February 20, 2016 01:08
-
-
Save doyonghoon/02f60feead4e764d2117 to your computer and use it in GitHub Desktop.
Find a relation between nodes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package graph; | |
import com.google.gson.JsonArray; | |
import com.google.gson.JsonElement; | |
import com.google.gson.JsonObject; | |
import java.util.ArrayList; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Set; | |
import java.util.function.Consumer; | |
public class Connection { | |
public static void main(String[] args) { | |
Connection c = new Connection(); | |
Set<Node> nodes = c.findConnections(c.createInput()); | |
c.printRelations(nodes); | |
} | |
private void printRelations(Set<Node> nodes) { | |
List<Node> relations = new ArrayList<>(); | |
for (Node node : nodes) { | |
if (!node.isVisited) { | |
if (relations.isEmpty()) { | |
// start new relation. | |
preOrder(node, relations); | |
} else { | |
// print relation and clear it. | |
System.out.println("Relation: " + relations); | |
relations.clear(); | |
preOrder(node, relations); | |
} | |
} | |
} | |
if (!relations.isEmpty()) { | |
System.out.println("Relation: " + relations); | |
relations.clear(); | |
} | |
} | |
private void preOrder(Node node, List<Node> relations) { | |
if (relations != null && node != null && !node.isVisited) { | |
node.isVisited = true; | |
relations.add(node); | |
for (Node adjNode : node.getAdjacentNodes()) { | |
preOrder(adjNode, relations); | |
} | |
} | |
} | |
private Set<Node> findConnections(JsonArray json) { | |
final Set<Node> result = new HashSet<>(); | |
for (JsonElement aJson : json) { | |
JsonObject row = (JsonObject) aJson; | |
row.entrySet().forEach(new Consumer<Map.Entry<String, JsonElement>>() { | |
@Override | |
public void accept(Map.Entry<String, JsonElement> rowEntry) { | |
final Node node = getNodeInstance(rowEntry.getKey(), result); | |
result.add(node); | |
for (JsonElement adjElement : rowEntry.getValue().getAsJsonArray()) { | |
Node adjNode = getNodeInstance(adjElement.getAsString(), result); | |
node.addAdjacentNode(adjNode); | |
result.add(adjNode); | |
} | |
} | |
}); | |
} | |
return result; | |
} | |
private JsonArray createInput() { | |
JsonArray array = new JsonArray(); | |
array.add(createNode("A", createAdjacentNodes("B", "C"))); | |
array.add(createNode("B", createAdjacentNodes("D"))); | |
array.add(createNode("C", createAdjacentNodes("D"))); | |
array.add(createNode("D", createAdjacentNodes())); | |
array.add(createNode("E", createAdjacentNodes("F", "H"))); | |
array.add(createNode("F", createAdjacentNodes())); | |
array.add(createNode("G", createAdjacentNodes())); | |
array.add(createNode("H", createAdjacentNodes())); | |
System.out.println(array); | |
return array; | |
} | |
private JsonObject createNode(String item, JsonArray adjacentNodes) { | |
JsonObject node = new JsonObject(); | |
node.add(item, adjacentNodes); | |
return node; | |
} | |
private JsonArray createAdjacentNodes(String... item) { | |
JsonArray array = new JsonArray(); | |
for (String i : item) { | |
array.add(i); | |
} | |
return array; | |
} | |
private Node getNodeInstance(String data, Set<Node> list) { | |
if (list.isEmpty()) { | |
return new Node(data); | |
} | |
for (Node tmp : list) { | |
if (tmp.data.equals(data)) { | |
return tmp; | |
} | |
} | |
return new Node(data); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment