Блог

Привет, мне было интересно, есть ли какой-либо способ найти все возможные пути между двумя узлами N1 и N2 в JUNG. Заранее спасибо за любую помощь 🙂

У меня было несколько задач, в которых мне требовались все пути из вершины 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>();
    }
}
  

Согласно документации, я не думаю, что существует готовый способ получить все пути между двумя узлами. Но вы можете легко адаптировать для этого поиск в ширину, управляя списком просмотренных узлов и рекурсивно просматривая график, начиная с указанного узла. Вы можете использовать методы, предоставляемые AbstractGraph классом (документ здесь), например getIncidentVertices .

В любом случае я не думаю, что это дешевая проблема..

Вычисление всех возможных путей между N1 и N2 в наихудшем случае обходится в O (n!) и может иметь такое количество результатов.

Почти наверняка вам не нужны все возможные пути. Какую проблему вы пытаетесь решить?

Это простое решение возвращает все пути.

Он работает также с циклическими графами, выводя все циклические пути, следовательно, его можно использовать также для обнаружения циклов, чего нет в 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);
        }
    }
}
  

Я создал небольшую вариацию, которая позволяет использовать общие, но больше не является статичной. Однако ваш тип должен быть сопоставимым. Для базового метода comparable не требуется. Однако я добавил другую функцию, которая была необходима для моих целей, которая заключалась в поиске всех уникальных путей, то есть два пути не могут иметь общего ребра в позиции в пути. Я проверяю только одинаковое положение путей для одного и того же ребра, поэтому, например, если оба пути начинаются с одного и того же ребра, они не уникальны. Если i-е ребро в обоих путях является общим, оно не уникально. Пути все еще могут содержать одно и то же ребро, просто не в той же позиции (индексе) в пути. Я также добавил параметр max-depth, потому что кажется, что all paths равно 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);
        }
    }
}
}
  

Вот несколько примеров уникальных путей и результатов для этой реализации.

A—1—> B—2—> C и A—1—> D—2—> C = уникальные.

A—1—> B—2—> C—3—> D и A—1—> E—2—> C—3—> D = не уникальный. Ребро C—3—> D используется совместно как ребро 3.

A-1-> B-2-> C-3-> D и A-1-> E-2-> B-3-> C-4-> D = уникальный. Ребро C—#—D содержится в обоих путях, однако в первом пути это ребро 3, а во втором пути это ребро 4.