test.java.old

UML设计测试工具

/*
 * USE - UML based specification environment
 * Copyright (C) 1999-2004 Mark Richters, University of Bremen
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  
 */

/* $ProjectHeader: use 2-3-0-release.1 Mon, 12 Sep 2005 20:18:33 +0200 green $ */

package org.tzi.use.graph.layout;
import org.tzi.use.graph.*;
import java.util.*;
import javax.swing.*;
import java.awt.*;


/**
 * @version 	$ProjectVersion: 2-3-0-release.1 $
 * @author 	Mark Richters
 */

public class Test {

    public Object[] sort(DirectedGraph g) {
	BitSet visited = new BitSet(g.size());

	Iterator nodes = g.iterator();
	int n = 0;
	while ( nodes.hasNext() ) {
	    Object node = nodes.next();
	    visited.set(n);
	    
	}
	return null;
    }


    public static DirectedGraph condense(DirectedGraph g1, Object[] orderedNodes) {
	// copy graph while absorbing 1-1 nodes with outgoing edge to
	// 1-2 or 1-3 node
	DirectedGraph g2 = new DirectedGraphBase();
	g2.add(orderedNodes[0]);
	for (int i = 1; i < orderedNodes.length - 1; i++) {
	    boolean absorb = false;
	    Object n1 = orderedNodes[i];
	    // check for 1-1 node
	    if ( g1.numIncomingEdges(n1) == 1 && g1.numOutgoingEdges(n1) == 1 ) {
		// get target node at outgoing edge
		Object n2 = g1.targetNodeSet(n1).iterator().next();
		int n2OutDegree = g1.numOutgoingEdges(n2);
		// check for 1-2 or 1-3 node
		if ( g1.numIncomingEdges(n2) == 1 
		     && (n2OutDegree == 2 || n2OutDegree == 3) ) {
		    absorb = true;
		}
	    }

	    if ( ! absorb ) 
		g2.add(n1);
	}
	return g2;
    }

    public static List formPairs(DirectedGraph g, Object[] orderedNodes) {
	ArrayList pairs = new ArrayList();

	int i = orderedNodes.length - 2;
	while ( i > 1 ) {
	    Object n = orderedNodes[i];
	    int ind = g.numIncomingEdges(n);
	    int outd = g.numOutgoingEdges(n);
	    System.out.println("node: " + n + " " + ind + "-" + outd);
	    if ( outd == 1 && (ind == 1 || ind == 2 || ind == 3) ) {
		i--;
	    } else if ( ind == 1 && (outd == 2 || outd == 3) ) {
		pairs.add(new Object[] { orderedNodes[i-1], n});
		i -= 2;
	    } else if ( ind == 2 && outd == 2 ) {
		Set predecessors = g.sourceNodeSet(n);
		int j = 1; 
		while ( j <= i ) {
		    Object n2 = orderedNodes[i - j];
		    if ( predecessors.contains(n2) ) {
			pairs.add(new Object[] { n2, n});
			break;
		    } else
			j++;
		}
		i = i - j - 1;
	    }
	    
	}

	return pairs;
    }

    public static Object[] removeCycles(final DirectedGraph g) {
	LinkedList sl = new LinkedList();
	LinkedList sr = new LinkedList();
	ArrayList rest = new ArrayList();
	
	Iterator nodes = g.iterator();
	while ( nodes.hasNext() ) {
	    Object node = nodes.next();
	    int ind = g.numIncomingEdges(node);
	    int outd = g.numOutgoingEdges(node);
	    if ( outd == 0 ) {
		// prepend sinks to sr
		sr.addFirst(node);
	    } else if ( ind == 0 ) {
		// append source to sl
		sl.addLast(node);
	    } else {
		rest.add(node);
	    }
	}
	System.out.println("sl = " + sl);
	System.out.println("sr = " + sr);
	
	System.out.println("rest before sort = " + rest);
	Collections.sort(rest, new Comparator() {
		public int compare(Object node1, Object node2) {
		    int d1 = g.numOutgoingEdges(node1) - g.numIncomingEdges(node1);
		    int d2 = g.numOutgoingEdges(node2) - g.numIncomingEdges(node2);
		    return d2 - d1;
		}
	    });
	System.out.println("rest after sort = " + rest);

	nodes = rest.iterator();
	while ( nodes.hasNext() ) {
	    Object node = nodes.next();
	    sl.addLast(node);
	}

	System.out.println("sl = " + sl);
	System.out.println("sr = " + sr);
	sl.addAll(sr);
	return sl.toArray();
    }

