org.gersteinlab.tyna.core.graph
Class AbstractGraph

java.lang.Object
  extended by org.gersteinlab.tyna.core.graph.AbstractGraph
All Implemented Interfaces:
java.io.Serializable, AdvancedGraph, Graph
Direct Known Subclasses:
AbstractMultiGraph, AbstractSimpleGraph

public abstract class AbstractGraph
extends java.lang.Object
implements AdvancedGraph

        This class is the abstract parent class of all actual graph classes. It
        contians some codes common to all graph classes.

        The reasons for having a Graph class and an AbstractGraph class are as
        follows:
        . Each actual graph class may have multiple "parents", such as
          SimpleGraph and DirectedGraph. This can only be achieved by interfaces
          but not abstract classes.
        . The interfaces, having short names such as Graph, are convenient to
          use. They are the official signatures to declare that a class is a
          graph class.
        . The interfaces are for sharing, so that other implemenations may also
          follow them. The abstract classes correspond to the current specific
          implementation.
        . Abstract classes are defined to avoid redundant codes that are common
          among different actual graph classes.
        

Version:
1.2 (September 10, 2007) Change History: 1.0 - Initial version 1.1 - nodes becomes a ID -> node map 1.2 - Added adjacency, Laplacian and diffusion distance matrices
Author:
Kevin Yuk-Lap Yip
See Also:
Serialized Form

Nested Class Summary
protected  class AbstractGraph.AbstractGraphEdgeIterator
           
protected  class AbstractGraph.AbstractGraphNodeIterator
           
protected  class AbstractGraph.BetweennessNode
          A utility class for calculating betweenness.
protected  class AbstractGraph.DuplicateTree
          A utility class for removing duplicated chains/cycles.
protected  class AbstractGraph.HeadTailTree
          A utility class for computing minimal and maximal motifs.
protected  class AbstractGraph.HeadTree
          A utility class for computing minimal and maximal motifs.
protected  class AbstractGraph.TailTree
          A utility class for computing minimal and maximal motifs.
 
Field Summary
protected  java.util.Map attrs
          The attributes of the graph.
protected  int edgeCount
          The number of edges in the graph.
protected  java.util.Map edges
          The edges of the graph.
protected  long lastModified
          The last modified time of the graph.
protected  java.util.Map nodes
          The nodes of the graph.
protected  java.util.Map revEdges
          The reverse edges of the graph if it is directed.
 
Constructor Summary
AbstractGraph()
          Default constructor: creates an empty graph.
AbstractGraph(Graph graph)
          Copy constructor: creates a copy of an existing graph.
 
Method Summary
protected  void accumulateLocalBetweenness(AbstractGraph.BetweennessNode bn, java.util.Map result)
           
 void addNode(Node node)
          Add a node to the graph.
protected  void checkEdge(Edge edge)
          Check if an edge is non null.
protected  void checkNode(Node node)
          Check if a node is non null and is in the graph.
protected  void computeLocalBetweenness(AbstractGraph.BetweennessNode bn)
           
 boolean containsEdge(Node node1, Node node2)
          Whether there is an edge between the two nodes.
 boolean containsNode(Node node)
          Whether a given node is in the graph.
 int[][] getAdjacencyMatrix(java.util.List nodeList)
          Get the adjacency matrix of a subgraph according to a given node order.
 java.util.Map getAllUnweightedShortestPaths()
          Get all unweighted shortest paths from every node to every node.
 java.util.Map getAllUnweightedShortestPaths(Node node1)
          Get all unweighted shortest paths from a given node to every node.
 java.util.List getAllUnweightedShortestPaths(Node node1, Node node2)
          Get all unweighted shortest paths from node1 to node2.
 java.lang.Object getAttr(java.lang.Object attrName)
          Get the (possibly null) value of an attribute of the graph.
 java.util.Map getAttrs()
          Get the (possibly null) attribute map of the graph.
 double getBetweenness(Node node)
          Get the betweenness of a node n, which is defined as the number of node pairs (n1, n2) where the shortest path from n1 to n2 passes through n, with the following two requirements: .
 java.util.Map getBetweennesses()
          A simple algorithm that involves two phases: a minimum spanning graph constructing phase and a depth-first computation phase.
 double getClusCoef(Node node)
          Get the clustering coefficient of a node n, which is defined as follows: let E(n) be the set of nodes n'<>n such that (n, n1) is in the set of all edges of the graph, E.
 java.util.Map getClusCoefs()
          Get the clustering coefficients of all nodes in the graph.
 int getConnectedComponentCount()
          Get the number of connected components in the graph.
 java.util.List getConnectedComponents()
          Get the connected components of the graph.
 java.util.List getCycles(int minSize, int maxSize)
          Get all cycles of distinct nodes that .
