Графический алгоритм. Глядя на улучшение масштабируемости.

Question

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

private Multiset<String> paths = new Multiset<String>();  

public Multiset<String> createSF(DAGNode n) { 

    for (DAGNode succ : n.getSuccessors()) 
     createSF(succ); 
    if (!n.isVisited()) 
     for (String s : makePathList(n)) 
      paths.put(s); 

    n.setVisited(true); 
    return paths; 
} 

private List<String> makePathList(DAGNode n) { 
    List<String> list = new ArrayList<String>(); 

    list.add(n.getLabel()); 
    for (DAGNode node : n.getSuccessors()) 
     list.addAll(append(n.getLabel(), makePathList(node))); 

return list; 
} 

private List<String> append(String s, List<String> src) { 
    List<String> ls = new ArrayList<String>(); 
    for (String str : src) 
    ls.add(s + "/" + str); 

    return ls; 
} 

EDIT:

Я сейчас, используя объект пути для представления пути и иметь пин-указал горлышко бутылки к этим двум методам:

public List<Path> createPathList(Tree n) { 
    List<Path> list = new ArrayList<Path>(); 
    list.add(new Path(n.getNodeName())); 
    for (Tree node : n.getSuccessors()) { 
     list.addAll(append(n.getNodeName(), createPathList(node))); 
    } 
    return list; 
} 

public List<Path> append(String s, List<Path> src) { 
    List<Path> ls = new ArrayList<Path>(); 
    for (Path path : src) { 
     ls.add(new Path(path, s)); 
    } 
    return ls; 
} 

Проблема в том, когда граф размер M эти методы будут называться M раз, это означает, что здесь создано много списков ... есть ли более эффективный способ создания возврата для createPathList()?

Answer 1

Чтобы ответить на этот вопрос, необходимо понять, зачем вам нужен список путей. Список путей не дает вам дополнительной информации о том, что у вас есть в представлении DAG.

Если вы хотите вычислить вещи для каждого пути отдельно или вычислить что-то вроде sum/min/max по всем путям, это тоже можно сделать с использованием самой DAG.

Если вы настаиваете на сохранении отдельных путей, одним из вариантов было бы преобразование вашей DAG в вариант Trie. Другим вариантом может быть использование некоторого варианта представления Lempel-Ziv. Это зависит от ваших типов DAG и от того, что вы ожидаете от информации о путях.

Answer 2

Посмотрите на исходный код DOT от Graphviz, это может дать вам несколько идей.

Answer 3

Пожалуйста, позвольте мне поставить два (надеюсь, полезные) комментарии первая:

У меня были некоторые трудности с пониманием кода, потому что некоторые из имен методов в заблуждение меня. От взгляда на имена я ожидал чего-то другого. Могу ли я предложить некоторые рефакторинга:

makePathList -> createPathList // you actually create a List here 
append -> createPathList // yes, same name as above because it creates the same 
         // type of list, just with different parameters 

(удалена часть ответа, который стал устаревшим после редактирования Роберта)

Как сказал Маргус, заменив конкатенации строк с StringBuilder дописывания цепи не увеличивает представление. Компиляторы могут оптимизировать конкатенации String для StringBuilder в любом случае (я видел такой байт-код).

Вы можете попытаться преобразовать DAG в древовидную структуру. Представьте невидимый корень со всеми узлами как прямые дети. Теперь для каждого узла добавьте его преемники (дочерние и/или родственные). Число листьев теперь должно быть равно числу путей, и каждый граф от корня до любого листа - это один путь в DAG.

Редактировать

Небольшое улучшение - это микро-оптимизации, но по крайней мере он оставит меньше мусора:

private List<String> append(String node, List<String> allPathsStartingAfterNode) { 
    List<String> allPathsStartingAtNode = new ArrayList<String>(); 
    String nodeWithSeparator = node + "/"; 

    for (String aPathStartingAfterNode : allPathsStartingAfterNode) { 
     allPathsStartingAtNode.add(nodeWithSeparator + aPathStartingAfterNode); 
    } 

    return allPathsStartingAtNode; 
} 

Answer 4

Простая модификация (в зависимости от того, как использовать эти данные), могут быть загружайте пути лениво, таким образом, если вы склонны использовать только несколько путей, вы даже не создадите каких-либо путей.

Конечно, это полностью зависит от ожидаемого использования