    private static void nextLayer(DirectedGraph g, List layers, Set layer) {
	System.out.println("layer = " + layer);
	Set aboveLayer = null;
	Iterator nodeIter = layer.iterator();
	while ( nodeIter.hasNext() ) {
	    Object node = nodeIter.next();
	    // consider immediate predecessors of node for next layer
	    Set predecessors = g.sourceNodeSet(node);
	    System.out.println("node = " + node + ", predecessors = " + predecessors);
	    Iterator predIter = predecessors.iterator();
	    while ( predIter.hasNext() ) {
		Object predNode = predIter.next();
		Set targets = g.targetNodeSet(predNode);
		System.out.println("node = " + predNode + ", targets = " + targets);
		if ( layer.containsAll(targets) ) {
		    if ( aboveLayer == null ) {
			aboveLayer = new HashSet();
			layers.add(aboveLayer);
		    }
		    aboveLayer.add(predNode);
		}
	    }
	}
	if ( aboveLayer != null )
	    nextLayer(g, layers, aboveLayer);
    }

//      public static void layer2(DirectedGraph g) {
//  	int[] nodeLayer = new int[g.size()];

//  	Iterator nodeIter = g.iterator();
//  	while ( nodeIter.hasNext() ) {
//  	    Object node = nodeIter.next();
//  	    nodeLayer[node.num()] int outd = g.numOutgoingEdges(node);

//      }


    // p. 248
    public static DirectedGraph graph1() {
	final int N = 13;
	int[][] edges = { 
	    {1,2}, {1,4}, {1,5}, 
	    {2,3}, {2,4}, {2,12}, 
	    {3,4}, {3,9}, {3,11},
	    {4,8},
	    {5,6}, {5,7}, {5,9},
	    {6,7}, {6,10}, {6,13},
	    {7,8}, {7,9},
	    {8,11}, {8,12},
	    {9,12},
	    {10,11}, {10,13},
	    {11,13},
	    {12,13},
	};
	return newGraph(N, edges);
    }

    // p. 295
    public static DirectedGraph graph2() {
	final int N = 9;
	int[][] edges = { 
	    {1,2}, {2,3}, {2,5}, {3,6}, {4,1}, {4,5}, {5,8},
	    {6,5}, {6,9}, {7,4}, {8,7}, {9,8}
	};
	return newGraph(N, edges);
    }

    public static DirectedGraph graph3() {
	final int N = 5;
	int[][] edges = { 
	    {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {3,4}
	};
	return newGraph(N, edges);
    }

    public static DirectedGraph newGraph(int N, int[][] edges) {
	DirectedGraph g = new DirectedGraphBase(N);
	Object[] nodes = new Object[N];
	for (int i = 0; i < N; i++) {
	    nodes[i] = new Integer(i + 1);
	    g.add(nodes[i]);
	}
	    
	for (int i = 0; i < edges.length; i++) {
	    // System.out.println(edges[i].length);
	    g.addEdge(new DirectedEdgeBase(nodes[edges[i][0] - 1], 
					   nodes[edges[i][1] - 1]));
	}
	return g;
    }


    public static void main(String[] args) {
  	DirectedGraph g;
//  	System.out.println(g);
//  	System.out.println();
//  	removeCycles(g);

//  	System.out.println();
	g = graph3();
	System.out.println(g);
	System.out.println();
	LayeredLayout l = new LayeredLayout(g);
	Layout layout = l.layout();
	//Object[] orderedNodes = removeCycles(g);
	//layer(g, orderedNodes);

	GraphPanel gp = new GraphPanel(layout);
	JFrame f = new JFrame("GraphPanel");

	// Layout the content pane
        JPanel contentPane = new JPanel();
        contentPane.setLayout(new BorderLayout());
        contentPane.add(new JScrollPane(gp), BorderLayout.CENTER);
        f.setContentPane(contentPane);
	f.pack();
	f.setVisible(true);
    }
}