Направлена реализация графика в Java


Здесь я приложил свои Java-реализация направленный граф. Я использовал модифицированный смежности-список механиком использовать карту вместо списка для быстрого поиска раз. Ищу комментарии и предложения на мой подход, в частности, является ли или не стоит внедрении карту, чтобы заменить список смежности, или если я пишу ДПП / БФС методы правильно.

Графа класс:

public class Graph<T> {

    private HashMap<GraphNode<T>, HashSet<GraphNode<T>>> adjacencyMap;
    private int numVertices;
    private int numEdges;
    private final String type = "directed";
    private final boolean weighted = false;

    public Graph() {
        this.adjacencyMap = new HashMap<>();
    }

    /**
    * Adds a vertex to the graph.
    * @param vertex vertex to add.
    * @return true if vertex was added successfully, false if otherwise.
    * @
    */
    public boolean addVertex(GraphNode<T> vertex) {
        if(!this.adjacencyMap.containsKey(vertex)) {
            this.adjacencyMap.put(vertex, new HashSet<>());
            this.numVertices++;
            return true;
        }
        return false;
    }

    /**
    * Removes a specified vertex from the graph.
    * @param vertex vertex to remove.
    * @return true if vertex was removed successfully, false if otherwise.
    * @
    */
    public boolean removeVertex(GraphNode<T> vertex) {
        if(this.adjacencyMap.containsKey(vertex)) {
            this.adjacencyMap.remove(vertex);
            for(Map.Entry<GraphNode<T>, HashSet<GraphNode<T>>> entry : this.adjacencyMap.entrySet()) {
                if(entry.getValue().contains(vertex)) {
                    this.adjacencyMap.get(entry.getKey()).remove(vertex);
                }
            }
            this.numVertices--;
            return true;
        }
        return false;
    }

    /**
    * Adds an edge between two vertices to the graph.
    * @param x source vertex of edge to add.
    * @param y destination vertex of edge to add.
    * @return true if the edge was added successfully, false if otherwise.
    * @
    */
    public boolean addEdge(GraphNode<T> x, GraphNode<T> y) {
        if(this.adjacencyMap.containsKey(x)) {
            if(!this.adjacencyMap.get(x).contains(y)) {
                this.adjacencyMap.get(x).add(y);
                this.numEdges++;
                return true;
            }
        }
        return false;
    }

    /**
    * Removes a specified edge between two vertices from the graph, if it already exists.
    * @param x source vertex of edge to remove.
    * @param y destination vertex of edge to remove.
    * @return true if the edge was removed successfully, false if otherwise.
    * @
    */
    public boolean removeEdge(GraphNode<T> x, GraphNode<T> y) {
        if(this.adjacencyMap.containsKey(x)) {
            if(this.adjacencyMap.get(x).contains(y)) {
                this.adjacencyMap.get(x).remove(y);
                this.numEdges--;
                return true;
            }
        }
        return false;
    }

    /**
    * Determines if two vertices are adjacent (or, if an edge exists between them).
    * @param x source vertex.
    * @param y destination vertex.
    * @return true if both vertices are adjacent, false if otherwise.
    * @
    */
    public boolean isAdjacent(GraphNode<T> x, GraphNode<T> y) {
        HashSet<GraphNode<T>> adjacencySet = this.adjacencyMap.get(x);
        if(adjacencySet != null) {
            if(adjacencySet.contains(y)) {
                return true;
            }
        }
        return false;
    }

    /**
    * Determines if graph contains a given vertex or not.
    * @param vertex vertex to search.
    * @return true if the graph contains the vertex, false if otherwise.
    * @
    */
    public boolean containsVertex(GraphNode<T> vertex) {
        if(this.adjacencyMap.containsKey(vertex)) {
            return true;
        }
        return false;
    }

    /**
    * Returns a HashSet containing all neighbors of a given vertex (or, all vertices with which the vertex shares an edge).
    * @param vertex vertex to search.
    * @return a HashSet containing all neighbors of the vertex.
    * @
    */
    public HashSet<GraphNode<T>> getNeighbors(GraphNode<T> vertex) {
        return this.adjacencyMap.get(vertex);
    }

    /**
    * Determines whether or not a path exists between two nodes, using Depth-First Search.
    * Uses a wrapper method to initialize objects required for search traversal.
    * @param source source node to be used in search.
    * @param destination destination node to be used in search.
    * @return true if a path exists between source and destination nodes, false if otherwise.
    * @
    */
    public boolean depthFirstSearch(GraphNode<T> source, GraphNode<T> destination) {
        if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {
            return false;
        }
        Stack<GraphNode<T>> stack = new Stack<>();
        stack.push(source);
        return depthFirstSearch(stack, destination);
    }
    private boolean depthFirstSearch(Stack<GraphNode<T>> stack, GraphNode<T> destination) {
        HashMap<GraphNode<T>, VisitStatus> visited = new HashMap<>();
        while(!stack.isEmpty()) {
            GraphNode<T> current = stack.pop();
            visited.put(current, VisitStatus.VISITING);
            if(current.equals(destination)) {
                return true;
            }
            for(GraphNode<T> neighbor : this.adjacencyMap.get(current)) {
                if(visited.containsKey(neighbor)) {
                    if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {
                        stack.push(neighbor);
                    }
                } else {
                    stack.push(neighbor);
                }
            }
            visited.put(current, VisitStatus.VISITED);
        }
        return false;
    }