protected  void getCycles(int minSize, int maxSize, java.util.LinkedHashSet chain, Node last, java.util.Set checkedNodes, java.util.List result)
           
protected  java.util.List getDefectiveCliquesMissingEdges(int k, int l)
           
protected  int getDegree(Node node)
           
protected  java.util.Map getDegrees()
           
protected  double[][] getDiffusionDistanceMatrix(double beta, int[][] laplacianMatrix)
           
protected  double[][] getDiffusionDistanceMatrix(double beta, java.util.List nodeList)
           
 java.util.Map getEccentricities()
          Get the eccentricities of all nodes in the graph.
 int getEccentricity(Node node)
          Get the eccentricity of a node n, which is deinfed as follows: A maximum shortest path of node n is a shortest path from n to a node reachable from it that has the largest length among all shortest paths from n to its reachable nodes.
 java.util.Map getEdgeBetweennesses()
          A simple algorithm that involves two phases: a minimum spanning graph constructing phase and a depth-first computation phase.
 int getEdgeCount()
          Get the number of edges in the graph.
 java.util.List getEdgeNodePairs()
          Return a list of unique node pairs between which there is an edge from the first node to the second node.
protected  java.util.List getEdges(Node node)
           
protected  java.util.List getFeedforwardLoops(int minSize, int maxSize)
           
protected  void getFeedforwardLoops(int minSize, int maxSize, java.util.LinkedHashSet chain, Node last, java.util.List result)
           
protected abstract  int getInDegree(Node node)
           
protected  java.util.Map getInDegrees()
           
protected abstract  java.util.List getInEdges(Node node)
           
protected  java.util.Set getInNeighbors(Node node)
           
protected  int[][] getLaplacianMatrix(int[][] adjacencyMatrix)
           
protected  int[][] getLaplacianMatrix(java.util.List nodeList)
           
 java.util.List getMaximalChains(int minSize, int maxSize)
          Get all chains of distinct nodes that .
protected  java.util.List getMaximalCliques()
           
protected  java.util.List getMaximalCompleteTwoLayerSubgraphs(int minSize1, int maxSize1, int minSize2)
           
protected  java.util.List getMaximalIndependentSets()
           
 java.util.List getMinimalChains(int minSize)
          Get all chains of distinct nodes that .
protected  java.util.Set getNeighbors(Node node)
           
 Node getNode(java.lang.Object nodeId)
          Get the node that has the input node ID.
 int getNodeCount()
          Get the number of nodes in the graph.
 NodeIterator getNodeIterator()
          Return an iterator of the nodes in the graph.
protected abstract  int getOutDegree(Node node)
           
protected  java.util.Map getOutDegrees()
           
protected abstract  java.util.List getOutEdges(Node node)
           
protected  java.util.Set getOutNeighbors(Node node)
           
 java.util.List getUnweightedShortestPath(Node node1, Node node2)
          Get an unweighted shortest path from node1 to node2.
 int getUnweightedShortestPathLength(Node node1, Node node2)
          Get the unweighted shortest path length from node1 to node2.
 java.util.Map getUnweightedShortestPathLengths()
          Get the unweighted shortest path lengths from every node to every node.
 java.util.Map getUnweightedShortestPathLengths(Node node1)
          Get the unweighted shortest path lengths from every node to every node.
 java.util.Map getUnweightedShortestPaths()
          Get an unweighted shortest path from every node to every node.
 java.util.Map getUnweightedShortestPaths(Node node1)
          Get an unweighted shortest path from a given node to every node.
