3
$\begingroup$

Say you have a graph like

a — b — c
|   |   |
e — f — g

and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e}, because c3 is not "basic" in the sense that c3 = c1 + c2 where the plus operator means to join two cycles along some edge e and then drop e from the graph.

I invented my own terminology in the above but basically I want to find all cycles in a graph that cannot be decomposed into smaller cycles. Does this problem have a name? Is there a known best algorithm for solving it?

I understand that enumerating all cycles runs in exponential time because there may be an exponential number of cycles but my intuition is that the number of basic cycles as defined above is related only polynomially to the number of edges in the graph.

$\endgroup$
10
  • $\begingroup$ Interesting question, but you might want to think more about your definition of "basic". If you replace every edge in your graph with two edges, then you would have three cycles, not two, because you only allowed joining on one edge. $\endgroup$ Mar 11, 2020 at 12:44
  • $\begingroup$ yes ... a better definition might be that c3 is not basic because the graph that is the union of c1 and c2 contains c3. $\endgroup$
    – jwezorek
    Mar 11, 2020 at 17:13
  • $\begingroup$ But the union of c1 and c3 contains c2 as well :) So then none of the cycles would be basic. $\endgroup$ Mar 11, 2020 at 17:29
  • $\begingroup$ oh true. I mean, from reading the "cycle basis" wikipedia article in the answer posted below, the operation I am talking about is the "symmetric difference" of the cycles i.e. c3 is the symmetric difference of c1 and c2. I was thinking the simple union based def was equivalent but as you point out, its not $\endgroup$
    – jwezorek
    Mar 11, 2020 at 18:01
  • $\begingroup$ This problem seems related to the problem of finding all faces of a planar embedding of some graph. I think if the graph is planar then the set of cycles I am looking for is the union of all the faces across all planar embeddings. $\endgroup$
    – jwezorek
    Mar 11, 2020 at 18:11

3 Answers 3

5
$\begingroup$

You might be interested in a cycle basis, especially a fundamental cycle basis (which actually consists of cycles).

$\endgroup$
0
$\begingroup$

Suppose that ${a}={1}$, ${b}=2$, ${c}=3$, ${e}=4$, ${f}=5$, ${g}=6$ $\implies$ we will have:

a — b — c       1 — 2 — 3
|   |   |  <=>  |   |   |
e — f — g       4 — 5 — 6

I can provide a solution of this problem, based on using of the algorithm Depth first search:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maximumSize=40;
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<int> graph[maximumSize], closedContour, temporary;
int vertices, edges;
set<vector<int>> contours;
void showContentSetVector(set<vector<int>> input)
{
    for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
    {
        for(auto item : *iterator)
        {
            cout<<item<<", ";
        }
        cout<<endl;
    }
    return;
}
bool compare(int i,int j)
{
    return (i<j);
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int initial, int current, int previous)
{
    if(visited[initial][current]==1)
    {
        for(int i=0; i<temporary.size(); ++i)
        {
            if(temporary[i]==current)
            {
                for(int j=i; j<temporary.size(); ++j)
                {
                    closedContour.push_back(temporary[j]);
                }
            }
        }
        sort(closedContour.begin(), closedContour.end(), compare);
        contours.insert(closedContour);
        closedContour.clear();
        return;
    }
    visited[initial][current]=1;
    temporary.push_back(current);
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        depthFirstSearch(initial, next, current);
    }
    temporary.pop_back();
    return;
}
void solve()
{
    createGraph();
    for(int vertex=1; vertex<=vertices; ++vertex)
    {
        temporary.clear();
        depthFirstSearch(vertex, vertex, -1);
    }
    cout<<"contours <- ";
    showContentSetVector(contours);
    return;
}
int main()
{
    solve();
    return 0;
}

Here is the result:

contours <- 
1: 1, 2, 3, 4, 5, 6, 
2: 1, 2, 4, 5, 
3: 2, 3, 5, 6, 
$\endgroup$
0
$\begingroup$

I suggest you take a look at the concepts of "Cycle Basis" and "Minimum Cycle Basis". Each is described in simple terms by NetworkX's documentation as below:

Cycle Basis. A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis.

Minimum Cycle Basis. Cycle basis for which the total weight (length for unweighted graphs) of all the cycles is minimum.

In order to be able to distinguish between the two quickly, assume that you have a undirected graph $G$ like below:

 A - B - C - D
 |   |   |   |
 E - F - G - H
 |   |   |   |
 H - I - J - K

Just trying to extract the cycle basis may lead to any of the results below, as both cases form a basis for the cycle space of $G$:

 1: A, B, F, E     |     1: A, B, F, E
 2: B, C, G, F     |     2: B, C, G, F
 3: C, D, G, H     |     3: C, D, G, H
 4: E, F, I, H     |     4: E, F, I, H
 5: F, G, J, I     |     5: I, J, K, H, D, C, B, F
 6: G, H, K, J     |     6: G, H, K, J

Based on your description, I assume your intention is to prevent cases such as cycle #5 of the right-hand side. To do so, you should rather extract Minimum Cycle Basis instead of Cycle Basis.

Here, are some references to delve deeper into the topic, if you are interested:

  • Paton, K., 1969. An algorithm for finding a fundamental set of cycles of a graph. Communications of the ACM, 12(9), pp.514-518.
  • Kavitha, T., Mehlhorn, K., Michail, D. and Paluch, K.E., AnO (m 2 n) Algorithm for Minimum Cycle Basis of Graphs.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.