Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The following is my actual <strong>untested</strong> C# code to find all these "base cycles":</p> <pre><code>public HashSet&lt;List&lt;EdgeT&gt;&gt; FindBaseCycles(ICollection&lt;VertexT&gt; connectedComponent) { Dictionary&lt;VertexT, HashSet&lt;List&lt;EdgeT&gt;&gt;&gt; cycles = new Dictionary&lt;VertexT, HashSet&lt;List&lt;EdgeT&gt;&gt;&gt;(); // For each vertex, initialize the dictionary with empty sets of lists of // edges foreach (VertexT vertex in connectedComponent) cycles.Add(vertex, new HashSet&lt;List&lt;EdgeT&gt;&gt;()); HashSet&lt;EdgeT&gt; 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&lt;List&lt;EdgeT&gt;&gt; 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&lt;EdgeT&gt; 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&lt;EdgeT&gt; cycleToSplit = cycleToSplitSet.GetEnumerator().Current; List&lt;EdgeT&gt; cycle1 = new List&lt;EdgeT&gt;(); List&lt;EdgeT&gt; cycle2 = new List&lt;EdgeT&gt;(); 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&lt;List&lt;EdgeT&gt;&gt; ret = new HashSet&lt;List&lt;EdgeT&gt;&gt;(); // Create the set of cycles, in each vertex should be remained only one // incident cycle foreach (HashSet&lt;List&lt;EdgeT&gt;&gt; remainingCycle in cycles.Values) ret.AddAll(remainingCycle); return ret; } </code></pre> <p><a href="https://stackoverflow.com/questions/1607124/algorithms-to-identify-all-the-cycle-bases-in-a-undirected-graph/1607826#1607826">Oggy's</a> code was <strong>very</strong> good and <strong>clear</strong> but i'm pretty sure it contains an error, or it's me that don't understand your pseudo python code :)</p> <pre><code>cycles[v] = [] </code></pre> <p>can't be a vertex indexed dictionary of lists of edges. In my opinion, it have to be a vertex indexed dictionary of <strong>sets of lists</strong> of edges.</p> <p>And, to add a precisation:</p> <pre><code>for vertex on cycle_to_split: </code></pre> <p>cycle-to-split is probably an <strong>ordered</strong> list of edges so to iterate it through vertices you have to convert it in a set of vertices. Order here is negligible, so it's a very simple alghoritm.</p> <p>I repeat, this is <strong>untested</strong> and <strong>uncomplete</strong> code, but is a step forward. It still requires a proper graph structure (i use an incidency list) and many graph alghoritms you can find in text books like Cormen. I wasn't able to find FindPath() and SplitCycle() in text books, and are <strong>very</strong> hard to code them in linear time of number of edges+vertices in the graph. Will report them here when I will test them.</p> <p>Thanks a lot Oggy!</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithms to Identify All the Cycle Bases in a UnDirected Graph
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USceztko
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COForgot: HashSet I've used here is not .NET 3.5 compliant as I had to add it myself (the project is still .NET 2.0), so for example it has AddAll() method. This sounds very java like, ahahahah :D
      singulars
      1. PO
      1. USceztko
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload