Является ли карта, содержащая значения, имеющие ссылки на другие ключи в карте, самой простой формой ориентированного графа? - PullRequest
1 голос
/ 19 сентября 2011
Map<K,V<List<K>> graph = new HashMap<K,V<List<K>>();

Существуют ли какие-либо серьезные препятствия для использования этого для представления ориентированного графа, который может быть циклическим?

РЕДАКТИРОВАТЬ:

Это было более запутанным, чем этовероятно, должно было быть.Это график разговоров для РПГ, и вот что я имею до сих пор.Я пытался определить, смогу ли я преобразовать это в более простую форму:

Инициализировано для NPC:

public interface ConversationGraphI {

    void init();

    Map<String, DialogueNodeI> getConversation();

    void setConversation(Map<String, DialogueNodeI> conversation);
}

Часть диалога с вариантами ответа:

public interface DialogueNodeI {

    String getText();

    void setText(String text);

    List<ResponseChoiceI> getResponseChoices();

    void setResponseChoices(List<ResponseChoiceI> responseChoices);
}

Выбор ответа, который затем может вернуться к другой части диалога на карте:

public interface ResponseChoiceI {

    String getResponseText();

    void setResponseText(String responseText);

    String getDialogueKey();

    void setDialogueKey(String dialogueKey);
}

Ответы [ 2 ]

2 голосов
/ 20 сентября 2011

Я думаю, что главная проблема в том, что вы не сможете легко хранить данные о каждом ребре. Это зависит от того, даст ли вам объект типа V это. Тем не менее, я согласен с комментарием Andrei LED, что было бы лучше использовать явный тип Edge:

Map<K,Collection<Edge<K>>>

Если вам вообще не нужно хранить метаданные, то вы можете пойти еще проще:

Map<K,Collection<K>>

В качестве альтернативы подходу «все в одном» я видел графики, представленные двумя отдельными коллекциями, одна для узлов и одна для ребер. Если N является узлом, то что-то вроде этого:

Collection<N>  // nodes
Collection<Edge<N>>  // edges between nodes
0 голосов
/ 19 сентября 2011

Ну, я думаю, вам нужно использовать TreeMap, чтобы упорядочить ключи в их естественном порядке. Если нет, то это был бы непрямой граф, не так ли? Кроме того, будет ли он соответствовать всем остальным критериям прямого графа, будет зависеть от того, какую фактическую реализацию вы дадите объектам Keys и Values, которые вы там поместили.

...