Thread: [jgrapht-users] edges of a graph

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hi,

I am a newbie to JGraphT. What I want is to extract all connected subgraphs
from a griven graph. Below is the code that I have used to familiarize
myself with JGraphT. Two questions:

1. Why do I not get the desired edge sets from the given graph?

2. Wouldn't it be nice to include a subgraph extractor as a general
functionality in the JGraphT package?

Thanks.
Hans-Martin Adorf

/*
 * Demo.java
 */

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.jgraph.graph.DefaultEdge;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.graph.SimpleGraph;

/**
 *
 * @author Hans-Martin Adorf
 */
public class Demo {

    public static void main(String... args) {
        UndirectedGraph<String, DefaultEdge> g =
                new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        String v1 = "v1";
        String v2 = "v2";
        String v3 = "v3";
        String v4 = "v4";

        // add the vertices
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);

        // add edges
        g.addEdge(v1, v2);
        // g.addEdge(v2, v3);
        g.addEdge(v3, v4);
        // g.addEdge(v4, v1);

        System.out.println(g);              // returns ([v1, v2, v3, v4],
[null={v1,v2}, null={v3,v4}])
        System.out.println(g.edgeSet());    // returns [null, null]
        System.out.println(g.edgesOf(v1));  // returns [null]

        ConnectivityInspector connectivityInspector = new
ConnectivityInspector(g);
        System.out.println(connectivityInspector.isGraphConnected());
        List<Set<String>> connectedSets =
connectivityInspector.connectedSets();
        System.out.println(connectedSets);

        System.out.println(extractConnectedGraphs(g, connectedSets));

    }

    public static Set<UndirectedGraph<String, DefaultEdge>>
extractConnectedGraphs(
            UndirectedGraph<String, DefaultEdge> sourceGraph,
            List<Set<String>> connectedVertexList) {
        Set<UndirectedGraph<String, DefaultEdge>> result = new
HashSet<UndirectedGraph<String, DefaultEdge>>();
        for (Set<String> connectedVertices : connectedVertexList) {
            result.add(extractConnectedGraph(sourceGraph,
connectedVertices));
        }
        return result;
    }

    public static UndirectedGraph<String, DefaultEdge>
extractConnectedGraph(
            UndirectedGraph<String, DefaultEdge> sourceGraph,
            Set<String> connectedVertices) {
        UndirectedGraph<String, DefaultEdge> targetGraph =
                new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
        for (String vertex : connectedVertices) {
            addEdges(sourceGraph, vertex, targetGraph);
        }
        return targetGraph;
    }

    public static UndirectedGraph<String, DefaultEdge> addEdges(
            UndirectedGraph<String, DefaultEdge> sourceGraph,
            String vertex,
            UndirectedGraph<String, DefaultEdge> targetGraph) {
        targetGraph.addVertex(vertex);
        System.out.println(sourceGraph.edgesOf(vertex));
        for (DefaultEdge edge : sourceGraph.edgesOf(vertex)) {
            targetGraph.addEdge((String) edge.getSource(), (String)
edge.getTarget());
        }
        return targetGraph;
    }
}