org.gersteinlab.tyna.core.graph
Interface AdvancedGraph

All Superinterfaces:
Graph, java.io.Serializable
All Known Implementing Classes:
AbstractGraph, AbstractMultiGraph, AbstractSimpleGraph, DirectedMultiGraph, DirectedSimpleGraph, UndirectedMultiGraph, UndirectedSimpleGraph

public interface AdvancedGraph
extends Graph

        This interface declares advanced methods such as graph statistics that
        are not mandatory for basic implementations of Graph classes.

        The methods are not synchronized for efficiency reasons. May need to
        change in the future if concurrent access is required.
        

Version:
1.1 (September 10, 2007) Change History: 1.0 - Initial version 1.1 - Added adjacency matrix
Author:
Kevin Yuk-Lap Yip

Method Summary
 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.
 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()
          Get the betweenness of all nodes in the graph.
 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 .
 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()
          Get the betweenness of all edges in the graph.
 java.util.List getMaximalChains(int minSize, int maxSize)
          Get all chains of distinct nodes that .
 java.util.List getMinimalChains(int minSize)
          Get all chains of distinct nodes that .
 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.
 
Methods inherited from interface org.gersteinlab.tyna.core.graph.Graph
addEdge, addNode, containsEdge, containsNode, getAttr, getAttrs, getEdgeCount, getEdgeIterator, getEdgeNodePairs, getNode, getNodeCount, getNodeIterator, setAttr
 

Method Detail

getAdjacencyMatrix

int[][] getAdjacencyMatrix(java.util.List nodeList)
Get the adjacency matrix of a subgraph according to a given node order.

Parameters:
nodeList - The list of nodes in the subgraph
Returns:
The adjacency matrix

getClusCoef

double getClusCoef(Node node)
                   throws java.lang.IllegalArgumentException,
                          java.lang.NullPointerException
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.

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

java.util.Map getClusCoefs()
Get the clustering coefficients of all nodes in the graph.

Returns:
The clustering coefficients of the nodes, in a Node to Double map

getEccentricity

int getEccentricity(Node node)
                    throws java.lang.IllegalArgumentException,
                           java.lang.NullPointerException
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.

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

java.util.Map getEccentricities()
Get the eccentricities of all nodes in the graph.

Returns:
The eccentricities of the nodes, in a Node to Integer map

getBetweenness

double getBetweenness(Node node)
                      throws java.lang.IllegalArgumentException,
                             java.lang.NullPointerException
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.

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

java.util.Map getBetweennesses()
Get the betweenness of all nodes in the graph.

Returns:
The betweenness of the nodes, in a Node to Double map

getEdgeBetweennesses

java.util.Map getEdgeBetweennesses()
Get the betweenness of all edges in the graph.

Returns:
The betweenness of the edges, in an Edge to (Edge to Double map) map

getConnectedComponents

java.util.List getConnectedComponents()
Get the connected components of the graph.

Returns:
The connected components, in a List of Set objects

getConnectedComponentCount

int getConnectedComponentCount()
Get the number of connected components in the graph.

Returns:
The number of connected components

getUnweightedShortestPath

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

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

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

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

getUnweightedShortestPathLength

int getUnweightedShortestPathLength(Node node1,
                                    Node node2)
                                    throws java.lang.IllegalArgumentException,
                                           java.lang.NullPointerException
Get the unweighted shortest path length from node1 to node2.

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

java.util.Map getUnweightedShortestPaths(Node node1)
Get an unweighted shortest path from a given node to every node.

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

java.util.Map getAllUnweightedShortestPaths(Node node1)
Get all unweighted shortest paths from a given node to every node.

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.

getUnweightedShortestPathLengths

java.util.Map getUnweightedShortestPathLengths(Node node1)
Get the unweighted shortest path lengths from every node to every node.

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

java.util.Map getUnweightedShortestPaths()
Get an unweighted shortest path from every node to every node.

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

java.util.Map getAllUnweightedShortestPaths()
Get all unweighted shortest paths from every node to every node.

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

java.util.Map getUnweightedShortestPathLengths()
Get the unweighted shortest path lengths from every node to every node.

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

java.util.List getMinimalChains(int minSize)
                                throws java.lang.IllegalArgumentException
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

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

getMaximalChains

java.util.List getMaximalChains(int minSize,
                                int maxSize)
                                throws java.lang.IllegalArgumentException
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

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

getCycles

java.util.List getCycles(int minSize,
                         int maxSize)
                         throws java.lang.IllegalArgumentException
Get all cycles of distinct nodes that . Have at least minSize nodes . Have at most maxSize nodes

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