1 2 
1 3 
2 4 
3 4 
3 5 
4 1 
4 5 
4 6 
5 6

从上面的示例图将是这样的

在上面的简化示例中,例如节点1的路径是
α[1 – > 2 – > 4 – > 1],[1 – > 2 – > 4 – > 5],[1 – > 2 – > 4 – > 6],[1 – > 3 – > 4 – > 1],
[1 – > 3 – > 4 – > 5],[1 – > 3 – > 4 – > 6]και[1 – > 3 – > 5 – > 6]
因此地图缩小将为节点1输出顶点1,5,6(
(a)每个顶点只能计算一次,并且
(b)我们仅在存在长度为3的圆形路径时包括当前顶点,如示例[1 – > 2 – > 4 – > 1]和[1 – > 3 – > 4 – > 1].

我很失落,因为我相信这需要图论和算法的知识,而且我们没有被教过任何与之相关的知识.

如果有人能给我正确的方向开始,我将不胜感激. (我已经研究过最短路径理论,但我不确定它是否会对这个特定的练习有用)

在此先感谢,并有一个愉快的假期.

编辑

我尝试创建adjucency列表,但我希望输出为“vertexID”“node1 node2 node3 node4 …”我看到在输出文件中我的reducer将每个顶点Id的列表拆分为三对.

例如,如果我有一个连接到Z,X,C,V,B,N,M,G,H,J,K,L的顶点A我将它输出为

Z,C

A V,N

A M,H

A J,L

下面是我的mapper和reducer

public class AdjacentsListDriver extends Configured implements Tool {
 
    @Override
    public int run(String[] args) throws Exception {
 
 
 
        Configuration conf = getConf();
        Job job = Job.getInstance(conf);
        job.setJobName("Test driver");
        job.setJarByClass(AdjacentsListDriver.class);
 
        String[] arg0 = new GenericOptionsParser(conf,args).getRemainingArgs();
        if (arg0.length != 2) {
            System.err.println("Usage: hadoop jar <my_jar> <input_dir> <output_dir>");
            System.exit(1);
        }
 
        Path in = new Path(arg0[0]);
        Path out = new Path(arg0[1]);
 
        FileInputFormat.setInputPaths(job,in);
        FileOutputFormat.setOutputPath(job,out);
 
        job.setMapperClass(ListMapper.class);
        job.setReducerClass(ListReducer.class);
 
        job.setInputFormatClass(TextInputFormat.class);
        job.setOutputFormatClass(TextOutputFormat.class);
 
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);    
        job.waitForCompletion(true);
 
        return 0;
    }
 
    public static void main(String[] args) throws Exception {
        int res = ToolRunner.run(new Configuration(),new AdjacentsListDriver(),args);
        System.exit(res);
 
    }
 
 
 
}
 
 
 
 
 
/**
 * @author George
 * Theoretically this takes a key(vertexID) and maps all nodes that are connected to it in one hop....
 *
 */
public class ListMapper extends Mapper<LongWritable,Text,Text> {
 
    private Text vertexID = new Text();
    //private LongWritable vertice= new LongWritable(0);
    private Text vertice=new Text();
 
    public void map(LongWritable key,Text value,Context context) throws IOException,InterruptedException {
 
        String line = value.toString();
        StringTokenizer itr = new StringTokenizer(line,"\n");
        StringTokenizer itrInside;
 
        //vertice=new LongWritable(Long.valueOf(value.toString()).longValue());
 
 
        while (itr.hasMoreTokens()) {
            if(itr.countTokens() > 2){
 
            }//ignore first line ??
            else{
                itrInside=new StringTokenizer(itr.toString());
                vertexID.set(itr.nextToken());
 
                while(itrInside.hasMoreTokens()){               
                    vertice.set(itrInside.nextToken());
                    context.write(vertexID,value);
                }           
            }
        }
 
    }
 
}
 
@override
public class ListReducer extends Reducer<Text,Text>{
    public void reduce(Text key,Iterable<Text> values,InterruptedException {
 
        String vertices="";
 
        for (Text value : values) {
            if(vertices=="")
                vertices+=value.toString();
            else
                vertices=vertices+","+value.toString();         
        }
 
        Text value=new Text();
        value.set(vertices);
        context.write(key,value);
 
    }
 
}