Package com.jgalgo.graph

Class Graphs

  • public class Graphs
extends Object
    Static methods class for graphs.
    Author:
    Barak Ugav

    • Field Detail

      • EmptyGraphUndirected

        public static final IndexGraph EmptyGraphUndirected
        An undirected graphs with no vertices and no edges

      • EmptyGraphDirected

        public static final IndexGraph EmptyGraphDirected
        A directed graphs with no vertices and no edges

    • Method Detail

      • newCompleteGraphUndirected

        public static IndexGraph newCompleteGraphUndirected​(int numberOfVertices)
        Create a new undirected complete graph with a fixed number of vertices.

        Given a set of vertices \(V\), the complete graph \(G=(V,E)\) is the graph with the edges set \(E=\{\{u,v\} \mid u,v \in V, u \neq v \}\), namely there is a single edge between any pair of vertices \(u,v\). The created graph will have a fixed number of vertices \(n\), and a fixed number of edges \({n \choose 2}\). No vertex or edge can be removed or added, but weights can be added. This graph is useful in cases where all edges exists, but we want to avoid using \(O(n^2)\) memory, for example for metric TSP, where each two vertices (points in a 2D world) are connected by an edge.

        Parameters:
        numberOfVertices - the number of vertices in the graph. Note that its impossible to change the number of vertices after the graph was created.
        Returns:
        a new undirected complete graph

      • newCompleteGraphDirected

        public static IndexGraph newCompleteGraphDirected​(int numberOfVertices)
        Create a new directed complete graph with a fixed number of vertices.

        Given a set of vertices \(V\), the complete graph \(G=(V,E)\) is the graph with the edges set \(E=\{(u,v) \mid u,v \in V, u \neq v \}\), namely there are two edges between any pair of vertices \(u,v\) where one is the reverse of the other. The created graph will have a fixed number of vertices \(n\), and a fixed number of edges \(2 {n \choose 2}\) (the additional factor of \(2\) is due to the directiveness of the edges). No vertex or edge can be removed or added, but weights can be added. This graph is useful in cases where all edges exists, but we want to avoid using \(O(n^2)\) memory, for example for metric TSP, where each two vertices (points in a 2D world) are connected by an edge.

        Parameters:
        numberOfVertices - the number of vertices in the graph. Note that its impossible to change the number of vertices after the graph was created.
        Returns:
        a new directed complete graph