サイト内におけるページ間のリンク構造を可視化する
戻る
::::::::::::::
GraphViewer.bat
::::::::::::::
java GraphViewer
::::::::::::::
CommonDrawer.java
::::::::::::::
import java.awt.*;
import java.util.*;
/**
* $Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
* @author KISHI Yasuhiro
* ２次元座標をリスト化したものを線分で繋いで描画する汎用クラス
*/
public class CommonDrawer implements Paintable {
private java.util.Map vertexMap;
private Color color;
private double cx;
private double cy;
public void setVertexMap( java.util.Map vertexMap, Color color, double cx, double cy ) {
this.vertexMap = vertexMap;
this.color = color;
this.cx = cx;
this.cy = cy;
}
public void paint( Graphics g ) {
g.setColor( color );
Iterator iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
double x = vertex.getX();
double y = vertex.getY();
java.util.List links = vertex.getLinks();
for ( int i = 0;i < links.size();i++ ) {
Vertex link = ( Vertex ) links.get( i );
g.drawLine( ( int ) ( x + cx ), ( int ) ( y + cy ), ( int ) ( link.getX() + cx ), ( int ) ( link.getY() + cy ) );
}
}
}
}
::::::::::::::
CrossReferenceContainer.java
::::::::::::::
import java.util.*;
import java.io.*;
/**
* $Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
* @author KISHI Yasuhiro
*/
public class CrossReferenceContainer extends HashMap {
private Reader reader;
/** クローリングした結果が格納されるMAP */
private Map crawlingResult;
public CrossReferenceContainer() {
super();
crawlingResult = new HashMap();
}
public void setReader( Reader reader ) {
this.reader = reader;
}
public void parse() throws Throwable {
try {
// クロール結果の内容を全て読み込む
setCrawlingResult();
// クロスレファレンスを求める
getCrossReference();
} catch ( Throwable e ) {
throw e;
}
}
private void getCrossReference() {
Iterator iterator = this.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
seekLinks( url );
}
}
private void seekLinks( String url ) {
System.err.print( "*" );
// System.out.println( url );
Iterator iterator = crawlingResult.keySet().iterator();
while ( iterator.hasNext() ) {
String key = ( String ) iterator.next();
String value = ( String ) crawlingResult.get( key );
if ( url.equals( value ) ) {
if ( key.length() == 0 ) {
// ルートノードである
continue;
}
String parentKey = getParentKey( key );
// System.out.println( "*** " + key + " --> " + parentKey);
addLinks( url, parentKey );
}
}
}
private String getParentKey( String key ) {
if ( !key.contains( "-" ) ) {
return "";
} else {
String[] arr = key.split( "-" );
StringBuilder sb = new StringBuilder();
sb.append( arr[ 0 ] );
for ( int i = 1;i < arr.length - 1;i++ ) {
sb.append( "-" );
sb.append( arr[ i ] );
}
return sb.toString();
}
}
private void addLinks( String url, String parentKey ) {
String linkURL = ( String ) crawlingResult.get( parentKey );
// System.out.println( " " + linkURL );
HashSet links = ( HashSet ) this.get( url );
if ( !links.contains( linkURL ) ) {
links.add( linkURL );
}
}
private void setCrawlingResult() throws Throwable {
BufferedReader br = new BufferedReader( reader );
try {
String line = null;
while ( ( line = br.readLine() ) != null ) {
// System.out.println( line);
String token[] = line.split( "\t" );
// System.out.println(token[0]);
if ( token.length != 2 ) {
System.err.println( "不正な行です-> " + line );
continue;
}
String path = token[ 0 ];
String url = token[ 1 ];
crawlingResult.put( path, url );
this.put( url, new HashSet() );
}
br.close();
} catch ( Throwable e ) {
throw e;
}
}
public void dumpAll() {
System.out.println();
Iterator iterator = this.keySet().iterator();
int i = 0;
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
HashSet links = ( HashSet ) this.get( url );
// それぞれのURLとそれにリンクしているURLの数をダンプする
System.out.printf( "%s", url );
System.out.printf( "\t%4d\n", links.size() );
}
}
/** 単体試験 */
static public void main( String[] args ) throws Throwable {
if ( args.length != 1 ) {
System.out.println( "Usage: java CrossReferenceContainer [inputFileName]" );
System.exit( 1 );
}
CrossReferenceContainer container = new CrossReferenceContainer();
try {
container.setReader( new FileReader( args[ 0 ] ) );
container.parse();
container.dumpAll();
} catch ( Throwable e ) {
throw e;
}
}
}
::::::::::::::
DifferentiationManager.java
::::::::::::::
import java.util.*;
/**
* $Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
* @author KISHI Yasuhiro
* それぞれのVertexが持っているリンクの数をもとに表示位置を決める
*/
public class DifferentiationManager {
/** グループの個数 */
private int divisionCount;
/** グループ分けしたVertexを格納したHASH */
private Map divisionMap;
/** 最大半径 */
private double maxRadius;
private Map vertexMap;
public DifferentiationManager( Map vertexMap ) {
this.vertexMap = vertexMap;
}
public void setDivisionCount( int divisionCount ) {
this.divisionCount = divisionCount;
}
public void setMaxRadius( double maxRadius ) {
this.maxRadius = maxRadius;
}
/** 各々のVertexが持つリンク数の最大値を求める */
private int getMaxNumberOfLinks() {
int max = 0;
Iterator iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
List list = vertex.getLinks();
if ( max < list.size() ) {
max = list.size();
}
}
return max;
}
/** 度数分布を求める */
private void getFrequencyDistribution() {
int maxNumberOfLinks = getMaxNumberOfLinks();
Iterator iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
List list = vertex.getLinks();
// 保持するリンク数ごとにグループ分けするためのIDを求める
int division = ( int ) ( list.size() * 1.0 / maxNumberOfLinks * divisionCount );
// System.out.println( vertex.getName() + "\t" + list.size() + "\t" + division);
if ( divisionMap == null ) {
divisionMap = new TreeMap();
}
List vertexList = ( List ) divisionMap.get( division );
if ( vertexList == null ) {
vertexList = new LinkedList();
vertexList.add( vertex );
divisionMap.put( division, vertexList );
} else {
vertexList.add( vertex );
}
}
}
/** 得られた度数分布をダンプする */
private void dumpFrequencyDistribution() {
Iterator iterator = divisionMap.keySet().iterator();
while ( iterator.hasNext() ) {
Integer division = ( Integer ) iterator.next();
List vertexList = ( List ) divisionMap.get( division );
double radius = maxRadius * ( divisionCount + 1 - division.intValue() ) / divisionCount;
System.out.println( division + "\t" + vertexList.size() + "\t" + radius );
}
}
// グループ化したVertexに座標を与える
public void differentiate() {
getFrequencyDistribution();
//======================================
// DEBUG用
//======================================
dumpFrequencyDistribution();
// 各グループごとに座標をセットしていく
Iterator iterator = divisionMap.keySet().iterator();
while ( iterator.hasNext() ) {
Integer division = ( Integer ) iterator.next();
List vertexList = ( List ) divisionMap.get( division );
double radius = maxRadius * ( divisionCount + 1 - division.intValue() ) / divisionCount;
// 同一グループの場合は、同一円周上に均等に配置する
for ( int i = 0;i < vertexList.size();i++ ) {
double radian = 2.0 * Math.PI * i / vertexList.size();
double x = radius * Math.cos( radian );
double y = radius * Math.sin( radian );
// X座標、Y座標を与える
Vertex vertex = ( Vertex ) vertexList.get( i );
vertex.setPosition( x, y );
}
}
}
}
::::::::::::::
DrawingPanel.java
::::::::::::::
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
/**
* $Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
* @author KISHI Yasuhiro
*/
public class DrawingPanel extends JPanel implements Runnable {
private GraphModel model;
private CommonDrawer drawer;
public DrawingPanel() {
// モデルのインスタンス化
try {
// --- 後でUIからパラメータを設定できるように変更する予定
model = new GraphModel( "myData.tsv" );
} catch ( Throwable e ) {
e.printStackTrace();
}
// 各Vertexが保有するリンクの数から、それぞれの座標を設定する
// --- 後でUIからパラメータを設定できるように変更する予定
DifferentiationManager manager = new DifferentiationManager( model.getVertexMap() );
manager.setDivisionCount( 10 );
manager.setMaxRadius( 150.0 );
manager.differentiate();
// 描画するクラスをインスタンス化
drawer = new CommonDrawer();
drawer.setVertexMap( model.getVertexMap(), Color.white, 400.0, 300.0 );
// スレッド開始
Thread thread = new Thread( this );
thread.start();
}
public void run() {
while ( true ) {
SwingUtilities.invokeLater(
new Runnable() {
public void run() {
repaint();
}
}
);
try {
Thread.sleep( 100 );
} catch ( Exception e ) {
e.printStackTrace();
}
}
}
public void paintComponent( Graphics g ) {
int width = getWidth();
int height = getHeight();
// 画面クリア
g.setColor( Color.black );
// このコンポーネントのサイズを取得する
g.fillRect( 0 , 0 , width , height );
// 各頂点を結ぶ線分を描画
drawer.paint( g );
// 各頂点を移動させる(収縮させる）
VertexDisplacer.deflate( model.getVertexMap() );
// 各頂点を移動させる(膨張させる）
VertexDisplacer.inflate( model.getVertexMap() );
}
/** あとで別のユーティリティクラスに移動する */
static String sprintf( String format, Object obj ) throws Exception {
String value = null;
try {
// C言語のsprinfもどき
ByteArrayOutputStream baos = new ByteArrayOutputStream();
PrintWriter pw = new PrintWriter( baos );
pw.printf( format, obj );
pw.flush();
pw.close();
value = baos.toString( "UTF8" );
baos.close();
} catch ( Exception e ) {
throw e;
} finally {
return value;
}
}
}
::::::::::::::
GraphModel.java
::::::::::::::
import java.io.*;
import java.util.*;
/**
$Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
@author KISHI Yasuhiro
*/
public class GraphModel {
/** VertexクラスのオブジェクトとURLの関係性を格納したMAP */
private Map vertexMap;
/** 入力TSVファイル */
private String inputFileName;
/** URL同士のクロスレファレンス情報を格納するMAP */
private CrossReferenceContainer container;
public GraphModel( String inputFileName ) throws Throwable {
this.inputFileName = inputFileName;
try {
init();
} catch ( Throwable e ) {
throw e;
}
// VertexクラスのオブジェクトとURLの関係性を構築
createVertexMap();
// Vertexクラスのオブジェクト同士の関連性を構築
createRelationshipAmongVertices();
}
/** 指定したURLに対応するリンクをVertexレベルで求める */
public List getVertexLinks( String url ) {
Vertex vertex = ( Vertex ) vertexMap.get( url );
return vertex.getLinks();
}
/** Vertexクラスのオブジェクト同士の関連性を構築 */
private void createRelationshipAmongVertices() {
Iterator iterator = container.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
// このURLにリンクされているURLのリストが取得される
Set links = ( HashSet ) container.get( url );
Vertex vertex = ( Vertex ) vertexMap.get( url );
linkVertices( vertex, links );
}
}
private void linkVertices( Vertex vertex, Set links ) {
Iterator iterator = links.iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex counterVertex = ( Vertex ) vertexMap.get( url );
// Vertex同士をリンクする
vertex.addLink( counterVertex );
}
}
/** VertexクラスのオブジェクトとURLの関係性を構築 */
private void createVertexMap() {
Iterator iterator = container.keySet().iterator();
vertexMap = new TreeMap();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
// System.out.println( url );
vertexMap.put( url, new Vertex( url ) );
}
}
/** クロスレファレンスを求める */
private void init() throws Throwable {
container = new CrossReferenceContainer();
try {
container.setReader( new FileReader( inputFileName ) );
container.parse();
} catch ( Throwable e ) {
throw e;
}
}
public Map getVertexMap() {
return vertexMap;
}
public void dumpVertexPosition() {
// セットされた座標をダンプしてみる
Iterator iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
double x = vertex.getX();
double y = vertex.getY();
System.out.printf( "%s %5.2f %5.2f\n",
vertex.getName(), x, y );
}
}
/** 単体試験 */
static public void main( String[] args ) throws Throwable {
if ( args.length != 1 ) {
System.out.println( "Usage: java GraphModel [inputFileName]" );
System.exit( 1 );
}
GraphModel model;
try {
model = new GraphModel( args[ 0 ] );
} catch ( Throwable e ) {
throw e;
}
// テストコード→リンクの確認
System.out.println();
List list = model.getVertexLinks( "http://www.yodobashi.com/enjoy_more/cm/cat_8427434/66.html" );
Iterator iterator = list.iterator();
while ( iterator.hasNext() ) {
Vertex vertex = ( Vertex ) iterator.next();
System.out.println( "\t" + vertex.getName() );
}
// 各Vertexが保有するリンクの数から、それぞれの座標を設定する
DifferentiationManager manager = new DifferentiationManager( model.getVertexMap() );
manager.setDivisionCount( 10 );
manager.setMaxRadius( 200.0 );
manager.differentiate();
// 頂点の座標をダンプしてみる
model.dumpVertexPosition();
}
}
::::::::::::::
GraphViewer.java
::::::::::::::
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
/**
<pre>
サイト内におけるページ間のリンク構造を可視化する
</pre>
$Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
@author KISHI Yasuhiro
*/
public class GraphViewer extends JFrame {
private DrawingPanel dp = new DrawingPanel();
public static void main( String args[] ) {
new GraphViewer().setVisible( true );
}
public GraphViewer() {
//----------------------------------------------------
// タイトル
//----------------------------------------------------
setTitle( "サイト内におけるページ間のリンク構造を可視化する" );
setDefaultCloseOperation( EXIT_ON_CLOSE );
//----------------------------------------------------
// 描画用パネルを追加
//----------------------------------------------------
dp.setPreferredSize( new Dimension( 800 , 600 ) );
this.add( dp );
this.pack();
}
}
::::::::::::::
Paintable.java
::::::::::::::
import java.awt.*;
/**
$Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
@author KISHI Yasuhiro
*/
public interface Paintable {
public void paint( Graphics g );
}
::::::::::::::
Position.java
::::::::::::::
public class Position {
double x;
double y;
public Position( double x, double y ) {
this.x = x;
this.y = y;
}
public void setXY( double x, double y ) {
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
}
::::::::::::::
Vertex.java
::::::::::::::
import java.util.*;
/**
* $Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
* @author KISHI Yasuhiro
* グラフ構造における頂点を表現するクラス
*/
public class Vertex {
private List links;
private String name;
private Position position;
public Vertex( String name ) {
this.name = name;
}
/** XY座標を与える */
public void setPosition( double x, double y ) {
if ( position == null ) {
position = new Position( x, y );
} else {
position.setXY( x, y );
}
}
public double getX() {
return position.getX();
}
public double getY() {
return position.getY();
}
public String getName() {
return name;
}
public void addLink( Vertex vertex ) {
if ( links == null ) {
links = new LinkedList();
}
links.add( vertex );
}
public List getLinks() {
return links;
}
public void deflateNext() {
//=========================================================
// リンクしている頂点の重心をもとめてそれに近づく(距離1.0だけ）
//=========================================================
double x = this.position.getX();
double y = this.position.getY();
List list = this.getLinks();
Iterator iterator = list.iterator();
double avgX = 0.0;
double avgY = 0.0;
while ( iterator.hasNext() ) {
Vertex link = ( Vertex ) iterator.next();
avgX += link.getX();
avgY += link.getY();
}
// 重心の位置を取得
avgX /= list.size();
avgY /= list.size();
double diffX = avgX - x;
double diffY = avgY - y;
double distance = Math.sqrt( diffX * diffX + diffY * diffY );
x += 1.0 / distance * diffX;
y += 1.0 / distance * diffY;
position.setXY( x, y );
}
public void inflateNext( double cx, double cy ) {
//=========================================================
// 全体の中心点をもとめてそこから離れる(距離1.0だけ）
//=========================================================
double x = this.position.getX();
double y = this.position.getY();
List list = this.getLinks();
Iterator iterator = list.iterator();
double diffX = cx - x;
double diffY = cy - y;
double distance = Math.sqrt( diffX * diffX + diffY * diffY );
x -= 1.0 / distance * diffX;
y -= 1.0 / distance * diffY;
position.setXY( x, y );
}
}
::::::::::::::
VertexDisplacer.java
::::::::::::::
import java.util.*;
/**
$Id: GraphViewer.html,v 1.1 2009/06/22 16:11:45 kishi Exp kishi $
*/
public class VertexDisplacer {
static public void deflate( Map vertexMap ) {
Iterator iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
vertex.deflateNext();
}
}
static public void inflate( Map vertexMap ) {
Iterator iterator;
// 全体の重心を求める
double wx = 0.0;
double wy = 0.0;
iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
wx += vertex.getX();
wy += vertex.getY();
}
wx /= vertexMap.size();
wy /= vertexMap.size();
// 全体の重心から膨張させる
iterator = vertexMap.keySet().iterator();
while ( iterator.hasNext() ) {
String url = ( String ) iterator.next();
Vertex vertex = ( Vertex ) vertexMap.get( url );
vertex.inflateNext( wx, wy );
}
}
}
戻る
