Partition graph by connection degree

Question

I would to ask if there is already algorithms for graphs that partition graphs into subgraphs like the screenshot attached:

Graph has edges A-B,B-C,C-D, D-E, C-F, F-G

I need to partition it to 3 parts since vertex C has degree of 3: A-B-C C-D-E C-F-G

First I was thinking that I can remove C node and disconnect graph using typical methods. But maybe there already known method to partition graphs by nodes degree?

Answer 1

I wrote a simple algorithm for this. Please note that the graph is needed to be ordered

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

More generic example with 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; }
}