Finding all paths in JUNG?

Question

Hi I was wondering if there is any way to find all the possible paths between two nodes N1 and N2 in JUNG. Thanks in advance for any help :)

Answer 1

This simple solution returns all the paths.

It works also with cyclic graphs, printing all cycling paths, hence it can be used also for cycle detection, which is not available in JUNG.

It uses an arbitrary class Entity for the nodes, and Edge for the edges. You can create such objects (make sure to implement hashcode() and equals()), or simply substitute them with String objects, depending on your needs.

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);
        }
    }
}

Answer 2

I created a slight variation that allows you to use generics, but is no longer static. Your type has to be comparable though. For the basic method comparable is not necessary. However, I added another function, which was necessary for my purposes which was to find all unique paths, that is two paths cannot share an edge at the position in the path. I only check the same position of the paths for the same edge, so for example if both paths start with the same edge, they are not unique. If the i-th edge in both paths is shared it is not unique. The paths can still contain the same edge, just not in the same position (index) in the path. I also added a max-depth parameter, because it seems all paths is n! which is never good.

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);
        }
    }
}
}

Here are some examples of unique-paths and the results for this implementation.

A--1-->B--2-->C and A--1-->D--2-->C = unique.

A--1-->B--2-->C--3-->D and A--1-->E--2-->C--3-->D = not unique. Edge C--3-->D is shared as edge 3.

A--1-->B--2-->C--3-->D and A--1-->E--2-->B--3-->C--4-->D = unique. Edge C--#--D is contained in both paths, however in the first path it is edge 3, and in the second path it is edge 4.

Answer 3

According to the documentation I don't think there is an out-of-the-box way to have all paths between two nodes. But you can easily adapt a breadth-first search to do this by managing a list of nodes that have been seen and visiting recursively the graph starting from the specified node. You can use the methods provided by the AbstractGraph class (doc here), eg getIncidentVertices.

In any case I don't think it is cheap problem..

Answer 4

Calculating all the possible paths between N1 and N2 costs O(n!) in the worst case, and may have that many outputs.

It is almost certainly the case that you don't want all the possible paths. What problem are you trying to solve?

Answer 5

I had some tasks in which i required all paths from vertex A to B.

Here, I took the ShortestPathDemo.java and modified it a bit to call it PathDemo.java. One can find both shortest and full path in a graph.

/******************************
        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>();
    }
}