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 |
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 nodenode2
- 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 nodenode2
- 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 nodenode2
- 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