Skip to content

Commit 8d1dc4a

Browse files
mbastianmbastian
committed
Implement shortest path filter #1859 
1 parent acb3870 commit 8d1dc4a

File tree

8 files changed

+575
-1
lines changed

8 files changed

+575
-1
lines changed

‎modules/FiltersPlugin/pom.xml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,10 @@
3636
<groupId>${project.groupId}</groupId>
3737
<artifactId>statistics-plugin</artifactId>
3838
</dependency>
39+
<dependency>
40+
<groupId>${project.groupId}</groupId>
41+
<artifactId>algorithms-plugin</artifactId>
42+
</dependency>
3943
<!-- <dependency>
4044
<groupId>${project.groupId}</groupId>
4145
<artifactId>timeline</artifactId>

‎modules/FiltersPlugin/src/main/java/org/gephi/filters/plugin/graph/ShortestPathBuilder.java‎

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
package org.gephi.filters.plugin.graph;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
import javax.swing.Icon;
6+
import javax.swing.JPanel;
7+
import org.gephi.algorithms.shortestpath.AbstractShortestPathAlgorithm;
8+
import org.gephi.algorithms.shortestpath.BellmanFordShortestPathAlgorithm;
9+
import org.gephi.algorithms.shortestpath.DijkstraShortestPathAlgorithm;
10+
import org.gephi.filters.api.FilterLibrary;
11+
import org.gephi.filters.spi.Category;
12+
import org.gephi.filters.spi.ComplexFilter;
13+
import org.gephi.filters.spi.Filter;
14+
import org.gephi.filters.spi.FilterBuilder;
15+
import org.gephi.filters.spi.FilterProperty;
16+
import org.gephi.graph.api.DirectedGraph;
17+
import org.gephi.graph.api.Edge;
18+
import org.gephi.graph.api.Graph;
19+
import org.gephi.graph.api.Node;
20+
import org.gephi.project.api.Workspace;
21+
import org.openide.util.Exceptions;
22+
import org.openide.util.Lookup;
23+
import org.openide.util.NbBundle;
24+
import org.openide.util.lookup.ServiceProvider;
25+
26+
@ServiceProvider(service = FilterBuilder.class)
27+
public class ShortestPathBuilder implements FilterBuilder {
28+
29+
@Override
30+
public Category getCategory() {
31+
return FilterLibrary.TOPOLOGY;
32+
}
33+
34+
@Override
35+
public String getName() {
36+
return NbBundle.getMessage(ShortestPathBuilder.class, "ShortestPathBuilder.name");
37+
}
38+
39+
@Override
40+
public Icon getIcon() {
41+
return null;
42+
}
43+
44+
@Override
45+
public String getDescription() {
46+
return NbBundle.getMessage(EgoBuilder.class, "ShortestPathBuilder.description");
47+
}
48+
49+
@Override
50+
public Filter getFilter(Workspace workspace) {
51+
return new ShortestPathFilter();
52+
}
53+
54+
@Override
55+
public JPanel getPanel(Filter filter) {
56+
ShortestPathUI ui = Lookup.getDefault().lookup(ShortestPathUI.class);
57+
if (ui != null) {
58+
return ui.getPanel((ShortestPathFilter) filter);
59+
}
60+
return null;
61+
}
62+
63+
@Override
64+
public void destroy(Filter filter) {
65+
}
66+
67+
public static class ShortestPathFilter implements ComplexFilter {
68+
69+
private String node1Pattern = "";
70+
private String node2Pattern = "";
71+
72+
@Override
73+
public Graph filter(Graph graph) {
74+
String str1 = node1Pattern.toLowerCase();
75+
String str2 = node2Pattern.toLowerCase();
76+
77+
Node n1 = null;
78+
Node n2 = null;
79+
80+
for (Node n : graph.getNodes()) {
81+
if (n.getId().toString().toLowerCase().equals(str1)) {
82+
n1 = n;
83+
} else if ((n.getLabel() != null) && n.getLabel().toLowerCase().equals(str1)) {
84+
n1 = n;
85+
} else if (n.getId().toString().toLowerCase().equals(str2)) {
86+
n2 = n;
87+
} else if ((n.getLabel() != null) && n.getLabel().toLowerCase().equals(str2)) {
88+
n2 = n;
89+
}
90+
}
91+
92+
if (n1 != null && n2 != null) {
93+
AbstractShortestPathAlgorithm algorithm;
94+
if (graph.isDirected()) {
95+
algorithm = new BellmanFordShortestPathAlgorithm((DirectedGraph) graph, n1);
96+
} else {
97+
algorithm = new DijkstraShortestPathAlgorithm(graph, n1);
98+
}
99+
100+
algorithm.compute();
101+
102+
Set<Edge> retainEdges = new HashSet<>();
103+
Set<Node> retainNodes = new HashSet<>();
104+
if (algorithm.getDistances().get(n2) != Double.POSITIVE_INFINITY) {
105+
retainNodes.add(n2);
106+
Edge predecessorEdge = algorithm.getPredecessorIncoming(n2);
107+
Node predecessor = algorithm.getPredecessor(n2);
108+
while (predecessorEdge != null && predecessor != n1) {
109+
retainEdges.add(predecessorEdge);
110+
retainNodes.add(predecessor);
111+
predecessorEdge = algorithm.getPredecessorIncoming(predecessor);
112+
predecessor = algorithm.getPredecessor(predecessor);
113+
}
114+
retainEdges.add(predecessorEdge);
115+
retainNodes.add(n1);
116+
}
117+
118+
for (Node node : graph.getNodes().toArray()) {
119+
if (!retainNodes.contains(node)) {
120+
graph.removeNode(node);
121+
}
122+
}
123+
124+
for (Edge edge : graph.getEdges().toArray()) {
125+
if (!retainEdges.contains(edge)) {
126+
graph.removeEdge(edge);
127+
}
128+
}
129+
}
130+
131+
return graph;
132+
}
133+
134+
@Override
135+
public String getName() {
136+
return NbBundle.getMessage(ShortestPathBuilder.class, "ShortestPathBuilder.name");
137+
}
138+
139+
@Override
140+
public FilterProperty[] getProperties() {
141+
try {
142+
return new FilterProperty[] {
143+
FilterProperty.createProperty(this, String.class, "firstNodePattern"),
144+
FilterProperty.createProperty(this, String.class, "secondNodePattern")};
145+
} catch (NoSuchMethodException ex) {
146+
Exceptions.printStackTrace(ex);
147+
}
148+
return new FilterProperty[0];
149+
}
150+
151+
public String getFirstNodePattern() {
152+
return node1Pattern;
153+
}
154+
155+
public void setFirstNodePattern(String node1Pattern) {
156+
this.node1Pattern = node1Pattern;
157+
}
158+
159+
public String getSecondNodePattern() {
160+
return node2Pattern;
161+
}
162+
163+
public void setSecondNodePattern(String node2Pattern) {
164+
this.node2Pattern = node2Pattern;
165+
}
166+
}
167+
}