protected  java.util.Map getUnweightedShortestPaths(Node node1, boolean findAll)
           
protected  java.util.List getUnweightedShortestPaths(Node node1, Node node2, boolean findAll)
           
protected  void markModified()
          Mark the current object as modified.
protected  void saveGraph(Graph graph)
          Copy the content of the input graph to this object.
 void setAttr(java.lang.Object attrName, java.lang.Object attrVal)
          Set the value of an attribute of the graph.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface org.gersteinlab.tyna.core.graph.Graph
addEdge, getEdgeIterator
 

Field Detail

nodes

protected java.util.Map nodes
The nodes of the graph.


edges

protected java.util.Map edges
The edges of the graph. A (node1 -> neighbors) map, where neighbors is a (node2 -> attributes) map, and attributes could be a map or a list of map, depending on whether the graph is a simple graph or a multigraph.


revEdges

protected java.util.Map revEdges
The reverse edges of the graph if it is directed. For undirected graph, it points to edges.


attrs

protected java.util.Map attrs
The attributes of the graph.


edgeCount

protected int edgeCount
The number of edges in the graph.


lastModified

protected long lastModified
The last modified time of the graph.

Constructor Detail

AbstractGraph

public AbstractGraph()
Default constructor: creates an empty graph.


AbstractGraph

public AbstractGraph(Graph graph)
              throws GraphTypeException,
                     java.lang.NullPointerException
Copy constructor: creates a copy of an existing graph. It does not handle graph types explicitly, but let methods such as addNode() to handle. For example, if the copy constructor of a simple graph object is called with a multigraph object supplied as parameter value, the instantiation will be successful if the multigraph does not have properties that violate a simple graph. Similarly, if the copy constructor of an undirected graph object is called with a directed graph object, each directed edge will be treated as an undirected edge. If there is a directed edge from node1 to node2 and also one from node2 to node1, the instantiation will not be successful if the undirected graph is simple. The Node and Edge objects in the original graph will be shared by both Graph objects, but they do not share the node and edge lists. This means adding or removing nodes/edges from one graph will not affect the content of the other graph.

Throws:
GraphTypeException - If the input graph cannot be created as an object of the target graph type
java.lang.NullPointerException - If graph == null
Method Detail

addNode

public void addNode(Node node)
             throws GraphTypeException,
                    java.lang.NullPointerException
Description copied from interface: Graph
Add a node to the graph. If the node already exists, the graph will keep only one copy. See Node for the definition of two nodes being equal.

Specified by:
addNode in interface Graph
Parameters:
node - The node
Throws:
GraphTypeException - If the addition of the node violdates some requirements of the graph type
java.lang.NullPointerException - If node == null

containsNode

public boolean containsNode(Node node)
                     throws java.lang.NullPointerException
Description copied from interface: Graph
Whether a given node is in the graph.

Specified by:
containsNode in interface Graph
Parameters:
node - The node
Returns:
Whether the node is in the graph
Throws:
java.lang.NullPointerException - If node == null

containsEdge

public boolean containsEdge(Node node1,
                            Node node2)
                     throws java.lang.IllegalArgumentException,
                            java.lang.NullPointerException
Description copied from interface: Graph
Whether there is an edge between the two nodes. If the graph is directed, it is to ask whether there is an edge form the first node to the second node.

Specified by:
containsEdge in interface Graph
Parameters:
node1 - The first node
node2 - The second node
Returns:
Whether there is an edge between the nodes
Throws:
java.lang.IllegalArgumentException - If any of the nodes is not in the graph
java.lang.NullPointerException - If node1 == null or node2 == null

getNode

public Node getNode(java.lang.Object nodeId)
Description copied from interface: Graph
Get the node that has the input node ID.

Specified by:
getNode in interface Graph
Parameters:
nodeId - The node ID
Returns:
The node if exist, null otherwise

getAttr

