QuickGraph находит степень вершин

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

Вот пример структуры данных, которую я составляю:

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));

Мне просто нужен список вершин в этом графе, у которых нет "внутренних" ребер (inстепень = 0).


c# quickgraph
person Mark Richman    schedule 29.08.2014    source источник
comment
Кто проголосовал за закрытие? Что непонятного в этом вопросе? Я голосую за то, чтобы оставить открытым.   -  person chiccodoro    schedule 29.08.2014
comment
@chiccodoro Спасибо! Я тоже не понимаю, почему это непонятно.   -  person Mark Richman    schedule 29.08.2014
comment
Есть ли у Vertex что-то вроде свойства IncomingEdges или хотя бы что-то вроде свойства AdjacentEdges? Тогда, конечно, вы можете фильтровать, используя componentGraph.Vertices.Where(v => !v.IncomingEdges.Any() или аналогичный. Однако я считаю, что вам нужна реализация определенного алгоритма, чтобы сделать его более производительным...   -  person chiccodoro    schedule 01.09.2014
comment
У него есть OutEdges, но нет InEdges. Это первое, что я искал.   -  person Mark Richman    schedule 01.09.2014
comment
Я думаю, что нашел решение. Парень (или девушка), проголосовавший за закрытие, помог вам привлечь внимание :-)   -  person chiccodoro    schedule 01.09.2014

Ответы (1)


arrow_upward
2
arrow_downward

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

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

Как следует из этого обсуждения, метод получения степени входа можно найти на IBidirectionalIncidenceGraph.

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

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

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)
person chiccodoro    schedule 01.09.2014
comment
Я думаю, что это будет работать для меня! У меня будет всего несколько (‹50) вершин, поэтому эффективность не имеет большого значения. Я попробую и отмечу это как ответ, когда он у меня заработает. Спасибо! - person Mark Richman; 02.09.2014
comment
@ Марк, более чем рад предложить помощь по вопросу, который я нашел только в обзоре :-) - person chiccodoro; 02.09.2014
comment
это был хороший способ сказать мне RTFM? - person Mark Richman; 02.09.2014
comment
@Mark, это тоже было не в последнюю очередь предназначено. Думаю, мне просто повезло найти то, что вы искали. Я не знал библиотеки, но знаю понятия графов, степеней и т.д.; когда я увидел, что на ваш вопрос до сих пор нет ответа и он все еще находится в очереди на рассмотрение, я подумал, что скорее поспешу вам помочь (и доказать, что вопрос был достаточно ясен) - person chiccodoro; 02.09.2014