Как сделать проекцию двудольного графа с JUNG

Question

Я создал двудольный граф в JUNG, и я хотел бы иметь одномодовую проекцию для одного из наборов узлов. В проекции два узла одного и того же набора будут связаны, если они имеют общий узел, принадлежащий другому множеству. Есть ли функция в JUNG, которая уже делает это? Код, который я до сих пор (очень медленно для двудольных сетей 1600 узлов, где только 400 принадлежит множеству Я хочу, чтобы спроецировать) является:

public static void perform(UndirectedSparseGraph<Node, Edge> g, List<Node> companies) throws Exception { 
    // 
    UndirectedSparseGraph<Node, Edge> oneMode = new UndirectedSparseGraph<>(); 
    // 
    for (Node n : companies) { 
     // take my concepts 
     Collection<Node> myConcepts = g.getNeighbors(n); 
     // for each of my concepts 
     for (Node m : myConcepts) { 
      // take its companies 
      Collection<Node> itsCompanies = g.getNeighbors(m); 
      // for each of the companies that use this concept 
      for (Node nn : itsCompanies) { 
       // if company is not myself 
       if (!nn.equals(n)) { 
        // if at least one of these is not in the graph, go straight to add a link 
        if (!oneMode.containsVertex(nn) || !oneMode.containsVertex(n)) { 
         // add a new link 
         Edge edge = new Edge(1); 
         // set edge name 
         edge.setName(findEdgeLabel(n, nn)); 
         edge.setFrom(nn); 
         edge.setTo(n); 
         // add a link between myself and this company 
         oneMode.addEdge(edge, n, nn, EdgeType.UNDIRECTED); 
        } else { 
         if (oneMode.isNeighbor(n, nn)) { 
          // retrieve edge based on the label 
          boolean incrementWeight = incrementWeight(oneMode.getEdges(), findEdgeLabel(n, nn)); 
          if (!incrementWeight) { 
           throw new Exception("doesn't work"); 
          } 
         } else { 
          // add a new link 
          Edge edge = new Edge(1); 
          // set edge name 
          edge.setName(findEdgeLabel(n, nn)); 
          edge.setFrom(nn); 
          edge.setTo(n); 
          // add a link between myself and this company 
          oneMode.addEdge(edge, n, nn, EdgeType.UNDIRECTED); 
         } 
        } 
       } 
      } 
     } 
    } 
    // now write result to file 
    try (PrintWriter writer = new PrintWriter("icleantech-one-mode.csv", "UTF-8")) { 
     // iterate 
     for (Edge e : oneMode.getEdges()) { 
      writer.println(e.getFrom().getName() + ";" + e.getTo().getName() + ";" + String.valueOf(e.getWeight())); 
     } 
    } catch (FileNotFoundException | UnsupportedEncodingException ex) { 
     Logger.getLogger(BipartiteProjection.class.getName()).log(Level.SEVERE, null, ex); 
    } 
} 

private static String findEdgeLabel(Node n, Node nn) { 
    if (n.getId() < nn.getId()) { 
     return String.valueOf(n.getId() + "-" + nn.getId()); 
    } else { 
     return String.valueOf(nn.getId() + "-" + n.getId()); 
    } 
} 

private static boolean incrementWeight(Collection<Edge> edges, String findEdgeLabel) { 
    for (Edge e : edges) { 
     if (e.getName().equals(findEdgeLabel)) { 
      // increase weight 
      e.setWeight(e.getWeight() + 1); 
      return true; 
     } 
    } 
    return false; 
} 

узкого места в коде, когда я хочу, чтобы обновить веса ссылки ... без него, код действительно быстр ... Я понятия не имею, где я ошибаюсь ... любая помощь более чем приветствуется.

Answer 1

Самый эффективный способ сделать это, на сегодняшний день, - использовать Hypergraph вместо двудольного графика. (Один раздел становится вершинами гиперграфа, другой - гиперэджем, каждый гиперрегл соединяет вершины, которые были связаны с соответствующей вершиной в исходном графе.) Тогда вы можете просто спросить вершину для своих соседей в гиперграфе, а вы сделанный.