График разделов по степени подключения - PullRequest
Новая
       31

График разделов по степени подключения

0 голосов
/ 26 декабря 2018

GraphPartitionScreenshot

Я хотел бы спросить, есть ли уже алгоритмы для графов, которые разбивают графы на подграфы, как на скриншоте:

Граф имеет ребра AB, BC, CD, DE,CF, FG

Мне нужно разбить его на 3 части, поскольку вершина C имеет степень 3: ABC CDE CFG

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

1 Ответ

0 голосов
/ 26 декабря 2018

Я написал простой алгоритм для этого.Обратите внимание, что график необходимо заказать 

public static void Main()
{
    Console.WriteLine("Hello World");
    var str = "A-B,B-C,C-D,D-E,C-F,F-G";
    var resultSet = Graph(str.Split(','), '-');

}


public static string[] Graph(string[] s, char delimiter)
{
    var resultSet = new List<string>();

    var prevOperLeft = "";
    var prevOperRight = "";

    foreach (var part in s)
    {
        var oper = part.Split(delimiter);
        var left = oper[0];
        var right = oper[1];

        if (prevOperRight == left)
        {
            resultSet.Add(string.Format("{0}{1}{2}{3}{4}", prevOperLeft, delimiter, left, delimiter, right));
            prevOperLeft = prevOperRight = "";
        }
        else
        {
            prevOperLeft = left;
            prevOperRight = right;
        }
    }

    return resultSet.ToArray();
}

https://dotnetfiddle.net/e3kmpR

Более общий пример с LinkedList 

public static IList<LinkedList<T>> Graph2<T>(LinkedList<T> ll) where T: class
{
    var resultSet = new List<LinkedList<T>>();

    T prevOperLeft = null;
    T prevOperRight = null;

    while (ll.Count > 0) 
    {
        var left = ll.First.Value;
        ll.RemoveFirst();
        var right = ll.First.Value;
        ll.RemoveFirst();

        if (prevOperRight != null && prevOperRight.Equals(left))
        {
            resultSet.Add(new LinkedList<T>(new []{ prevOperLeft, left, right }));
            prevOperLeft = prevOperRight = null;
        }
        else
        {
            prevOperLeft = left;
            prevOperRight = right;
        }
    }

    return resultSet;
}

public static void Main()
{
    var A = new MyClass {Name = "A"};
    var B = new MyClass {Name = "B"};
    var C = new MyClass {Name = "C"};
    var D = new MyClass {Name = "D"};
    var E = new MyClass {Name = "E"};
    var F = new MyClass {Name = "F"};
    var G = new MyClass {Name = "G"};

    List<MyClass> list = new List<MyClass>
    {
         A,B,B,C,C,D,D,E,C,F,F,G
    };

    LinkedList<MyClass> ll = new LinkedList<MyClass>(list);
    var resultSet2 = Graph2(ll);
}

class MyClass
{
    public string Name { get; set; }
}
...