java.lang.Object

com.google.javascript.jscomp.graph.Graph<N,E>

com.google.javascript.jscomp.graph.DiGraph<N,E>

com.google.javascript.jscomp.graph.LinkedDirectedGraph<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 LinkedDirectedGraph<N,E> extends DiGraph<N,E> implements GraphvizGraph

A directed graph using linked list within nodes to store edge information.

This implementation favors directed graph operations inherited from DirectedGraph. Operations from Graph would tends to be slower.

Nested Class Summary

Nested classes/interfaces inherited from class com.google.javascript.jscomp.graph.DiGraph
DiGraph.DiGraphEdge<N,E>, DiGraph.DiGraphNode<N,E>

Nested classes/interfaces inherited from class com.google.javascript.jscomp.graph.Graph
Graph.GraphEdge<N,E>

Nested classes/interfaces inherited from interface com.google.javascript.jscomp.graph.GraphvizGraph
GraphvizGraph.GraphvizEdge, GraphvizGraph.GraphvizNode
Field Summary

Fields

Modifier and Type

Field

Description

protected final Map<N,com.google.javascript.jscomp.graph.LinkedDirectedGraph.LinkedDirectedGraphNode<N,E>>

nodes
Constructor Summary

Constructors

Modifier

Constructor

Description

protected

LinkedDirectedGraph(boolean useNodeAnnotations, boolean useEdgeAnnotations)
Method Summary

Modifier and Type

Method

Description

void

connect(N srcValue, E edgeValue, N destValue)

Connects two nodes in the graph with an edge.

static <N, E> LinkedDirectedGraph<N,E>

create()

DiGraph.DiGraphNode<N,E>

createDirectedGraphNode(N nodeValue)

GraphNode<N,E>

createNode(N value)

Gets a node from the graph given a value.

static <N, E> LinkedDirectedGraph<N,E>

createWithEdgeAnnotations()

static <N, E> LinkedDirectedGraph<N,E>

createWithNodeAnnotations()

static <N, E> LinkedDirectedGraph<N,E>

createWithoutAnnotations()

void

disconnect(N n1, N n2)

Disconnects two nodes in the graph by removing all edges between them.

void

disconnectInDirection(N srcValue, N destValue)

Disconnects all edges from n1 to n2.

List<DiGraph.DiGraphEdge<N,E>>

getDirectedGraphEdges(N n1, N n2)

DiGraph.DiGraphNode<N,E>

getDirectedGraphNode(N nodeValue)

Iterable<DiGraph.DiGraphNode<N,E>>

getDirectedGraphNodes()

Gets an immutable iterable over all the nodes in the graph.

List<DiGraph.DiGraphNode<N,E>>

getDirectedPredNodes(DiGraph.DiGraphNode<N,E> dNode)

List<DiGraph.DiGraphNode<N,E>>

getDirectedPredNodes(N nodeValue)

List<DiGraph.DiGraphNode<N,E>>

getDirectedSuccNodes(DiGraph.DiGraphNode<N,E> dNode)

List<DiGraph.DiGraphNode<N,E>>

getDirectedSuccNodes(N nodeValue)

List<Graph.GraphEdge<N,E>>

getEdges()

Gets an immutable list of all edges.

List<Graph.GraphEdge<N,E>>

getEdges(N n1, N n2)

Retrieves an edge from the graph.

Graph.GraphEdge<N,E>

getFirstEdge(N n1, N n2)

Retrieves any edge from the graph.

List<GraphvizGraph.GraphvizEdge>

getGraphvizEdges()

Retrieve a list of edges in the graph.

List<GraphvizGraph.GraphvizNode>

getGraphvizNodes()

Retrieve a list of nodes in the graph.

List<DiGraph.DiGraphEdge<N,E>>

getInEdges(N nodeValue)

Gets an immutable list of in edges of the given node.

String

getName()

Name of the graph.

List<GraphNode<N,E>>

getNeighborNodes(DiGraph.DiGraphNode<N,E> node)

List<GraphNode<N,E>>

getNeighborNodes(N value)

Gets the neighboring nodes.

