Class Graph

java.lang.Object
smile.graph.Graph
Direct Known Subclasses:
AdjacencyList, AdjacencyMatrix
public abstract class Graph extends Object
A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. The edges may be directed (asymmetric) or undirected (symmetric). A graph is a weighted graph if a number (weight) is assigned to each edge. Such weights might represent, for example, costs, lengths or capacities, etc., depending on the problem.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    Graph.Edge
    Graph edge.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Graph(boolean digraph)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    Graph
    addEdge(int source, int target)
    Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
    Graph
    addEdge(int source, int target, double weight)
    Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
    Graph
    addEdges(Collection<Graph.Edge> edges)
    Adds a set of edges to the graph.
    int[]
    arbitraryInsertion()
    Returns the approximate solution to TSP with the arbitrary insertion heuristic.
    int[][]
    bfcc()
    Returns the connected components by breadth-first search.
    void
    bfs(VertexVisitor visitor)
    BFS search on graph and performs some operation defined in visitor on each vertex during traveling.
    int[]
    bfsort()
    Topological sort digraph by breadth-first search of graph.
    int[]
    christofides()
    Returns the approximate solution to TSP with Christofides algorithm.
    int[][]
    dfcc()
    Returns the connected components by depth-first search.
    void
    dfs(VertexVisitor visitor)
    DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
    int[]
    dfsort()
    Reverse topological sort digraph by depth-first search of graph.
    double[][]
    dijkstra()
    Calculates the all pair shortest-path by Dijkstra algorithm.
    double[]
    dijkstra(int s)
    Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
    double[]
    dijkstra(int s, boolean weighted)
    Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
    String
    dot()
    Returns the graphic representation in Graphviz dot format.
    String
    dot(String name, String[] label)
    Returns the graphic representation in Graphviz dot format.
    int[]
    farthestInsertion()
    Returns the approximate solution to TSP with the farthest insertion heuristic.
    abstract void
    forEachEdge(int vertex, ArrayElementConsumer action)
    Performs an action for each edge of a vertex.
    int
    getDegree(int vertex)
    Returns the degree of the specified vertex.
    double
    getDistance(int source, int target)
    Returns the distance between two vertices.
    abstract List<Graph.Edge>
    getEdges(int vertex)
    Returns the edges from the specified vertex.
    abstract int
    getInDegree(int vertex)
    Returns the in-degree of the specified vertex.
    abstract int
    getOutDegree(int vertex)
    Returns the out-degree of the specified vertex.
    double
    getPathDistance(int[] path)
    Returns the distance of path.
    abstract int
    getVertexCount()
    Returns the number of vertices.
    abstract double
    getWeight(int source, int target)
    Returns the weight assigned to a given edge.
    abstract boolean
    hasEdge(int source, int target)
    Returns true if and only if this graph contains an edge going from the source vertex to the target vertex.
    int[]
    heldKarp()
    Returns the optimal TSP tour with Held-Karp algorithm.
    boolean
    isDigraph()
    Return true if the graph is directed.
    abstract DoubleStream
    mapEdges(int vertex, ArrayElementFunction mapper)
    Returns a stream consisting of the results of applying the given function to the edge weights of a vertex.
    int[]
    nearestInsertion()
    Returns the approximate solution to TSP with the nearest insertion heuristic.
    double
    opt2(int[] tour, int maxIter)
    Improves an existing TSP tour with the 2-opt heuristic.
    double
    prim(List<Graph.Edge> mst)
    Returns the minimum spanning tree (MST) for a weighted undirected graph by Prim's algorithm.
    Graph
    removeEdge(int source, int target)
    In a simple graph, removes and returns the edge going from the specified source vertex to the specified target vertex.
    Graph
    removeEdges(Collection<Graph.Edge> edges)
    Removes a set of edges from the graph.
    abstract Graph
    setWeight(int source, int target, double weight)
    Sets the weight assigned to a given edge.
    abstract Graph
    subgraph(int[] vertices)
    Returns a subgraph containing all given vertices.
    abstract Matrix
    toMatrix()
    Returns the (dense or sparse) matrix representation of the graph.
    int[]
    tsp()
    Returns the optimal travelling salesman problem (TSP) tour with branch and bound algorithm.
    abstract void
    updateEdges(int vertex, ArrayElementFunction mapper)
    Updates the edge weights of a vertex.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Graph

      public Graph(boolean digraph)
      Constructor.
      Parameters:
      digraph - true if this is a directed graph.

  • Method Details

    • isDigraph

      public boolean isDigraph()
      Return true if the graph is directed.
      Returns:
      true if the graph is directed.

    • dot

      public String dot()
      Returns the graphic representation in Graphviz dot format. Try http://viz-js.com/ to visualize the returned string.
      Returns:
      the graphic representation in Graphviz dot format.

    • dot

      public String dot(String name, String[] label)
      Returns the graphic representation in Graphviz dot format. Try http://viz-js.com/ to visualize the returned string.
      Parameters:
      name - the graph name.
      label - the label of nodes.
      Returns:
      the graphic representation in Graphviz dot format.

    • toMatrix

      public abstract Matrix toMatrix()
      Returns the (dense or sparse) matrix representation of the graph.
      Returns:
      the matrix representation of the graph.

    • subgraph

      public abstract Graph subgraph(int[] vertices)
      Returns a subgraph containing all given vertices.
      Parameters:
      vertices - the vertices to be included in subgraph.
      Returns:
      a subgraph containing all given vertices

    • getVertexCount

      public abstract int getVertexCount()
      Returns the number of vertices.
      Returns:
      the number of vertices.

    • hasEdge

      public abstract boolean hasEdge(int source, int target)
      Returns true if and only if this graph contains an edge going from the source vertex to the target vertex. In undirected graphs the same result is obtained when source and target are inverted.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      true if this graph contains the specified edge.

    • getWeight

      public abstract double getWeight(int source, int target)
      Returns the weight assigned to a given edge. Unweighted graphs always return 1.0. If the edge doesn't exist, it returns zero. For minimization problems such as TSP, use getDistance as it will return infinity instead.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      the edge weight

    • getDistance

      public double getDistance(int source, int target)
      Returns the distance between two vertices.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      the distance between two vertices.

    • setWeight

      public abstract Graph setWeight(int source, int target, double weight)
      Sets the weight assigned to a given edge.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      weight - the edge weight
      Returns:
      this graph.

    • getEdges

      public abstract List<Graph.Edge> getEdges(int vertex)
      Returns the edges from the specified vertex. If no edges are touching the specified vertex returns an empty set.
      Parameters:
      vertex - the id of vertex for which a set of touching edges is to be returned.
      Returns:
      the edges touching the specified vertex.

    • forEachEdge

      public abstract void forEachEdge(int vertex, ArrayElementConsumer action)
      Performs an action for each edge of a vertex.
      Parameters:
      vertex - the vertex id.
      action - a non-interfering action to perform on the edges.

    • mapEdges

      public abstract DoubleStream mapEdges(int vertex, ArrayElementFunction mapper)
      Returns a stream consisting of the results of applying the given function to the edge weights of a vertex.
      Parameters:
      vertex - the vertex id.
      mapper - a non-interfering, stateless function to map each edge weight of a vertex.
      Returns:
      the stream of the new values of edge weights.

    • updateEdges

      public abstract void updateEdges(int vertex, ArrayElementFunction mapper)
      Updates the edge weights of a vertex.
      Parameters:
      vertex - the vertex id.
      mapper - a function to map each edge weight to new value.

    • addEdge

      public Graph addEdge(int source, int target)
      Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      this graph.

    • addEdge

      public Graph addEdge(int source, int target, double weight)
      Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      weight - the weight of edge.
      Returns:
      this graph.

    • addEdges

      public Graph addEdges(Collection<Graph.Edge> edges)
      Adds a set of edges to the graph.
      Parameters:
      edges - edges to be added to this graph.
      Returns:
      this graph.

    • removeEdges

      public Graph removeEdges(Collection<Graph.Edge> edges)
      Removes a set of edges from the graph.
      Parameters:
      edges - edges to be removed from this graph.
      Returns:
      this graph.

    • removeEdge

      public Graph removeEdge(int source, int target)
      In a simple graph, removes and returns the edge going from the specified source vertex to the specified target vertex.
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      this graph.

    • getDegree

      public int getDegree(int vertex)
      Returns the degree of the specified vertex. A degree of a vertex in an undirected graph is the number of edges touching that vertex.
      Parameters:
      vertex - the id of vertex.
      Returns:
      the degree of the specified vertex.

    • getInDegree

      public abstract int getInDegree(int vertex)
      Returns the in-degree of the specified vertex. An in-degree of a vertex in a directed graph is the number of edges head to that vertex.
      Parameters:
      vertex - the id of vertex.
      Returns:
      the degree of the specified vertex.

    • getOutDegree

      public abstract int getOutDegree(int vertex)
      Returns the out-degree of the specified vertex. An out-degree of a vertex in a directed graph is the number of edges from that vertex.
      Parameters:
      vertex - the id of vertex.
      Returns:
      the degree of the specified vertex.

    • dfsort

      public int[] dfsort()
      Reverse topological sort digraph by depth-first search of graph.
      Returns:
      the vertices in the reverse topological order.

    • dfcc

      public int[][] dfcc()
      Returns the connected components by depth-first search.
      Returns:
      a two-dimensional array of which each row is the vertices in the same connected component.

    • dfs

      public void dfs(VertexVisitor visitor)
      DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
      Parameters:
      visitor - the visitor functor.

    • bfsort

      public int[] bfsort()
      Topological sort digraph by breadth-first search of graph.
      Returns:
      the vertices in the topological order.

    • bfcc

      public int[][] bfcc()
      Returns the connected components by breadth-first search.
      Returns:
      a two-dimensional array of which each row is the vertices in the same connected component.

    • bfs

      public void bfs(VertexVisitor visitor)
      BFS search on graph and performs some operation defined in visitor on each vertex during traveling.
      Parameters:
      visitor - the visitor functor.

    • dijkstra

      public double[] dijkstra(int s)
      Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
      Parameters:
      s - the source vertex.
      Returns:
      The distance to all vertices from the source.

    • dijkstra

      public double[] dijkstra(int s, boolean weighted)
      Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
      Parameters:
      s - The source vertex.
      weighted - Ignore edge weights if false.
      Returns:
      The distance to all vertices from the source. If weighted is false, it is the length of the shortest path to other vertices.

    • dijkstra

      public double[][] dijkstra()
      Calculates the all pair shortest-path by Dijkstra algorithm.
      Returns:
      the length of shortest-path between vertices.

    • prim

      public double prim(List<Graph.Edge> mst)
      Returns the minimum spanning tree (MST) for a weighted undirected graph by Prim's algorithm. MST is a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
      Parameters:
      mst - an output container to hold edges in the MST.
      Returns:
      the cost of minimum spanning tree.

    • getPathDistance

      public double getPathDistance(int[] path)
      Returns the distance of path.
      Parameters:
      path - the path.
      Returns:
      the distance.

    • tsp

      public int[] tsp()
      Returns the optimal travelling salesman problem (TSP) tour with branch and bound algorithm.
      Returns:
      the optimal TSP tour.

    • heldKarp

      public int[] heldKarp()
      Returns the optimal TSP tour with Held-Karp algorithm. It works on graph up to 31 vertices.
      Returns:
      the optimal TSP tour.

    • nearestInsertion

      public int[] nearestInsertion()
      Returns the approximate solution to TSP with the nearest insertion heuristic.
      Returns:
      the approximate solution to TSP.

    • farthestInsertion

      public int[] farthestInsertion()
      Returns the approximate solution to TSP with the farthest insertion heuristic.
      Returns:
      the approximate solution to TSP.

    • arbitraryInsertion

      public int[] arbitraryInsertion()
      Returns the approximate solution to TSP with the arbitrary insertion heuristic.
      Returns:
      the approximate solution to TSP.

    • opt2

      public double opt2(int[] tour, int maxIter)
      Improves an existing TSP tour with the 2-opt heuristic. The method reconnects pairs of non-adjacent edges until no more pairs can be swapped to further improve the solution.
      Parameters:
      tour - an existing TSP tour. It may be revised with a better tour of lower cost.
      maxIter - the maximum number of iterations of the outer loop.
      Returns:
      the improved tour cost.

    • christofides

      public int[] christofides()
      Returns the approximate solution to TSP with Christofides algorithm.
      Returns:
      the approximate solution to TSP.