Package com.google.javascript.jscomp.graph

Class LinkedUndirectedGraph<N,E>

java.lang.Object
com.google.javascript.jscomp.graph.Graph<N,E>
com.google.javascript.jscomp.graph.UndiGraph<N,E>
com.google.javascript.jscomp.graph.LinkedUndirectedGraph<N,E>
Type Parameters:
N - Value type that the graph node stores.
E - Value type that the graph edge stores.
All Implemented Interfaces:
AdjacencyGraph<N,E>, GraphvizGraph
public class LinkedUndirectedGraph<N,E> extends UndiGraph<N,E> implements GraphvizGraph
An undirected graph using linked list within nodes to store edge information.

  • Field Details

    • nodes

      protected final Map<N,com.google.javascript.jscomp.graph.LinkedUndirectedGraph.LinkedUndirectedGraphNode<N,E>> nodes

  • Constructor Details

    • LinkedUndirectedGraph

      protected LinkedUndirectedGraph(boolean useNodeAnnotations, boolean useEdgeAnnotations)

  • Method Details

    • newSubGraph

      public SubGraph<N,E> newSubGraph()
      Description copied from interface: AdjacencyGraph
      Returns an empty SubGraph for this Graph.
      Specified by:
      newSubGraph in interface AdjacencyGraph<N,E>

    • createWithoutAnnotations

      public static <N, E> LinkedUndirectedGraph<N,E> createWithoutAnnotations()

    • createWithNodeAnnotations

      public static <N, E> LinkedUndirectedGraph<N,E> createWithNodeAnnotations()

    • createWithEdgeAnnotations

      public static <N, E> LinkedUndirectedGraph<N,E> createWithEdgeAnnotations()

    • create

      public static <N, E> LinkedUndirectedGraph<N,E> create()

    • connect

      public void connect(N srcValue, E edgeValue, N destValue)
      Description copied from class: Graph
      Connects two nodes in the graph with an edge.
      Specified by:
      connect in class Graph<N,E>
      Parameters:
      srcValue - First node.
      edgeValue - The edge.
      destValue - Second node.

    • disconnect

      public void disconnect(N srcValue, N destValue)
      Description copied from class: Graph
      Disconnects two nodes in the graph by removing all edges between them.
      Specified by:
      disconnect in class Graph<N,E>
      Parameters:
      srcValue - First node.
      destValue - Second node.

    • createUndirectedGraphNode

      public UndiGraph.UndiGraphNode<N,E> createUndirectedGraphNode(N nodeValue)

    • getNeighborNodes

      public List<GraphNode<N,E>> getNeighborNodes(N value)
      Description copied from class: Graph
      Gets the neighboring nodes.
      Specified by:
      getNeighborNodes in class Graph<N,E>
      Parameters:
      value - The node's value.
      Returns:
      A list of neighboring nodes.

    • getNeighborNodesIterator

      public Iterator<GraphNode<N,E>> getNeighborNodesIterator(N value)
      Specified by:
      getNeighborNodesIterator in class Graph<N,E>

    • getUndirectedGraphEdges

      public List<UndiGraph.UndiGraphEdge<N,E>> getUndirectedGraphEdges(N n1, N n2)

    • getUndirectedGraphNode

      public UndiGraph.UndiGraphNode<N,E> getUndirectedGraphNode(N nodeValue)
      Specified by:
      getUndirectedGraphNode in class UndiGraph<N,E>

    • getUndirectedGraphNodes

      public Collection<UndiGraph.UndiGraphNode<N,E>> getUndirectedGraphNodes()

    • createNode

      public GraphNode<N,E> createNode(N value)
      Description copied from class: Graph
      Gets a node from the graph given a value. New nodes are created if that value has not been assigned a graph node. Values equality are compared using Object.equals.
      Specified by:
      createNode in class Graph<N,E>
      Parameters:
      value - The node's value.
      Returns:
      The corresponding node in the graph.

    • getEdges

      public List<Graph.GraphEdge<N,E>> getEdges(N n1, N n2)
      Description copied from class: Graph
      Retrieves an edge from the graph.
      Specified by:
      getEdges in class Graph<N,E>
      Parameters:
      n1 - Node one.
      n2 - Node two.
      Returns:
      The list of edges between those two values in the graph.

    • getFirstEdge

      public Graph.GraphEdge<N,E> getFirstEdge(N n1, N n2)
      Description copied from class: Graph
      Retrieves any edge from the graph.
      Specified by:
      getFirstEdge in class Graph<N,E>
      Parameters:
      n1 - Node one.
      n2 - Node two.
      Returns:
      The first edges between those two values in the graph. null if there are none.

    • getNode

      public GraphNode<N,E> getNode(N value)
      Description copied from interface: AdjacencyGraph
      Gets a node from the graph given a value. Values equality are compared using Object.equals.
      Specified by:
      getNode in interface AdjacencyGraph<N,E>
      Parameters:
      value - The node's value.
      Returns:
      The corresponding node in the graph, null if there value has no corresponding node.

    • isConnected

      public boolean isConnected(N n1, N n2)
      Description copied from class: Graph
      Checks whether two nodes in the graph are connected.
      Specified by:
      isConnected in class Graph<N,E>
      Parameters:
      n1 - Node 1.
      n2 - Node 2.
      Returns:
      true if the two nodes are connected.

    • isConnected

      public boolean isConnected(N n1, E e, N n2)
      Description copied from class: Graph
      Checks whether two nodes in the graph are connected by the given edge type.
      Specified by:
      isConnected in class Graph<N,E>
      Parameters:
      n1 - Node 1.
      e - The edge type.
      n2 - Node 2.

    • getGraphvizEdges

      public List<GraphvizGraph.GraphvizEdge> getGraphvizEdges()
      Description copied from interface: GraphvizGraph
      Retrieve a list of edges in the graph.
      Specified by:
      getGraphvizEdges in interface GraphvizGraph
      Returns:
      A list of edges in the graph.

    • getName

      public String getName()
      Description copied from interface: GraphvizGraph
      Name of the graph.
      Specified by:
      getName in interface GraphvizGraph
      Returns:
      Name of the graph.

    • getGraphvizNodes

      public List<GraphvizGraph.GraphvizNode> getGraphvizNodes()
      Description copied from interface: GraphvizGraph
      Retrieve a list of nodes in the graph.
      Specified by:
      getGraphvizNodes in interface GraphvizGraph
      Returns:
      A list of nodes in the graph.

    • isDirected

      public boolean isDirected()
      Description copied from interface: GraphvizGraph
      Graph type.
      Specified by:
      isDirected in interface GraphvizGraph
      Returns:
      True if the graph is a directed graph.

    • getNodes

      public Collection<GraphNode<N,E>> getNodes()
      Description copied from class: Graph
      Gets an immutable list of all nodes.
      Specified by:
      getNodes in interface AdjacencyGraph<N,E>
      Specified by:
      getNodes in class Graph<N,E>

    • getEdges

      public List<Graph.GraphEdge<N,E>> getEdges()
      Description copied from class: Graph
      Gets an immutable list of all edges.
      Specified by:
      getEdges in class Graph<N,E>

    • getNodeDegree

      public int getNodeDegree(N value)
      Description copied from class: Graph
      Gets the degree of a node.
      Specified by:
      getNodeDegree in class Graph<N,E>
      Parameters:
      value - The node's value.
      Returns:
      The degree of the node.