Iterator<GraphNode<N,E>>

getNeighborNodesIterator(N value)

GraphNode<N,E>

getNode(N nodeValue)

Gets a node from the graph given a value.

int

getNodeDegree(N value)

Gets the degree of a node.

Collection<GraphNode<N,E>>

getNodes()

Gets an immutable list of all nodes.

List<DiGraph.DiGraphEdge<N,E>>

getOutEdges(N nodeValue)

Gets an immutable list of out edges of the given node.

boolean

isConnectedInDirection(N n1, E edgeValue, N n2)

Checks whether two nodes in the graph are connected via a directed edge with the given value.

boolean

isConnectedInDirection(N n1, N n2)

Checks whether two nodes in the graph are connected via a directed edge.

boolean

isDirected()

Graph type.

SubGraph<N,E>

newSubGraph()

Returns an empty SubGraph for this Graph.

Methods inherited from class com.google.javascript.jscomp.graph.DiGraph
isConnected, isConnected

Methods inherited from class com.google.javascript.jscomp.graph.Graph
clearEdgeAnnotations, clearNodeAnnotations, connectIfNotFound, getWeight, hasNode, popEdgeAnnotations, popNodeAnnotations, pushEdgeAnnotations, pushNodeAnnotations

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details
- nodes
  
  protected final Map<N,com.google.javascript.jscomp.graph.LinkedDirectedGraph.LinkedDirectedGraphNode<N,E>> nodes
Constructor Details
- LinkedDirectedGraph
  
  protected LinkedDirectedGraph(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> LinkedDirectedGraph<N,E> createWithoutAnnotations()
- createWithNodeAnnotations
  
  public static <N, E> LinkedDirectedGraph<N,E> createWithNodeAnnotations()
- createWithEdgeAnnotations
  
  public static <N, E> LinkedDirectedGraph<N,E> createWithEdgeAnnotations()
- create
  
  public static <N, E> LinkedDirectedGraph<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 n1, N n2)
  
  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:
  
  n1 - First node.
  
  n2 - Second node.
- disconnectInDirection
  
  public void disconnectInDirection(N srcValue, N destValue)
  
  Description copied from class: DiGraph
  
  Disconnects all edges from n1 to n2.
  
  Specified by:
  
  disconnectInDirection in class DiGraph<N,E>
  
  Parameters:
  
  srcValue - Source node.
  
  destValue - Destination node.
- getDirectedGraphNodes
  
  public Iterable<DiGraph.DiGraphNode<N,E>> getDirectedGraphNodes()
  
  Description copied from class: DiGraph
  
  Gets an immutable iterable over all the nodes in the graph.
  
  Specified by:
  
  getDirectedGraphNodes in class DiGraph<N,E>
- getDirectedGraphNode
  
  public DiGraph.DiGraphNode<N,E> getDirectedGraphNode(N nodeValue)
  
  Specified by:
  
  getDirectedGraphNode in class DiGraph<N,E>
- getNode
  
  public GraphNode<N,E> getNode(N nodeValue)
  
  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:
  
  nodeValue - The node's value.
  
  Returns:
  
  The corresponding node in the graph, null if there value has no corresponding node.
- getInEdges
  
  public List<DiGraph.DiGraphEdge<N,E>> getInEdges(N nodeValue)
  
  Description copied from class: DiGraph
  
  Gets an immutable list of in edges of the given node.
  
  Specified by:
  
  getInEdges in class DiGraph<N,E>
- getOutEdges
  
  public List<DiGraph.DiGraphEdge<N,E>> getOutEdges(N nodeValue)
  
  Description copied from class: DiGraph
  
  Gets an immutable list of out edges of the given node.
  
  Specified by:
  
  getOutEdges in class DiGraph<N,E>
- createDirectedGraphNode
  
  public DiGraph.DiGraphNode<N,E> createDirectedGraphNode(N nodeValue)
  
  Specified by:
  
  createDirectedGraphNode in class DiGraph<N,E>
