Is there a function that is sort of like igraph_is_connected but for edges. E.g. in the graph with vertices: 0,1,2,3, having edges: 0-1 and 1-2, it would be considered “connected”, even though vertex 3 is disconnected from this graph. If the edges were 0-1 and 1-2, the graph would be considered disconnected.
Do you mean that you simply want to ignore zero-degree vertices before checking if an undirected graph is connected?
You can use igraph_clusters and compute only the csize. Then loop through the component sizes and see if there is more than once which has size greater than 1.
Thanks! This is just what I was after!
What I said above is actually incorrect because we may have size-1 components (isolated vertices) which have self-loops.
We could do something like this:
- Compute the degree vector (
igraph_degree) - Loop through it and find the first vertex whose degree is > 0. If there is none, the graph can be considered “edge-connected” (not a good term, but let us use it here). If there is one, let us assume that the component of this vertex is the single component containing edges.
- Compute the clusters, including the membership vector
- Loop through the membership vector and for each vertex that does not belong to the component identified above, check that its degree is 0. If we find one which has a degree > 0, then the graph is not “edge-connected”.
Given how complicated this is, I think it wouldn’t be a bad idea to add a function with this functionality to C/igraph.
I don’t understand. If we simple look at components of size 1, that would work regardless of self-loops, wouldn’t it? That is, if there is only one component of size > 1, it would consist of only isolates and a giant component. Perhaps we should term this “isolate-free-connected”, or something? But I don’t think it would merit a function on its own.
Or do you mean that isolates with self-loop have degree 1, and therefore, if there are such isolates with self-loops, the graph would not be “edge-connected”? In this case, I would simply suggest to remove all nodes with degree 0 from the graph, and then see if the graph is connected. This wouldn’t merit a function on its own either, I think?
Whether the OP is interested in the first (exclude isolates) or the latter definition (exclude degree 0) is not clear to me. Perhaps there is yet another view, it seems that your definition @szhorvat is somewhat different still, but I don’t fully understand it.
@vtraag For context, I am almost certain that OP is Yasir and he needed this for the Eulerian paths project. I did not realize this at the time when I answered the question.
In order for a graph to have an Eulerian path, it is necessary that any edge be reachable from any other edge. In other words, the line graph is connected. (“Edge-connected” was a bad choice of term on my part, as it is very close to k-edge-connected which means something else.)
Here the line graph is connected:
Here it is not:
Yes, you are right. I was thinking along the lines of providing an internal function for use in the igraph_is_eulerian function
Yes. To be precise, an isolate with k self-loops has degree 2k.
That is entirely reasonable for a one-off application, but it is too expensive for igraph_is_eulerian. We do not want to copy and modify the graph in that function.
We need to exclude degree 0.
@Yas BTW getting all of this right is really not easy. Some of these edge cases are quite tricky. After realizing that we got these special cases wrong at first, I tried to push some other systems and find bugs. It didn’t take long to find one in Mathematica:
In[7]:= EulerianGraphQ[Graph[{1, 2}, {1 -> 1, 1 -> 1}]]
Out[7]= False
Oops!
That’s a graph with two vertices, one having two self-loops, the other zero. It’s clearly Eulerian but Mathematica says it’s not.
1 Like
OK, it wasn’t clear to me that this indeed concerned internal functions. Perhaps this topic should be moved to the Development category in that case?
I now also better understand your proposal. It should just ensure that every non-zero degree vertex is part of the same connected component.