Author: ghuck
Date: 2011-07-30 07:49:43 -0700 (Sat, 30 Jul 2011)
New Revision: 26343
Added:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTree.java
Removed:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTreeUnweighted.java
Modified:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphInterface.java
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphPlugin.java
csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.cpp
csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.h
Log:
Started working on adding weighted MST support
Modified:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphInterface.java
===================================================================
---
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphInterface.java
2011-07-29 23:19:26 UTC (rev 26342)
+++
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphInterface.java
2011-07-30 14:49:43 UTC (rev 26343)
@@ -68,5 +68,8 @@
// Minimum spanning tree - unweighted
public static native int minimum_spanning_tree_unweighted(int res[]);
+ // Minimum spanning tree - weighted
+ public static native int minimum_spanning_tree_weighted(int res[], double
weights[]);
+
}
Modified:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphPlugin.java
===================================================================
---
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphPlugin.java
2011-07-29 23:19:26 UTC (rev 26342)
+++
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/IgraphPlugin.java
2011-07-30 14:49:43 UTC (rev 26343)
@@ -77,11 +77,17 @@
IsConnected isConnectedAction2 = new IsConnected(this, "Selected
Nodes", true);
Cytoscape.getDesktop().getCyMenus().addCytoscapeAction((CytoscapeAction)
isConnectedAction2);
- MinimumSpanningTreeUnweighted mst = new
MinimumSpanningTreeUnweighted(this, "All nodes", false);
+ MinimumSpanningTree mst = new MinimumSpanningTree(this, "All
nodes", false, false);
Cytoscape.getDesktop().getCyMenus().addCytoscapeAction((CytoscapeAction) mst);
- MinimumSpanningTreeUnweighted mst2 = new
MinimumSpanningTreeUnweighted(this, "Selected Nodes", true);
+ MinimumSpanningTree mst2 = new MinimumSpanningTree(this, "Selected
Nodes", true, false);
Cytoscape.getDesktop().getCyMenus().addCytoscapeAction((CytoscapeAction) mst2);
+
+ MinimumSpanningTree mst3 = new MinimumSpanningTree(this, "All
nodes", false, true);
+
Cytoscape.getDesktop().getCyMenus().addCytoscapeAction((CytoscapeAction) mst3);
+
+ MinimumSpanningTree mst4 = new MinimumSpanningTree(this, "Selected
Nodes", true, true);
+
Cytoscape.getDesktop().getCyMenus().addCytoscapeAction((CytoscapeAction) mst4);
// Layouts
CyLayouts.addLayout(new CircleLayout(), "Igraph");
Copied:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTree.java
(from rev 26266,
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTreeUnweighted.java)
===================================================================
---
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTree.java
(rev 0)
+++
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTree.java
2011-07-30 14:49:43 UTC (rev 26343)
@@ -0,0 +1,211 @@
+/**************************************************************************************
+Copyright (C) Gerardo Huck, 2011
+
+
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+**************************************************************************************/
+
+package cytoscape.plugins.igraph;
+
+import java.awt.event.ActionEvent;
+import javax.swing.JOptionPane;
+import java.util.*;
+
+import cytoscape.Cytoscape;
+import cytoscape.*;
+import cytoscape.data.*;
+import cytoscape.plugin.CytoscapePlugin;
+import cytoscape.util.CytoscapeAction;
+import cytoscape.logger.CyLogger;
+import giny.model.*;
+
+import giny.view.NodeView;
+import cytoscape.view.CyNodeView;
+import cytoscape.view.CyNetworkView;
+
+import com.sun.jna.Library;
+import com.sun.jna.Native;
+import com.sun.jna.Platform;
+
+
+public class MinimumSpanningTree extends CytoscapeAction {
+
+ Boolean selectedOnly;
+ Boolean isWeighted;
+
+ public MinimumSpanningTree(IgraphPlugin myPlugin,
+ String name,
+ boolean selectedOnly,
+ boolean isWeighted) {
+ super(name);
+ this.selectedOnly = new Boolean(selectedOnly);
+ this.isWeighted = new Boolean(isWeighted);
+ if (isWeighted)
+ setPreferredMenu("Plugins.Igraph.Minimum Spanning Tree (Weighted)");
+ else
+ setPreferredMenu("Plugins.Igraph.Minimum Spanning Tree
(Unweighted)");
+
+ }
+
+ public void actionPerformed(ActionEvent e) {
+
+ CyLogger logger = CyLogger.getLogger(MinimumSpanningTree.class);
+
+ try {
+ CyNetwork network = Cytoscape.getCurrentNetwork();
+ int numNodes;
+ if (selectedOnly)
+ numNodes = network.getSelectedNodes().size();
+ else
+ numNodes = network.getNodeCount();
+
+ /* Load graph into Igraph library */
+ HashMap<Integer,Integer> mapping =
IgraphAPI.loadGraph(selectedOnly, false);
+
+ /* Prepare variables to hold results from native call
*/
+ int[] mst = new int[2 * numNodes - 2];
+ int numEdges;
+
+ /* Compute MST */
+ if (isWeighted) {
+ // Compute weights
+ double[] weights;
+ weights = new double[mapping.size()];
+
+ // TODO: Compute weights!!!
+
+ numEdges = IgraphInterface.minimum_spanning_tree_weighted(mst,
weights);
+
+ } else {
+ numEdges =
IgraphInterface.minimum_spanning_tree_unweighted(mst);
+ }
+
+// logger.info("Nodes in MST: " + numNodes);
+// logger.info("Edges in MST: " + numEdges);
+// String nodesString = new String();
+// for (int i = 0; i < 2 * numEdges; i++)
+// nodesString = nodesString + mst[i] + ", ";
+// logger.info("Nodes: "+ nodesString);
+
+ /* Create new network & networkView */
+ CyNetworkView oldView = Cytoscape.getCurrentNetworkView();
+
+ // Prepare nodes
+ int[] nodes = new int[numNodes];
+ int j = 0;
+ Iterator<Node> nodeIt;
+ if(selectedOnly) {
+ nodeIt = network.getSelectedNodes().iterator();
+ } else {
+ nodeIt = network.nodesIterator();
+ }
+
+ while(nodeIt.hasNext()){
+ Node node = nodeIt.next();
+ nodes[j] = node.getRootGraphIndex();
+ j++;
+ }
+
+ // Prepare edges
+ int[] edges = new int[numEdges];
+ int i = 0;
+
+
+ // create node reverse mapping (igraphId -> rootGraphIndex)
+ HashMap<Integer,Integer> reverseMapping = new
HashMap<Integer,Integer>(mapping.size());
+
+ Iterator<Map.Entry<Integer,Integer>> mapIter =
mapping.entrySet().iterator();
+ while (mapIter.hasNext()) {
+ Map.Entry entry = (Map.Entry) mapIter.next();
+ reverseMapping.put((Integer) entry.getValue(), (Integer)
entry.getKey());
+ }
+
+
+ for (int k = 0; k < 2 * numEdges; k += 2) {
+
+ // get rootGraphId's for both nodes of this edge
+ int n1 = reverseMapping.get(mst[k]);
+ int n2 = reverseMapping.get(mst[k + 1]);
+
+ // Get edges starting or ending in n1
+ int[] adjacentEdgesArray =
network.getAdjacentEdgeIndicesArray(n1,
+
true, // undirected edges
+
true, // incoming edges
+
true); // outgoing edges
+
+ for (int l = 0; l < adjacentEdgesArray.length; l++) {
+ Edge edge = network.getEdge(adjacentEdgesArray[l]);
+ int edgeSource = edge.getSource().getRootGraphIndex();
+ int edgeTarget = edge.getTarget().getRootGraphIndex();
+
+ if (edgeSource == n2 || edgeTarget == n2) {
+ // This edge is in the MST!
+ edges[i] = edge.getRootGraphIndex();
+ i++;
+ break;
+ }
+ }
+ }
+
+ if (i != numEdges) {
+ JOptionPane.showMessageDialog(Cytoscape.getDesktop(), "ERROR!
Edges found: " + i + " , should be: " + numEdges);
+ return;
+ }
+
+
+ String newNetworkName = "Minimum Spanning Tree (" +
network.getTitle() + ")";
+
+ CyNetwork newNetwork = Cytoscape.createNetwork(nodes,
+ edges,
+ newNetworkName,
+ network,
+ true);
+
+
+ /* Set node positions */
+ CyNetworkView newView = Cytoscape.getCurrentNetworkView();
+
+ Iterator<Node> newNodesIt = newNetwork.nodesIterator();
+
+ while(newNodesIt.hasNext()){
+ Node node = newNodesIt.next();
+ NodeView newNodeView = newView.getNodeView(node);
+ NodeView oldNodeView = oldView.getNodeView(node);
+
+ //oldNodeView.;
+
+ // Set X and Y positions
+ newNodeView.setXPosition(oldNodeView.getXPosition());
+ newNodeView.setYPosition(oldNodeView.getYPosition());
+
+ // Set label position
+ newNodeView.setLabelPosition(oldNodeView.getLabelPosition());
+ }
+
+ // Redraw the whole network
+ newView.updateView();
+ newView.redrawGraph(true, true);
+ newView.fitContent();
+
+
+ } catch (Exception ex) {
+ ex.printStackTrace();
+ String message = "Error:\n" + ex.getMessage();
+ JOptionPane.showMessageDialog( Cytoscape.getDesktop(), message);
+ }
+
+ }
+
+}
\ No newline at end of file
Deleted:
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTreeUnweighted.java
===================================================================
---
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTreeUnweighted.java
2011-07-29 23:19:26 UTC (rev 26342)
+++
csplugins/trunk/soc/ghuck/IgraphPlugin/src/cytoscape/plugins/igraph/MinimumSpanningTreeUnweighted.java
2011-07-30 14:49:43 UTC (rev 26343)
@@ -1,216 +0,0 @@
-/**************************************************************************************
-Copyright (C) Gerardo Huck, 2011
-
-
-This program is free software: you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation, either version 3 of the License, or
-(at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program. If not, see <http://www.gnu.org/licenses/>.
-
-**************************************************************************************/
-
-package cytoscape.plugins.igraph;
-
-import java.awt.event.ActionEvent;
-import javax.swing.JOptionPane;
-import java.util.*;
-
-import cytoscape.Cytoscape;
-import cytoscape.*;
-import cytoscape.data.*;
-import cytoscape.plugin.CytoscapePlugin;
-import cytoscape.util.CytoscapeAction;
-import cytoscape.logger.CyLogger;
-import giny.model.*;
-
-import giny.view.NodeView;
-import cytoscape.view.CyNodeView;
-import cytoscape.view.CyNetworkView;
-
-import com.sun.jna.Library;
-import com.sun.jna.Native;
-import com.sun.jna.Platform;
-
-
-public class MinimumSpanningTreeUnweighted extends CytoscapeAction {
-
- Boolean selectedOnly;
-
- public MinimumSpanningTreeUnweighted(IgraphPlugin myPlugin, String name,
boolean selectedOnly) {
- super(name);
- setPreferredMenu("Plugins.Igraph.Minimum Spanning Tree (Unweighted)");
- this.selectedOnly = new Boolean(selectedOnly);
- }
-
- public void actionPerformed(ActionEvent e) {
-
- CyLogger logger =
CyLogger.getLogger(MinimumSpanningTreeUnweighted.class);
-
- try {
- CyNetwork network = Cytoscape.getCurrentNetwork();
- int numNodes;
- if (selectedOnly)
- numNodes = network.getSelectedNodes().size();
- else
- numNodes = network.getNodeCount();
-
- /* Load graph into Igraph library */
- HashMap<Integer,Integer> mapping =
IgraphAPI.loadGraph(selectedOnly, false);
-
- /* Prepare variables to hold results from native call
*/
- int[] mst = new int[2 * numNodes - 2];
- int numEdges;
-
- /* Compute MST */
- numEdges = IgraphInterface.minimum_spanning_tree_unweighted(mst);
-
- logger.info("Nodes in MST: " + numNodes);
- logger.info("Edges in MST: " + numEdges);
- String nodesString = new String();
- for (int i = 0; i < 2 * numEdges; i++)
- nodesString = nodesString + mst[i] + ", ";
- logger.info("Nodes: "+ nodesString);
-
- /* Create new network & networkView */
- CyNetworkView oldView = Cytoscape.getCurrentNetworkView();
-
- // Prepare nodes
- int[] nodes = new int[numNodes];
- int j = 0;
- Iterator<Node> nodeIt;
- if(selectedOnly) {
- nodeIt = network.getSelectedNodes().iterator();
- } else {
- nodeIt = network.nodesIterator();
- }
-
- while(nodeIt.hasNext()){
- Node node = nodeIt.next();
- nodes[j] = node.getRootGraphIndex();
- j++;
- }
-
- // Prepare edges
- int[] edges = new int[numEdges];
- int i = 0;
-
-
- // create node reverse mapping (igraphId -> rootGraphIndex)
- HashMap<Integer,Integer> reverseMapping = new
HashMap<Integer,Integer>(mapping.size());
-
- Iterator<Map.Entry<Integer,Integer>> mapIter =
mapping.entrySet().iterator();
- while (mapIter.hasNext()) {
- Map.Entry entry = (Map.Entry) mapIter.next();
- reverseMapping.put((Integer) entry.getValue(), (Integer)
entry.getKey());
- }
-
-
- for (int k = 0; k < 2 * numEdges; k += 2) {
-
- // get rootGraphId's for both nodes of this edge
- int n1 = reverseMapping.get(mst[k]);
- int n2 = reverseMapping.get(mst[k + 1]);
-
- // Get edges starting or ending in n1
- int[] adjacentEdgesArray =
network.getAdjacentEdgeIndicesArray(n1,
-
true, // undirected edges
-
true, // incoming edges
-
true); // outgoing edges
-
- for (int l = 0; l < adjacentEdgesArray.length; l++) {
- Edge edge = network.getEdge(adjacentEdgesArray[l]);
- int edgeSource = edge.getSource().getRootGraphIndex();
- int edgeTarget = edge.getTarget().getRootGraphIndex();
-
- if (edgeSource == n2 || edgeTarget == n2) {
- // This edge is in the MST!
- edges[i] = edge.getRootGraphIndex();
- i++;
- break;
- }
- }
- }
-
- if (i != numEdges) {
- JOptionPane.showMessageDialog(Cytoscape.getDesktop(), "ERROR!
Edges found: " + i + " , should be: " + numEdges);
- return;
- }
-
-
-// Iterator<Edge> edgeIt = network.edgesIterator();
-// while(edgeIt.hasNext()){
-// Edge edge = (CyEdge) edgeIt.next();
-// Node source = edge.getSource();
-// Node target = edge.getTarget();
-
-// int n1 = mapping.get(source.getRootGraphIndex());
-// int n2 = mapping.get(target.getRootGraphIndex());
-
-// logger.info("N1 = " + n1 + " N2 = " + n2);
-
-// for(int k = 0; k < 2 * numEdges; k += 2) {
-// if (mst[k] == n1 && mst[k + 1] == n2){
-// edges[i] = edge.getRootGraphIndex();
-// logger.info("Edge: " + edges[i] + ", i = " + i);
-// i++;
-// break;
-// }
-// }
-// }
-
-// JOptionPane.showMessageDialog(Cytoscape.getDesktop(), "i = " + i +
" , numEdges = " + numEdges);
-
-
- String newNetworkName = "Minimum Spanning Tree (" +
network.getTitle() + ")";
-
- CyNetwork newNetwork = Cytoscape.createNetwork(nodes,
- edges,
- newNetworkName,
- network,
- true);
-
-
- /* Set node positions */
- CyNetworkView newView = Cytoscape.getCurrentNetworkView();
-
- Iterator<Node> newNodesIt = newNetwork.nodesIterator();
-
- while(newNodesIt.hasNext()){
- Node node = newNodesIt.next();
- NodeView newNodeView = newView.getNodeView(node);
- NodeView oldNodeView = oldView.getNodeView(node);
-
- //oldNodeView.;
-
- // Set X and Y positions
- newNodeView.setXPosition(oldNodeView.getXPosition());
- newNodeView.setYPosition(oldNodeView.getYPosition());
-
- // Set label position
- newNodeView.setLabelPosition(oldNodeView.getLabelPosition());
- }
-
- // Redraw the whole network
- newView.updateView();
- newView.redrawGraph(true, true);
- newView.fitContent();
-
-
- } catch (Exception ex) {
- ex.printStackTrace();
- String message = "Error:\n" + ex.getMessage();
- JOptionPane.showMessageDialog( Cytoscape.getDesktop(), message);
- }
-
-
- }
-
-}
\ No newline at end of file
Modified: csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.cpp
===================================================================
--- csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.cpp
2011-07-29 23:19:26 UTC (rev 26342)
+++ csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.cpp
2011-07-30 14:49:43 UTC (rev 26343)
@@ -205,7 +205,39 @@
return e;
}
+int minimum_spanning_tree_weighted(int res[], double weights[]) {
+ igraph_t mst;
+ int from, to;
+ long int ecount = igraph_ecount(&g);
+ igraph_vector_t weights_vector;
+ igraph_vector_init(&weights_vector, ecount);
+ for (int i = 0; i < ecount; i++)
+ VECTOR(weights_vector)[i] = weights[i];
+
+ // Calculate MST
+ igraph_minimum_spanning_tree_prim(&g, &mst, &weights_vector);
+
+ // Copy results
+ int e = igraph_ecount(&mst);
+
+ // printf("Number of edges in MST: %d\n", e);
+
+ for(int i = 0; i < e ; i++) {
+ igraph_edge(&mst, i, &from, &to);
+ res[2 * i] = from;
+ res[2 * i + 1] = to;
+ }
+
+ // Clean up
+ igraph_destroy(&mst);
+ destroy_graph();
+ igraph_vector_destroy(&weights_vector);
+
+ return e;
+}
+
+
// int igraph_minimum_spanning_tree(const igraph_t *graph, igraph_vector_t
*res,
// const igraph_vector_t *weights);
// int igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst,
Modified: csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.h
===================================================================
--- csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.h
2011-07-29 23:19:26 UTC (rev 26342)
+++ csplugins/trunk/soc/ghuck/IgraphPlugin/src/igraphWrapper/igraphJNA.h
2011-07-30 14:49:43 UTC (rev 26343)
@@ -46,6 +46,9 @@
// Minimum spanning tree - unweighted
int minimum_spanning_tree_unweighted(int res[]);
+ // Minimum spanning tree - weighted
+ int minimum_spanning_tree_weighted(int res[], double weights[]);
+
//test functions
--
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.