- 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.
- 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.
- getDirectedGraphEdges
  
  public List<DiGraph.DiGraphEdge<N,E>> getDirectedGraphEdges(N n1, N n2)
  
  Specified by:
  
  getDirectedGraphEdges in class DiGraph<N,E>
- isConnectedInDirection
  
  public boolean isConnectedInDirection(N n1, N n2)
  
  Description copied from class: DiGraph
  
  Checks whether two nodes in the graph are connected via a directed edge.
  
  Specified by:
  
  isConnectedInDirection in class DiGraph<N,E>
  
  Parameters:
  
  n1 - Node 1.
  
  n2 - Node 2.
  
  Returns:
  
  true if the graph contains edge from n1 to n2.
- isConnectedInDirection
  
  public boolean isConnectedInDirection(N n1, E edgeValue, N n2)
  
  Description copied from class: DiGraph
  
  Checks whether two nodes in the graph are connected via a directed edge with the given value.
  
  Specified by:
  
  isConnectedInDirection in class DiGraph<N,E>
  
  Parameters:
  
  n1 - Node 1.
  
  edgeValue - edge value tag
  
  n2 - Node 2.
  
  Returns:
  
  true if the edge exists.
- getDirectedPredNodes
  
  public List<DiGraph.DiGraphNode<N,E>> getDirectedPredNodes(N nodeValue)
  
  Specified by:
  
  getDirectedPredNodes in class DiGraph<N,E>
- getDirectedSuccNodes
  
  public List<DiGraph.DiGraphNode<N,E>> getDirectedSuccNodes(N nodeValue)
  
  Specified by:
  
  getDirectedSuccNodes in class DiGraph<N,E>
- getDirectedPredNodes
  
  public List<DiGraph.DiGraphNode<N,E>> getDirectedPredNodes(DiGraph.DiGraphNode<N,E> dNode)
  
  Specified by:
  
  getDirectedPredNodes in class DiGraph<N,E>
- getDirectedSuccNodes
  
  public List<DiGraph.DiGraphNode<N,E>> getDirectedSuccNodes(DiGraph.DiGraphNode<N,E> dNode)
  
  Specified by:
  
  getDirectedSuccNodes in class DiGraph<N,E>
- 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.
- 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.
- getName
  
  public String getName()
  
  Description copied from interface: GraphvizGraph
  
  Name of the graph.
  
  Specified by:
  
  getName in interface GraphvizGraph
  
  Returns:
  
  Name of 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>
- 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.
- getNeighborNodes
  
  public List<GraphNode<N,E>> getNeighborNodes(DiGraph.DiGraphNode<N,E> node)
- getNeighborNodesIterator
  
  public Iterator<GraphNode<N,E>> getNeighborNodesIterator(N value)
  
  Specified by:
  
  getNeighborNodesIterator 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.

Class LinkedDirectedGraph<N,E>

Nested Class Summary

Nested classes/interfaces inherited from class com.google.javascript.jscomp.graph.DiGraph

Nested classes/interfaces inherited from class com.google.javascript.jscomp.graph.Graph

Nested classes/interfaces inherited from interface com.google.javascript.jscomp.graph.GraphvizGraph

Field Summary

Constructor Summary

Method Summary

Methods inherited from class com.google.javascript.jscomp.graph.DiGraph

Methods inherited from class com.google.javascript.jscomp.graph.Graph

Methods inherited from class java.lang.Object

Field Details

nodes

Constructor Details

LinkedDirectedGraph

Method Details

newSubGraph

createWithoutAnnotations

createWithNodeAnnotations

createWithEdgeAnnotations

create

connect

disconnect

disconnectInDirection

getDirectedGraphNodes

getDirectedGraphNode

getNode

getInEdges

getOutEdges

createDirectedGraphNode

getEdges

getFirstEdge

createNode

getDirectedGraphEdges

isConnectedInDirection

isConnectedInDirection

getDirectedPredNodes

getDirectedSuccNodes

getDirectedPredNodes

getDirectedSuccNodes

getGraphvizEdges

getGraphvizNodes

getName

isDirected

getNodes

getNeighborNodes

getNeighborNodes

getNeighborNodesIterator

getEdges

getNodeDegree