خوارزميات لتحديد كل دورة قواعد في الرسم البياني صليات

Question

لدي صليات الرسم البياني مع قمة الرأس V و Edge E.أنا أبحث عن خوارزمية لتحديد كل دورة قواعد في هذا الرسم البياني.

أعتقد Tarjans الخوارزمية هو بداية جيدة.ولكن الإشارة لقد حول إيجاد جميع دورات, لا دورة القاعدة ( التي ، بحكم التعريف هي دورة لا يمكن بناؤها من قبل الاتحاد من دورات أخرى).

على سبيل المثال, نلقي نظرة على الرسم البياني أدناه:

لذا خوارزمية سيكون مفيدا.إذا كان هناك موجود تنفيذ (يفضل أن يكون في C#) إنه حتى أفضل!

Answer 1

من ما أستطيع أن أقول, ليس فقط هو براين حدس على الفور ، ولكن أقوى الاقتراح يحمل:كل حافة هذا ليس في الدنيا شجرة الامتداد يضيف واحد بالضبط الجديدة "القاعدة دورة".

أن نرى هذا, دعونا نرى ماذا يحدث عند إضافة ميزة E ليس في MST.دعونا نفعل المفضلة الرياضيات الطريق إلى تعقيد الأمور و إضافة بعض الرموز ;) استدعاء الأصلي الرسم البياني ز الرسم البياني قبل إضافة E G', و الرسم البياني بعد إضافة E G".لذلك نحن بحاجة إلى معرفة كيف "قاعدة العد دورة" التغيير من غرام إلى غرام".

مضيفا E يجب أن تغلق على الأقل دورة واحدة (وإلا E سيكون في MST من ز في المقام الأول).لذا من الواضح أنه يجب إضافة ما لا يقل عن واحد "القاعدة دورة" إلى تلك القائمة بالفعل في ز'.لكن هل هذا إضافة أكثر من واحد ؟

فإنه لا يمكن إضافة أكثر من اثنين ، لأنه لا حافة يمكن أن يكون عضوا في أكثر من عقدين من قاعدة دورات.ولكن إذا ه عضو في قاعدة دورات ، ثم "الاتحاد" من هذين قاعدة دورات لابد قاعدة دورة في ز' ، مرة أخرى حتى نحصل على أن التغيير في عدد من الدورات لا تزال واحدة.

وبالتالي على كل طرف في MST يمكنك الحصول على قاعدة جديدة دورة.وبالتالي فإن "العد" جزء بسيط.إيجاد جميع حواف لكل قاعدة دورة هو اصعب قليلا ولكن بعد التفكير أعلاه, وأعتقد أن هذا يمكن أن تفعل ذلك (في شبه الثعبان):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

تحرير:يجب أن تجد كل قاعدة دورات في الرسم البياني (في base_cycles وضعت في الجزء السفلي).الافتراضات هي التي تعرف كيف:

• العثور على الحد الأدنى من شجرة الامتداد من الرسم البياني (mst[G])
• معرفة الفرق بين قائمتين (حواف \ mst[G])
• تجد تقاطع اثنين من القوائم
• العثور على الطريق بين اثنين من القمم على MST
• تقسيم الدورة إلى مجموعتين بإضافة ميزة اضافية إلى ذلك (الدالة split)

أساسا يلي المناقشة أعلاه.لكل حافة ليس في MST, لديك حالتين:إما أن يجلب جديد تماما قاعدة دورة أو انشقاقات موجود في اثنين.لتتبع أي من الاثنين هو القضية ، ونحن تتبع كل قاعدة دورات قمة الرأس هو جزء من (باستخدام دورات القاموس).

Answer 2

من على قمة رأسي ، وأود أن تبدأ من خلال النظر في أي الحد الأدنى من شجرة الامتداد خوارزمية (بريم Kruskal ، إلخ).لا يمكن أن يكون هناك أكثر من قاعدة دورات (إذا فهمت بشكل صحيح) من الحواف التي ليست في MST....

Answer 3

ما يلي هو بلدي الفعلية لم تختبر C# رمز للعثور على جميع هذه "القاعدة دورات":

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy كان رمز جدا جيد واضح ولكن أنا متأكد من أنه يحتوي على خطأ أو إنه أنا الذي لا أفهم الزائفة كود بايثون :)

cycles[v] = []

لا يمكن أن تكون قمة الرأس فهرسة قاموس قوائم الحواف.في رأيي أنه يجب أن تكون قمة الرأس فهرسة قاموس مجموعات من القوائم من الحواف.

و لإضافة precisation:

for vertex on cycle_to_split:

دورة إلى الانقسام هو الارجح أمرت قائمة حواف حتى إلى تكرار ذلك من خلال القمم لديك لتحويل ذلك في مجموعة من القمم.الأمر هنا لا يكاد يذكر, حتى انها بسيطة جدا alghoritm.

أكرر هذا لم تختبر و uncomplete مدونة, ولكن هو خطوة إلى الأمام.فإنه لا يزال يتطلب السليم الرسم البياني هيكل (يمكنني استخدام incidency قائمة) والعديد من الرسم البياني alghoritms يمكنك أن تجد في الكتب مثل Cormen.لم أكن قادرة على العثور على FindPath() و SplitCycle() في الكتب المدرسية ، جدا من الصعب رمز لهم في الزمن الخطي من عدد من حواف+القمم في الرسم البياني.سوف يقدم لهم هنا عندما كنت سوف اختبار لهم.

شكرا جزيلا Oggy!

Answer 4

الطريقة القياسية للكشف عن دورة استخدام اثنين من التكرار - على كل التكرار ، أحد يتحرك إلى الأمام خطوة واحدة واثنين آخرين.يجب أن يكون هناك دورة في مرحلة الإشارة إلى بعضها البعض.

هذا النهج يمكن أن تمتد إلى تسجيل دورات حتى وجدت والانتقال.