public java.lang.Object getAttr(java.lang.Object attrName)
Description copied from interface: Graph
Get the (possibly null) value of an attribute of the graph.

Specified by:
getAttr in interface Graph
Parameters:
attrName - The name of the attribute
Returns:
The value of the attribute

getAttrs

public java.util.Map getAttrs()
Description copied from interface: Graph
Get the (possibly null) attribute map of the graph. A copy of the stored map is returned.

Specified by:
getAttrs in interface Graph
Returns:
The attribute map

setAttr

public void setAttr(java.lang.Object attrName,
                    java.lang.Object attrVal)
Description copied from interface: Graph
Set the value of an attribute of the graph.

Specified by:
setAttr in interface Graph
Parameters:
attrName - The name of the attribute
attrVal - The value of the attribute

getNodeCount

public int getNodeCount()
Description copied from interface: Graph
Get the number of nodes in the graph.

Specified by:
getNodeCount in interface Graph
Returns:
The number of nodes in the graph.

getEdgeCount

public int getEdgeCount()
Description copied from interface: Graph
Get the number of edges in the graph.

Specified by:
getEdgeCount in interface Graph
Returns:
The number of edges in the graph.

getNodeIterator

public NodeIterator getNodeIterator()
Description copied from interface: Graph
Return an iterator of the nodes in the graph. Unless otherwise specified by the implemented class, the node order in the returned iterator needs not be predictable from the order in which the nodes are added and/or removed.

Specified by:
getNodeIterator in interface Graph
Returns:
The iterator

getEdgeNodePairs

public java.util.List getEdgeNodePairs()
Description copied from interface: Graph
Return a list of unique node pairs between which there is an edge from the first node to the second node. For undirected graphs, the order is unimportant, but only one of the two possible orders will be returned.

Specified by:
getEdgeNodePairs in interface Graph
Returns:
The list of node pairs, each as a Node[]

getAdjacencyMatrix

public int[][] getAdjacencyMatrix(java.util.List nodeList)
Description copied from interface: AdvancedGraph
Get the adjacency matrix of a subgraph according to a given node order.

Specified by:
getAdjacencyMatrix in interface AdvancedGraph
Parameters:
nodeList - The list of nodes in the subgraph
Returns:
The adjacency matrix

getBetweenness

public double getBetweenness(Node node)
                      throws java.lang.IllegalArgumentException,
                             java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get the betweenness of a node n, which is defined as the number of node pairs (n1, n2) where the shortest path from n1 to n2 passes through n, with the following two requirements: . For undirected graphs, n1 <> n2 . A shortest path is not counted as passing through its two end points If there are multiple shortest paths from n1 to n2, the count will be the fraction of the paths that pass through the node.

Specified by:
getBetweenness in interface AdvancedGraph
Parameters:
node - The node
Returns:
The betweenness of the node
Throws:
java.lang.IllegalArgumentException - If the node is not in the graph
java.lang.NullPointerException - If node == null

getBetweennesses

public java.util.Map getBetweennesses()
A simple algorithm that involves two phases: a minimum spanning graph constructing phase and a depth-first computation phase.

Specified by:
getBetweennesses in interface AdvancedGraph
Returns:
The betweenness of the nodes, in a Node to Double map

getEdgeBetweennesses

public java.util.Map getEdgeBetweennesses()
A simple algorithm that involves two phases: a minimum spanning graph constructing phase and a depth-first computation phase. Multiple edges from a node to another are treated as a single edge.

Specified by:
getEdgeBetweennesses in interface AdvancedGraph
Returns:
The betweenness of the edges, in an Edge to (Edge to Double map) map

computeLocalBetweenness

protected void computeLocalBetweenness(AbstractGraph.BetweennessNode bn)

accumulateLocalBetweenness

protected void accumulateLocalBetweenness(AbstractGraph.BetweennessNode bn,
                                          java.util.Map result)

getClusCoef

