1
嗨，我想知道是否有任何方法可以找到JUNG中两个节点N1和N2之间的所有可能路径。 在此先感谢您的帮助:)寻找JUNG的所有路径？
A
回答
3
我曾在我需要从顶点A的所有路径B.
这里的一些任务，我把ShortestPathDemo.java和修改有点称之为PathDemo.java。可以在图表中找到最短路径和完整路径。
/******************************
PathDemo.java
******************************/
/*
* Created on Jan 2, 2004
*/
package exasym;
import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Graphics;
import java.awt.Paint;
import java.awt.Stroke;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Point2D;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import javax.swing.BorderFactory;
import javax.swing.BoxLayout;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.SwingConstants;
import org.apache.commons.collections15.Transformer;
import edu.uci.ics.jung.algorithms.layout.FRLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler;
import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.visualization.Layer;
import edu.uci.ics.jung.visualization.VisualizationViewer;
import edu.uci.ics.jung.visualization.control.DefaultModalGraphMouse;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer;
/**
* Demonstrates use of the shortest path algorithm and visualization of the
* results.
*
* @author danyelf
*/
public class PathDemo extends JPanel {
/**
*
*/
private static final long serialVersionUID = 7526217664458188502L;
/**
* Starting vertex
*/
private String mFrom;
/**
* Ending vertex
*/
private String mTo;
private Graph<String, String> mGraph;
private Set<String> mPred;
private BFSDistanceLabeler<String, String> bdl;
private Graph<String, String> path;
protected boolean full = true;
private JLabel label;
public PathDemo() {
this.mGraph = getGraph();
setBackground(Color.WHITE);
// show graph
final Layout<String, String> layout = new FRLayout<String, String>(
mGraph);
final VisualizationViewer<String, String> vv = new VisualizationViewer<String, String>(
layout);
vv.setBackground(Color.WHITE);
vv.getRenderContext().setVertexDrawPaintTransformer(
new MyVertexDrawPaintFunction<String>());
vv.getRenderContext().setVertexFillPaintTransformer(
new MyVertexFillPaintFunction<String>());
vv.getRenderContext().setEdgeDrawPaintTransformer(
new MyEdgePaintFunction());
vv.getRenderContext().setEdgeStrokeTransformer(
new MyEdgeStrokeFunction());
vv.getRenderContext().setVertexLabelTransformer(
new ToStringLabeller<String>());
vv.setGraphMouse(new DefaultModalGraphMouse<String, String>());
vv.addPostRenderPaintable(new VisualizationViewer.Paintable() {
public boolean useTransform() {
return true;
}
public void paint(Graphics g) {
if (mPred == null)
return;
// for all edges, paint edges that are in shortest path
for (String e : layout.getGraph().getEdges()) {
if (isBlessed(e)) {
String v1 = mGraph.getEndpoints(e).getFirst();
String v2 = mGraph.getEndpoints(e).getSecond();
Point2D p1 = layout.transform(v1);
Point2D p2 = layout.transform(v2);
p1 = vv.getRenderContext().getMultiLayerTransformer()
.transform(Layer.LAYOUT, p1);
p2 = vv.getRenderContext().getMultiLayerTransformer()
.transform(Layer.LAYOUT, p2);
Renderer<String, String> renderer = vv.getRenderer();
renderer.renderEdge(vv.getRenderContext(), layout, e);
}
}
}
});
setLayout(new BorderLayout());
add(vv, BorderLayout.CENTER);
// set up controls
add(setUpControls(), BorderLayout.SOUTH);
}
boolean isBlessed(String e) {
Iterator<String> it = path.getEdges().iterator();
while (it.hasNext()) {
String edge = it.next();
if (edge.equalsIgnoreCase(e.toString()))
return true;
}
return false;
}
/**
* @author danyelf
*/
public class MyEdgePaintFunction implements Transformer<String, Paint> {
public Paint transform(String e) {
if (path == null || path.getEdges().size() == 0)
return Color.BLACK;
if (isBlessed(e)) {
return new Color(0.0f, 0.0f, 1.0f, 0.5f);// Color.BLUE;
} else {
return Color.LIGHT_GRAY;
}
}
}
public class MyEdgeStrokeFunction implements Transformer<String, Stroke> {
protected final Stroke THIN = new BasicStroke(1);
protected final Stroke THICK = new BasicStroke(2);
public Stroke transform(String e) {
if (path == null || path.getEdges().size() == 0)
return THIN;
if (isBlessed(e)) {
return THICK;
} else
return THIN;
}
}
/**
* @author danyelf
*/
public class MyVertexDrawPaintFunction<V> implements Transformer<V, Paint> {
public Paint transform(V v) {
return Color.black;
}
}
public class MyVertexFillPaintFunction<String> implements
Transformer<String, Paint> {
public Paint transform(String v) {
if (v.equals(mFrom)) {
return Color.BLUE;
}
if (v.equals(mTo)) {
return Color.BLUE;
}
if (path == null) {
return Color.LIGHT_GRAY;
} else {
if (mGraph.getVertices().contains(v)) {
return Color.RED;
} else {
return Color.LIGHT_GRAY;
}
}
}
}
/**
*
*/
private JPanel setUpControls() {
JPanel panel = new JPanel();
panel.setBackground(Color.WHITE);
panel.setLayout(new BoxLayout(panel, BoxLayout.PAGE_AXIS));
panel.setBorder(BorderFactory.createLineBorder(Color.black, 3));
label = new JLabel(
"Select a pair of vertices for which all possible paths will be displayed");
panel.add(label);
JPanel jpPathType = new JPanel();
jpPathType.add(new JLabel("Path type", SwingConstants.LEFT));
jpPathType.add(getPathBox());
JPanel jpFrom = new JPanel();
jpFrom.add(new JLabel("vertex from", SwingConstants.LEFT));
jpFrom.add(getSelectionBox(true));
JPanel jpTo = new JPanel();
jpTo.add(new JLabel("vertex to", SwingConstants.LEFT));
jpTo.add(getSelectionBox(false));
panel.add(jpPathType);
panel.add(jpFrom);
panel.add(jpTo);
return panel;
}
public Component getPathBox() {
Set<String> str = new HashSet<String>();
str.add("Shortest");
str.add("Full");
final JComboBox path = new JComboBox(str.toArray());
path.setSelectedItem("Full");
path.setBackground(Color.WHITE);
path.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
String option = (String) path.getSelectedItem();
if (option.equals("Full")) {
full = true;
label.setText("Select a pair of vertices for which all possible paths will be displayed");
} else {
full = false;
label.setText("Select a pair of vertices for which a shortest path will be displayed");
}
drawPath();
repaint();
}
});
return path;
}
protected void drawPath() {
if (mFrom == null || mTo == null) {
return;
}
path = getNewGraph();
if (full) {
path = getPaths();
} else {
path = drawShortest();
}
}
private Component getSelectionBox(final boolean from) {
Set<String> s = new TreeSet<String>();
for (String v : mGraph.getVertices()) {
s.add(v);
}
final JComboBox choices = new JComboBox(s.toArray());
choices.setSelectedIndex(-1);
choices.setBackground(Color.WHITE);
choices.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String v = (String) choices.getSelectedItem();
if (from) {
mFrom = v;
} else {
mTo = v;
}
drawPath();
repaint();
}
});
return choices;
}
/**
* @return
*
*/
protected Graph<String, String> getPaths() {
path = getNewGraph();
Set<String> visited = new HashSet<String>();
LinkedList<String> currpath = new LinkedList<String>();
findAllPaths(mFrom, visited, path, currpath);
return path;
}
private void findAllPaths(String start, Set<String> visited,
Graph<String, String> path, LinkedList<String> currpath) {
if (visited.contains(start)) {
return;
}
visited.add(start);
currpath.addLast(start);
if (start.equals(mTo)) {
String pred = null;
for (String l : currpath) {
if (pred != null) {
path.addVertex(l);
path.addVertex(pred);
path.addEdge((pred + l), pred, l);
}
pred = l;
}
currpath.removeLast();
visited.remove(start);
return;
}
for (String edge : mGraph.getOutEdges(start)) {
String succ = mGraph.getDest(edge);
findAllPaths(succ, visited, path, currpath);
}
visited.remove(start);
currpath.removeLast();
}
protected Graph<String, String> drawShortest() {
path = getNewGraph();
LinkedList<String> currpath = new LinkedList<String>();
DijkstraShortestPath<String, String> alg = new DijkstraShortestPath(
mGraph);
List<String> l = alg.getPath(mFrom, mTo);
Iterator<String> itrCon = l.iterator();
while (itrCon.hasNext()) {
String c = (String) itrCon.next();
String source = mGraph.getSource(c);
String dest = mGraph.getDest(c);
path.addEdge(source + dest, source, dest);
}
return path;
}
public static void main(String[] s) {
JFrame jf = new JFrame();
jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
jf.getContentPane().add(new PathDemo());
jf.pack();
jf.setVisible(true);
}
/**
* @return the graph for this demo
*/
Graph<String, String> getGraph() {
// Graph<V, E> where V is the type of the vertices and E is the type of
// the edges
Graph<String, String> g = new DirectedSparseGraph<String, String>();
// Add some vertices. From above we defined these to be type Integer.
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
// Note that the default is for undirected edges, our Edges are Strings.
g.addEdge("AB", "A", "B"); // Note that Java 1.5 auto-boxes primitives
g.addEdge("BC", "B", "C");
g.addEdge("AC", "A", "C");
g.addEdge("BA", "B", "A");
g.addEdge("CB", "C", "B");
g.addEdge("CA", "C", "A");
g.addEdge("AD", "A", "D");
g.addEdge("CD", "C", "D");
/*
* g.addEdge("AB", "A", "B", EdgeType.DIRECTED); // Note that Java 1.5
* auto-boxes primitives g.addEdge("BC", "B", "C", EdgeType.DIRECTED);
* g.addEdge("AC", "A", "C", EdgeType.DIRECTED);
*/
return g;
}
Graph<String, String> getNewGraph() {
return new DirectedSparseGraph<String, String>();
}
}
1
根据文档，我不认为有两种节点之间的所有路径的开箱即用的方式。但是，您可以通过管理已查看的节点列表并轻松地从指定节点开始递归访问图形，从而轻松地调整宽度优先搜索。您可以使用AbstractGraph类（doc here）提供的方法，例如getIncidentVertices。
在任何情况下，我不认为这是便宜的问题..
1
计算N1和N2之间的所有可能路径，在最坏情况下的成本为O（n！），并可能有很多输出。
几乎可以肯定的是，你不想要所有可能的路径。你想解决什么问题？
0
这个简单的解决方案返回所有的路径。
它的工作原理也与循环图，打印所有自行车道，因此它也可用于循环检测，这是不提供JUNG。
它使用Entity任意类的节点，并且为Edge边缘。您可以创建这样的对象（确保实施hashcode()和equals()），或根据您的需要简单地用String对象替换它们。
public class AllPaths {
private static List<List<Edge>> allPaths;
public static List<List<Edge>> getAllPathsBetweenNodes(DirectedGraph<Entity, Edge> graph, Entity startNode, Entity endNode) {
allPaths = new ArrayList<List<Edge>>();
List<Edge> currentPath = new ArrayList<Edge>();
findAllPaths(startNode, startNode, endNode, currentPath, graph);
return allPaths;
}
private static void findAllPaths(Entity currentNode, Entity startNode, Entity endNode, List<Edge> currentPath, DirectedGraph<Entity, Edge> graph) {
Collection<Edge> outgoingEdges = graph.getOutEdges(currentNode);
for (Edge outEdge : outgoingEdges) {
Entity outNode = outEdge.getSupertype();
if (outNode.equals(startNode)) {
List<Edge> cyclePath = new ArrayList<Edge>(currentPath);
cyclePath.add(outEdge);
System.out.println("Found cycle provoked by path " + cyclePath);
continue;
}
List<Edge> newPath = new ArrayList<Edge>(currentPath);
newPath.add(outEdge);
if (outNode.equals(endNode)) {
allPaths.add(newPath);
continue;
}
findAllPaths(outNode, startNode, endNode, newPath, graph);
}
}
}
0
我创建了一个微小的变化，允许您使用泛型，但不再是静态的。尽管你的类型必须相当。对于可比较的基本方法是没有必要的。但是，我添加了另一个函数，这对于我的目的是必需的，即查找所有唯一路径，即两个路径无法在路径中的位置共享边。我只检查相同边缘的路径的相同位置，例如，如果两条路径以相同边缘开始，它们不是唯一的。如果两个路径中的第i条边被共享，则它不是唯一的。路径仍然可以包含相同的边，只是不在路径中的相同位置（索引）。我还添加了最大深度参数，因为它似乎所有路径都是n！这从来都不好。
public class AllPathDetector<V, E extends Comparable>
{
private List<List<E>> allPaths;
public List<List<E>> getAllPathsBetweenNodes(DirectedGraph<V, E> graph,
V startNode, V endNode, int maxDepth)
{
allPaths = new ArrayList<List<E>>();
List<E> currentPath = new ArrayList<E>();
findAllPaths(startNode, startNode, endNode, currentPath, graph, maxDepth, 0);
return allPaths;
}
public List<List<E>> getAllUniqePathsBetweenNodes(DirectedGraph<V, E> graph,
V startNode, V endNode, int maxDepth)
{
allPaths = new ArrayList<List<E>>();
List<E> currentPath = new ArrayList<E>();
findAllUniquePaths(startNode, startNode, endNode, currentPath, graph, maxDepth, 0);
return allPaths;
}
private void findAllPaths(V currentNode, V startNode, V endNode,
List<E> currentPath, DirectedGraph<V, E> graph,
int maxDepth, int currentDepth)
{
Collection<E> outgoingEdges = graph.getOutEdges(currentNode);
if (currentDepth < maxDepth)
{
for (E outEdge : outgoingEdges)
{
V outNode = graph.getDest(outEdge);
//String outNode = outEdge.getSupertype();
if (outNode.equals(startNode))
{
List<E> cyclePath = new ArrayList<E>(currentPath);
cyclePath.add(outEdge);
System.out.println("Found cycle provoked by path " + cyclePath);
continue;
}
List<E> newPath = new ArrayList<E>(currentPath);
newPath.add(outEdge);
if (outNode.equals(endNode))
{
allPaths.add(newPath);
continue;
}
findAllPaths(outNode, startNode, endNode, newPath, graph, maxDepth, currentDepth + 1);
}
}
}
private void findAllUniquePaths(V currentNode, V startNode, V endNode,
List<E> currentPath, DirectedGraph<V, E> graph,
int maxDepth, int currentDepth)
{
Collection<E> outgoingEdges = graph.getOutEdges(currentNode);
if (currentDepth < maxDepth)
{
for (E outEdge : outgoingEdges)
{
V outNode = graph.getDest(outEdge);
//String outNode = outEdge.getSupertype();
if (outNode.equals(startNode))
{
List<E> cyclePath = new ArrayList<E>(currentPath);
cyclePath.add(outEdge);
System.out.println("Found cycle provoked by path " + cyclePath);
continue;
}
List<E> newPath = new ArrayList<E>(currentPath);
newPath.add(outEdge);
if (outNode.equals(endNode))
{
//Check for unique-ness before adding.
boolean unique = true;
//Check each existing path.
for (int pathItr = 0; pathItr < allPaths.size(); pathItr++)
{
//Compare the edges of the paths.
for (int edgeItr = 0; edgeItr < allPaths.get(pathItr).size(); edgeItr++)
{
//If the edges are the same, this path is not unique.
if (allPaths.get(pathItr).get(edgeItr).compareTo(newPath.get(edgeItr)) == 0)
{
unique = false;
}
}
}
//After we check all the edges, in all the paths,
//if it is still unique, we add it.
if (unique)
{
allPaths.add(newPath);
}
continue;
}
findAllUniquePaths(outNode, startNode, endNode, newPath, graph, maxDepth, currentDepth + 1);
}
}
}
}
以下是unique-paths的一些示例以及此实现的结果。
A - 1 - >乙 - 2 - > C和A - 1 - > d - 2 - > C =唯一的。
A - 1 - >乙 - 2 - “ç - 3 - > d和A - 1 - >电子 - 2 - ”ç - 3 - > d =不是唯一的。边缘Ç - 3 - 1 - - >乙 - 2 - “ç - 3 - > d和A - 1 - > E> d如边缘3
共享 - 2 - > B - 3 - > C - 4 - > D =唯一。边缘Ç - ＃ - d包含在两个路径，但在第一条路径是边缘3，并在第二条路径是边缘4.
相关问题
- 1. 寻找路径计划
- 2. 帮助寻找路径
- 3. 在Prolog中寻找路径
- 4. 寻找关键路径？
- 5. 使用Floyd-Warshall寻找所有最短路径和距离
- 6. “找不到路径的一部分”寻找一个UNC路径
- 7. 查找路径上的所有点AS3
- 8. 找到我所有的caches_action路径
- 9. 寻找爬山功能的路径
- 10. 寻找最近点的路径向前
- 11. AnkhSVN错误，寻找奇怪的路径
- 12. 寻找迷宫中的最短路径
- 13. 寻找最短路径数的算法
- 14. 寻找资源文件夹的路径？
- 15. 寻找.winmd路径的静态库
- 16. 寻找最短路径访问网格上的所有非封锁广场
- 17. 用传送器寻找路径
- 18. 在邻接矩阵中寻找路径
- 19. 序言：在迷宫中寻找路径
- 20. 路径寻找迷宫错误
- 21. 通过烟雾寻找路径
- 22. 在JSON代码中寻找路径
- 23. 在Minimax路径寻找解决方案中寻找路径和最大称量的边缘？
- 24. 查找有循环的有向图中的所有路径
- 25. SublimeCodeIntel没有在python 3路径中寻找
- 26. fs unlink找不到所需的路径
- 27. 有向无环图：找到特定节点的所有路径
- 28. 找到没有指定结束节点的所有路径？
- 29. Netbeans没有找到我所有的include_once路径
- 30. 局游戏寻路 - 找到多个最优路径
我发现在我自己的算法的错误。如果'currentNode'已经被访问，findAllPaths（）方法应该立即返回null。因此，存储已访问节点的“Set”并读取它以修复该错误已足够。 – Alphaaa 2013-02-22 14:31:07