Erstellen von Gruppen aus einem gerichteten Graph-Wörterbuch

Question

Gegeben ein Wörterbuch eines gerichteten Graphen, das verschachtelte Gruppen und deren Mitglieder darstellt, alle Benutzer für eine bestimmte Gruppe zurückgeben.

Beispiel-

Hashmap- 

key|Values 

Group1- [ Group3, Group5, User8, User2] 
Group2 -[ Group1, User9] 
Group3 -[ Group4, User5] 
Group4 -[ User1, User3] 
Group5 -[ User4, User7] 

O/P sollte sein:

group1 : [User1, User3,User5, User4, User7,User8, User2] 
group2 : [User1, User3,User5, User6, User7,User8, User9] 
group3: [User1, User3,User5] 
group4: [User1, User3] 
group5: [User4, User7] 

ich eine rekursive Funktion beispielsweise in verschiedener Art und Weise versucht, aber ich gerade zu Ende gegangen meinem Kopf kratzen.

public static void main(String[] args) { 
     HashMap<String, List<String>> hmap = new HashMap<String,List<String>>(); 
     List<String> l1 = new ArrayList<String>(); 
     List<String> l2 = new ArrayList<String>(); 
     List<String> l3 = new ArrayList<String>(); 
     List<String> l4 = new ArrayList<String>(); 
     List<String> l5 = new ArrayList<String>(); 
     l1.add("group3"); l1.add("group5"); l1.add("user8"); l1.add("user2"); 
     l2.add("group1"); l2.add("user9"); 
     l3.add("group4"); l3.add("user5"); 
     l4.add("user1"); l4.add("user3"); 
     l5.add("user4"); l5.add("user9"); 
     hmap.put("group1",l1); 
     hmap.put("group2",l2); 
     hmap.put("group3",l3); 
     hmap.put("group4",l4); 
     System.out.println(hmap); 
     flatten(hmap); 

    } 


    public static void flatten(HashMap<String, List<String>> hmap){ 
     ArrayList<String> groups = new ArrayList<String>(); 
     for(Entry<String,List<String>> entryset : hmap.entrySet()){ 
      groups.add(entryset.getKey()); 
     } 
     System.out.println(groups); 
     for(Entry<String,List<String>> entryset : hmap.entrySet()){ 
      String s1 = entryset.getKey(); 
      //HashSet<String> set1 = new HashSet<String>(); 
      ArrayList<String> values = new ArrayList<String>(); 
      values.addAll(entryset.getValue()); 

     } 

Answer 1

Hier ist eine Möglichkeit, es zu tun Scala mit:

def run(): Unit = 
{ 
    /* Simply initializing the given data into User and Group classes */ 
    val (u1, u2, u3, u4) = (new User("u1"), new User("u2"), new User("u3"), new User("u4")) 
    val (u5, u6, u7, u8, u9) = (new User("u5"), new User("u6"), new User("u7"), new User("u8"), new User("u9")) 
    val g5 = new Group(List(u4, u7)) 
    val g4 = new Group(List(u1, u3)) 
    val g3 = new Group(List(g4, u5)) 
    val g1 = new Group(List(g3, g5, u8, u2)) 
    val g2 = new Group(List(g1, u9)) 

    /* Put the groups into a list */ 
    var groups = List(g1, g2, g3, g4, g5) 

    /* Map/loop over each group, calling `resolveItems` on each */ 
    groups = groups.map{_.resolveItems} 

    /* Print out each of the resolved groups */ 
    groups.foreach{println} 
} 

/* A simple class representing the Group entity */ 
case class Group(var items: List[Any]) 
{ 
    /* 
     Returns a new group by recursively resolving the items 
     in this group into only users 
    */ 
    def resolveItems: Group = 
    { 
     new Group(this.items.map{ 
      // If the item is a group, resolve it into users 
      case g: Group => g.resolveItems 
      // If the item is a user, just move along 
      case u: User => u 
     }.distinct) 
    } 

    /* Override to string for pretty printing */ 
    override 
    def toString: String = items.mkString(", ") 
} 

/* Simply class representing the user entity */ 
case class User(val name: String) 
{ 
    override 
    def toString : String = name 
} 

Ausgang:

u1, u3, u5, u4, u7, u8, u2 
u1, u3, u5, u4, u7, u8, u2, u9 
u1, u3, u5 
u1, u3 
u4, u7