import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * @return There is only one shortest path! We have to prevent endless
 *         looping!
 */
public static KspTestScenario<String, MyLink> getUnreachabilitiyScenario() {
	Graph<String, MyLink> graph = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String s = new String("S"); // the source
	graph.addVertex(s);
	String v = new String("V"); // the unreachable vertex!
	graph.addVertex(v);
	String w = new String("W"); // the intermediate vertex
	graph.addVertex(w);
	String t = new String("T"); // the target
	graph.addVertex(t);

	graph.addEdge(new MyLink(1, "S-V"), s, v, EdgeType.DIRECTED); // dead-end
	graph.addEdge(new MyLink(1, "S-W"), s, w, EdgeType.DIRECTED);
	graph.addEdge(new MyLink(1, "W-T"), w, t, EdgeType.DIRECTED);

	List<MyLink> path = new ArrayList<MyLink>();
	path.add(graph.findEdge(s, w));
	path.add(graph.findEdge(w, t));

	List<List<MyLink>> temp = new LinkedList<List<MyLink>>();
	temp.add(path);

	return new KspTestScenario<String, MyLink>(graph, temp, s, t);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void testUnreachable() {
	Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String n1 = new String("S"); // S
	g.addVertex(n1);
	String n2 = new String("A"); // A
	g.addVertex(n2);
	String n3 = new String("B"); // B -- not connected
	g.addVertex(n3);

	g.addEdge(new MyLink(1, "S-A"), n1, n2, EdgeType.DIRECTED); // S - A

	Transformer<MyLink, Number> weightTrans = new Transformer<MyLink, Number>() {
		@Override
		public Number transform(MyLink link) {
			return link.getWeight();
		}
	};
	SuurballeTarjan<String, MyLink> testMain = new SuurballeTarjan<String, MyLink>(
			g, weightTrans);
	assertEquals(null, testMain.getDisjointPaths(n1, n3));
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void testNoDisjointSolution() {
	Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String n1 = new String("A"); // A
	g.addVertex(n1);
	String n2 = new String("B"); // B
	g.addVertex(n2);

	g.addEdge(new MyLink(2, "A-B"), n1, n2, EdgeType.DIRECTED);

	Transformer<MyLink, Number> weightTrans = new Transformer<MyLink, Number>() {
		@Override
		public Number transform(MyLink link) {
			return link.getWeight();
		}
	};
	SuurballeTarjan<String, MyLink> testMain = new SuurballeTarjan<String, MyLink>(
			g, weightTrans);
	assertEquals("[[A-B]]", testMain.getDisjointPaths(n1, n2).toString());
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * This method reverse the path "path" in the graph "graph" and returns it.
 * 
 * @param graph
 *            the input graph which will not be changed.
 * @param path
 *            the path to reverse
 * @return a new graph with the reversed path
 */
private Graph<V, E> reverseEdges(Graph<V, E> graph, List<E> path) {
	if (graph == null || path == null)
		throw new IllegalArgumentException();
	Graph<V, E> clone = new DirectedOrderedSparseMultigraph<V, E>();

	for (V v : graph.getVertices())
		clone.addVertex(v);
	for (E e : graph.getEdges())
		clone.addEdge(e, graph.getEndpoints(e));

	for (E link : path) {
		V src = clone.getSource(link);
		V dst = clone.getDest(link);
		clone.removeEdge(link);
		clone.addEdge(link, dst, src, EdgeType.DIRECTED);
	}
	return clone;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/** <p>Obtains a {@code JUNG} graph from a given set of links.</p>
 * 
 * @param nodes Collection of nodes
 * @param links Collection of links
 * @return {@code JUNG} graph */
public static Graph<Node, Link> getGraphFromLinkMap(Collection<Node> nodes, Collection<Link> links)
{
	Graph<Node, Link> graph = new DirectedOrderedSparseMultigraph<Node, Link>();

	for (Node node : nodes)
		graph.addVertex(node);

	if (links != null)
	{
		for (Link e : links)
		{
			if (!graph.containsVertex(e.getOriginNode())) throw new RuntimeException("Bad"); //graph.addVertex(e.getOriginNode());
			if (!graph.containsVertex(e.getDestinationNode())) throw new RuntimeException("Bad"); //graph.addVertex(e.getDestinationNode());
			graph.addEdge(e, e.getOriginNode(), e.getDestinationNode());
		}
	}

	return graph;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/** This method reverse the path "path" in the graph "graph" and returns it.
 * 
 * @param graph the input graph which will not be changed.
 * @param path the path to reverse
 * @return a new graph with the reversed path
 * @since 0.3.0 */
private static <V, E> Graph<V, E> reverseEdges(Graph<V, E> graph, List<E> path)
{
	if (graph == null || path == null) throw new IllegalArgumentException();
	Graph<V, E> clone = new DirectedOrderedSparseMultigraph<V, E>();

	for (V v : graph.getVertices())
		clone.addVertex(v);
	for (E e : graph.getEdges())
		clone.addEdge(e, graph.getEndpoints(e));

	for (E link : path)
	{
		V src = clone.getSource(link);
		V dst = clone.getDest(link);
		clone.removeEdge(link);
		clone.addEdge(link, dst, src, EdgeType.DIRECTED);
	}

	return clone;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
public static <V, E> Network readJUNGGraph(DirectedOrderedSparseMultigraph<V, E> graph, int modularityFunction) {
    StringBuilder stringBuilder = new StringBuilder();
    ArrayList<Object> vertices = new ArrayList<>(graph.getVertices());
    for (E edge : graph.getEdges()) {
        Pair<V> endpoints = graph.getEndpoints(edge);
        int firstVertex = vertices.indexOf(endpoints.getFirst());
        int secondVertex = vertices.indexOf(endpoints.getSecond());
        int smallerVertex, largerVertex;

        if (firstVertex > secondVertex) {
            smallerVertex = secondVertex;
            largerVertex = firstVertex;
        } else {
            smallerVertex = firstVertex;
            largerVertex = secondVertex;
        }
        stringBuilder.append(smallerVertex).append("\t").append(largerVertex).append("\n");
    }
    return readInputString(stringBuilder.toString(), modularityFunction);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
private static DirectedOrderedSparseMultigraph<String, String> getSimpleMultigraph() {
    DirectedOrderedSparseMultigraph<String, String> multigraph = new DirectedOrderedSparseMultigraph<>();
    Stream.of("A", "B", "C", "D", "E", "F").forEachOrdered(multigraph::addVertex);

    multigraph.addEdge("A->B", "A", "B");
    multigraph.addEdge("B->C", "B", "C");
    multigraph.addEdge("C->A", "C", "A");

    multigraph.addEdge("A->D", "A", "D");

    multigraph.addEdge("D->E", "D", "E");
    multigraph.addEdge("E->F", "E", "F");
    multigraph.addEdge("F->D", "F", "D");

    return multigraph;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * This method reverse the path "path" in the graph "graph" and returns it.
 *
 * @param graph the input graph which will not be changed.
 * @param path  the path to reverse
 * @return a new graph with the reversed path
 */
private Graph<V, E> reverseEdges(Graph<V, E> graph, List<E> path) {
    if (graph == null || path == null)
        throw new IllegalArgumentException();
    Graph<V, E> clone = new DirectedOrderedSparseMultigraph<V, E>();

    for (V v : graph.getVertices())
        clone.addVertex(v);
    for (E e : graph.getEdges())
        clone.addEdge(e, graph.getEndpoints(e));

    for (E link : path) {
        V src = clone.getSource(link);
        V dst = clone.getDest(link);
        clone.removeEdge(link);
        clone.addEdge(link, dst, src, EdgeType.DIRECTED);
    }
    return clone;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * @return There is only one shortest path! We have to prevent endless
 * looping!
 */
public static KspTestScenario<String, MyLink> getUnreachabilitiyScenario() {
    Graph<String, MyLink> graph = new DirectedOrderedSparseMultigraph<String, MyLink>();

    String s = new String("S"); // the source
    graph.addVertex(s);
    String v = new String("V"); // the unreachable vertex!
    graph.addVertex(v);
    String w = new String("W"); // the intermediate vertex
    graph.addVertex(w);
    String t = new String("T"); // the target
    graph.addVertex(t);

    graph.addEdge(new MyLink(1, "S-V"), s, v, EdgeType.DIRECTED); // dead-end
    graph.addEdge(new MyLink(1, "S-W"), s, w, EdgeType.DIRECTED);
    graph.addEdge(new MyLink(1, "W-T"), w, t, EdgeType.DIRECTED);

    List<MyLink> path = new ArrayList<MyLink>();
    path.add(graph.findEdge(s, w));
    path.add(graph.findEdge(w, t));

    List<List<MyLink>> temp = new LinkedList<List<MyLink>>();
    temp.add(path);

    return new KspTestScenario<String, MyLink>(graph, temp, s, t);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void testUnreachable() {
    Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();

    String n1 = new String("S"); // S
    g.addVertex(n1);
    String n2 = new String("A"); // A
    g.addVertex(n2);
    String n3 = new String("B"); // B -- not connected
    g.addVertex(n3);

    g.addEdge(new MyLink(1, "S-A"), n1, n2, EdgeType.DIRECTED); // S - A

    Transformer<MyLink, Number> weightTrans = new Transformer<MyLink, Number>() {
        @Override
        public Number transform(MyLink link) {
            return link.getWeight();
        }
    };
    SuurballeTarjan<String, MyLink> testMain = new SuurballeTarjan<String, MyLink>(
            g, weightTrans);
    assertEquals(null, testMain.getDisjointPaths(n1, n3));
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void testNoDisjointSolution() {
    Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();

    String n1 = new String("A"); // A
    g.addVertex(n1);
    String n2 = new String("B"); // B
    g.addVertex(n2);

    g.addEdge(new MyLink(2, "A-B"), n1, n2, EdgeType.DIRECTED);

    Transformer<MyLink, Number> weightTrans = new Transformer<MyLink, Number>() {
        @Override
        public Number transform(MyLink link) {
            return link.getWeight();
        }
    };
    SuurballeTarjan<String, MyLink> testMain = new SuurballeTarjan<String, MyLink>(
            g, weightTrans);
    assertEquals("[[A-B]]", testMain.getDisjointPaths(n1, n2).toString());
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * @return There is only one shortest path! We have to prevent endless
 *         looping!
 */
public static KspTestScenario<String, MyLink> getLoopScenario() {
	Graph<String, MyLink> graph = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String s = new String("S"); // the source
	graph.addVertex(s);
	String a = new String("A"); // the intermediate vertex 1
	graph.addVertex(a);
	String b = new String("B"); // the intermediate vertex 2
	graph.addVertex(b);
	String t = new String("T"); // the target
	graph.addVertex(t);

	graph.addEdge(new MyLink(1, "S-A"), s, a, EdgeType.DIRECTED);
	graph.addEdge(new MyLink(1, "A-B"), a, b, EdgeType.DIRECTED);
	graph.addEdge(new MyLink(1, "B-A"), b, a, EdgeType.DIRECTED); // loop!
	graph.addEdge(new MyLink(1, "B-T"), b, t, EdgeType.DIRECTED);

	List<MyLink> path = new ArrayList<MyLink>();
	path.add(graph.findEdge(s, a));
	path.add(graph.findEdge(a, b));
	path.add(graph.findEdge(b, t));

	List<List<MyLink>> temp = new LinkedList<List<MyLink>>();
	temp.add(path);

	return new KspTestScenario<String, MyLink>(graph, temp, s, t);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
/**
 * @return Self-loop at start and unreachable target.
 */
public static KspTestScenario<String, MyLink> getSelfLoopUnreachableScenario() {
	Graph<String, MyLink> graph = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String s = new String("S"); // the source
	graph.addVertex(s);
	String t = new String("T");
	graph.addVertex(t);

	graph.addEdge(new MyLink(20, "S-S"), s, s, EdgeType.DIRECTED); // loop

	List<List<MyLink>> temp = new LinkedList<List<MyLink>>();

	return new KspTestScenario<String, MyLink>(graph, temp, s, t);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test(expected = IllegalArgumentException.class)
public void constructorTest2() {
	Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();
	Transformer<MyLink, Number> weightTrans = null;

	new SuurballeTarjan<String, MyLink>(g, weightTrans);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void testTargetRemoval() {
	Graph<String, MyLink> g = new DirectedOrderedSparseMultigraph<String, MyLink>();

	String n1 = new String("S"); // S
	g.addVertex(n1);
	String n2 = new String("A"); // A
	g.addVertex(n2);
	String n3 = new String("B"); // B
	g.addVertex(n3);
	String n4 = new String("C"); // C
	g.addVertex(n4);
	String n5 = new String("D"); // D
	g.addVertex(n5);

	g.addEdge(new MyLink(3, "S-A"), n1, n2, EdgeType.DIRECTED); // S - A
	g.addEdge(new MyLink(1, "A-C"), n2, n4, EdgeType.DIRECTED); // A - C
	g.addEdge(new MyLink(3, "S-B"), n1, n3, EdgeType.DIRECTED); // S - B
	g.addEdge(new MyLink(3, "B-C"), n3, n4, EdgeType.DIRECTED); // B - C
	g.addEdge(new MyLink(3, "C-D"), n4, n5, EdgeType.DIRECTED); // C - D

	Transformer<MyLink, Number> weightTrans = new Transformer<MyLink, Number>() {
		@Override
		public Number transform(MyLink link) {
			return link.getWeight();
		}
	};
	SuurballeTarjan<String, MyLink> testMain = new SuurballeTarjan<String, MyLink>(
			g, weightTrans);
	assertEquals("[[S-A, A-C, C-D]]", testMain.getDisjointPaths(n1, n5)
			.toString());
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test(expected = IllegalArgumentException.class)
public void basics() {
	Graph<String, MyLink> graph = new DirectedOrderedSparseMultigraph<String, MyLink>();
	Transformer<MyLink, Number> weightTrans = null;

	factory.create(graph, weightTrans);
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Override
public Graph<String, String> createGraph() {
	// edu.uci.ics.jung.graph.Tree<String,String> treeGraph = new DelegateTree<String,String>();
	DirectedOrderedSparseMultigraph<String, String> treeGraph = new DirectedOrderedSparseMultigraph<String, String>();

	Tree root = this.model.getRoot();
	treeGraph.addVertex("Root");
	vertexMap.put("Root", root);
	addTree(treeGraph, root, "Root");

	return new DelegateForest<String, String>(treeGraph);
	// return treeGraph;
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void jungToNetworkEquivalence() {
    DirectedOrderedSparseMultigraph<String, String> multigraph = getSimpleMultigraph();
    Network network = ModularityOptimizer.readJUNGGraph(multigraph, 1);

    Assert.assertEquals(network.getNNodes(), multigraph.getVertexCount(), "Vertex counts do not match!");
    Assert.assertEquals(network.getNEdges(), multigraph.getEdgeCount(), "Edge counts do not match!");
    Assert.assertEquals(network.getNEdgesPerNode(), multigraph.getVertices().stream().mapToInt(multigraph::getNeighborCount).toArray(), "The numbers of neighbors do not match!");
}
 

import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; //导入依赖的package包/类
@Test
public void networkModularityDetection() {
    DirectedOrderedSparseMultigraph<String, String> multigraph = getSimpleMultigraph();
    Network network = ModularityOptimizer.readJUNGGraph(multigraph, 1);

    double resolution = 1d / (2 * network.getTotalEdgeWeight() + network.getTotalEdgeWeightSelfLinks());
    VOSClusteringTechnique vosClusteringTechnique = new VOSClusteringTechnique(network, resolution);
    Random r = new Random(0);
    vosClusteringTechnique.runIteratedLouvainAlgorithmWithMultilevelRefinement(100, r);
    Assert.assertEquals(vosClusteringTechnique.getClustering().getNodesPerCluster(), new int[][]{{0, 1, 2}, {3, 4, 5}}, "Incorrect clustering!");
}