‎modules/FiltersPlugin/src/main/java/org/gephi/filters/plugin/graph/ShortestPathUI.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/*
2+
Copyright 2008-2010 Gephi
3+
Authors : Mathieu Bastian <[email protected]>
4+
Website : http://www.gephi.org
5+
6+
This file is part of Gephi.
7+
8+
DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
9+
10+
Copyright 2011 Gephi Consortium. All rights reserved.
11+
12+
The contents of this file are subject to the terms of either the GNU
13+
General Public License Version 3 only ("GPL") or the Common
14+
Development and Distribution License("CDDL") (collectively, the
15+
"License"). You may not use this file except in compliance with the
16+
License. You can obtain a copy of the License at
17+
http://gephi.org/about/legal/license-notice/
18+
or /cddl-1.0.txt and /gpl-3.0.txt. See the License for the
19+
specific language governing permissions and limitations under the
20+
License. When distributing the software, include this License Header
21+
Notice in each file and include the License files at
22+
/cddl-1.0.txt and /gpl-3.0.txt. If applicable, add the following below the
23+
License Header, with the fields enclosed by brackets [] replaced by
24+
your own identifying information:
25+
"Portions Copyrighted [year] [name of copyright owner]"
26+
27+
If you wish your version of this file to be governed by only the CDDL
28+
or only the GPL Version 3, indicate your decision by adding
29+
"[Contributor] elects to include this software in this distribution
30+
under the [CDDL or GPL Version 3] license." If you do not indicate a
31+
single choice of license, a recipient has the option to distribute
32+
your version of this file under either the CDDL, the GPL Version 3 or
33+
to extend the choice of license to its licensees as provided above.
34+
However, if you add GPL Version 3 code and therefore, elected the GPL
35+
Version 3 license, then the option applies only if the new code is
36+
made subject to such option by the copyright holder.
37+
38+
Contributor(s):
39+
40+
Portions Copyrighted 2011 Gephi Consortium.
41+
*/
42+
43+
package org.gephi.filters.plugin.graph;
44+
45+
import javax.swing.JPanel;
46+
47+
/**
48+
* @author Mathieu Bastian
49+
*/
50+
public interface ShortestPathUI {
51+
52+
JPanel getPanel(ShortestPathBuilder.ShortestPathFilter shortestPathFilter);
53+
}

