I have the following simple, disconnected, undirected graph:
G1 = (V1, E1)
V1 = {'a', 'b', 'c', 'd', 'e', 'f', 'k', 'l', 'x', 'y', 'z'}
E1 = {
{'a', 'b'}, {'a', 'c'},
{'d', 'e'}, {'d', 'f'},
{'k', 'l'},
{'x', 'y'}, {'x', 'z'}
}
I store it in this way:
private final Map<String, List<String>> graph = Map.of(
"a", List.of("b", "c"),
"d", List.of("e", "f"),
"k", List.of("l"),
"x", List.of("y", "z"));
I need to implement the following method:
public void apply(String connectFrom, List<String> connectTos)
If we call it, it should apply the new connection(s) and output every connection from the connected component in which from (in this example: 'a') is:
apply("a", List.of("d", "k"));
The output should be this:
['a - b','a - c','a - d','a - e','a - f','a - k','a - l','b - a','b - c','b - d','b - e','b - f','b - k','b - l','c - a','c - b','c - d','c - e','c - f','c - k','c - l','d - a','d - b','d - c','d - e','d - f','d - k','d - l','e - a','e - b','e - c','e - d','e - f','e - k','e - l','f - a','f - b','f - c','f - d','f - e','f - k','f - l','k - a','k - b','k - c','k - d','k - e','k - f','k - l','l - a','l - b','l - c','l - d','l - e','l - f','l - k']
In this example the output contains every connection of the graph, excluded:
['x - y', 'x - z', 'y - x', 'y - z', 'z - x', 'z - y']
Because {'x', 'y'}, {'x', 'z'} forms a separate component:
G1 = (V1, E1)
V1 = {'a', 'b', 'c', 'd', 'e', 'f', 'k', 'l', 'x', 'y', 'z'}
E1 = {
{'a', 'b'}, {'a', 'c'}, {'a', 'd'}, {'a', 'k'},
{'d', 'e'}, {'d', 'f'},
{'k', 'l'},
{'x', 'y'}, {'x', 'z'}
}
I created a GitHub Gist and a Replit snippet about my idea.
In my solution I used adjacency matrix which is quite expensive first...
But very helpful and also cheap to maintain.
Cheap... Especially without updateComponentMapping
These are my static helpers from the bottom of my Graph<T> class:
//...
public static <T extends Comparable<T>> Set<T> getNodeSet(Map<T, List<T>> graph) {
Set<T> nodeSet = new TreeSet<>(graph.keySet());
nodeSet.addAll(
graph.values().stream()
.flatMap(List::stream)
.collect(Collectors.toSet()));
return nodeSet;
}
public static <T extends Comparable<T>> int[][] getAdjacencyMatrix(Map<T, List<T>> graph) {
return getAdjacencyMatrix(graph, getNodeSet(graph));
}
public static <T extends Comparable<T>> int[][] getAdjacencyMatrix(Map<T, List<T>> graph, Set<T> nodes) {
List<T> nodeList = new ArrayList<>(nodes);
int[][] matrix = new int[nodeList.size()][nodeList.size()];
graph.forEach(
(from, toList) ->
toList.forEach(
to -> setAdjacency(matrix, nodeList.indexOf(from), nodeList.indexOf(to), 1)));
return matrix;
}
private static void setAdjacency(int[][] matrix, int from, int to, int value) {
matrix[from][to] = value;
matrix[to][from] = value;
}
}
Based on the static helper methods, I build a Graph<T> object:
public static class Graph<T extends Comparable<T>> {
private final List<T> nodeList;
private final int[][] adjacencyMatrix;
private final int[] componentMapping;
public Graph(Map<T, List<T>> graph) {
var nodeSet = getNodeSet(graph);
nodeList = new ArrayList<>(nodeSet);
adjacencyMatrix = getAdjacencyMatrix(graph, nodeSet);
componentMapping = new int[nodeList.size()];
updateComponentMapping();
}
// ...
Where I populate componentMapping with IDs to mark connected components:
//...
private void updateComponentMapping() {
IntStream.range(0, componentMapping.length).forEach(
i -> componentMapping[i] = i
);
int componentId;
for (int i = 0; i < componentMapping.length; i++) {
componentId = componentMapping[i];
for (int j = i; j < componentMapping.length; j++) {
if (adjacencyMatrix[i][j] == 1 && componentMapping[j] == j) {
componentMapping[j] = componentId;
}
}
}
}
//...
After that, printing is quite easy:
//...
public int getNodeId(T node) {
int index = nodeList.indexOf(node);
if (0 <= index && index < nodeList.size()) {
return index;
} else {
throw new IllegalArgumentException("Node index is out of range.");
}
}
public int getComponentId(T node) {
return componentMapping[getNodeId(node)];
}
public void printAllConnections() {
printComponentConnections(-1);
}
public void printComponentConnections(int componentId) {
StringJoiner result = new StringJoiner("','", "['", "']");
nodeList.forEach(
from -> {
if (getComponentId(from) == componentId || componentId < 0) {
nodeList.forEach(
to -> {
if (isConnected(from, to)) {
result.add(String.format("%s - %s", from, to));
}
}
);
}});
System.out.println(result);
}
public boolean isConnected(T from, T to) {
return isConnected(getNodeId(from), getNodeId(to));
}
public boolean isConnected(int indexFrom, int indexTo) {
return indexFrom == indexTo
? adjacencyMatrix[indexFrom][indexTo] == 1
: componentMapping[indexFrom] == componentMapping[indexTo];
}
//...
But we need new connections also, so there are addConnection and its helpers:
//...
public void addConnections(T from, List<T> to) {
int fromIndex = getNodeId(from);
to.forEach(node -> connect(fromIndex, getNodeId(node)));
updateComponentMapping();
}
private void connect(int from, int to) {
set(from, to, 1);
}
private void disconnect(int from, int to) {
set(from, to, 0);
}
private void set(int from, int to, int value) {
setAdjacency(adjacencyMatrix, from, to, value);
}
//...
And finally...
private static final Map<String, List<String>> graphMap =
Map.of(
"a", List.of("b", "c"),
"d", List.of("e", "f"),
"k", List.of("l"),
"x", List.of("y", "z"));
public static void main(String[] args) {
var graph = new Graph<>(graphMap);
graph.addConnections("a", List.of("d", "k"));
int componentId = graph.getComponentId("a");
graph.printComponentConnections(componentId);
//graph.printAllConnections();
}
I'm new to the Big O notation, but I think: