fr.curie.BiNoM.pathways.analysis.structure
Class GraphAlgorithms

java.lang.Object
  fr.curie.BiNoM.pathways.analysis.structure.GraphAlgorithms

public class GraphAlgorithms
extends java.lang.Object

Implementation of graph algorithms without use of any node or edge semantics

Constructor Summary

GraphAlgorithms()

Method Summary

static java.util.Vector<Graph>	CombineIncludedGraphsApprox(java.util.Vector<Graph> graphs, float thresh) Clusters graphs with node overlap more than threshold
static java.util.Vector<Graph>	ConnectedComponents(Graph graph)
static java.util.Vector<Graph>	CycleDecomposition(Graph graph, int sizeThreshold)
static java.util.Vector<Graph>	Dijkstra(Graph graph, Node source, Node target, boolean directedGraph, boolean suboptimal, double searchRadius)
static java.util.Vector<Graph>	DijkstraAlgorithm(Graph graph, Node source, Node target, boolean directedGraph, double searchRadius)
static void	DijkstraProcedure(Graph graph, int isource, int iend, double[] d, java.util.Vector<java.util.Vector<java.lang.Integer>> previous, boolean directedGraph, double searchRadius) Principal Dijkstra procedure 2 for each vertex v in V[G] // Initializations 3 d[v] := infinity // Unknown distance function from s to v 4 previous[v] := undefined 5 d[s] := 0 // Distance from s to s 6 S := empty set // Set of all visited vertices 7 Q := V[G] // Set of all unvisited vertices 8 while Q is not an empty set // The algorithm itself 9 u := Extract_Min(Q) // Remove best vertex from priority queue 10 S := S union {u} // Mark it 'visited' 11 for each edge (u,v) outgoing from u 12 if d[u] + w(u,v) < d[v] // Relax (u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u
static java.util.Set	extractClosestNodes(java.util.Set Q, double[] d, java.util.HashSet<java.lang.Integer> non_empties, java.util.Vector temp, double searchRadius) Sub-routine for Dijkstra algorithm search for an items with minimum d[item] and removes from Q
static java.util.Vector<Graph>	FindAllPaths(Graph graph, Node source, java.util.Set<Node> targets, boolean directedGraph, double searchRadius) Note: searchRadius here is the number of edges from source (edge weights are not considered)
static Graph	GetBiggestGraph(java.util.Vector v)
static Graph	GetConnectedComponent(Graph graph, Node n)
static java.util.Vector<java.util.Vector<Edge>>	neighboursOfNodeHash(Graph graph, boolean directedGraph) Sub-routine for Dijkstra's algorithm Returns vector (of length number of nodes) of vectors of outgoing edges numbers
static java.util.Vector<Graph>	PruneGraph(Graph graph, boolean includeInterface) Graph pruning (eliminataing IN and OUT layers)
static java.util.Vector<Graph>	StronglyConnectedComponentsTarjan(Graph graph, int minimumComponentSize)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphAlgorithms

public GraphAlgorithms()

Method Detail

ConnectedComponents

public static java.util.Vector<Graph> ConnectedComponents(Graph graph)

Parameters:

graph -

Returns:

List of connected components

StronglyConnectedComponentsTarjan

public static java.util.Vector<Graph> StronglyConnectedComponentsTarjan(Graph graph,
                                                                        int minimumComponentSize)

Parameters:

graph -

minimumComponentSize -

Returns:

List of strongly connected components

PruneGraph

public static java.util.Vector<Graph> PruneGraph(Graph graph,
                                                 boolean includeInterface)

Graph pruning (eliminataing IN and OUT layers)

Parameters:

graph - is modified after the procedure and contains the cyclic part of the graph

Returns:

Two subgraphs - IN-layer, OUT-layer

CycleDecomposition

public static java.util.Vector<Graph> CycleDecomposition(Graph graph,
                                                         int sizeThreshold)

Parameters:

graph -

sizeThreshold -

Returns:

List of minimal cycles

Dijkstra

public static java.util.Vector<Graph> Dijkstra(Graph graph,
                                               Node source,
                                               Node target,
                                               boolean directedGraph,
                                               boolean suboptimal,
                                               double searchRadius)

Parameters:

graph -

source -

target -

directedGraph -

suboptimal -

Returns:

List of shortest or suboptimal shortest paths from source to target

FindAllPaths

public static java.util.Vector<Graph> FindAllPaths(Graph graph,
                                                   Node source,
                                                   java.util.Set<Node> targets,
                                                   boolean directedGraph,
                                                   double searchRadius)

Note: searchRadius here is the number of edges from source (edge weights are not considered)

Parameters:

graph -

source -

target -

directedGraph -

Returns:

List of all non-intersecting paths from source to target

DijkstraAlgorithm

public static java.util.Vector<Graph> DijkstraAlgorithm(Graph graph,
                                                        Node source,
                                                        Node target,
                                                        boolean directedGraph,
                                                        double searchRadius)

DijkstraProcedure

public static void DijkstraProcedure(Graph graph,
                                     int isource,
                                     int iend,
                                     double[] d,
                                     java.util.Vector<java.util.Vector<java.lang.Integer>> previous,
                                     boolean directedGraph,
                                     double searchRadius)

Principal Dijkstra procedure 2 for each vertex v in V[G] // Initializations 3 d[v] := infinity // Unknown distance function from s to v 4 previous[v] := undefined 5 d[s] := 0 // Distance from s to s 6 S := empty set // Set of all visited vertices 7 Q := V[G] // Set of all unvisited vertices 8 while Q is not an empty set // The algorithm itself 9 u := Extract_Min(Q) // Remove best vertex from priority queue 10 S := S union {u} // Mark it 'visited' 11 for each edge (u,v) outgoing from u 12 if d[u] + w(u,v) < d[v] // Relax (u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u

neighboursOfNodeHash

public static java.util.Vector<java.util.Vector<Edge>> neighboursOfNodeHash(Graph graph,
                                                                            boolean directedGraph)

Sub-routine for Dijkstra's algorithm Returns vector (of length number of nodes) of vectors of outgoing edges numbers

extractClosestNodes

public static java.util.Set extractClosestNodes(java.util.Set Q,
                                                double[] d,
                                                java.util.HashSet<java.lang.Integer> non_empties,
                                                java.util.Vector temp,
                                                double searchRadius)

Sub-routine for Dijkstra algorithm search for an items with minimum d[item] and removes from Q

GetConnectedComponent

public static Graph GetConnectedComponent(Graph graph,
                                          Node n)

Parameters:

graph -

n -

Returns:

Connected component containing node n

CombineIncludedGraphsApprox

public static java.util.Vector<Graph> CombineIncludedGraphsApprox(java.util.Vector<Graph> graphs,
                                                                  float thresh)

Clusters graphs with node overlap more than threshold

Parameters:

graphs -

thresh -

Returns:

List of graph clusters

GetBiggestGraph

public static Graph GetBiggestGraph(java.util.Vector v)

Parameters:

v -

Returns:

The biggest graph in the list v