‎modules/FiltersPlugin/src/main/resources/org/gephi/filters/plugin/graph/Bundle.properties‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,4 +23,7 @@ KCoreBuilder.name = K-core
2323
KCoreBuilder.description = Keep graph in which all nodes have degree at least k.
2424

2525
HasSelfLoopBuilder.name = Has Self-loop
26-
HasSelfLoopBuilder.description = Keep only nodes that have at least one self-loop
26+
HasSelfLoopBuilder.description = Keep only nodes that have at least one self-loop
27+
28+
ShortestPathBuilder.name = Shortest Path
29+
ShortestPathBuilder.description = Keep nodes and edges in the shortest path between two nodes. Nodes are found with regex on ID and LABEL.

‎modules/FiltersPluginUI/src/main/java/org/gephi/ui/filters/plugin/graph/ShortestPathPanel.form‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
<?xml version="1.0" encoding="UTF-8" ?>
2+
3+
<Form version="1.5" maxVersion="1.7" type="org.netbeans.modules.form.forminfo.JPanelFormInfo">
4+
<AuxValues>
5+
<AuxValue name="FormSettings_autoResourcing" type="java.lang.Integer" value="1"/>
6+
<AuxValue name="FormSettings_autoSetComponentName" type="java.lang.Boolean" value="false"/>
7+
<AuxValue name="FormSettings_generateFQN" type="java.lang.Boolean" value="true"/>
8+
<AuxValue name="FormSettings_generateMnemonicsCode" type="java.lang.Boolean" value="false"/>
9+
<AuxValue name="FormSettings_i18nAutoMode" type="java.lang.Boolean" value="true"/>
10+
<AuxValue name="FormSettings_layoutCodeTarget" type="java.lang.Integer" value="1"/>
11+
<AuxValue name="FormSettings_listenerGenerationStyle" type="java.lang.Integer" value="0"/>
12+
<AuxValue name="FormSettings_variablesLocal" type="java.lang.Boolean" value="false"/>
13+
<AuxValue name="FormSettings_variablesModifier" type="java.lang.Integer" value="2"/>
14+
</AuxValues>
15+
16+
<Layout>
17+
<DimensionLayout dim="0">
18+
<Group type="103" groupAlignment="0" attributes="0">
19+
<Group type="102" attributes="0">
20+
<EmptySpace max="-2" attributes="0"/>
21+
<Group type="103" groupAlignment="0" attributes="0">
22+
<Group type="102" alignment="0" attributes="0">
23+
<Component id="labelNodeId1" min="-2" max="-2" attributes="0"/>
24+
<EmptySpace type="unrelated" max="-2" attributes="0"/>
25+
<Component id="nodeIdTextField" pref="106" max="32767" attributes="0"/>
26+
</Group>
27+
<Group type="102" alignment="0" attributes="0">
28+
<Component id="labelNodeId2" min="-2" max="-2" attributes="0"/>
29+
<EmptySpace type="unrelated" max="-2" attributes="0"/>
30+
<Component id="nodeIdTextField2" max="32767" attributes="0"/>
31+
</Group>
32+
</Group>
33+
<EmptySpace max="-2" attributes="0"/>
34+
<Group type="103" groupAlignment="0" attributes="0">
35+
<Component id="okButton1" min="-2" max="-2" attributes="0"/>
36+
<Component id="okButton2" alignment="1" min="-2" max="-2" attributes="0"/>
37+
</Group>
38+
<EmptySpace max="-2" attributes="0"/>
39+
</Group>
40+
</Group>
41+
</DimensionLayout>
42+
<DimensionLayout dim="1">
43+
<Group type="103" groupAlignment="0" attributes="0">
44+
<Group type="102" alignment="0" attributes="0">
45+
<EmptySpace min="-2" pref="6" max="-2" attributes="0"/>
46+
<Group type="103" groupAlignment="3" attributes="0">
47+
<Component id="labelNodeId1" alignment="3" min="-2" max="-2" attributes="0"/>
48+
<Component id="nodeIdTextField" alignment="3" min="-2" max="-2" attributes="0"/>
49+
<Component id="okButton1" alignment="3" min="-2" max="-2" attributes="0"/>
50+
</Group>
51+
<EmptySpace type="unrelated" max="-2" attributes="0"/>
52+
<Group type="103" groupAlignment="3" attributes="0">
53+
<Component id="labelNodeId2" alignment="3" min="-2" max="-2" attributes="0"/>
54+
<Component id="nodeIdTextField2" alignment="3" min="-2" max="-2" attributes="0"/>
55+
<Component id="okButton2" alignment="3" min="-2" max="-2" attributes="0"/>
56+
</Group>
57+
<EmptySpace pref="18" max="32767" attributes="0"/>
58+
</Group>
59+
</Group>
60+
</DimensionLayout>
61+
</Layout>
62+
<SubComponents>
63+
<Component class="javax.swing.JLabel" name="labelNodeId1">
64+
<Properties>
65+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
66+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.labelNodeId1.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
67+
</Property>
68+
</Properties>
69+
</Component>
70+
<Component class="javax.swing.JTextField" name="nodeIdTextField">
71+
<Properties>
72+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
73+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.nodeIdTextField.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
74+
</Property>
75+
<Property name="toolTipText" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
76+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.nodeIdTextField.toolTipText" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
77+
</Property>
78+
</Properties>
79+
</Component>
80+
<Component class="javax.swing.JButton" name="okButton1">
81+
<Properties>
82+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
83+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.okButton1.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
84+
</Property>
85+
<Property name="margin" type="java.awt.Insets" editor="org.netbeans.beaninfo.editors.InsetsEditor">
86+
<Insets value="[2, 7, 2, 7]"/>
87+
</Property>
88+
</Properties>
89+
</Component>
90+
<Component class="javax.swing.JLabel" name="labelNodeId2">
91+
<Properties>
92+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
93+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.labelNodeId2.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
94+
</Property>
95+
</Properties>
96+
</Component>
97+
<Component class="javax.swing.JTextField" name="nodeIdTextField2">
98+
<Properties>
99+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
100+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.nodeIdTextField2.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
101+
</Property>
102+
<Property name="toolTipText" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
103+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.nodeIdTextField2.toolTipText" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
104+
</Property>
105+
</Properties>
106+
</Component>
107+
<Component class="javax.swing.JButton" name="okButton2">
108+
<Properties>
109+
<Property name="text" type="java.lang.String" editor="org.netbeans.modules.i18n.form.FormI18nStringEditor">
110+
<ResourceString bundle="org/gephi/ui/filters/plugin/graph/Bundle.properties" key="ShortestPathPanel.okButton2.text" replaceFormat="org.openide.util.NbBundle.getMessage({sourceFileName}.class, &quot;{key}&quot;)"/>
111+
</Property>
112+
<Property name="margin" type="java.awt.Insets" editor="org.netbeans.beaninfo.editors.InsetsEditor">
113+
<Insets value="[2, 7, 2, 7]"/>
114+
</Property>
115+
</Properties>
116+
</Component>
117+
</SubComponents>
118+
</Form>

0 commit comments

Comments
 (0)