Соединение краев вершин по метке ребер в структуре данных графа - PullRequest
Новая
       12

Соединение краев вершин по метке ребер в структуре данных графа

0 голосов
/ 08 октября 2019

Исходя из всего, что я видел, стандартный способ соединить вершины (или узлы - как бы вы их ни называли) вместе - создать ребро, которое содержит вершину «от» и вершину «к». Существует несколько различных способов представления этой связи (adjacency list, adjacency matrix, incident matrix и т. Д.).

Можно задать ребра (и вершины) labels, чтобы присвоить тождество / значениекрай. Им также может быть дано weight (которое можно считать таким же, как label, но из того, что я видел - есть разница).

, реализующее adjacency list с ребрами, имеющими labels будет выглядеть следующим образом (псевдокод): 

myGraph.adjacencyList = {
    "vertex1": {
        "vertex2": "label",
        "vertex3": "label",
        "vertex4": "anotherLabel"
    }
}

Однако, чтобы найти, если у вершины есть ребро с определенной меткой, операция становится O(|D|) - где |D| (градусы)число ребер в вершине: 

// pseudo code
const getAdjacenciesConnectedByLabel = (graph, fromVertex, label) => Object.entries(graph.adjacencyList[fromVertex]).reduce((adjacenciesConnectedByLabel, [toVertex, edgeLabel]) => adjacenciesConnectedByLabel.concat(edgeLabel === label ? toVertex : []), []);

// this would then be used as follows:
getAdjacenciesConnectedByLabel(myGraph, 'vertex1', 'label');
// >>> ["vertex2", "vertex3"]

Чтобы выполнить операцию O(1) (моя цель), моей первой идеей было "перевернуть", как хранятся смежные значения: 

anotherGraph.adjacencyList = {
    "vertex1": {
        "label": ["vertex2", "vertex3"],
        "anotherLabel": ["vertex4"]
    }
}
const getAdjacenciesConnectedByLabel = (graph, fromVertex, label) => graph.adjacencyList[fromVertex][label];

Однако теперь операция по поиску, если у вершины есть ребро к другой вершине (isAdjacent), становится O(|D|) (если не хуже - я на самом деле не совсем знаю, как представить следующую функцию в BigO нотация - возможно O(|D| * |L|), где |L| - количество меток на вершину): 

const isAdjacent = (graph, from, to) => Object.values(graph.adjacencyList[from]).reduce(bool, vertexSet) => !bool ? bool : vertexSet.includes(to), false);
// this could be slightly optimized if you were to use a for or while loop which then stopped as soon as a matching "to" vertex was found

// this would then be used as follows:
isAdjacent(anotherGraph, 'vertex1', 'vertex3');
// >>> true

Я пытаюсь найти способ сделать оба типа операций O(1). Моя единственная другая идея - создать еще один «индекс», который затем будет отслеживатьТолько края между вершинами, а затем список смежности будут содержать метки, но это кажется излишне сложным.

Если невозможно найти способ сделать оба типа операций O(1), я хочузнать, какой будет рекомендуемый метод (из двух приведенных выше) для создания списка смежности, чтобы большинство операций выполнялось O(1) при попытке работать со связями данных.

Думаю, я быхочу, чтобы мои операции, в которых «смежность была связана по метке», были O(1) (то есть adjacencyList выглядела бы так: (vertexFrom, (label, verticesTo))), поскольку это был бы хороший способ фильтрации / извлечения данных (по их отношениям - названия меток AKA)). Но я мог бы полностью пропустить отметку, и на самом деле было бы лучше иметь adjacency list хранилище на (vertexFrom, (vertexTo, label)), и если мне нужно , чтобы проверить label, мне пришлось бы перебрать каждую смежную вершину.

Если это имеет смысл.

...