Поиск в QuickGraph для вершин

Я использую QuickGraph для создания ориентированного ациклического графа. Мне нужно найти все вершины, у которых степень равна нулю. Я не вижу эту поддержку в коллекции Vertices графика или способе фильтрации с использованием LINQ.Поиск в QuickGraph для вершин

Здесь пока структура выборки данных я сочиняю:

var componentGraph = new AdjacencyGraph<Component, Edge<Component>>(); 

var serverOnMachineA = new TalismaServerComponent("CLTDEPAPI10"); 
var serverOnMachineB = new TalismaServerComponent("CLTDEPAPI11"); 
var appServerOnMachineB = new TalismaAppServerComponent("CLTDEPAPI11"); 
var webComponentsOnMachineC = new TalismaWebComponentsComponent("CLTDEPFE1"); 

componentGraph.AddVertex(serverOnMachineA); 
componentGraph.AddVertex(serverOnMachineB); 
componentGraph.AddVertex(appServerOnMachineB); 
componentGraph.AddVertex(webComponentsOnMachineC); 

componentGraph.AddEdge(new Edge<Component>(appServerOnMachineB, serverOnMachineA)); 
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, appServerOnMachineB)); 
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, serverOnMachineB));

Я просто нужен список вершин в этом графике, которые не имеют «в» края (полустепень захода = 0).

источник

2014-08-29 Mark Richman

Кто голосовал за закрытие? Что непонятно в этом вопросе? Я голосую за то, что остаюсь открытым. – chiccodoro

@chiccodoro Спасибо! Я не понимаю, почему это тоже неясно. –

Имеет ли 'Vertex' что-либо вроде свойства' IncomingEdges' или, по крайней мере, что-то вроде свойства 'AdjacentEdges'? Затем, конечно, вы можете фильтровать, используя 'componentGraph.Vertices.Where (v =>! V.IncomingEdges.Any()' или подобное. Однако я считаю, что вам нужна реализация определенного алгоритма, чтобы сделать это более эффективным ... – chiccodoro

Возможно, вам понадобится другой тип графика. Дайвинг немного в форумы и источник QuickGraph я нашел BidirectionalGraph класс, который является

Изменяемыми направлены структура графа данных эффективным для разреженного представления графа, где из-кромка и кромки в-должны быть перечислены. Требуется вдвое больше памяти, чем граф смежности.

Метод для получения в-степени, кажется, можно найти на IBidirectionalIncidenceGraph, как this discussion подразумевает.

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

BidirectionalGraph быстрее для этого, но занимает в два раза больше места для хранения книг. Используя его, вы можете сделать что-то вроде:

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)

источник

2014-09-01 14:46:54 chiccodoro

Я думаю, что это сработает для меня! У меня будет только несколько (<50) вершин, поэтому эффективность не вызывает большого беспокойства. Я дам этому попытку и отмечу это как ответ, когда у меня есть работа. Благодаря! –

@Mark, более чем рад, я мог бы предложить помощь по вопросу, который я нашел только в обзоре :-) – chiccodoro

был ли это приятным способом сказать мне RTFM? –

Поиск в QuickGraph для вершин

ответ

Смежные вопросы