Author: paperwing
Date: 2012-03-22 15:04:44 -0700 (Thu, 22 Mar 2012)
New Revision: 28621
Modified:
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/input/SelectionInputHandler.java
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/layouts/SphericalLayoutAlgorithmTask.java
Log:
Started method to find the largest clique in a set of nodes a given common
neighbor, will need to generate permutations of the neighbors list in order to
find the largest clique
Modified:
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/input/SelectionInputHandler.java
===================================================================
---
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/input/SelectionInputHandler.java
2012-03-22 21:57:55 UTC (rev 28620)
+++
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/input/SelectionInputHandler.java
2012-03-22 22:04:44 UTC (rev 28621)
@@ -11,6 +11,7 @@
import org.cytoscape.model.CyTable;
import org.cytoscape.paperwing.internal.data.GraphicsData;
import org.cytoscape.paperwing.internal.data.GraphicsSelectionData;
+import org.cytoscape.paperwing.internal.layouts.SphericalLayoutAlgorithmTask;
import org.cytoscape.paperwing.internal.tools.NetworkToolkit;
import org.cytoscape.view.model.CyNetworkView;
@@ -71,6 +72,14 @@
} else {
selectedNodeIndices.add(newHoverNodeIndex);
+
+ // Debug: Find size of biggest
clique containing this node
+
+ /*
+ System.out.println("Size of
clique: " + SphericalLayoutAlgorithmTask.findCliques(
+
graphicsData.getNetworkView().getModel()).get(
+
graphicsData.getNetworkView().getModel().getNode(newHoverNodeIndex)).size());
+ */
}
} else if (newHoverEdgeIndex != NO_INDEX) {
Modified:
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/layouts/SphericalLayoutAlgorithmTask.java
===================================================================
---
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/layouts/SphericalLayoutAlgorithmTask.java
2012-03-22 21:57:55 UTC (rev 28620)
+++
csplugins/trunk/toronto/yuedong/paperwing-impl/src/main/java/org/cytoscape/paperwing/internal/layouts/SphericalLayoutAlgorithmTask.java
2012-03-22 22:04:44 UTC (rev 28621)
@@ -1,11 +1,15 @@
package org.cytoscape.paperwing.internal.layouts;
import java.util.Collection;
+import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
+import java.util.Map;
import java.util.Set;
+import org.cytoscape.model.CyEdge.Type;
+import org.cytoscape.model.CyNetwork;
import org.cytoscape.model.CyNode;
import org.cytoscape.paperwing.internal.geometric.Vector3;
import org.cytoscape.paperwing.internal.tools.NetworkToolkit;
@@ -31,8 +35,6 @@
@Override
protected void doLayout(TaskMonitor taskMonitor) {
-
- /*
// Break graph into partitions
List<LayoutPartition> partitions =
PartitionUtil.partition(networkView, false, null);
@@ -41,8 +43,8 @@
System.out.println("Number of partitions: " + numPartitions);
- double xOffsetAmount = 1000;
- double yOffsetAmount = 1000;
+ double xOffsetAmount = 200;
+ double yOffsetAmount = 200;
Collection<View<CyNode>> partitionNodeViews;
@@ -54,16 +56,14 @@
partitionNodeViews.add(nodeView);
}
+ partition.offset(count * xOffsetAmount, count *
yOffsetAmount);
+ arrangeAsSphere(partitionNodeViews);
- partition.offset(count * xOffsetAmount, count *
yOffsetAmount);
-
count++;
}
-
- */
- arrangeAsSphere(networkView.getNodeViews());
+ // arrangeAsSphere(networkView.getNodeViews());
}
@@ -147,6 +147,68 @@
return 100 + nodeCount;
}
+ private Map<CyNode, Collection<CyNode>> findCliques(CyNetwork network) {
+ // TODO: Implement optimization by partitioning the graph
before finding cliques
+
+ Collection<CyNode> nodesList = new
HashSet<CyNode>(network.getNodeList());
+
+ // A map that maps every node to the biggest clique containing
that node
+ Map<CyNode, Collection<CyNode>> cliques = new HashMap<CyNode,
Collection<CyNode>>();
+
+ // Find the largest clique containing each node
+ for (CyNode currentNode : nodesList) {
+
+ Collection<CyNode> clique = new HashSet<CyNode>();
+ clique.add(currentNode);
+
+ // Loop through every neighbor of the current node
+ for (CyNode neighbor :
network.getNeighborList(currentNode, Type.ANY)) {
+
+ boolean addToCurrentClique = true;
+
+ for (CyNode cliqueNode : clique) {
+ if
(network.getConnectingEdgeList(cliqueNode, neighbor, Type.ANY).isEmpty()) {
+ addToCurrentClique = false;
+ }
+ }
+
+ if (addToCurrentClique) {
+ clique.add(neighbor);
+ }
+ }
+
+ cliques.put(currentNode, clique);
+ }
+
+ return cliques;
+ }
+
+ // Find the largest clique containing a given node from a given network
+ private Collection<CyNode> findLargestClique(CyNode node, CyNetwork
network) {
+ Collection<CyNode> clique = new HashSet<CyNode>();
+ clique.add(node);
+
+ List<CyNode> neighbors = network.getNeighborList(node,
Type.ANY);
+
+ // Loop through every neighbor of the current node
+ for (CyNode neighbor : neighbors) {
+
+ boolean addToCurrentClique = true;
+
+ for (CyNode cliqueNode : clique) {
+ if (network.getConnectingEdgeList(cliqueNode,
neighbor, Type.ANY).isEmpty()) {
+ addToCurrentClique = false;
+ }
+ }
+
+ if (addToCurrentClique) {
+ clique.add(neighbor);
+ }
+ }
+
+ return clique;
+ }
+
/**
* Return a list of all cliques in the given set of nodes, sorted in
order of decreasing size.
* A clique is a subgraph where there is an edge between any 2 nodes.
@@ -154,9 +216,51 @@
* @param nodeViews The set of node view objects that should be used to
find cliques.
* @return A list of cliques found, sorted in order of decreasing size.
*/
- private List<Collection<View<CyNode>>>
findCliques(Collection<View<CyNode>> nodeViews) {
- List<Collection<View<CyNode>>> cliques = new
LinkedList<Collection<View<CyNode>>>();
+ private List<Collection<CyNode>> findCliquesOld(CyNetwork network) {
+ List<Collection<CyNode>> cliques = new
LinkedList<Collection<CyNode>>();
+ // TODO: Implement optimization by partitioning the graph
before finding cliques
+
+ Collection<CyNode> nodesToBeVisited = new
HashSet<CyNode>(network.getNodeList());
+ Collection<CyNode> nodesPlacedInClique;
+
+ Collection<CyNode> clique;
+ CyNode currentNode;
+
+ // Find the largest clique containing each node
+ while(!nodesToBeVisited.isEmpty()) {
+ currentNode = nodesToBeVisited.iterator().next();
+
+ clique = new HashSet<CyNode>();
+ clique.add(currentNode);
+
+ nodesPlacedInClique = new HashSet<CyNode>();
+ nodesPlacedInClique.add(currentNode);
+
+ // Loop through every potential neighbor for the
current node
+ for (CyNode potentialNeighbor : nodesToBeVisited) {
+ if (potentialNeighbor != currentNode) {
+ boolean addToCurrentClique = true;
+
+ for (CyNode cliqueNode : clique) {
+ if
(!network.containsEdge(potentialNeighbor, cliqueNode)
+ &&
!network.containsEdge(cliqueNode, potentialNeighbor)) {
+
+ addToCurrentClique =
false;
+ }
+ }
+
+ if (addToCurrentClique) {
+ clique.add(potentialNeighbor);
+
nodesPlacedInClique.add(potentialNeighbor);
+ }
+ }
+ }
+
+ cliques.add(clique);
+ nodesToBeVisited.removeAll(nodesPlacedInClique);
+ }
+
return null;
}
}
--
You received this message because you are subscribed to the Google Groups
"cytoscape-cvs" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/cytoscape-cvs?hl=en.
