Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Suppose we have a Bipartite graph. If you want each node to have degree 0, 1 or 2, one way to do this would be the following. If you want to do a <em>matching</em>, either look up the algorithm (I don't remember it), or change maxDegree to 1 and I think it should work as a matching instead. Regardless, let me know if this doesn't do what you want.</p> <pre><code>def hamiltPath(graph): """This partitions a bipartite graph into a set of components with each component consisting of a hamiltonian path.""" # The maximum degree maxDegree = 2 # Get all the nodes. We will process each of these. remaining = graph.vertices() # Create a new empty graph to which we will add pairs of nodes. newGraph = Graph() # Loop while there's a remaining vertex. while len(remaining) &gt; 0: # Get the next arbitrary vertex. node = remaining.pop() # Now get its neighbors that are in the remaining set. neighbors = [n for n in graph.neighbors(node) if n in remaining] # If this list of neighbors is non empty, then add (node, neighbors[0]) # to the new graph. if len(neighbors) &gt; 0: # If this is not an optimal algorithm, I suspect the selection # a vertex in this indexing step is the crux. Improve this # selection and the algorthim might be optimized, if it isn't # already (optimized in result not time or space complexity). neighbor = neighbors[0] newGraph.addEdge(node, neighbor) # "node" has already been removed from the remaining vertices. # We need to remove "neighbor" if its degree is too high. if len(newGraph.neighbors(neighbor)) &gt;= maxDegree: remaining.remove(neighbor) return newGraph class Graph: """A graph that is represented by pairs of vertices. This was created For conciseness, not efficiency""" def __init__(self): self.graph = set() def addEdge(self, a, b): """Adds the vertex (a, b) to the graph""" self.graph = self.graph.union({(a, b)}) def neighbors(self, node): """Returns all of the neighbors of a as a set. This is safe to modify.""" return (set(a[0] for a in self.graph if a[1] == node). union( set(a[1] for a in self.graph if a[0] == node) )) def vertices(self): """Returns a set of all of the vertices. This is safe to modify.""" return (set(a[1] for a in self.graph). union( set(a[0] for a in self.graph) )) def __repr__(self): result = "\n" for (a, b) in self.graph: result += str(a) + "," + str(b) + "\n" # Remove the leading and trailing white space. result = result[1:-1] return result graph = Graph() graph.addEdge("0", "4") graph.addEdge("1", "8") graph.addEdge("2", "8") graph.addEdge("3", "5") graph.addEdge("3", "6") graph.addEdge("3", "7") graph.addEdge("3", "8") graph.addEdge("3", "9") graph.addEdge("3", "10") graph.addEdge("3", "11") print(graph) print() print(hamiltPath(graph)) # Result of this is: # 10,3 # 1,8 # 2,8 # 11,3 # 0,4 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POdelete random edges of a node till degree = 1 networkx
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USWords Like Jared
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POdelete random edges of a node till degree = 1 networkx
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you for your answer jared, I have been looking at your code but I am unsureits doing what I hope. Sorry I will continue to work on this.
      singulars
      1. PO
      1. USuser1317221_G
    2. COCould you give some example input and output graphs, then?
      singulars
      1. PO
      1. USWords Like Jared
    3. COdef addEdge(self, a, b): """Adds the vertex (a, b) to the graph""" self.graph = self.graph.union({(a, b)}) syntax eror
      singulars
      1. PO
      1. USuser1317221_G
 

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