This comes up often enough that we ought to add a note about it to the ideas page.
Aaron Meurer On Mon, Mar 18, 2013 at 1:59 PM, Brian Granger <elliso...@gmail.com> wrote: > A number of people have asked about graph theory in sympy in the past. > Our feeling is that with the high quality of NetworkX, it doesn't > make sense to reinvent graph theory in sympy. Maybe talk to the > NetworkX folks about doing a GSoC with them? > > On Mon, Mar 18, 2013 at 2:06 AM, Rajat Kapoor <rajat100...@gmail.com> wrote: >> About me >> >> Hi, my name is Rajat Kapoor and I'm currently pursuing Engg. in Electrical >> and Electronics along with M.S. in Mathematics in BITS Pilani Goa. >> >> I'm from India, and have sheer interest in computer programming as well as >> Mathematics. Few of my favorite areas in Mathematics include Optimization >> Techniques and Graph Theory >> >> Contact: rajat100...@gmail.com , rajat100493(skype), rajatkapoor(github) >> >> Programming Skills >> >> I've done coding in several high-level languages (C, C++,Java, C#, Python). >> My most preferred among all these is C#, mostly because of the powerful IDE >> options available but when it comes to cross platform development, I prefer >> Python because of its simplicity. I have completed a few intermediate level >> virtual courses in Python at college and have had guidance from a helpful >> lot of seniors with regard to a few informal projects in python. Apart from >> this I have amateur programming skills in web technologies including HTML, >> CSS, XML, PHP. Other areas of interest include Image Processing(using >> SimpleCV and OpenCV). I also have a very basic knowledge of GUI based >> programming in Java as well as python(using PyQt and wxWidgets). I have a >> negligible experience with git but I've learnt the concept well and have >> started using it lately. >> >> Project Idea: >> >> Becasue of my avid interest in the above mentioned areas I propose the idea >> of working on ONE of the following projects, which seems viable as well as >> pretty apt to be merged into sympy >> >> Addition of a new Optimization module >> >> OR >> >> Addition of Graph Theory Module >> >> Though my peak interest is in developing the above mentioned modules, but >> due to its strong dependencies on the matrices module, I'll have to add some >> more functionality to the matrices module. >> >> Optimization Module: >> >> Features of the optimization module: >> >> Solving to linear programming problems from the given matrix or polynomial >> input: Simplex algorithms along with a few variations(M-method, Two Phase, >> Dual Simplex, and Generalised Simplex methods) will be used to solve such >> problems >> >> Recognition of special cases(degeneracy, alternative optima, unboundedness, >> infeasability) >> >> Transformation into dual problems: using primal dual relations >> >> Post optimal analysis: how feasibility and optimality are affected >> >> Transportation model solving: Starting solution to be obtained via northwest >> corner method/ least cost method/vogel approximation method then proceeding >> towards optimality using simplex iterations >> >> Assignment model solving: using Hungarian method. >> >> Any other ideas relating to the optimization field will also be added >> >> Graph Theory Module(which i personally prefer more): >> >> Input of graphs will be taken in form of adjacency list/adjacency matrix/ >> incidence matrix. Interconversion between these three forms will be >> provided.This module will initially aim to provide the following >> functionality: >> >> Manipulation with degree of vertices, including detection of cut vertices, >> formation of line graphs, finding closure, eccentricity,girth of a graph >> >> Simple graph operations like join, subtract, union, etc will be added >> >> Isomorphic graph detection will be implemented, by using some of the >> functions in the already existing matrices module. Extra functions required >> will be added to the matrices module itself. >> >> Functionality relating to the regularity as well as planarity(Tarjan's >> algorithm) of graphs will also be added. >> >> Cycles: number of cycles and the cycles itself will be found out. Detection >> of cycles in the graph will be done using Tarjan's algorithm or any other >> algorithm that can be implemented with ease. >> >> Trees: all functions regarding no of nodes, root node, nodes at seperate >> levels, etc. Trees will be recognized by cycle detection process. Minimum >> spanning tree finding functionality will be added using Krusal's or Prim's >> algorithm. >> >> Hamiltonian graphs: methods of detection will be implemented using Dirac's, >> Ore's definition or Bondy-Chvátal theorem or by finding a cut vertex. >> >> Eulerian graphs : Checking the “even-ness” of degree of all vertices. Fleury >> algorothm (implemented using Tarjan's algorithm to detect bridges) or >> Hierholzer's algorithm to find the eulerian cycle. >> >> Special classes of graphs viz. Complete graphs, bipartite graphs, >> multipartite graphs and hypercubes will also be pre-defined >> >> I have a very clear idea on how to implement the ideas stated above. These >> functions will be first implemented for simple, undirected graphs and then >> will be extended to multigraphs, directed graphs in due course of time. >> Moreover, other suggested functionality will also be added. >> >> Main Question: Please give me advice on which module do you think will be >> more useful for integrating with sympy, OPTIMIZATION or GRAPH THEORY. This >> would help me focus the efforts on the preferred module before the GSOC >> official dates so i can get a headstart.(I'll be working on graph theory >> module anyways, if you agree to add its functionality in sympy). >> >> Although I prefer working on the above mentioned ideas,but I am open to >> working on your suggested ideas too due to my familiarity with sympy. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to sympy+unsubscr...@googlegroups.com. >> To post to this group, send email to sympy@googlegroups.com. >> Visit this group at http://groups.google.com/group/sympy?hl=en. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> > > > > -- > Brian E. Granger > Cal Poly State University, San Luis Obispo > bgran...@calpoly.edu and elliso...@gmail.com > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
