Package smile.graph

Class AdjacencyMatrix

java.lang.Object
smile.graph.Graph
smile.graph.AdjacencyMatrix
All Implemented Interfaces:
Serializable
public class AdjacencyMatrix extends Graph implements Serializable
An adjacency matrix representation of a graph. Only simple graph is supported.
See Also:

  • Constructor Details

    • AdjacencyMatrix

      public AdjacencyMatrix(int n)
      Constructor.
      Parameters:
      n - the number of vertices.

    • AdjacencyMatrix

      public AdjacencyMatrix(int n, boolean digraph)
      Constructor.
      Parameters:
      n - the number of vertices.
      digraph - true if this is a directed graph.

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • getVertexCount

      public int getVertexCount()
      Description copied from class: Graph
      Returns the number of vertices.
      Specified by:
      getVertexCount in class Graph
      Returns:
      the number of vertices.

    • hasEdge

      public boolean hasEdge(int source, int target)
      Description copied from class: Graph
      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.
      Specified by:
      hasEdge in class Graph
      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 double getWeight(int source, int target)
      Description copied from class: Graph
      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.
      Specified by:
      getWeight in class Graph
      Parameters:
      source - the id of source vertex of the edge.
      target - the id of target vertex of the edge.
      Returns:
      the edge weight

    • setWeight

      public AdjacencyMatrix setWeight(int source, int target, double weight)
      Description copied from class: Graph
      Sets the weight assigned to a given edge.
      Specified by:
      setWeight in class Graph
      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 List<Graph.Edge> getEdges(int vertex)
      Description copied from class: Graph
      Returns the edges from the specified vertex. If no edges are touching the specified vertex returns an empty set.
      Specified by:
      getEdges in class Graph
      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 void forEachEdge(int vertex, ArrayElementConsumer action)
      Description copied from class: Graph
      Performs an action for each edge of a vertex.
      Specified by:
      forEachEdge in class Graph
      Parameters:
      vertex - the vertex id.
      action - a non-interfering action to perform on the edges.

    • mapEdges

      public DoubleStream mapEdges(int vertex, ArrayElementFunction mapper)
      Description copied from class: Graph
      Returns a stream consisting of the results of applying the given function to the edge weights of a vertex.
      Specified by:
      mapEdges in class Graph
      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 void updateEdges(int vertex, ArrayElementFunction mapper)
      Description copied from class: Graph
      Updates the edge weights of a vertex.
      Specified by:
      updateEdges in class Graph
      Parameters:
      vertex - the vertex id.
      mapper - a function to map each edge weight to new value.

    • getInDegree

      public int getInDegree(int vertex)
      Description copied from class: Graph
      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.
      Specified by:
      getInDegree in class Graph
      Parameters:
      vertex - the id of vertex.
      Returns:
      the degree of the specified vertex.

    • getOutDegree

      public int getOutDegree(int vertex)
      Description copied from class: Graph
      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.
      Specified by:
      getOutDegree in class Graph
      Parameters:
      vertex - the id of vertex.
      Returns:
      the degree of the specified vertex.

    • subgraph

      public AdjacencyMatrix subgraph(int[] vertices)
      Description copied from class: Graph
      Returns a subgraph containing all given vertices.
      Specified by:
      subgraph in class Graph
      Parameters:
      vertices - the vertices to be included in subgraph.
      Returns:
      a subgraph containing all given vertices

    • toMatrix

      public Matrix toMatrix()
      Description copied from class: Graph
      Returns the (dense or sparse) matrix representation of the graph.
      Specified by:
      toMatrix in class Graph
      Returns:
      the matrix representation of the graph.

    • toArray

      public double[][] toArray()
      Returns the adjacency matrix.
      Returns:
      the adjacency matrix

    • pushRelabel

      public double pushRelabel(double[][] flow, int source, int sink)
      Push-relabel algorithm for maximum flow.
      Parameters:
      flow - the flow network.
      source - the source vertex.
      sink - the sink vertex.
      Returns:
      the maximum flow between source and sink.