The proof for the number of colors needed to fill in regions on a planar map was solved using graph coloring, so yes, that is what I'm referring to.
I was more just thinking about the classic coloring problem of scheduling a finite number of resources with minimal conflicts. A year and a half or so ago I got the idea of using Neo4j as project management database. I still think it has a lot of potential even if the market doesn't need any more project management tools. Some project management-type problems involve scheduling resources and managing dependencies between activities. Some of those problems might be easily solved using coloring algorithms. I recall an example from my Graph Theory class (some <cough> 20 years ago or so), a problem about aligning Ally flight crews, languages, and aircrafts they were qualified to work on during WWII operations over Europe. I'm sure these sorts of matching issues come up in practical applications often. I really didn't have anything specific in mind though. FWIW, I saw on Wikipedia just a couple of minutes ago that there is an algorithm for solving Sudoku puzzles that uses coloring. That could make a nifty little Neo4j small-graph demo program actually... https://secure.wikimedia.org/wikipedia/en/wiki/Graph_coloring Thanks for the reply and offer for more help if I need it some day! > Hi Rick, > > As you say, color is just an integer, so all you need is to index the > integer (use lucene, or connect all nodes to a node of the right color). > > However, since you use the term 'color' I wonder if you are referring to > the > problem of finding minimal color similarities between related nodes? I > mean > similar to the problem of coloring adjacent countries on a map with > sufficiently different colors to make them visually distinctive. This is a > well know graph problem, but in some scenarios a 'plain graph' solution is > not ideal. For example, I deal with mobile network frequency planning, > where > towers (modeled as nodes) need sufficiently different frequencies as to > not > interfere with nearby towers (with 'nearby' modeled as weighted > relationships). There is no perfect solution, but by modeling a cost > weight > on the relationships, you can apply an iterative optimization algorithm to > the graph to find near optimal solutions. > > If your problem is more like this one, we can discuss it further, probably > off-list since this is now rather domain specific :-) > > Regards, Craig > > On Wed, Mar 2, 2011 at 10:06 PM, Rick Otten <[email protected]> wrote: > >> There are a number of possible applications for coloring a graph. I was >> poking around in the neo4j documentation, but did not turn up any >> examples >> or canned routines for this. >> >> I was imagining finding something like "ColorGraphNodes([color property >> name])" which puts a property on each node identifying its color (some >> sort of integer) and thus would allow you to then get all nodes of a >> similar color. >> >> Do computer scientists have a different name for a coloring than >> mathematicians (ie, am I just looking for the wrong keyword), or is that >> something that hasn't really been packaged yet, or maybe it is something >> with no good scalable algorithms, and thus is not relevant in the large >> graph world, or maybe folks who need it, implement it themselves on a >> case-by-case basis? >> >> I do not have a specific use case in mind at the moment, just a lot of >> half baked ideas. >> >> >> -- >> Rick Otten >> [email protected] >> O=='=+ >> >> >> _______________________________________________ >> Neo4j mailing list >> [email protected] >> https://lists.neo4j.org/mailman/listinfo/user >> > _______________________________________________ > Neo4j mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user > -- Rick Otten [email protected] O=='=+ _______________________________________________ Neo4j mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
