Блог

У меня есть следующий простой, несвязный, неориентированный график:

 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'}
     }
 

Я храню его таким образом:

 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"));
 

Мне нужно реализовать следующий метод:

 public void apply(String connectFrom, List<String> connectTos)
 

Если мы вызовем его, он должен применить новое соединение(соединения) и вывести каждое соединение из подключенного компонента, в котором from (в этом примере: «a») находится:

 apply("a", List.of("d", "k"));
 

Результат должен быть таким:

 ['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']
 

В этом примере выходные данные содержат все соединения графика, исключая:

 ['x - y', 'x - z', 'y - x', 'y - z', 'z - x', 'z - y']
 

Потому {'x', 'y'}, {'x', 'z'} что образует отдельный компонент:

 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'}
     }
 

Я создал суть GitHub и повторил фрагмент моей идеи.

В своем решении я использовал матрицу смежности, которая сначала довольно дорогая…
Но очень полезная и дешевая в обслуживании.
Дешевый… Особенно без updateComponentMapping

Это мои статические помощники из низших классов моего Graph<T> класса:

 //...
    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;
    }
}
 

На основе статических вспомогательных методов я создаю Graph<T> объект:

 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();
    }

// ...
 

Где я componentMapping заполняю идентификаторы для маркировки подключенных компонентов:

 //...

    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 amp;amp; componentMapping[j] == j) {
                    componentMapping[j] = componentId;
                }
            }
        }
    }

//...
 

После этого печать становится довольно простой:

 //...

    public int getNodeId(T node) {
        int index = nodeList.indexOf(node);

        if (0 <= index amp;amp; 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];
    }

//...
 

Но нам также нужны новые связи, поэтому есть addConnection и его помощники:

 //...
    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);
    }
//...
 

И наконец…

 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();
}
 

Я новичок в нотации Big O, но я думаю, что:

• Построение матрицы смежности с первого раза: O(n ²)
• Добавьте новые соединения в матрицу смежности: O(1)
• Обновление сопоставления компонентов: O(n ²)
• Подключения для печати также: O(n ²)