Java实现两个图的匹配率计算

用java实现以下功能。

两个图A和B之间的匹配率计算公式：

，其中|A|表示图A中顶点个数，表示图A和图B共同顶点

组成的子图。例如下图中R1和P1的匹配率为：(4*4)/(4*5)= 0.8.

给定两组子图R, P, 例如，如下图R = {R1, R2}，P={P1,P2, P3}, 以R和P

中的每一个图做为一个顶点，构造一个新的图，图中的边上的权值表示两

个图之间的匹配率。R和P之间最大匹配率计算方法如下：

1.在新构造的图中找出一组边，使得P和R中的每一个顶点最多出现一条

边上，而且边的权重累加和最大。

2.最大匹配率为：第1步选择边的权重之和除以R中子图的个数

例如: 下图中最大匹配率为：(0.8+0.75)/2

**********************************************************************************************

Subgraph类，代码如下：

package MatchRate;
import java.util.ArrayList;
import java.util.List;
public class SubGraph {
private boolean []visited;//设置节点是否访问过
public
ArrayList<ArrayList<Integer>> DFSTraverse(int[][]a,int N){
/深度优先遍历
ArrayList<ArrayList<Integer>> sub_graph=new ArrayList<ArrayList<Integer>>();
visited= new boolean[N];
for(int i=0;i<N;i++) visited[i]=false;
for(int i=0;i<N;i++) {
if(!visited[i]) {
ArrayList<Integer> b=new ArrayList<Integer>();//存放一个子图
DFS(a,i,b,N);
//存放所有子图
sub_graph.add(b);
}
}
return sub_graph;
}
public void DFS(int[][]a,int v,List b,int N){
//深度优先遍历所有点
int w;
visited[v]=true;
b.add(v);
w=firstAdjvex(a,v,N);
while(w>=0){
if(!visited[w]) DFS(a,w,b,N);
w=nextAdjvex(a,v,N);
}
}
public int firstAdjvex(int[][]a,int v,int N){
for(int i=0;i<N;i++){
if(a[v][i]!=0)
return i;
}
return -1;
}
public int nextAdjvex(int[][]a,int v,int N){
for(int i=0;i<N;i++){
if(a[v][i]!=0&&!visited[i])
return i;
}
return -1;
}
}

package MatchRate;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class ReadData {
public int ReadN(String fileName){
//读取图的顶点的个数
int N=0;
try {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line = null;
line=reader.readLine();
String str[] = line.split("\s+");
N=Integer.parseInt(str[0].trim());
}catch (FileNotFoundException e) {
e.printStackTrace();
}catch (IOException e) {
e.printStackTrace();
}
return N;
}
public int[][] ReadGraph(String fileName,int N){
//读取图到一个数组中
int[][] arr=new int[N][N];
try {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line = null;
line=reader.readLine();
int i=0;
while((line=reader.readLine())!=null){
String str[] = line.split("\s+");
for(int j=0;j<N;j++){
arr[i][j]=Integer.parseInt(str[j].trim());
}
i++;
}
}catch (FileNotFoundException e) {
e.printStackTrace();
}catch (IOException e) {
e.printStackTrace();
}
return arr;
}
}

package MatchRate;
import java.util.ArrayList;
public class Maxinum {
public double maxinum(ArrayList<ArrayList<Double>> m){
double maxinum=0.0;	//最终的输出最大匹配率
double sum=0.0;//每一个子图的最大匹配率之和
for(int i=0;i<m.size();i++){
double max=0.0;//每一个子图的最大匹配率
for(int j=0;j<m.get(i).size();j++){
if(m.get(i).get(j)>max){
max=m.get(i).get(j);
}
}
sum=sum+max;
}
maxinum=sum/m.size();
double sum1=0.0;//每一个子图的最大匹配率之和
for(int ii=0;ii<m.get(0).size();ii++){
double max1=0.0;//每一个子图的最大匹配率
for(int jj=0;jj<m.size();jj++){
if(m.get(jj).get(ii)>max1){
max1=m.get(jj).get(ii);
}
}
sum1=sum1+max1;
}
if(maxinum<(sum1/m.get(0).size())){
//判断是否小于另一个图的子图的最大匹配率，如果小于则把大的赋值给maximum
maxinum=sum1/m.get(0).size();
}
return maxinum;//返回最大匹配率的值
}
}

package MatchRate;
import java.util.ArrayList;
public class Match {
public ArrayList<ArrayList<Double>> match(ArrayList<ArrayList<Integer>> a,ArrayList<ArrayList<Integer>> b){
ArrayList<ArrayList<Double>> m=new ArrayList<ArrayList<Double>>();
//存放每个图的子图的所有匹配率
for(int i=0;i<a.size();i++){
double rate=0.0;
ArrayList<Double> MR=new ArrayList<Double>();//存放一个子图的所有匹配率
for(int j=0;j<b.size();j++){
int common=0;
for(int k=0;k<b.get(j).size();k++){
if(a.get(i).contains(b.get(j).get(k))){
//判断两个子图中相同的顶点个数
common++;
}
}
rate=((common*common*1.00)/(a.get(i).size()*b.get(j).size()*1.00))*1.00;
//算出两个图的匹配率
MR.add(rate);
}
m.add(MR);
}
return m;
}
}

package MatchRate;
import java.util.ArrayList;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
String fileName="data/11.txt";
String fileName1="data/22.txt";
ReadData rd=new ReadData();
int N = 0,N1=0;//记录图的元素个数
N=rd.ReadN(fileName);
N1=rd.ReadN(fileName1);
int [][] a=new int[N][N];//存储图的邻接矩阵
int [][] a1=new int[N1][N1];
a=rd.ReadGraph(fileName, N);
System.out.print("====第一个输入的邻接矩阵====");
System.out.println();
System.out.print(N);
System.out.println();
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.print(a[i][j]);
}
System.out.println();
}
a1=rd.ReadGraph(fileName1, N1);
System.out.print("====第二个输入的邻接矩阵====");
System.out.println();
System.out.print(N1);
System.out.println();
for(int i=0;i<N1;i++){
for(int j=0;j<N1;j++){
System.out.print(a1[i][j]);
}
System.out.println();
}
ArrayList<ArrayList<Integer>> sub_graph=new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> sub_graph1=new ArrayList<ArrayList<Integer>>();
//用来存放图的子图
SubGraph sg=new SubGraph();
sub_graph=sg.DFSTraverse(a, N);
System.out.print("====第一个图的子图====");
System.out.println();
System.out.print(sub_graph.toString());
System.out.println();
sub_graph1=sg.DFSTraverse(a1, N1);
System.out.print("====第二个图的子图====");
System.out.println();
System.out.print(sub_graph1.toString());
System.out.println();
Match m=new Match();
ArrayList<ArrayList<Double>> rate=new ArrayList<ArrayList<Double>>();
//存放所有子图的所有匹配率
rate=m.match(sub_graph, sub_graph1);
System.out.print("====每个子图的对应的匹配率====");
System.out.println();
System.out.print(rate.toString());
System.out.println();
double maxinum;//存放两个图的最大匹配率
Maxinum mn=new Maxinum();
maxinum=mn.maxinum(rate);
System.out.print("====图一和图二的最大匹配率====");
System.out.println();
System.out.print(maxinum);
System.out.println();
}
}

最后

以上就是彩色月饼为你收集整理的Java实现两个图的匹配率计算的全部内容，希望文章能够帮你解决Java实现两个图的匹配率计算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。