Als Aufgabe wurde uns die Aufgabe übertragen, Kartenreduzierungsfunktionen zu erstellen, die für jeden Knoten n in der Google Web Graph-Liste die Knoten ausgeben, die Sie in drei Schritten von Knoten n aus erreichen können. (Die aktuellen Daten finden Sie hier:http://snap.stanford.edu/data/web-Google.html) Hier ist ein Beispiel, wie die Elemente in der Liste sein werden:

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

Aus dem obigen Beispiel ist dies ein Diagramm

In dem obigen vereinfachten Beispiel sind die Pfade zum Beispiel von Knoten 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] und somit wird die Kartenverkleinerung für Knoten 1 die Eckpunkte 1,5,6 ausgeben ((a) jeder Eckpunkt muss nur einmal gezählt werden, und (b) wir schließen den aktuellen Eckpunkt nur ein, wenn es eine Kreisbahn von gibt Länge 3, wie im Beispiel [1 -> 2 -> 4 -> 1] und [1 -> 3 -> 4 -> 1].

Ich bin sehr verloren, weil ich glaube, dass dies Kenntnisse der Graphentheorie und der Algorithmen erfordert, und wir haben nichts im Zusammenhang damit gelernt.

Ich werde es sehr schätzen, wenn mir jemand die richtige Richtung für den Start geben kann. (Ich habe mir die Theorie des kürzesten Weges und dergleichen angesehen, bin mir aber nicht sicher, ob sie für diese bestimmte Übung nützlich sein wird.)

Vielen Dank im Voraus und schöne Feiertage.

BEARBEITEN

Ich versuche, die Adjuzenzliste zu erstellen, aber während ich erwarte, dass die Ausgabe "vertexID" "node1 node2 node3 node4 ..." ist, sehe ich, dass mein Reduzierer in der Ausgabedatei die Liste für jede Vertex-ID in Dreierpaare aufteilt.

Wenn ich zum Beispiel den Scheitelpunkt A habe, der mit Z, X, C, V, B, N, M, G, H, J, K und L verbunden ist, wird dieser als ausgegeben

A Z, X, C

A V, B, N

A M, G, H

A J, K, L

Unten sind mein Mapper und 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, 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, Text, Text>{
    public void reduce(Text key, Iterable<Text> values, Context context) throws IOException, 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);

    }

}