Reading the wikipedia article reminds me of why graph coloring was entirely *unsuccessful* in solving cellular networks channel assignment problem. Even though it is an allocation of resources problem, which sounds like it should suite graph coloring, there are two key differences:
- The number of resources are fixed (ie. k is constant). Most of the theory in graph coloring is about finding the minimum k for a fixed graph, which is definitely the wrong problem to solve for fixed resource allocation. - Edge weights are not considered. I did not fing a single reference to edge weighting for vertex coloring problems. Without that consideration, the application of graph coloring seems entirely impractical. Even for map coloring, two countries could share a large or small border, and that should affect the color choices made, but is not considered (as far as I can tell). Neither is the difference of the colors. If you have a large color set (large k), some colors will be very similar (visually), and this must be taken into account. So much theory, and so impractical :-( >From what I know, existing cellular channel allocation algorithms use different approaches. Despite this, I have been thinking of a new algorithm for this that will use graph theory in two ways, one for identifying loosely connected cliques (similar to a database partitioning problem), and one for solving subsets of the resource allocation problem. It would be nice to have a few graph coloring algorithms in Neo4j to play with. Are you planning on coding the Sudoku one? :-) On Wed, Mar 2, 2011 at 10:51 PM, Rick Otten <[email protected]> wrote: > 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 > _______________________________________________ Neo4j mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
