Just some very quick notes without looking through it fully:

• This function should return a ptr_vector_t, each element of which is a basis element, i.e. a vector_t of edge indices.
• It must work for multigraphs, e.g. 1-2, 1-2, 2-3 has one cycle.
• It must also handle self-loops.
• It should work on directed graphs and simply ignore edge directions. One may want to use the result to create an edge-cycle matrix where 0, 1 and -1 are used to indicate whether an edge is not in a cycle, in the cycle pointing in the cycle direction, or in the cycle pointing in the reverse direction, respectively. This is a common thing to do with cycle bases.

You seem to be using some raw char * arrays for boolean vectors. We also have igraph_vector_bool_t. I did notice that an igraph_bool_t is an int, i.e. typically 32-bit instead of 8-bit. Perhaps this is why you went with the raw char array? @ntamas Can you comment on why igraph_bool_t is int and not, say, and unsigned char?

I have no idea; this has always been this way before I joined the development of igraph. I think we could change this easily. You could try changing the typedef of igraph_bool_t to unsigned char in the source and see if anything breaks (it shouldn't - if it does, then the point where it breaks is probably an interesting place to look at as it could uncover places where we are (ab)using an igraph_bool_t to do something else).

I have no idea; this has always been this way before I joined the development of igraph. I think we could change this easily. You could try changing the typedef of igraph_bool_t to unsigned char in the source and see if anything breaks

This breaks the R interface because is there a logical is an int.

Some more comments:

I think the following would be reasonable names / prototypes:

int igraph_fundamental_cycle_basis(const igraph_t *graph, igraph_vector_ptr_t *basis);
int igraph_minimum_cycle_basis(const igraph_t *graph, igraph_vector_ptr_t *basis, const igraph_vector_t *weights);

Alternatively, minimum_weight_cycle_basis would be more precise, but longer.

I do not think we need to include "undirected" in the name, as this is understood. In many applications, people would run this on directed (i.e. oriented) graphs and also want to know if each edge points along the cycle direction or opposite to it. This information could even be optionally returned by the function in an additional vector (however, it is easy enough to compute, so maybe we don't need to include it).

I do not think we need to include "unweighted" in the name, as weights are not relevant for bases unless we look for the minimum weight one (which is a special application). However, it is useful to indicate that it returns a fundamental basis.

I believe the implementation can be made more efficient in the following way.

While doing a BFS, you maintain a vector father that denotes for each node the node through which it was first visited (i.e. this corresponds to the spanning tree). Let us initially set father to -1 for all nodes, so that if father[i] < 0 it means that node i was not yet visited. In addition, we keep a vector dist which is the distance from the root vertex. Whenever you encounter a node i that was already visited (father[i] > 0) when traversing the edge j -> i, you backtrack the fathers of i and j (i.e. ancestors) until dist[i] == dist[j] and then keep iterating until the ancestors are identical. In other words:

int ancestor_i = i;
int ancestor_j = j;
while (ancestor_i != ancestor_j)
{
  if (dist[ancestor_i] > dist[ancestor_j])
    ancestor_i = father[ancestor_i];
  else if (dist[ancestor_i] < dist[ancestor_j])
    ancestor_j = father[ancestor_j];
  else
  {
    ancestor_i = father[ancestor_i];
    ancestor_j = father[ancestor_j];
  }
}

By maintaining the traversed list of ancestors, you have the list of vertices in the cycle. If ancestor_i == j you know that the cycle was directed and otherwise it is an undirected cycle (i.e. a cycle ignoring the edge directions). If you want a vector of edges instead of vertices (which is probably more useful in a multigraph) you can use edge ids instead of vertex ids to identify the father (i.e. the edge that leads to the father). Finally, for multiple components you should include a root vector that identifies from which root the node was reached. If root[i] != root[j] no cycle can be identified.

I believe that the initial BFS that you perform is sufficient for immediately identifying the cycles, while creating the spanning tree. In other words, you identify the cycles as you are building the spanning tree in one go. You now repeatedly perform a DFS on the resulting spanning tree, but you will then repeatedly backtrack the same paths I believe (i.e. the parent variable remains essentially identical across igraph_dfs runs).

And probably you should indeed call it parent instead of father :)

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@iosonofabio If you are still working on this, feel free to remove the wontfix label. Stalebot will also stop bothering this PR if you add the pinned label to it.

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

I restarted working on this one, don't worry about the massive merge commits for now, I can squash-rebase at the end.

Great! I noticed you merged in develop so perhaps we should discuss whether this should go into master or develop. If my understanding is correct, this is an entirely new function, right? That means it can go into master, because it is backwards compatible. But that means that we should not bring in all the changes from the develop branch. What do you think?

Good point. I'm working on the weighted graph function which is significantly more messy than the unweighted one, so I'm unclear on the time frame - not so familiar with Horton cycles I admit. There's also no urgency I believe. So maybe develop is fine? But I'm also fine rebasing against master

I'd say keep it on develop. As for me, I tend to do all development on develop now.

Ok, I'm sharpening the tools for this one. Some advice would be appreciated, but in terms of general approach and specific code. Two points in particular:

1. It seems reasonable to me to implement this algorithm: https://dl.acm.org/doi/abs/10.1145/1644015.1644023, see fig 2. Anyone objects or has a better suggestion?

2. I starting shaping up the code for that and it needs a bunch of auxiliary functions that might be useful beyond this particular PR, e.g. an approximate calculation of a feedback vertex set. If anyone could have a quick look at my igraph_minimum_cycle_basis (only a stub) and comment on what functions exist already and whether any of the private ones should instead be lifted to be part to the API, I'be be grateful.

Thanks!
Fabio

It seems reasonable to me to implement this algorithm: https://dl.acm.org/doi/abs/10.1145/1644015.1644023, see fig 2. Anyone objects or has a better suggestion?

I actually ran into the same publication recently. It sounded like an interesting option, although I have not yet explored the details.

I can read the paper, that's not the problem. How much difference do you think it will make in practice versus the increased complexity?

My understanding is the more recent approach does not use all vertices but just a feedback vertex set (which we have to implement separately - can default to all vertices of degree != 2 for now if I'm not wrong). Moreover it also only analyzes cycles in distinct subtrees from the root.

However this algorithm requires travelling across the trees from root to leaves, which is more difficult than the other way (just storing a parent vector). That's what I'm wondering right now, i.e. what an efficient data type would be for that purpose.

Wait, I should just look a little longer. Seems like the minimum spanning tree prim function uses a vector of edges to store the tree, we can do the same here. Then we can travel from root to children relatively easily.

2\. argsort?

If you do need this is practice, I think it would make a great contribution to the igraph_vector* types. It would probably be good to make this a public implementation then.

Thanks @szhorvat . At this stage I'm not fixing memory leaks and similar stuff, but thanks.

I haven't seen any comments on the general strategy, I'm just pushing ahead then. I'll come back to the nitty gritty details once the core of the algorithm is implemented 👍

@iosonofabio Is the fundamental cycles part considered to be ready now?

For the minimum cycle basis, I am familiar with Horton's algorithm, which is simple:

• find fundamental cycles corresponding to a BFS tree starting from each vertex
• order the entire group of cycles by weight
• starting from the smallest, use Gaussian elimination to find a linearly independent set which is a basis

I am not familiar with the paper you linked. I'd need to look at it in detail to comment, which would take a few hours. I need to force myself off igraph for now, so I can make progress on other projects ...

Fantastic @szhorvat , thanks for the recap. The paper is an incremental improvement over that. Don't worry too much about this one, it'll take me a few more days ;-)

FYI, I just came across igraph_vector_order (and it siblings igraph_vector_order1 and igraph_vector_order1_int), which essentially provide an argsort of a vector. This really shows that we should make these functions public and provide decent documentation for them.

This one is also not urgent, esp. since @szhorvat has implemented a similar algorithm. Closing for now.