Skip to content

Instantly share code, notes, and snippets.

@doyonghoon
Created February 20, 2016 01:08
Show Gist options
  • Save doyonghoon/02f60feead4e764d2117 to your computer and use it in GitHub Desktop.
Save doyonghoon/02f60feead4e764d2117 to your computer and use it in GitHub Desktop.
Find a relation between nodes
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