public double getClusCoef(Node node)
                   throws java.lang.IllegalArgumentException,
                          java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get the clustering coefficient of a node n, which is defined as follows: let E(n) be the set of nodes n'<>n such that (n, n1) is in the set of all edges of the graph, E. ClusCoef(n) = (\sum_{n1 \in E(n), n2 \in E(n), n1 \neq n2} I((n1, n2) \in E)) / (|E(n) * (E(n) - 1)|), where I is the indicator function: I(true) = 1, I(false) = 0. Notes: . For directed graphs, (n1, n2) is different from (n2, n1). . For undirected graphs, each node in E(n) acts as n1 once and n2 once . For nodes that have zero or one neighbors, the clustering coefficient is defined as 0.

Specified by:
getClusCoef in interface AdvancedGraph
Parameters:
node - The node
Returns:
The clustering coefficient of the node
Throws:
java.lang.IllegalArgumentException - If the node is not in the graph
java.lang.NullPointerException - If node == null

getClusCoefs

public java.util.Map getClusCoefs()
Description copied from interface: AdvancedGraph
Get the clustering coefficients of all nodes in the graph.

Specified by:
getClusCoefs in interface AdvancedGraph
Returns:
The clustering coefficients of the nodes, in a Node to Double map

getConnectedComponents

public java.util.List getConnectedComponents()
Description copied from interface: AdvancedGraph
Get the connected components of the graph.

Specified by:
getConnectedComponents in interface AdvancedGraph
Returns:
The connected components, in a List of Set objects

getConnectedComponentCount

public int getConnectedComponentCount()
Description copied from interface: AdvancedGraph
Get the number of connected components in the graph.

Specified by:
getConnectedComponentCount in interface AdvancedGraph
Returns:
The number of connected components

getEccentricity

public int getEccentricity(Node node)
                    throws java.lang.IllegalArgumentException,
                           java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get the eccentricity of a node n, which is deinfed as follows: A maximum shortest path of node n is a shortest path from n to a node reachable from it that has the largest length among all shortest paths from n to its reachable nodes. The shortest path length, i.e., the eccentricity, of a node n is the length of its maximum shortest paths.

Specified by:
getEccentricity in interface AdvancedGraph
Parameters:
node - The node
Returns:
The eccentricity of the node (-1 if there are no paths from n to any node)
Throws:
java.lang.IllegalArgumentException - If the node is not in the graph
java.lang.NullPointerException - If node == null

getEccentricities

public java.util.Map getEccentricities()
Description copied from interface: AdvancedGraph
Get the eccentricities of all nodes in the graph.

Specified by:
getEccentricities in interface AdvancedGraph
Returns:
The eccentricities of the nodes, in a Node to Integer map

getUnweightedShortestPath

public java.util.List getUnweightedShortestPath(Node node1,
                                                Node node2)
                                         throws java.lang.IllegalArgumentException,
                                                java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get an unweighted shortest path from node1 to node2. The path is shortest in terms of the number of hops.

Specified by:
getUnweightedShortestPath in interface AdvancedGraph
Parameters:
node1 - The source node
node2 - The destination node
Returns:
A list of nodes, including node1 and node2, on the shortest path. null if there exists no path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.
Throws:
java.lang.IllegalArgumentException - If any of the nodes is not in the graph
java.lang.NullPointerException - If node1 == null or node2 == null

getAllUnweightedShortestPaths

public java.util.List getAllUnweightedShortestPaths(Node node1,
                                                    Node node2)
                                             throws java.lang.IllegalArgumentException,
                                                    java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get all unweighted shortest paths from node1 to node2. The paths are shortest in terms of the number of hops.

Specified by:
getAllUnweightedShortestPaths in interface AdvancedGraph
Parameters:
node1 - The source node
node2 - The destination node
Returns:
A list of shortest paths, each as a list of nodes, including node1 and node2, on the shortest path. null if there exists no path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.
Throws:
java.lang.IllegalArgumentException - If any of the nodes is not in the graph
java.lang.NullPointerException - If node1 == null or node2 == null

getUnweightedShortestPaths

protected java.util.List getUnweightedShortestPaths(Node node1,
                                                    Node node2,
                                                    boolean findAll)
                                             throws java.lang.IllegalArgumentException,
                                                    java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException

getUnweightedShortestPathLength

public int getUnweightedShortestPathLength(Node node1,
                                           Node node2)
                                    throws java.lang.IllegalArgumentException,
                                           java.lang.NullPointerException
Description copied from interface: AdvancedGraph
Get the unweighted shortest path length from node1 to node2.

Specified by:
getUnweightedShortestPathLength in interface AdvancedGraph
Parameters:
node1 - The source node
node2 - The destination node
Returns:
The shortest path length. -1 if there exists no paths from node1 to node2. The situation that node1 equals node2 is not treated as a special case. The length is -1 if there is no explicit path from node1 back to itself, 1 if it has a self loop, and the shortest path length otherwise.
Throws:
java.lang.IllegalArgumentException - If any of the nodes is not in the graph
java.lang.NullPointerException - If node1 == null or node2 == null

getUnweightedShortestPaths

public java.util.Map getUnweightedShortestPaths(Node node1)
Description copied from interface: AdvancedGraph
Get an unweighted shortest path from a given node to every node.

Specified by:
getUnweightedShortestPaths in interface AdvancedGraph
Parameters:
node1 - The source node
Returns:
A (Node node2 -> List shortestPath) map (has entries only for those node2 that are reachable from node1), shortestPath is a list of nodes, including node1 and node2, on a shortest path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.

getAllUnweightedShortestPaths

public java.util.Map getAllUnweightedShortestPaths(Node node1)
Description copied from interface: AdvancedGraph
Get all unweighted shortest paths from a given node to every node.

Specified by:
getAllUnweightedShortestPaths in interface AdvancedGraph
Parameters:
node1 - The source node
Returns:
A (Node node2 -> List shortestPaths) map (has entries only for those node2 that are reachable from node1), shortestPaths is a list of shortest paths, each as a list of nodes, including node1 and node2, on the shortest path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.

getUnweightedShortestPaths

protected java.util.Map getUnweightedShortestPaths(Node node1,
                                                   boolean findAll)
                                            throws java.lang.IllegalArgumentException,
                                                   java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException

getUnweightedShortestPathLengths

public java.util.Map getUnweightedShortestPathLengths(Node node1)
Description copied from interface: AdvancedGraph
Get the unweighted shortest path lengths from every node to every node.

Specified by:
getUnweightedShortestPathLengths in interface AdvancedGraph
Parameters:
node1 - The source node
Returns:
A (Node node2 -> Integer length) map (has entries only for thoese node2 that are reachable from node2), length is the shortest path length from node1 to node2. The situation that node1 equals node2 is not treated as a special case. The length is -1 if there is no explicit path from node1 back to itself, 1 if it has a self loop, and the shortest path length otherwise.

getUnweightedShortestPaths

public java.util.Map getUnweightedShortestPaths()
Description copied from interface: AdvancedGraph
Get an unweighted shortest path from every node to every node.

Specified by:
getUnweightedShortestPaths in interface AdvancedGraph
Returns:
A (Node node1 -> Map map1) map (each node must have an entry), map1 is a (Node node2 -> List shortestPath) map (has entries only for those node2 that are reachable from node1), shortestPath is a list of nodes, including node1 and node2, on a shortest path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.

getAllUnweightedShortestPaths

public java.util.Map getAllUnweightedShortestPaths()
Description copied from interface: AdvancedGraph
Get all unweighted shortest paths from every node to every node.

Specified by:
getAllUnweightedShortestPaths in interface AdvancedGraph
Returns:
A (Node node1 -> Map map1) map (each node must have an entry), map1 is a (Node node2 -> List shortestPaths) map (has entries only for those node2 that are reachable from node1), shortestPaths is a list of shortest paths, each as a list of nodes, including node1 and node2, on the shortest path from node1 to node2. If node1 equals node2, the list exists only if there is a path from node1 back to itself. If node1 has a self loop, the list contains two entries of node1, just as in other paths.

getUnweightedShortestPathLengths

public java.util.Map getUnweightedShortestPathLengths()
Description copied from interface: AdvancedGraph
Get the unweighted shortest path lengths from every node to every node.

Specified by:
getUnweightedShortestPathLengths in interface AdvancedGraph
Returns:
A (Node node1 -> Map map1) map (each node must have an entry), map1 is a (Node node2 -> Integer length) map (has entries only for thoese node2 that are reachable from node2), length is the shortest path length from node1 to node2. The situation that node1 equals node2 is not treated as a special case. The length is -1 if there is no explicit path from node1 back to itself, 1 if it has a self loop, and the shortest path length otherwise.

getMinimalChains

public java.util.List getMinimalChains(int minSize)
                                throws java.lang.IllegalArgumentException
Description copied from interface: AdvancedGraph
Get all chains of distinct nodes that . Have at least minSize nodes . Are minimal, i.e., no deletions of consecutive nodes from the head or tail result in a chain that satisfies the above requirement

Specified by:
getMinimalChains in interface AdvancedGraph
Returns:
A list of Node[], each representing a chain
Throws:
java.lang.IllegalArgumentException - If the input size is invalid

getMaximalChains

public java.util.List getMaximalChains(int minSize,
                                       int maxSize)
                                throws java.lang.IllegalArgumentException
Description copied from interface: AdvancedGraph
Get all chains of distinct nodes that . Have at least minSize nodes . Have at most maxSize nodes . Are maximal, i.e., no insertions of consecutive nodes to the head or tail result in a chain that satisfies the above requirements

Specified by:
getMaximalChains in interface AdvancedGraph
Returns:
A list of Node[], each representing a chain
Throws:
java.lang.IllegalArgumentException - If the input sizes are invalid

getCycles

public java.util.List getCycles(int minSize,
                                int maxSize)
                         throws java.lang.IllegalArgumentException
Description copied from interface: AdvancedGraph
Get all cycles of distinct nodes that . Have at least minSize nodes . Have at most maxSize nodes

Specified by:
getCycles in interface AdvancedGraph
Returns:
A list of Node[], each representing a cycle by an array of distinct nodes
Throws:
java.lang.IllegalArgumentException - If the input sizes are invalid

getCycles

protected void getCycles(int minSize,
                         int maxSize,
                         java.util.LinkedHashSet chain,
                         Node last,
                         java.util.Set checkedNodes,
                         java.util.List result)

getDegree

protected int getDegree(Node node)
                 throws java.lang.IllegalArgumentException,
                        java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
UndirectedGraph.getDegree(Node)

getInDegree

protected abstract int getInDegree(Node node)
                            throws java.lang.IllegalArgumentException,
                                   java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getOutDegree(Node)

getOutDegree

protected abstract int getOutDegree(Node node)
                             throws java.lang.IllegalArgumentException,
                                    java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getOutDegree(Node)

getDegrees

protected java.util.Map getDegrees()
See Also:
UndirectedGraph.getDegrees()

getInDegrees

protected java.util.Map getInDegrees()
See Also:
DirectedGraph.getInDegrees()

getOutDegrees

protected java.util.Map getOutDegrees()
See Also:
DirectedGraph.getOutDegrees()

getEdges

protected java.util.List getEdges(Node node)
                           throws java.lang.IllegalArgumentException,
                                  java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
UndirectedGraph.getDegree(Node)

getInEdges

protected abstract java.util.List getInEdges(Node node)
                                      throws java.lang.IllegalArgumentException,
                                             java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getInEdges(Node)

getOutEdges

protected abstract java.util.List getOutEdges(Node node)
                                       throws java.lang.IllegalArgumentException,
                                              java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getOutEdges(Node)

getNeighbors

protected java.util.Set getNeighbors(Node node)
                              throws java.lang.IllegalArgumentException,
                                     java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
UndirectedGraph.getDegree(Node)

getInNeighbors

protected java.util.Set getInNeighbors(Node node)
                                throws java.lang.IllegalArgumentException,
                                       java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getInNeighbors(Node)

getOutNeighbors

protected java.util.Set getOutNeighbors(Node node)
                                 throws java.lang.IllegalArgumentException,
                                        java.lang.NullPointerException
Throws:
java.lang.IllegalArgumentException
java.lang.NullPointerException
See Also:
DirectedGraph.getOutNeighbors(Node)

getFeedforwardLoops

protected java.util.List getFeedforwardLoops(int minSize,
                                             int maxSize)
                                      throws java.lang.IllegalArgumentException
Throws:
java.lang.IllegalArgumentException
See Also:
AdvancedDirectedGraph.getFeedforwardLoops(int,int)

getFeedforwardLoops

protected void getFeedforwardLoops(int minSize,
                                   int maxSize,
                                   java.util.LinkedHashSet chain,
                                   Node last,
                                   java.util.List result)

getMaximalCompleteTwoLayerSubgraphs

protected java.util.List getMaximalCompleteTwoLayerSubgraphs(int minSize1,
                                                             int maxSize1,
                                                             int minSize2)
                                                      throws java.lang.IllegalArgumentException
Throws:
java.lang.IllegalArgumentException
See Also:
AdvancedDirectedGraph.getMaximalCompleteTwoLayerSubgraphs(int, int, int)

getLaplacianMatrix

protected int[][] getLaplacianMatrix(java.util.List nodeList)
See Also:
AdvancedUndirectedGraph.getLaplacianMatrix(List)

getLaplacianMatrix

protected int[][] getLaplacianMatrix(int[][] adjacencyMatrix)
See Also:
AdvancedUndirectedGraph.getLaplacianMatrix(int[][])

getDiffusionDistanceMatrix

protected double[][] getDiffusionDistanceMatrix(double beta,
                                                java.util.List nodeList)
                                         throws JSci.maths.MaximumIterationsExceededException
Throws:
JSci.maths.MaximumIterationsExceededException - If the eigen problem cannot be solved in a predefined number of iterations
See Also:
AdvancedUndirectedGraph#getDiffusionDistancematrix(double, List)

getDiffusionDistanceMatrix

protected double[][] getDiffusionDistanceMatrix(double beta,
                                                int[][] laplacianMatrix)
                                         throws JSci.maths.MaximumIterationsExceededException
Throws:
JSci.maths.MaximumIterationsExceededException - If the eigen problem cannot be solved in a predefined number of iterations
See Also:
AdvancedUndirectedGraph.getDiffusionDistanceMatrix(double, int[][])

getMaximalIndependentSets

protected java.util.List getMaximalIndependentSets()
See Also:
AdvancedUndirectedGraph.getMaximalIndependentSets()

getMaximalCliques

protected java.util.List getMaximalCliques()
See Also:
AdvancedUndirectedGraph.getMaximalCliques()

getDefectiveCliquesMissingEdges

protected java.util.List getDefectiveCliquesMissingEdges(int k,
                                                         int l)
                                                  throws java.lang.IllegalArgumentException
Throws:
java.lang.IllegalArgumentException
See Also:
AdvancedUndirectedGraph.getDefectiveCliquesMissingEdges(int, int)

checkNode

protected void checkNode(Node node)
                  throws java.lang.IllegalArgumentException,
                         java.lang.NullPointerException
Check if a node is non null and is in the graph.

Parameters:
node - The node to be checked
Throws:
java.lang.IllegalArgumentException - If the node is not in the graph
java.lang.NullPointerException - If node == null

checkEdge

protected void checkEdge(Edge edge)
                  throws java.lang.NullPointerException
Check if an edge is non null.

Parameters:
edge - The edge to be checked
Throws:
java.lang.NullPointerException - If edge == null

markModified

protected void markModified()
Mark the current object as modified. This method saves the current time as the last modified time, and removes all cached objects (not including edgeCount, which is supposed to be updated by the modification methods).


saveGraph

protected void saveGraph(Graph graph)
                  throws GraphTypeException,
                         java.lang.NullPointerException
Copy the content of the input graph to this object.

Parameters:
graph - The input graph
Throws:
GraphTypeException - If the input graph is not compatible with the current one
java.lang.NullPointerException - If graph == null