    /**
    * Determines whether or not a path exists between two nodes, using Breadth-First Search.
    * Uses a wrapper method to initialize objects required for search traversal.
    * @param source source node to be used in search.
    * @param destination destination node to be used in search.
    * @return true if a path exists between source and destination nodes, false if otherwise.
    * @
    */
    public boolean breadthFirstSearch(GraphNode<T> source, GraphNode<T> destination) {
        if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {
            return false;
        }
        LinkedList<GraphNode<T>> queue = new LinkedList<>();
        queue.addLast(source);
        return breadthFirstSearch(queue, destination);
    }
    private boolean breadthFirstSearch(LinkedList<GraphNode<T>> queue, GraphNode<T> destination) {
        HashMap<GraphNode<T>, VisitStatus> visited = new HashMap<>();
        while(!queue.isEmpty()) {
            GraphNode<T> current = queue.removeFirst();
            visited.put(current, VisitStatus.VISITING);
            if(current.equals(destination)) {
                return true;
            }
            for(GraphNode<T> neighbor : this.adjacencyMap.get(current)) {
                if(visited.containsKey(neighbor)) {
                    if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {
                        queue.addLast(neighbor);
                    }
                } else {
                    queue.addLast(neighbor);
                }
            }
            visited.put(current, VisitStatus.VISITED);
        }
        return false;
    }

    /**
    * Returns the number of vertices within the graph.
    * @return an integer representing number of vertices contained within the graph.
    * @
    */
    public int getNumVertices() {
        return this.numVertices;
    }

    /**
    * Returns the number of edges within the graph.
    * @return an integer representing number of edges contained within the graph.
    * @
    */
    public int getNumEdges() {
        return this.numEdges;
    }

}

Класс GraphNode:

public class GraphNode<T> {

    private T data;

    public GraphNode() {}

    public GraphNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

VisitStatus перечисление:

public enum VisitStatus {
    UNVISITED,
    VISITING,
    VISITED
}


Комментарии
1 ответ

Объект поля объявления


    private HashMap<GraphNode<T>, HashSet<GraphNode<T>>> adjacencyMap;

Это может быть

    private Map<GraphNode<T>, Set<GraphNode<T>>> adjacencyMap = new HashMap<>();

Тогда вам не нужно указывать конструктору на всех.

Как правило, его предпочитают использовать интерфейс как тип, а не реализации. Это делает его легче изменить реализаций в будущем. И потому, что вы задаете реализации в меньшем количестве мест, а потому, что это заставляет вас код к интерфейсу.

Избыточных переменных


    public int getNumVertices() {
return this.numVertices;
}

Зачем numVertices? Почему не

    public int getVertexCount() {
return adjacencyMap.size();
}

Тогда вам не придется вручную сохранять дополнительную переменную, которая отслеживает информацию о том, что у вас уже есть.

Я предпочитаю в единственном числе имена (например, количество вершин) для особых переменных и множественного числа имена для коллекций. В этом случае, у вас есть простой скалярной переменной, и я хотел дать ему имя в единственном числе. Это конечно личные предпочтения, а не стандартный.

Вы не должны использовать this. С полей объекта в Java, если возникает конфликт между локальной переменной/параметра и объекта поля. Вы можете. Он будет работать нормально. Но вам не нужно этого делать. Некоторые считают, что это делает код более читабельным в том, что он указывает, что конкретная переменная является полем объекта, а не что-то местное. Мое личное предпочтение, чтобы оставить его без необходимости.

Сравните это с переменной холдинг граф краю. Эта переменная имеет реальное воздействие, так как он избавляет от необходимости рассчитывать количество ребер, которые хранятся во многих коллекциях. Но здесь, вершины графа, отслеживается именно по количеству ключей в adjacencyMap. Добавив дополнительную переменную означает, что есть еще одна вещь для поддержания. Еще одна вещь, которая может подвести.

Противоречивые фразеологизм

В нескольких местах, вы поддерживаете, что для того, чтобы путь между двумя вершинами, обе вершины должны быть в графе. Однако, при добавлении край, вы не сделаете этого.


        if(this.adjacencyMap.containsKey(x)) {
if(!this.adjacencyMap.get(x).contains(y)) {
this.adjacencyMap.get(x).add(y);
this.numEdges++;
return true;
}
}
return false;

Это может быть

        if (adjacencyMap.containsKey(x) && adjacencyMap.containsKey(y)) {
if (!adjacencyMap.get(x).contains(y)) {
adjacencyMap.get(x).add(y);
numEdges++;

return true;
}
}

return false;

Или

        if (adjacencyMap.containsKey(x)) {
if (!adjacencyMap.get(x).contains(y)) {
addVertex(y);
adjacencyMap.get(x).add(y);
numEdges++;

return true;
}
}

return false;

В любом случае, у вас есть только ребер в графе между двумя вершинами в графе.

Или даже

        Set<GraphNode<T>> adjacentVertices = adjacencyMap.get(x);
if (adjacentVertices != null && adjacentVertices.add(y)) {
addVertex(y);
numEdges++;

return true;
}

return false;

Теперь, вместо того, чтобы всегда проверять на наличие, мы предполагаем, что все там будет, пока не сказали, что это не так. Это изменение в узор почти всегда работает, когда containsKey сразу следует get.

Аналогично, мы сейчас проверяем, если add ничего после вызова он вместо того, чтобы проверить, если он будет работать, и назвать ее.

Потому что && оператор короткого замыкания, имеет такой же эффект, как если бы второе условие в секунду if внутри первого.

1
ответ дан 7 февраля 2018 в 04:02 Источник Поделиться